首页 > 代码库 > Codeforces Round #282 (Div. 2)
Codeforces Round #282 (Div. 2)
也是几百年没做CF咯,这场还是赛后做的,退化很多啦
A.Digital Counter
找规律 可能有火柴棍丢失,问你可能组成的数字有多少种,只需要肉眼看看每个数字填上火柴棍可能形成的数字,打个表就行了
#include <iostream>#include <cstdio>using namespace std;const int pos[] = {2, 7, 2, 3, 3, 4, 2, 5, 1, 2};int a, b;int main(){#ifdef LOCAL freopen("495A.in", "r", stdin);#endif a = getchar() - ‘0‘; b = getchar() - ‘0‘; printf("%d\n", pos[a]*pos[b]); return 0;}
B. Modular Equations
一开始没读懂题意,还以为是同余...就是
a / x = y ... b 给你a,b让你求x的可能个数
因为b是余数,所以需要满足0<=b<x
和素数只需要检查到sqrt(x)差不多,这里只需要枚举到sqrt(a-b)
这个复杂度还是能接受的O(sqrt(a-b))
一开始很傻逼,从sqrt(a-b)枚举到a-b...瞬间爆炸...TLE
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>using namespace std;const int MAXN = 1e5;int a, b, cnt;int pcnt[MAXN];bool prime[MAXN];int main(){#ifdef LOCAL freopen("495B.in", "r", stdin);#endif scanf("%d%d", &a, &b); if(a < b) printf("0\n"); else if(a == b) printf("infinity\n"); else { a -= b; for(int i = 1, t = sqrt(a); i <= t; i++) { if(a % i) continue; int x = i, y = a/i; if(x > b) cnt++; if(y > b) cnt++; if(x > b && x == y) cnt--; } printf("%d\n", cnt); } return 0;}
C. Treasure
感觉就是贪心了...一开始想法傻逼了,还去细分讨论很多,把自己绕进去了
就是让前面的‘#‘填入1个‘)‘,最后一个填入剩下所需的‘)‘
再跑一边检查一下有没有那个位置会使得‘)‘个数多余‘(‘个数
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <queue>using namespace std;const int MAXN = 1e5+10;int mcnt, acnt, hpos, lpos, lh;int inf[MAXN];char ins[MAXN];bool possible = true;queue<int> h;void noAnswer(){ printf("-1\n"); exit(0);}int main(){#ifdef LOCAL freopen("495C.in", "r", stdin);#endif scanf("%s", ins); for(int i = 0, t = strlen(ins); i < t; i++) { if(ins[i] == ‘(‘) mcnt++; else if(ins[i] == ‘)‘) mcnt--; else { lh = i; mcnt--; inf[i] = 1; h.push(i); } } if(mcnt < 0) noAnswer(); inf[lh] += mcnt; mcnt = 0; for(int i = 0, t = strlen(ins); i < t; i++) { if(ins[i] == ‘(‘) mcnt++; else if(ins[i] == ‘)‘) mcnt--; else mcnt -= inf[i]; if(mcnt < 0) noAnswer(); } while(!h.empty()) { printf("%d\n", inf[h.front()]); h.pop(); } return 0;}
D.Obsessive String
感觉CF的D题是足以制裁我了呢...KMP早就忘光了 更别说还要DP了 有空写写吧~
ABC做下来感觉细节还是蛮多的,不知道是因为自己退化了,还是这次比赛偏细节
Codeforces Round #282 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。