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

Codeforces Round #394 (Div. 2)

2024-09-02 18:52:47   209人阅读

A - Dasha and Stairs(water)

题意：能否找到一个区间内奇数偶数个数分别为a和b。被hack了一个0 0的数据点orz....

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 const int maxn = 100 + 5;
 5 typedef long long LL;
 6 typedef pair<int, int>pii;
 7 
 8 int main()
 9 {
10     int a, b;
11     cin >> a >> b;
12     int d = abs(a - b);
13     if(a == 0 && b == 0)
14     {
15         puts("NO");
16         return 0;
17     }
18     if(d >= 2)
19     {
20         puts("NO");
21     }
22     else
23     {
24         puts("YES");
25     }
26     return 0;
27 }
View Code

 

B - Dasha and friends (暴力)

题意：给你一个圆，按0-n-1编号，上面有一个点A，一个点B，然后有一堆障碍物，然后告诉你两个数组，分别是以A和B为参照物的障碍物的坐标。问你这两个数组是否有可能在同一个圆上。

思路：我是直接暴力了...因为数据范围太小了

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 const int maxn = 100 + 5;
 5 typedef long long LL;
 6 typedef pair<int, int>pii;
 7 int a[55], b[55], c[55], d[55];
 8 
 9 int n, L;
10 
11 bool solve()
12 {
13     for(int d = 0; d <= L; d++)
14     {
15         for(int k = 0; k < n; k++)
16         {
17             int ok = 1;
18             for(int i = 0; i < n; i++)
19             {
20                 if(a[ (i + k) % n ] != (b[i] + d) % L)
21                 {
22                     ok = 0;
23                 }
24             }
25             if(ok == 1) return true;
26 
27         }
28 
29     }
30     return false;
31 }
32 int main()
33 {
34     cin >> n >> L;
35     for(int i = 0; i < n; i++)
36     {
37         cin >> a[i];
38     }
39     sort(a, a + n);
40 
41     for(int i = 0; i < n; i++)
42     {
43         cin >> b[i];
44     }
45     sort(b, b + n);
46 
47     printf("%s\n", solve() ? "YES" : "NO");
48     return 0;
49 }
View Code

 

C - Dasha and Password （状压dp）

题意：密码里必须含有三种元素，然后给你n个长度为m的字符串，每行挑一个组成密码。问你指针们最少移动多少次能达到目标。初始的时候每一行的指针均默认指向第一个字母，每次移动可以使任意一个指针向左或向右边移动。

思路：直接状压dp就行了。

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 const int maxn = 100 + 5;
 5 typedef long long LL;
 6 typedef pair<int, int>pii;
 7 string s[55];
 8 int dp[55][10];
 9 int judge(char ch)
10 {
11     if(ch == ‘*‘ || ch == ‘&‘ || ch == ‘#‘)
12     {
13         return 1;
14     }
15     else if(ch >= ‘a‘ && ch <= ‘z‘)
16     {
17         return 2;
18     }
19     else if(ch >= ‘0‘ && ch <= ‘9‘)
20     {
21         return 4;
22     }
23 }
24 int main()
25 {
26     int n, m;
27     cin >> n >> m;
28     for(int i = 0; i < n; i++)
29     {
30         cin >> s[i];
31     }
32     memset(dp, INF, sizeof(dp));
33     for(int j = 0; j < m; j++)
34     {
35         int t = judge(s[0][j]);
36         dp[0][t] = min(dp[0][t], min(j, m - j));
37     }
38     for(int i = 1; i < n; i++)
39     {
40         for(int j = 0; j < m; j++)
41         {
42             int t = judge(s[i][j]);
43             for(int k = 0; k < 8; k++)
44             {
45                 dp[i][k | t] = min(dp[i][k | t], dp[i - 1][k] + min(j, m - j));
46             }
47         }
48     }
49     cout << dp[n - 1][7] << endl;
50     return 0;
51 }
View Code

 

D - Dasha and Very Difficult Problem（贪心）

题意：已知一个n，一个l，一个r，一个a数组，一个p数组，让你求b数组。然后a，b数组的元素都必须在l和r之间。c[i] = b[i] - a[i]，然后p数组就是c数组离散化后的结果。问你是否存在一个数组b满足要求。

思路：按p从小到大或从大到小排序都行。比如从小到大排序，那么这个时候就选择b[1] = l。然后递推就行了，贪心的方法很容易从样例里推测出来。唯一注意的就是从小到大的时候的那句max和从大到小的那句min。

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 const int maxn = 1e5 + 5;
 5 typedef long long LL;
 6 typedef pair<int, int>pii;
 7 
 8 struct node
 9 {
10     int a, b, p, id;
11     bool operator < (const node &other)const
12     {
13         return  p < other.p;
14     }
15 }nodes[maxn];
16 bool cmpid(node x, node y)
17 {
18     return x.id < y.id;
19 }
20 int main()
21 {
22     int n, l, r;
23     scanf("%d%d%d", &n, &l, &r);
24     for(int i = 1; i <= n; i++)
25     {
26         scanf("%d", &nodes[i].a);
27         nodes[i].id = i;
28     }
29     for(int i = 1; i <= n; i++)
30     {
31         scanf("%d", &nodes[i].p);
32     }
33     sort(nodes + 1, nodes + 1 + n);
34 
35     nodes[1].b = l;
36     int d = nodes[1].b - nodes[1].a;
37     for(int i = 2; i <= n; i++)
38     {
39         nodes[i].b = max(l, nodes[i].a + d + 1);
40         d = nodes[i].b - nodes[i].a;
41     }
42 
43     sort(nodes + 1, nodes + 1 + n, cmpid);
44 
45     for(int i = 1; i <= n; i++)
46     {
47         if(nodes[i].b < l || nodes[i].b > r)
48         {
49             puts("-1");
50             return 0;
51         }
52     }
53     for(int i = 1; i <= n; i++)
54     {
55         cout << nodes[i].b << ((i == n) ? ‘\n‘ : ‘ ‘);
56     }
57 
58     return 0;
59 }
View Code

 

E - Dasha and Puzzle（dfs+脑洞？）

题意：给你一棵n个结点的树，让你把它放到一个坐标系中，每条边都必须平行于坐标轴，问你是否可能，可能的话输出顶点坐标。

思路：

技术分享 
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 pair<int, int>ans[35];
 4 int siz[35];
 5 int dx[] = {0, 1, 0, -1};
 6 int dy[] = {1, 0, -1, 0};
 7 vector<int>G[35];
 8 void dfs(int cur, int pa)
 9 {
10     siz[cur] = 1;
11     for(auto o : G[cur])
12     {
13         if(o != pa)
14         {
15             dfs(o, cur);
16             siz[cur] += siz[o];
17         }
18     }
19 }
20 
21 void dfs(int cur, int pa, int dir)
22 {
23     dir = (dir - 1 + 4) % 4;
24     for(auto o : G[cur])
25     {
26         if(o != pa)
27         {
28 
29             ans[o] = {ans[cur].first + dx[dir] * siz[o], ans[cur].second + dy[dir] * siz[o]};
30             dfs(o, cur, dir);
31             dir = (dir + 1) % 4;
32         }
33     }
34 }
35 
36 
37 int main()
38 {
39     int n, u, v;
40     scanf("%d", &n);
41     for (int i = 0; i < n - 1; i++)
42     {
43         scanf("%d%d", &u, &v);
44         G[u].push_back(v);
45         G[v].push_back(u);
46     }
47     for(int i = 1; i <= n; i++)
48     {
49         if(G[i].size() > 4)
50         {
51             puts("NO");
52             return 0;
53         }
54     }
55     dfs(1, 0);
56     ans[1] = {0, 0};
57     dfs(1, -1, 0);
58     puts("YES");
59 
60     for(int i = 1; i <= n; i++)
61     {
62         cout << ans[i].first << " " << ans[i].second << "\n";
63     }
64     return 0;
65 }
View Code

 

F

 

Codeforces Round #394 (Div. 2)


联系
我们