首页 > 代码库 > Codeforces Round #406 (Div. 2)
Codeforces Round #406 (Div. 2)
A - The Monster(暴力)【AC:3k+】
题意:
给定整数a,b,c,d(1<=a,b,c,d<=100),求是否有y满足 y=a*x1+b=c*x2+d。x1,x2为正整数。
思路:
我们考虑成两条直线在坐标系上,然后你想极端情况,两者相交使得y最大,是不是a=c=100的时候,在无穷远处相交(平行嘛),那么c小一点点y=99x+100,y=100x+0。所以可以发现y的范围肯定不会超过10000。所以暴力出10000的范围内的数据,匹配一下有无答案就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int a, b, c, d; 5 6 int solve() 7 { 8 map<int, int>ma; 9 int y = b; 10 while(y <= 10000) 11 { 12 ma[y]++; 13 y += a; 14 } 15 16 y = d; 17 while(y <= 10000) 18 { 19 if(ma[y] != 0) return y; 20 y += c; 21 } 22 return -1; 23 } 24 25 int main() 26 { 27 scanf("%d%d%d%d", &a, &b, &c, &d); 28 printf("%d\n", solve()); 29 return 0; 30 }
B - Not Afraid(瞎搞)【AC:2k+】
题意:
这题的题意比较迷,好像大概是:给定n个序列,每个序列有ki个数,问是否每个序列都有两个数满足x1=-x2 n,K<=10000。
思路:
就瞎搞吧。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 10000 + 5; 4 int a[2 * maxn]; 5 6 int n, m; 7 bool isBoom() 8 { 9 int ok = 0; 10 for(int i = 0; i < m; i++) 11 { 12 memset(a, 0, sizeof(a)); 13 int k; 14 scanf("%d", &k); 15 while(k--) 16 { 17 int x; 18 scanf("%d", &x); 19 if(x < 0) x = -x + 10000; 20 a[x]++; 21 } 22 int boom = 1, maybe = 0; 23 for(int i = 1; i <= 10000; i++) 24 { 25 if(a[i] > 0 && a[i + 10000] != 0) boom = 0; 26 if(a[i] > 0) maybe = 1; 27 } 28 for(int i = 10001; i <= 20000; i++) 29 { 30 if(a[i] > 0 && a[i - 10000] != 0) boom = 0; 31 if(a[i] > 0) maybe = 1; 32 } 33 if(maybe && boom) ok = 1; 34 35 } 36 return ok; 37 } 38 39 int main() 40 { 41 scanf("%d%d", &n, &m); 42 43 44 if(isBoom()) puts("YES"); 45 else puts("NO"); 46 return 0; 47 }
C. Berzerk(博弈论dp)【AC:300+】
题意:
有n个点围成一个圈,两个人。两个人分别有k1,k2个数,他们玩一个游戏。轮流进行,每个人可以选择一个数(每个数都可以被多次选择)并且把棋子前移这么多格,到达1号点胜利,问两个人分别从2-n开始是否必胜,必败或者会循环。n<=7000
D. Legacy【AC:100-】
题意:
有n个点,m条路径。每条路径可以从一个点到一个点,也可以从一个区间到一个点,也可以从一个点到一个区间,都有一定的费用。求从s号点到达其他点的最小距离。 n,m<=100000
E. Till I Collapse(树状数组 or 主席树)【AC:100-】
题意:
给定n个数si,你要对这个序列分段,并且对于每个k(1<=k<=n)求出每段最多有k种不同的数的时候的最小分段数。 1<=si<=n<=100000
Codeforces Round #406 (Div. 2)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。