补题--25届acm校队训练赛

D 选数搜索; 2002; NOIP 普及组; 深度优先搜索 DFS; 剪枝; 素数判断,质数,筛法#includeiostream #includecstdio using namespace std; int n,k; int a[25]; bool isprime(int n) { if(n2) return false; if(n2) return true; for(int i2;i*in;i) { if(n%i0) return false; } return true; } int dfs(int choose,int asum,int start ,int end)//递归函数 { int sum0,i; if(choose0)return isprime(asum); //当choose选完判断asum是不是素数 for(istart;iend;i) // 遍历开始到最后 全组合 { sumsumdfs(choose-1,asuma[i],i1,end); } return sum; } int main() { cinnk; for(int i0;in;i) cina[i]; coutdfs(k,0,0,n-1)endl;(chosechoose0从零开始到结尾) return 0; }E 纪念品分组贪心 排序尽可能的少分点组尽量都分成两个纪念品从大的开始组队如果最大的与最小的都配不上队说明绝对不能配成两个只能是一个排序 利用双指针 去遍历结果将最大的与最小的和 跟最大限额比较如果 和不大于限额 就组数加一 左指针和右指针 变化反之 就移动右指针 组数加一#includebits/stdc.h long long n,w,c0; int p[30005]; using namespace std; int main() { scanf(%lld,w); scanf(%lld,n); for(int i0;in;i) { scanf(%d,p[i]); } sort(p,pn); int l0; int rn-1; int cnt0; while(lr) { if(p[l]p[r]w) { cnt; l; r--; } else { cnt; r--; } } coutcntendl; return 0; }I -与‘_’配对 -_-数学组合将上和下面的符号分别统计#includeiostream #includecstdio using namespace std; int t; long long u,d; long long n; char s[200005]; int main() { scanf(%d,t); while(t--) { u0; d0; scanf(%lld,n); scanf(%s,s); for(int i0;in;i) { if(s[i]-) u; if(s[i]_) d; } long long lu/2; long long ru-l; printf(%lld\n,l*r*d);// int*int*int 超范围 改为long long ; } return 0; }J 斐波那契数列ai2 ai ai1题目中ai2 ai ai1 , 其中1i 3,当 i 1 a3 a1 a2 当 i 2 时 a4 a2 a3当 i 3 时 a5 a3 a4其中 符合的情况有 两种或者是三种都符合a3a1a2a3a4-a2a3a5-a4#includeiostream #includecstdio using namespace std; int main() { int a1,a2,a3,a4,a5; int num1,num2,num3; int t; cint; while(t--) { int cnt0; cina1a2a4a5; num1a1a2; num2a4-a2; num3a5-a4; if(num1num2||num1num3||num2num1num1num3) { a3num1; } else if(num2num3) a3num2; else a3num3; if(a2a1a3) cnt; if(a4-a2a3) cnt; if(a5-a4a3) cnt; coutcntendl; } return 0; }B 两个字符合并为一个字符strings只要有相邻相同的 那么就会有最短长度 1 其他情况都是 原长度#includeiostream #includecstdio using namespace std; int t; int l; string s; bool allsametrue; int main() { cint; while(t--) { cins; ls.size(); for(int i0;il-1;i) { if(s[i]s[i1]) { allsametrue; break;// 当找不到时 跳出循环 不然会出错 } else allsamefalse; } if(allsamefalse) coutlendl; else cout1endl; } return 0; }G 素数个数数学; 枚举; 素数判断,质数,筛法素数筛埃氏筛法将合数筛去#includeiostream #includecstdio using namespace std; typedef long long ll; bool pri[1000000005]; ll cnt; int main() { ll n; scanf(%lld,n); for(int i2;i*in;i) { if(!pri[i]) for(int ji*i;jn;ji) pri[j]1; } for(int i2;in;i) { if(!pri[i]) cnt; } printf(%d\n,cnt); return 0; }欧拉筛 比埃氏筛快#includeiostream #includecstdio using namespace std; typedef long long ll; const int maxn1e810; bool pri[maxn]; ll cnt; ll pp0; int primes[maxn]; int main() { ll n; scanf(%lld,n); for(ll i2;in;i) { if(!pri[i]) primes[pp]i; for(int j1;primes[j]*injpp;j) { pri[primes[j]*i]1; if(i%primes[j]0) break; } } for(ll i2;in;i) { if(!pri[i]) cnt; } printf(%lld\n,cnt); return 0; }F 乒乓球11分制和21分制分制条件 1有一方的分数达到或超过本局的 “目标分”11 分制就是≥1121 分制就是≥21条件 2双方的分差≥2 分比如 11:9 可以结束但 11:10 不行要打到 12:10 才结束#includeiostream #includecstdio #includestring #includealgorithm #includecstdlib using namespace std; typedef long long ll; string s; int w0,l0;//WWWWWWWWWWWWWWWWWWWWWWLWE void work (int lo) { w0; l0; for(char c:s) { if(cE) break; if(cW) w; if(cL) l; if(max(w,l)loabs(w-l)2) { coutw:lendl; w0; l0; } } coutw:lendl; } int main() { string line; while(getline(cin,line)) //整段读入 刚开始用的cins 为将后续字符串读入 { sline; //把刚读到的一行文字拼接到总字符串 s 的后面 if(line.find(E)!string::npos)break; //string::npos 没找到 } work(11); coutendl; work(21); return 0; }