题意:
思路:
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