首页 > 代码库 > Codeforces Round #406 (Div. 2)

Codeforces Round #406 (Div. 2)

2024-09-10 15:17:46   219人阅读

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)


联系
我们