给出一个\(n\times m\)连连看的局面，下面有\(q\)次询问：两个位置的块能否消去，即两个位置的连线是否能少于两次转折，回答\(YES/NO\)。与一般的连连看不同之处在于，连线不能从外围绕过
先判断两个位置是否是空地，是否是一种颜色，然后从其中一个位置开始\(dfs/bfs\)，由于限制条件和转折次数有关，因此要记录转折次数。搜索的时候要先采用转折少的方案，不然复杂度不对。
时间复杂度\(O(Tnmq)\)
\(T\)为数据组数，\(n,m,q\)如题意。
在一个\(m\times n\)的矩形迷宫中，用空地、障碍和楼梯，楼梯有两个方向——左右和上下，而且每过\(1\)分钟换一次方向，登上楼梯并经过楼梯只需要\(1\)分钟，不能再楼梯上停留，求从起点到终点最短要多长时间。
与一般的迷宫问题唯一的不同点就是这个楼梯。楼梯的方向其实很好处理，当你处于一个状态\((x,y,t)\)，在位置\((x,y)\)时间为\(t\)时，你可以判断\(t\)的奇偶求出某个楼梯的方向。想明白了这个，就可以\(dfs/bfs\)了，求最短距离最好还是用\(bfs\)，我不知道为什么脑抽写了个\(dfs\)。
时间复杂度\(O(Tnm)\)
\(T\)是数据组数，\(n,m\)如题意。
给出\(n\)个数，求最大连续子序列——就是最大子段和呗。
那个经典的线性算法就不提了。刚刚想出另一个线性算法，\(sum[i]\)表示前\(i\)个的累加和。从小到大枚举子段的右端点\(R\)，可以尝试求出以\(R\)为右端点的最大子段和。我们可以找到\(\min_{i=1}^{i\leq R-1}{sum[i]}\)，设这个位置为\(L\)，那么\([L+1,R]\)就是所求的最大子段。
从左向右枚举\(R\)的同时维护这个\(min\)即可。
时间复杂度\(O(Tn)\)
\(T\)是数据组数，\(n\)是序列长度。
有\(N\)个数，给出他们两两之和，求这\(N\)个数。保证解存在且唯一。
整理一下数据，和共有\(K\)种，第\(i\)种为\(a[i]\)，出现\(b[i]\)次。
最小的和一定是最小两个数相加，先枚举最小数，然后开始\(dfs\)。
\(dfs\)每层先找到最小的未出现\(b[i]\)次的和数\(a[i]\)。枚举已经有的加数\(x\)，认为\(a[i]\)是由\(x+y\)组成的，并检验加数集合加入\(y\)是否合法，更新每个和数出现的次数，若可行就进行下一层\(dfs\)。
时间复杂度\(O(TN^{N^3}logN)\)，可行方案并不多，剪枝可以减掉很多，实际时间远小于上界。
\(T\)为数据组数，\(N\)为数字数量。
给出一些单词，你可以使用这个单词把它的首字母变成末字母，问你能否吧\(B\)变成\(M\)。
本质上是有向图连通性，怎么写都行\(dfs/bfs/floyd\)
时间复杂度\(O(TL)\)
\(T\)为数据组数，L为所有单词长度和。
给出\(n\)个字符串，你要找到最长的一个串使得这个串或者他的反转串在这\(n\)个串中都出现过。求这个长度。
很暴力的一道题。先枚举\(/\)二分这个长度\(L\)，然后从第一个串中枚举长度为\(L\)的串，判断它或它的反转串在剩下\(n-1\)个串中是否全部出现，如果全部出现，则答案\(L\)可行。
时间复杂度\(O(Tn^2L^2logL)\)
\(T\)为数据组数，\(n\)字符串数量，\(L\)为字符串长度。
给出很多组火星单词和对应的地球单词，然后给出一段火星文，把这段火星文中的火星单词全部替换为地球单词输出，如果不能识别某个火星单词，不做替换即可。
输入比较烦，注意是否读入了空行。
其实就是把火星文中的单词提取出来，尝试替换即可，但是这题不给数据范围，还是考虑一些高效的方法。如何判断一个单词是否出现过，可以用字符串\(Hash\)，也可以用\(STL\)的\(map<string,string>\)。不知道为啥我的字符串\(Hash\)挂了，不得不用\(map\)。
直接用\(map\)存好火星单词和地球单词的对应关系。然后从火星文里每次找一个单词，尝试替换。
时间复杂度\(O(TmLlogn)\)
\(T\)为数据组数，\(n\)为单词数量，\(L\)为字符串总长度，\(m\)为文章数量。
素数环问题。求出字典序最小的\(1\)到\(n\)的圆排列，要求相邻两数之和为质数。
\(dfs+\)回溯，第\(i\)层枚举第\(i\)个位置填什么，检验它与前数之和是否为质数。注意枚举了最后一个数之后还要检验最后一个数和第一个数。
时间复杂度\(O(Tn^n)\)，剪枝很有效，实际复杂度远小于上界。
\(T\)为数据组数，\(n\)为数字数量。
又是一个类似迷宫问题，不同点在于有些地方有怪物，打怪要小号一定时间。此题需要输出方案。
求最短时间最好用\(bfs\)（我怎么又写了\(dfs\)）。搜索的同时记录前驱位置，最后用这个前驱数组就可可以找到最优方案的路径了。
时间复杂度\(O(Tnm)\)
\(T\)为数据组数，\(n,m\)为地图长宽。
门票\(50\)元，售票处初始没有钱。
有\(m\)个拿着\(50\)元大钞的人，\(n\)个拿着\(100\)元巨钞的人，求共有多少种排队方案能让这\(m+n\)个人顺利买到票。
动态规划。
\(f[i][j]\)表示排好了\(i\)个拿着\(50\)元的人和\(j\)个拿着\(100\)元的人的方案数。
\[ f[i][j]=f[i-1][j]\times (m-i+1)+f[i][j-1]\times (n-j+1) \]
注意答案会非常大，要使用大数。
时间复杂度\(O(Tnm)\)
\(T\)为数据组数，\(n,m\)如题意。
一\(n\)个节点的树，树的每个节点上可能有一些\(bug\)。你有\(m\)组军队，每组军队可以处理一个节点的\(20\)个\(bug\)，处理掉一个节点的所有\(bug\)会有一定收益，你从\(1\)号节点出发，可以分兵，进入下一个节点之前必须解决掉当前节点的\(bug\)。求你能获得的最多收益。
树形动态规划，转移类似背包。
\(f[i][j]\)表示在以\(i\)为根的子树上，分配\(j\)组兵能获得的最大收益。
\[ f[x][j+k]=\max_{j+k\leq m}{\{f[x][j+k],f[x][j]+f[y][k]\}} \]
其中，\(x\)为当前节点，\(y\)为\(x\)的子节点。最终答案为\(f[1][m]\)
时间复杂度\(O(Tnm^2)\)
\(T\)为数据组数，\(n,m\)同题意。
给出一个字符串，输出反转串。
没啥好说的。
时间复杂度\(O(Tn)\)
\(T\)为数据组数，\(n\)为字符串长度。
在一个比赛中，有\(1\)号到\(100\)号葡萄给两个选手争抢，选手得分为抢到的葡萄编号之积。给出两个选手的得分，保证得分不同，低分选手会质疑高分选手说谎，假定低分选手不说谎(The player with the lower score is presumed to have told the truth)。你要判断高分选手是否说谎，如果说谎，输出低分选手分数，否则输出高分选手分数。
直接\(dfs\)搜索，每个编号有三种情况，两人都没拿或其中一个人拿。剪剪枝就好了。不过，其实低分选手还是可能说谎的，如果低分选手说谎，输出高分选手分数(与题目描述相悖，但是只有这样能过)。
时间复杂度\(O(3^{100}T)\)，实际复杂度远低于上界。
\(T\)为数据组数。
有一个\(n\)层电梯，从第\(i\)层可以向上或向下\(a[i]\)层，不能到达不存在的楼层。求从第\(A\)层到第\(B\)层最少要几次，不能到达则输出\(-1\)
从第\(A\)层开始\(bfs\)，记录当前位置和所用次数，第一次到达第\(B\)层即为答案。
时间复杂度\(O(Tn)\)
\(T\)为数据组数，\(n\)为层数。
给出\(m\)个木棍，问是否能拼成一个正方形。
\(dfs+\)剪枝。一定要枚举正方形的\(3\)条边分别使用了那些木棍，不能搜索第\(i\)个木棍属于第几条边。至于原因，说不清楚，反正会超时，可能是第二种搜索方式不利于剪枝。
时间复杂度\(O(3^mT)\)
\(T\)为数据组数，\(m\)为木棍数量。
//1001
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
const int maxn=1010;
const int ws_[4]={0,1,0,-1},ad_[4]={1,0,-1,0};
int N,M,mp[maxn][maxn],sx,sy,fx,fy;
int vis[maxn][maxn][4];
bool out(int x,int y){
????return x<=0||y<=0||x>N||y>M;
}
void dfs(int x,int y,int d,int t){
????if(t>2)return;
????if(t>=vis[x][y][d])return;
????vis[x][y][d]=t;
????int tx=x+ws_[d],ty=y+ad_[d];
????if(!out(tx,ty))
????????if(mp[tx][ty]==0||(tx==fx&&ty==fy))
????????????dfs(tx,ty,d,t);
????for(int i=0;i<4;i++)
????????if(d!=i){
????????????tx=x+ws_[i],ty=y+ad_[i];
????????????if(out(tx,ty))continue;
????????????if(mp[tx][ty]!=0&&!(tx==fx&&ty==fy))continue;
????????????dfs(tx,ty,i,t+1);
????????}
}
bool judge(){
????memset(vis,10,sizeof(vis));
????dfs(sx,sy,0,0);
????dfs(sx,sy,1,0);
????dfs(sx,sy,2,0);
????dfs(sx,sy,3,0);
????return vis[fx][fy][0]<=2||vis[fx][fy][1]<=2||vis[fx][fy][2]<=2||vis[fx][fy][3]<=2;
}
int main(){
????//freopen("in","r",stdin);
????while(1){
????????N=read(),M=read();
????????if(N+M==0)break;
????????for(int i=1;i<=N;i++)
????????????for(int j=1;j<=M;j++)
????????????????mp[i][j]=read();
????????for(int _=read();_;_--){
????????????sx=read(),sy=read(),fx=read(),fy=read();
????????????if(mp[sx][sy]!=mp[fx][fy]||!mp[sx][sy])
????????????????puts("NO");
????????????else if(!judge())
????????????????puts("NO");
????????????else
????????????????puts("YES");
????????}
????}
????return 0;
}
//1002
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
const int maxn=25;
const int ws_[4]={1,-1,0,0},ad_[4]={0,0,1,-1};
int N,M,sx,sy,fx,fy;
char mp[maxn][maxn];
int vis[maxn][maxn][2];
void dfs(int x,int y,int t){
????if(mp[x][y]=='*')return;
????if(t>=vis[x][y][t&1])
????????return;
????vis[x][y][t&1]=t;
????dfs(x,y,t+1);
????for(int i=0;i<4;i++){
????????int tx=x+ws_[i],ty=y+ad_[i];
????????if(mp[tx][ty]=='*')continue;
????????if(mp[tx][ty]=='|'){
????????????if(i<2&&!(t&1))
????????????????dfs(tx+ws_[i],ty,t+1);
????????????else if(i>=2&&(t&1))
????????????????dfs(tx,ty+ad_[i],t+1);
????????}
????????else if(mp[tx][ty]=='-'){
????????????if(i>=2&&!(t&1))
????????????????dfs(tx,ty+ad_[i],t+1);
????????????else if(i<2&&(t&1))
????????????????dfs(tx+ws_[i],ty,t+1);
????????}
????????else
????????????dfs(tx,ty,t+1);
????}
}
int main(){
????//freopen("in","r",stdin);
????while(scanf("%d%d",&N,&M)!=EOF){
????????memset(mp,'*',sizeof(mp));
????????memset(vis,10,sizeof(vis));
????????for(int i=1;i<=N;i++)
????????????for(int j=1;j<=M;j++){
????????????????mp[i][j]=one();
????????????????if(mp[i][j]=='S')sx=i,sy=j;
????????????????if(mp[i][j]=='T')fx=i,fy=j;
????????????}
????????dfs(sx,sy,0);
????????printf("%d\n",min(vis[fx][fy][0],vis[fx][fy][1]));
????}
????return 0;
}
//1003
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
const int maxn=10010;
int N,a[maxn];
int main(){
????//freopen("in","r",stdin);
????while(1){
????????N=read();
????????if(!N)break;
????????for(int i=1;i<=N;i++)
????????????a[i]=read();
????????long long sum=0,Min=0,ans=-1;
????????int idMin=0,ansL,ansR;
????????for(int i=1;i<=N;i++){
????????????sum+=a[i];
????????????if(sum-Min>ans)
????????????????ans=sum-Min,ansL=idMin+1,ansR=i;
????????????if(sum<Min)
????????????????Min=sum,idMin=i;
????????}
????????if(ans==-1)
????????????ans=0,ansL=1,ansR=N;
????????printf("%I64d %d %d\n",ans,a[ansL],a[ansR]);
????}
????return 0;
}
//1004
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
const int maxn=5010;
int N,M,tot,a[maxn],ans[maxn],vis[maxn];
bool succ;
void dfs(int x){
????if(succ)return;
????if(x==N+1){
????????sort(ans+1,ans+1+N);
????????for(int i=1;i<N;i++)
????????????printf("%d ",ans[i]);
????????printf("%d\n",ans[N]);
????????succ=1;
????????return;
????}
????for(int i=1;i<=tot;i++)
????????if(vis[i]){
????????????for(int j=1;j<x;j++){
????????????????int v=a[i]-ans[j];
????????????????if(v<=0)continue;
????????????????bool flag=1;
????????????????for(int k=1;k<x;k++){
????????????????????int tmp=v+ans[k];
????????????????????if(tmp>a[tot]){flag=0;break;}
????????????????????int pos=lower_bound(a+1,a+1+tot,tmp)-a;
????????????????????if(a[pos]!=tmp){flag=0;break;}
????????????????}
????????????????if(!flag)continue;
????????????????for(int k=1;k<x;k++){
????????????????????int tmp=v+ans[k];
????????????????????int pos=lower_bound(a+1,a+1+tot,tmp)-a;
????????????????????vis[pos]--;
????????????????????if(vis[pos]<0)flag=0;
????????????????}
????????????????ans[x]=v;
????????????????if(flag)
????????????????????dfs(x+1);
????????????????for(int k=1;k<x;k++){
????????????????????int tmp=v+ans[k];
????????????????????int pos=lower_bound(a+1,a+1+tot,tmp)-a;
????????????????????vis[pos]++;
????????????????}
????????????}
????????????break;
????????}
}
int main(){
????//freopen("in","r",stdin);
????while(1){
????????N=read();M=N*(N-1)/2;tot=0;
????????if(!N)break;
????????for(int i=1;i<=M;i++){
????????????int tmp=read();
????????????if(tmp!=a[tot])
????????????????a[++tot]=tmp,vis[tot]=1;
????????????else
????????????????vis[tot]++;
????????}
????????succ=0;
????????for(int i=1;i<=a[1];i++){
????????????ans[1]=i;
????????????dfs(2);
????????????if(succ)break;
????????}
????}
????return 0;
}
//1005
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
char s[1010];
bool e[26][26];
int main(){
????//freopen("in","r",stdin);
????while(scanf("%s",s+1)!=EOF){
????????memset(e,0,sizeof(e));
????????while(1){
????????????int len=strlen(s+1);
????????????if(len==1&&s[1]=='0')break;
????????????e[s[1]-'a'][s[len]-'a']=1;
????????????scanf("%s",s+1);
????????}
????????for(int i=0;i<26;i++)
????????????e[i][i]=1;
????????for(int k=0;k<26;k++)
????????????for(int i=0;i<26;i++)
????????????????for(int j=0;j<26;j++)
????????????????????e[i][j]|=e[i][k]&e[k][j];
????????if(e['b'-'a']['m'-'a'])
????????????puts("Yes.");
????????else
????????????puts("No.");
????}
????return 0;
}
//1006
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
const int maxn=110;
int N,len[maxn];
char s[maxn][maxn];
inline bool match(int a,int la,int ra,int b,int lb,int rb){
????for(;la<=ra;la++,lb++){
????????if(s[a][la]!=s[b][lb])
????????????return 0;
????}
????return 1;
}
inline bool revmatch(int a,int la,int ra,int b,int lb,int rb){
????for(;la<=ra;la++,rb--){
????????if(s[a][la]!=s[b][rb])
????????????return 0;
????}
????return 1;
}
bool check(int x){
????for(int i=1;i+x-1<=len[1];i++){
????????bool find=1;
????????for(int j=2;j<=N;j++){
????????????bool vis=0;
????????????for(int k=1;k+x-1<=len[j];k++)
????????????????if(match(1,i,i+x-1,j,k,k+x-1)||revmatch(1,i,i+x-1,j,k,k+x-1)){
????????????????????vis=1;
????????????????????break;
????????????????}
????????????if(!vis){
????????????????find=0;
????????????????break;
????????????}
????????}
????????if(find)
????????????return 1;
????}
????return 0;
}
int main(){
????//freopen("in","r",stdin);
????for(int _=read();_;_--){
????????int L=0,R=maxn,mid;
????????N=read();
????????for(int i=1;i<=N;i++){
????????????scanf("%s",s[i]+1);
????????????len[i]=strlen(s[i]+1);
????????????R=min(R,len[i]);
????????}
????????while(L+1<R){
????????????mid=(L+R)/2;
????????????if(check(mid))
????????????????L=mid;
????????????else R=mid;
????????}
????????printf("%d\n",L);
????}
????return 0;
}
//1007
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
return xx*ff;
}
map<string,string>mp;
string nul,st="START",en="END";
string s1,s2;
char s[3010];
char ch;
int len;
int main(){
//freopen("in","r",stdin);
cin>>s1;
while(1){
cin>>s1;
if(s1==en)
break;
cin>>s2;
mp[s2]=s1;
}
cin>>s1;
getchar();
while(1){
s1="";
gets(s);
len=strlen(s);
if(s[0]=='E'&&s[1]=='N'&&s[2]=='D'&&len==3)
break;
for(int i=0;i<len;i++){
if(s[i]>='a'&&s[i]<='z'){
s1+=s[i];
if(s[i+1]>'z'||s[i+1]<'a'){
if(mp[s1]!=nul)
cout<<mp[s1];
else
cout<<s1;
s1="";
}
}
else
putchar(s[i]);
}
if(s1!=nul)
cout<<s1;
puts("");
}
return 0;
}
//1008
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
const int maxn=25;
int N,a[maxn];
bool isprime[maxn*2];
void get_prime(int n=40){
????memset(isprime,1,sizeof(isprime));
????isprime[0]=isprime[1]=0;
????for(int i=2;i<=n;i++){
????????if(isprime[i])
????????????for(int j=i*i;j<=n;j+=i)
????????????????isprime[j]=0;
????}
}
bool use[maxn];
int ans[maxn];
void dfs(int x){
????if(x==N+1){
????????if(isprime[ans[1]+ans[N]]){
????????????for(int i=1;i<N;i++)
????????????????printf("%d ",ans[i]);
????????????printf("%d\n",ans[N]);
????????}
????????return;
????}
????for(int i=1;i<=N;i++)
????????if(!use[i]&&isprime[i+ans[x-1]]){
????????????ans[x]=i;
????????????use[i]=1;
????????????dfs(x+1);
????????????use[i]=0;
????????}
}
int main(){
????//freopen("in","r",stdin);
????get_prime();
????int cas=1;
????while(scanf("%d",&N)!=EOF){
????????printf("Case %d:\n",cas++);
????????use[1]=1,ans[1]=1;
????????dfs(2);
????????puts("");
????}
????return 0;
}
//1009
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
const int maxn=105,ws_[4]={0,1,0,-1},ad_[4]={1,0,-1,0};
int N,M;
char mp[maxn][maxn];
struct status{
????int x,y,t;
????status(int x=0,int y=0,int t=0){
????????this->x=x,this->y=y,this->t=t;
????}
????bool friend operator<(const status&A,const status&B){
????????return A.t>B.t;
????}
}from[maxn][maxn];
priority_queue<status>pq;
int vis[maxn][maxn];
inline bool out(int x,int y){
????return x<=0||y<=0||x>N||y>M;
}
void bfs(){
????memset(vis,10,sizeof(vis));
????pq.push(status(1,1,0));
????vis[1][1]=0;
????while(!pq.empty()){
????????status s=pq.top();
????????pq.pop();
????????for(int i=0;i<4;i++){
????????????int tx=s.x+ws_[i],ty=s.y+ad_[i],tt=s.t+1;
????????????if(out(tx,ty)||mp[tx][ty]=='X')
????????????????continue;
????????????if(mp[tx][ty]>='1'&&mp[tx][ty]<='9')
????????????????tt+=mp[tx][ty]-'0';
????????????if(tt<vis[tx][ty]){
????????????????vis[tx][ty]=tt;
????????????????pq.push(status(tx,ty,tt));
????????????????from[tx][ty]=s;
????????????}
????????}
????}
}
void dfs(int x,int y){
????if(x==1&&y==1)
????????return;
????status pre=from[x][y];
????dfs(pre.x,pre.y);
????printf("%ds:(%d,%d)->(%d,%d)\n",pre.t+1,pre.x-1,pre.y-1,x-1,y-1);
????if(mp[x][y]>='1'&&mp[x][y]<='9')
????????for(int i=1;i<=mp[x][y]-'0';i++)
????????????printf("%ds:FIGHT AT (%d,%d)\n",pre.t+i+1,x-1,y-1);
}
int main(){
//freopen("in","r",stdin);
????while(scanf("%d%d",&N,&M)!=EOF){
????????for(int i=1;i<=N;i++)
????????????for(int j=1;j<=M;j++)
????????????????mp[i][j]=one();
????????bfs();
????????if(vis[N][M]==vis[0][0])
????????????puts("God please help our poor hero.");
????????else{
????????????printf("It takes %d seconds to reach the target position, let me show you the way.\n",vis[N][M]);
????????????dfs(N,M);
????????}
????????puts("FINISH");
????}
return 0;
}
//1010
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
const int maxn=110,MOD=10000;
struct big{
????int num[200],len;
????big(){
????????memset(num,0,sizeof(num));
????????len=1;
????}
????big friend operator+(const big&A,const big&B){
????????big C;
????????C.len=max(A.len,B.len);
????????for(int i=1;i<=C.len;i++){
????????????C.num[i]+=A.num[i]+B.num[i];
????????????int k=i;
????????????while(C.num[k]>=MOD){
????????????????C.num[k+1]+=C.num[k]/MOD;
????????????????C.num[k]%=MOD;
????????????????k++;
????????????????if(k>C.len)
????????????????????C.len=k;
????????????}
????????}
????????return C;
????}
????big friend operator*(big A,int B){
????????big C;
????????C.len=A.len;
????????for(int i=1;i<=A.len;i++){
????????????C.num[i]+=A.num[i]*B;
????????????int k=i;
????????????while(C.num[k]>=MOD){
????????????????C.num[k+1]+=C.num[k]/MOD;
????????????????C.num[k]%=MOD;
????????????????k++;
????????????????if(k>C.len)
????????????????????C.len=k;
????????????}
????????}
????????return C;
????}
????void print(){
????????printf("%d",num[len]);
????????for(int i=len-1;i>=1;i--)
????????????printf("%04d",num[i]);
????}
}f[maxn][maxn];
int M,N;
int main(){
????//freopen("in","r",stdin);
????//freopen("out","w",stdout);
????int cas=1;
????while(1){
????????M=read(),N=read();
????????if(M+N==0)break;
????????printf("Test #%d:\n",cas++);
????????f[0][0].num[1]=1;
????????for(int i=1;i<=M;i++)
????????????f[i][0]=f[i-1][0]*(M-i+1);
????????for(int i=1;i<=M;i++)
????????????for(int j=1;j<=min(i,N);j++)
????????????????f[i][j]=f[i][j-1]*(N-j+1)+f[i-1][j]*(M-i+1);
????????f[M][N].print();
????????puts("");
????}
????return 0;
}
//1011
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
int N,M,t1,t2;
int cost[110],b[110];
int lin[110],len;
struct edge{
int y,next;
}e[210];
inline void insert(int xx,int yy){
e[++len].next=lin[xx];
lin[xx]=len;
e[len].y=yy;
}
int f[110][110];
void dfs(int x,int fa){
int need=cost[x]/20;
if(cost[x]%20)
need++;
for(int j=M;j>=need;j--)
f[x][j]=b[x];
for(int i=lin[x];i;i=e[i].next){
if(e[i].y==fa)
continue;
dfs(e[i].y,x);
for(int j=M;j>=need;j--)
for(int k=1;k<=M-j;k++)
f[x][j+k]=max(f[x][j+k],f[x][j]+f[e[i].y][k]);
}
}
int main(){
//freopen("in.txt","r",stdin);
while(1){
N=read(),M=read();
if(N==-1&&M==-1)
break;
len=0;
memset(lin,0,sizeof(lin));
for(int i=1;i<=N;i++)
cost[i]=read(),b[i]=read();
for(int i=1;i<N;i++){
t1=read(),t2=read();
insert(t1,t2),insert(t2,t1);
}
if((!M)||(!N)){
printf("0\n");
continue;
}
memset(f,0,sizeof(f));
dfs(1,0);
printf("%d\n",f[1][M]);
}
return 0;
}
//1012
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
const int maxn=80;
int N;
char s[maxn];
int main(){
????//freopen("in","r",stdin);
????for(int _=read();_;_--){
????????gets(s+1);
????????N=strlen(s+1);
????????for(int i=N;i>=1;i--)
????????????printf("%c",s[i]);
????????puts("");
????}
????return 0;
}
//1013
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
int N,M;
bool succ;
void dfs(int x,long long a,long long b){
????if(x==101||succ)return;
????if(N%a||M%b)return;
????if(a==N&&b==M){
????????succ=1;
????????return;
????}
????dfs(x+1,a*x,b);
????dfs(x+1,a,b*x);
????dfs(x+1,a,b);
}
int main(){
????//freopen("in","r",stdin);
????while(scanf("%d%d",&N,&M)!=EOF){
????????if(N>M)swap(N,M);
????????succ=0;
????????dfs(2,1,M);
????????if(!succ){
????????????printf("%d\n",M);
????????????continue;
????????}
????????succ=0;
????????dfs(2,1,1);
????????if(succ)printf("%d\n",M);
????????else printf("%d\n",N);
????}
????return 0;
}
//1014
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
????char ch=getchar();
????while(ch==' '||ch=='\n')
????????ch=getchar();
????return ch;
}
const int maxn=210,INF=1<<30;
int N,A,B,a[maxn];
int q[maxn],head,tail;
int vis[maxn];
void bfs(){
????for(int i=1;i<=N;i++)
????????vis[i]=INF;
????vis[A]=0;
????head=tail=1;
????q[head]=A;
????for(;head<=tail;head++){
????????int tmp=q[head]+a[q[head]];
????????if(tmp<=N&&vis[tmp]>vis[q[head]]+1){
????????????q[++tail]=tmp;
????????????vis[tmp]=vis[q[head]]+1;
????????}
????????tmp=q[head]-a[q[head]];
????????if(tmp>0&&vis[tmp]>vis[q[head]]+1){
????????????q[++tail]=tmp;
????????????vis[tmp]=vis[q[head]]+1;
????????}
????}
????if(vis[B]==INF)
????????puts("-1");
????else
????????printf("%d\n",vis[B]);
}
int main(){
????//freopen("in","r",stdin);
????while(1){
????????N=read();
????????if(!N)break;
????????A=read(),B=read();
????????for(int i=1;i<=N;i++)
????????????a[i]=read();
????????bfs();
????}
????return 0;
}
//1015
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
long long READ(){
long long xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
return xx*ff;
}
char one(){
char ch=getchar();
while(ch==' '||ch=='\n')
ch=getchar();
return ch;
}
const int maxn=25;
int A,N,a[maxn];
bool succ,use[maxn];
bool cmp(const int&x,const int&y){
return x>y;
}
void dfs(int x,int sum,int p){
if(x==4){
????????succ=1;
????????return;
????}
????if(succ)return;
????if(sum==A){
????????dfs(x+1,0,0);
????????return;
????}
????for(int i=p+1;i<=N;i++)
????????if(!use[i]&&a[i]+sum<=A){
????????????use[i]=1;
????????????dfs(x,sum+a[i],i);
????????????use[i]=0;
????????}
}
int main(){
//freopen("in","r",stdin);
for(int _=read();_;_--){
N=read();A=0;
for(int i=1;i<=N;i++)
a[i]=read(),A+=a[i];
if(A%4)
puts("no");
else{
sort(a+1,a+1+N,cmp);
A/=4;succ=0;
dfs(1,0,0);
if(succ)
puts("yes");
else
puts("no");
}
}
return 0;
}
原文：https://www.cnblogs.com/lzhAFO/p/11823196.html