首页 > 代码库 > Codeforces Round #268 (Div. 2)
Codeforces Round #268 (Div. 2)
A和B估算了一下复杂度都可以乱搞 所以就随意了
A代码：
#include <cstdio>#include <cstring>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 1000;int a[maxn];int main(){ //freopen("in.txt", "r", stdin); int n; scanf("%d", &n); int b, c; int tmp; scanf("%d", &b); for(int i = 0; i < b; i++) { scanf("%d", &tmp); a[tmp] = 1; } scanf("%d", &c); for(int i = 0; i < c; i++) { scanf("%d", &tmp); a[tmp] = 1; } bool flag = true; for(int i = 1; i <= n && flag; i++) { if(a[i] == 0) flag = false; } if(flag) printf("I become the guy.\n"); else printf("Oh, my keyboard!\n"); return 0;}
B代码：
#include <cstdio>#include <cstring>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 10000;int a[maxn];int rec[maxn];int main(){ //freopen("in.txt", "r", stdin); int p, q, l, r; int loc = 0; int maxnum = 0; scanf("%d%d%d%d", &p, &q, &l, &r); for(int i = 0; i < p; i++) { int x, y; scanf("%d%d", &x, &y); maxnum = max(maxnum, y); for(int j = x; j <= y; j++) { a[j] = 1; } } for(int i = 0; i < q; i++) { int x, y; scanf("%d%d", &x, &y); for(int j = x; j <= y; j++) { rec[loc++] = j; } } int ans = 0; for(int i = l; i <= r; i++) { bool flag = false; for(int j = 0; j < loc; j++) { if(rec[j]+i > maxnum) break; if(a[rec[j]+i] == 1) { flag = true; break; } } if(flag) ans++; } printf("%d\n", ans); return 0;}
C是构造
灵光一闪就...
小于等于3是没戏的
4的话是全部相乘
5的话是（4+5）* 3 - 2 - 1
考虑到2*3*4就正好是24 再想到乘法的幺元(单位元)是0 0可以强行去掉所有多余的数 所以只要构造出一个24和一个0就可以解决问题了
于是可以退出大于等于6的做法
注意它要输出的有n-1条等式
不要忘记最后让24 + 0 = 24
代码：
#include <cstdio>#include <cstring>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 10000;int a[maxn];int rec[maxn];int main(){ //freopen("in.txt", "r", stdin); int n; scanf("%d", &n); if(n <= 3) printf("NO\n"); else if(4 == n) { printf("YES\n"); printf("1 * 2 = 2\n"); printf("2 * 3 = 6\n"); printf("6 * 4 = 24\n"); } else if(n == 5) { printf("YES\n"); printf("4 + 5 = 9\n"); printf("3 * 9 = 27\n"); printf("27 - 2 = 25\n"); printf("25 - 1 = 24\n"); } else if(n >= 6) { printf("YES\n"); printf("6 - 1 = 5\n"); printf("5 - 5 = 0\n"); for(int i = 7; i <= n; i++) printf("0 * %d = 0\n", i); printf("2 * 3 = 6\n"); printf("6 * 4 = 24\n"); printf("0 + 24 = 24\n"); } return 0;}
D题一开始以为是一个简单贪心 少考虑了一种两边都能匹配的情况
应该有其他的办法 不过我是选择dfs
然后就是太久没有用STL了 都没什么使用它的意识了
感觉这种要给各个数据项打标记的题目使用map是比较好的
它可以由数值直接映射到数值 一步到位
传统方法的话如果数值大到超过几百万 要建立映射是一件很麻烦而且吃力不讨好的事情
再有就是关于如何存两个集合的和值的问题 如果分别存在两个变量A和B也可以 需要手动推一条公式
不过我还是习惯把它存在一个小数组里 这样根据它所在的集合能直接灵活取数
代码：
#include <cstdio>#include <cstring>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 1100100;int ans[maxn];int a[maxn], b[maxn];int n;int sum[2];map<int, int> check;bool dfs(int a, int k){ if(!check.count(sum[k] - a)) return false; if(check[sum[k] - a] == -1) { check[a] = check[sum[k] - a] = k; return true; } else { if(dfs(sum[k^1] - (sum[k] - a), k)) { check[a] = check[sum[k] - a] = k; return true; } else return false; }}int main(){ //freopen("in.txt", "r", stdin); bool flag = true; scanf("%d%d%d", &n, &sum[0], &sum[1]); memset(ans, -1, 4*n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); check[a[i]] = -1; } for(int i = 0; i < n && flag; i++) { if(check[a[i]] != -1) continue; if(!dfs(a[i], 0) && !dfs(a[i], 1)) flag = false; } if(!flag) printf("NO\n"); else { printf("YES\n"); for(int i = 0; i < n; i++) { printf("%d%c", check[a[i]], " \n"[i == n-1]); } } return 0;}
Codeforces Round #268 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。