题意：
思路：
Codeforces Round #370（Solved: 4 out of 5）
题意：有一个序列，然后对每一个进行ai = bi - bi + 1 + bi + 2 - bi + 3.... 的操作，最后得到了a 序列，给定 a 序列，求原序列。
思路：水。
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
+ ;
int a[maxn], b[maxn];
int main()
{
int n;
scanf("%d", &n);
; i <= n; i++)
{
scanf("%d", &a[i]);
}
a[n + ] = ;
; i <= n; i++)
{
printf(], i == n ? '\n' : ' ');
}
;
}
题意：一个人站在坐标原点处,他可以往上(U), 下(D), 左(L), 右(R), 四个方向移动,现给你一个移动序列,为了使他最后仍然能回到原点,你需要对这个序列做一些改变,每次可以改变其中一个字母,问最少的改变次数.
思路：水。
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
+ ;
char s[maxn];
int main()
{
scanf("%s", s);
, ans = , cnt_ud = , cnt_rl = ;
; i < strlen(s); i++)
{
switch(s[i])
{
case 'U': cnt_ud++;break;
case 'D': cnt_ud--;break;
case 'L': cnt_rl++;break;
case 'R': cnt_rl--;break;
}
}
int temp = abs(cnt_rl) + abs(cnt_ud);
== ) ok = , ans = temp / ;
;
if(ok)
{
printf("%d\n", ans);
}
else
{
puts("-1");
}
;
}
题意：给你两个值 a 和 b (a > b), 代表这里有两个等边三角形, 边长分别为 a 和 b, 你可以对边长为 a 的三角形进行变换, 每次变化你可以选择一条边, 并为其重新指定一个长度, 当然变换完成后还能组成一个三角形.问最少经过多少次变换可以把等边三角形的三边长度从 a 变换到 b
思路：倒过来想可能简单点，你每次要达到什么样的数据能最优，肯定是根据不变的两条边得到最大的第三条边。
然后特判一下这条新的第三条边大于x的情况就好了。
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
int main()
{
int x, y;
scanf("%d%d", &x, &y);
;
];
a[] = a[] = a[] = y;
] != x && a[] != x && a[] != x)
{
sort(a, a + );
a[] = a[] + a[] - ;
] > x) a[] = x;
cnt++;
}
printf();
;
}
D - Memory and Scores（dp+前缀和+滚动数组）
题意：A初始有一个分数a，B初始有一个分数b，有t轮比赛，每次比赛都可以取[-k, k]之间的数，问你最后A比B大的情况有多少种。
思路：dp[i][j]表示玩到第i次游戏时，得分是j的方案数。dp[i][j] = ∑dp[i-1][l], l∈[-k, k]。这样的话，然后状态数最多有t*(2*k*t)，有O（k^2*t^2）的复杂度。所以状态转移必须是O（1）的复杂度。
所以用前缀和来维护，能把复杂度降到O（k*t^2），sum[i] = sum[x] x∈[0, i-1]。
还可以采取滚动数组，降低空间复杂度。
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
;
;
int a, b, k, t;
LL dp[][maxn], sum[maxn];
int main()
{
scanf("%d%d%d%d", &a, &b, &k, &t);
dp[][] = ;
; i <= t; i++)
{
; j < maxn; j++)
{
)
sum[j] = dp[i - ][j] + sum[j - ];
else
sum[j] = dp[i - ][j];
sum[j] %= mod;//sum来处理前缀和
}
; j < maxn; j++)
{
* k - ) >= )
dp[i][j] = (sum[j] - sum[j - * k - ] + mod) % mod;
else
dp[i][j] = (sum[j] + mod) % mod;
}
}
; j < maxn; j++)
{
)
sum[j] = (sum[j - ] + dp[t][j]) % mod;
else
sum[j] = dp[t][j] % mod;
}
;
; i<=*k*t; i++)
{
>= )
ans += (LL)dp[t][i] * sum[i+a-b-] % mod;
ans %= mod;
}
printf("%d\n", ans);
;
}
Codeforces Round #371
Codeforces Round #372（Solved: 3 out of 5）
题意：就是你一定时间内不输入新的字，它就会清屏。问你最后你屏幕上还有几个字。
思路：水。
#include <cstdio>
int main()
{
int n, c;
scanf("%d%d", &n, &c);
, tot = ;
; i < n; i++)
{
scanf("%d", &x);
;
last = x, tot++;
}
printf("%d\n", tot);
;
}
题意：给你一个字符串，然后问你是否存在一个长度为26连续子序列，它包含所有的26个字母
思路：水。
#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
];
+ ];
int main()
{
scanf("%s", s);
int len = strlen(s);
;
)
{
; i <= len - ; i++)
{
mem(vis, );
; j < ; j++)
{
char t = s[i + j];
;
else if(t != '?') break;
) ok = ;
}
if(ok)
{
; j < ; j++)
{
if(s[i + j] == '?')
{
; k < ; k++)
{
if(!vis[k])
{
s[i + j] = 'A' + k;
vis[k] = ;
break;
}
}
}
}
break;
}
}
}
if(ok)
{
; i < len; i++)
{
if(s[i] == '?') s[i] = 'A';
printf("%c", s[i]);
}
puts("");
}
else
{
puts("-1");
}
;
}
题意：一开始你有数2，处于level1，你可以选择+或者开方。
选择加：那么现在的数字将加上当前的level。
选择开方：当且仅当你拥有的数是完全平方数，并且开方后level会加1，还要满足开方后所剩的数字是新的level的整数倍。
问从level1到level n+1 每一次需要+的次数【任意解即可】
思路：cur[i + 1] = sqrt(cur[i] + i * ans[i])；即cur[i + 1] * cur[i + 1] = cur[i] + i * ans[i]；且cur[i] % i == 0;
构造：cur[i] = i * (i - 1)
化简上面式子得到答案。
#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
int main()
{
int n;
scanf("%d", &n);
printf();
; i <= n ; i++)
{
printf() * (i + ) - (i - ));
}
;
}
Codeforces Round #373
Codeforces Round #374
A - One-dimensional Japanese Crossword
题意：让你求在长度为N的字符串中，连续的B的区间个数，和每个区间B的个数。
思路：水。
#include <set>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
];
];
int main()
{
int len;
scanf("%d", &len);
getchar();
scanf("%s", s);
, flag = , ans = ;
; i < len; i++)
{
if(s[i] != 'B' && cnt)
{
a[ans++] = cnt;
cnt = ;
}
else if(s[i] == 'B')
{
cnt++;
}
}
if(cnt) a[ans++] = cnt;
printf("%d\n", ans);
; i < ans; i++)
{
printf( ? '\n' : ' ');
}
;
}
题意：你有一堆不重复单词，其中有一个是你账号的密码。 现在你要按单词长度从小到大逐一尝试，但同长度的单词可以是任意顺序的。输入一个密码需要1秒，每输错k个密码需要等5秒才能再输。问最少、最多需要多少秒能登录账号？
思路：水。
#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
][], pass[];
map<int, int>ma;
int main()
{
int n, k;
scanf("%d%d", &n, &k);
getchar();
;
; i < n; i++)
{
scanf("%s", s[i]);
int len = strlen(s[i]);
ma[len]++;
}
scanf("%s", pass);
int ps_len = strlen(pass);
;
; i < ps_len; i++)
{
temp += ma[i];
}
+ temp + ;
temp += ma[ps_len];
) / k * + temp;
printf("%d %d\n", best_ans, worst_ans);
;
}
题意：给一个有向无环图（DAG），每条边有权值，找到一条从1到n的路径，使得路径上的点尽可能的大且路径长度不大于给定的T。
思路：因为是有向无环图，所以可以使用拓扑排序来遍历每一个点。又因为是DAG，所以无后效性，所以可以采用dp。
当入度为0的时候，它的dp值显然是已经确定了的。
//dp[i][j]表示编号为i的点，前面有j个点的路径的最小长度
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
const int INF = 0x3f3f3f3f;
+ ;
int ind[maxn_v], pre[maxn_v][maxn_v], dp[maxn_v][maxn_v];
int n, m, T;
struct edge
{
int to, co;
edge(int tt, int cc):to(tt), co(cc){}
bool operator < (const edge &other)const
{
return co > other.co;
}
};
vector<edge>G[maxn_v];
int main()
{
mem(pre, -);
scanf("%d%d%d", &n, &m, &T);
; i <= n; i++)
{
; j <= n; j++)
{
dp[i][j] = INF;
}
}
dp[][] = ;
; i < m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(edge(v ,w));
ind[v]++;
}
queue<int>que;
; i <= n; i++)
{
if(!ind[i]) que.push(i);
}
while(!que.empty())
{
int u = que.front();que.pop();
; i < G[u].size(); i++)
{
edge e = G[u][i];
ind[e.to]--;
if(!ind[e.to]) que.push(e.to);
; j <= n; j++)
{
] + e.co && dp[u][j - ] + e.co <= T)
{
dp[e.to][j] = dp[u][j - ] + e.co;
pre[e.to][j] = u;
}
}
}
}
int ans;
; i--)
{
if(dp[n][i] != INF)
{
ans = i;break;
}
}
printf();
stack<int>s;
int t = n;
; i--)
{
s.push(t);
t = pre[t][i];
) break;
}
while(!s.empty())
{
printf( ? '\n' : ' ');s.pop();
}
;
}
题意：有n个数，k次操作，每次操作可以将第i个数+x或者-x，输出k次操作后这n个数乘积最小时的数列。
思路：先将这个数列从小到大 排序，如果这个数列中有偶数个负数，那么就尽可能的处理出奇数个负数，然后每次取出绝对值最小的数，负数就-x，正数就+x。
#include <set>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}
+ ;
struct Node
{
LL pos, val;
Node(LL p, LL v){pos = p, val = v;}
bool operator < (const Node& other)const
{
return abs(val) > abs(other.val);
}
};
LL a[maxn];
int main()
{
int n, k, x;
scanf("%d%d%d", &n, &k, &x);
;
priority_queue<Node>que;
; i < n; i++)
{
scanf("%I64d", &a[i]);
que.push(Node(i, a[i]));
) num_negative++;
}
; i < k; i++)
{
Node cur = que.top();que.pop();
)
{
) a[cur.pos] -= x;
else a[cur.pos] += x;
) num_negative++;
}
else
{
) a[cur.pos] += x;
else a[cur.pos] -= x;
) num_negative++;
}
que.push(Node(cur.pos, a[cur.pos]));
}
; i < n; i++)
printf( ? '\n' : ' ');
;
}
Codeforces Round #375
Codeforces Round #376
Codeforces Round #377
Codeforces Round #378
Codeforces Round #379