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. "); else printf("Oh, my keyboard! "); 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 ", 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 "); else if(4 == n) { printf("YES "); printf("1 * 2 = 2 "); printf("2 * 3 = 6 "); printf("6 * 4 = 24 "); } else if(n == 5) { printf("YES "); printf("4 + 5 = 9 "); printf("3 * 9 = 27 "); printf("27 - 2 = 25 "); printf("25 - 1 = 24 "); } else if(n >= 6) { printf("YES "); printf("6 - 1 = 5 "); printf("5 - 5 = 0 "); for(int i = 7; i <= n; i++) printf("0 * %d = 0 ", i); printf("2 * 3 = 6 "); printf("6 * 4 = 24 "); printf("0 + 24 = 24 "); } 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 "); else { printf("YES "); for(int i = 0; i < n; i++) { printf("%d%c", check[a[i]], " "[i == n-1]); } } return 0; }