首页 > 代码库 > Codeforces Round #394 (Div. 2)
Codeforces Round #394 (Div. 2)
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 }
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 }
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 }
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 }
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 }
F
Codeforces Round #394 (Div. 2)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。