首页 > 代码库 > 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)