首页 > 代码库 > Codeforces Round #268 (Div. 1) solution
Codeforces Round #268 (Div. 1) solution
A.24 Game
题意：给你1, 2, ..., n-1, n 这个序列，每次你可以取出两个数做+/-/*三种操作之一，然后把结果放回到序列中，询问能否是的这个序列最后只剩下一个24。
解法：首先很明显n < 4的时候是无解的。如果n=4，那么1 * 2 * 3 * 4=24，如果n=5，那么(5 - 1 - 2) * 3 * 4 = 24。若n > 5，那么我可以做n - (n - 1) = 1，相当于变成了n-2时候的情况加一个1，那么显然最后让答案乘上这个1即可。
代码：
include <cstdio>#include <algorithm>#include <map>#include <vector>#include <string>#include <cstring>using namespace std;const int N = 500010;int a[N];int main() { int n; while( scanf("%d", &n) != EOF ) { if(n <= 3) { printf("NO\n"); continue; } else if(n % 2 == 0) { printf("YES\n"); int k = 0; for(int i = 5; i < n; i += 2) { printf("%d - %d = 1\n", i + 1, i); k++; } printf("1 * 2 = 2\n"); printf("2 * 3 = 6\n"); printf("6 * 4 = 24\n"); for(int i = 0; i < k; i++) printf("1 * 24 = 24\n"); } else { printf("YES\n"); int k = 0; for(int i = 6; i < n; i += 2) { printf("%d - %d = 1\n", i + 1, i); k++; } printf("5 - 1 = 4\n"); printf("4 - 2 = 2\n"); printf("2 * 3 = 6\n"); printf("6 * 4 = 24\n"); for(int i = 0; i < k; i++) printf("1 * 24 = 24\n"); } } return 0;}
B.Two Sets
题意：给你一列两两不同的数v[i]，然后两个正整数a,b，现在希望把序列v中的每个数都分到两个集合中的一个。假设两个集合为s,t，那么若x∈s，则a-x∈s，类似的有若x∈t，则b-x∈t。询问这列数能否被成功划分到两个集合。
解法：首先我们假设a<b。我们考虑现在这列数中最小的数，假设为x。若b-x在序列v中存在，那么我一定会把x和b-x都放到集合t中。因为如果我不把b-x和x放到t中，那么b-x这个元素就永远无法被任何其他的元素匹配了。原因是假设又另一个元素能和b-x匹配，我们设这个元素为y，由于x是当前序列中的最小值，那么y>x，则有y+b-x>b，那么显然和y+b-x=b矛盾。然后还需要考虑的就是有可能2 * x = a或 2 * x = b，这种特殊考虑一下就好了。呃，我的代码由于没想清楚写的比较复杂，思路也不完全是上述的思路，仅供参考。
代码：
#include <cstdio>#include <algorithm>#include <map>#include <vector>#include <string>#include <set>#include <cstring>using namespace std;const int N = 100010;int v[N];map<int, int> mp;set<int> s;set<int>::iterator it, is, ir;int main() { int n, a, b; while( scanf("%d%d%d", &n, &a, &b) != EOF ) { int oo = 0; if(a > b) { swap(a, b); oo = 1; }; s.clear(); mp.clear(); for(int i = 0; i < n; i++) { scanf("%d", &v[i]); s.insert(v[i]); } int flag = 0; for(it = s.begin(); s.size() > 0; it = s.begin()) { int p1 = *it; is = s.find(a - p1); if(2 * p1 == a) { is = s.find(b - p1); if(is != s.end()) { s.erase(p1); s.erase(b - p1); mp[p1] = 1; mp[b - p1] = 1; } else { s.erase(p1); mp[p1] = 0; } } else if(2 * p1 == b){ s.erase(p1); mp[p1] = 1; }else if(is == s.end()) { is = s.find(b - p1); if(is == s.end()) { if(2 * p1 == b) { s.erase(p1); mp[p1] = 1; } else { flag = 1; break; } } else { s.erase(b - p1); s.erase(p1); mp[b - p1] = 1; mp[p1] = 1; } } else { is = s.find(b - p1); if(is == s.end()) { if(a - p1 == p1) { flag = 1; break; } s.erase(a - p1); s.erase(p1); mp[a - p1] = 0; mp[p1] = 0; } else { is = s.find(b - a + p1); if(is == s.end()) { s.erase(a - p1); s.erase(p1); mp[a - p1] = 0; mp[p1] = 0; } else{ s.erase(b - p1); s.erase(p1); mp[b - p1] = 1; mp[p1] = 1; s.erase(a - p1); s.erase(b - a + p1); mp[a - p1] = 1; mp[b - a + p1] = 1; } } } } if(flag == 1) printf("NO\n"); else { printf("YES\n"); for(int i = 0; i < n; i++) printf("%d%c", (mp[v[i]] ^ oo), (i == (n - 1))?‘\n‘:‘ ‘); } } return 0;}
Codeforces Round #268 (Div. 1) solution
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。