ECUST_Algorithm_2019_3
2024-10-07 18:07:05
简要题意及解析
1001
给出一个\(n\times m\)连连看的局面，下面有\(q\)次询问：两个位置的块能否消去，即两个位置的连线是否能少于两次转折，回答\(YES/NO\)。与一般的连连看不同之处在于，连线不能从外围绕过
先判断两个位置是否是空地，是否是一种颜色，然后从其中一个位置开始\(dfs/bfs\)，由于限制条件和转折次数有关，因此要记录转折次数。搜索的时候要先采用转折少的方案，不然复杂度不对。
时间复杂度\(O(Tnmq)\)
\(T\)为数据组数，\(n,m,q\)如题意。
1002
在一个\(m\times n\)的矩形迷宫中，用空地、障碍和楼梯，楼梯有两个方向——左右和上下，而且每过\(1\)分钟换一次方向，登上楼梯并经过楼梯只需要\(1\)分钟，不能再楼梯上停留，求从起点到终点最短要多长时间。
与一般的迷宫问题唯一的不同点就是这个楼梯。楼梯的方向其实很好处理，当你处于一个状态\((x,y,t)\)，在位置\((x,y)\)时间为\(t\)时，你可以判断\(t\)的奇偶求出某个楼梯的方向。想明白了这个，就可以\(dfs/bfs\)了，求最短距离最好还是用\(bfs\)，我不知道为什么脑抽写了个\(dfs\)。
时间复杂度\(O(Tnm)\)
\(T\)是数据组数，\(n,m\)如题意。
1003
给出\(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\)是序列长度。
1004
有\(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\)为数字数量。
1005
给出一些单词，你可以使用这个单词把它的首字母变成末字母，问你能否吧\(B\)变成\(M\)。
本质上是有向图连通性，怎么写都行\(dfs/bfs/floyd\)
时间复杂度\(O(TL)\)
\(T\)为数据组数，\(L\)为所有单词长度和。
1006
给出\(n\)个字符串，你要找到最长的一个串使得这个串或者他的反转串在这\(n\)个串中都出现过。求这个长度。
很暴力的一道题。先枚举\(/\)二分这个长度\(L\)，然后从第一个串中枚举长度为\(L\)的串，判断它或它的反转串在剩下\(n-1\)个串中是否全部出现，如果全部出现，则答案\(L\)可行。
时间复杂度\(O(Tn^2L^2logL)\)
\(T\)为数据组数，\(n\)字符串数量，\(L\)为字符串长度。
1007
给出很多组火星单词和对应的地球单词，然后给出一段火星文，把这段火星文中的火星单词全部替换为地球单词输出，如果不能识别某个火星单词，不做替换即可。
输入比较烦，注意是否读入了空行。
其实就是把火星文中的单词提取出来，尝试替换即可，但是这题不给数据范围，还是考虑一些高效的方法。如何判断一个单词是否出现过，可以用字符串\(Hash\)，也可以用\(STL\)的\(map<string,string>\)。不知道为啥我的字符串\(Hash\)挂了，不得不用\(map\)。
直接用\(map\)存好火星单词和地球单词的对应关系。然后从火星文里每次找一个单词，尝试替换。
时间复杂度\(O(TmLlogn)\)
\(T\)为数据组数，\(n\)为单词数量，\(L\)为字符串总长度，\(m\)为文章数量。
1008
素数环问题。求出字典序最小的\(1\)到\(n\)的圆排列，要求相邻两数之和为质数。
\(dfs+\)回溯，第\(i\)层枚举第\(i\)个位置填什么，检验它与前数之和是否为质数。注意枚举了最后一个数之后还要检验最后一个数和第一个数。
时间复杂度\(O(Tn^n)\)，剪枝很有效，实际复杂度远小于上界。
\(T\)为数据组数，\(n\)为数字数量。
1009
又是一个类似迷宫问题，不同点在于有些地方有怪物，打怪要消耗一定时间。此题需要输出方案。
求最短时间最好用\(bfs\)（我怎么又写了\(dfs\)）。搜索的同时记录前驱位置，最后用这个前驱数组就可可以找到最优方案的路径了。
时间复杂度\(O(Tnm)\)
\(T\)为数据组数，\(n,m\)为地图长宽。
1010
门票\(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\)如题意。
1011
一\(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\)同题意。
1012
给出一个字符串，输出反转串。
没啥好说的。
时间复杂度\(O(Tn)\)
\(T\)为数据组数，\(n\)为字符串长度。
1013
在一个比赛中，有\(1\)号到\(100\)号葡萄给两个选手争抢，选手得分为抢到的葡萄编号之积。给出两个选手的得分，保证得分不同，低分选手会质疑高分选手说谎，假定低分选手不说谎(The player with the lower score is presumed to have told the truth)。你要判断高分选手是否说谎，如果说谎，输出低分选手分数，否则输出高分选手分数。
直接\(dfs\)搜索，每个编号有三种情况，两人都没拿或其中一个人拿。剪剪枝就好了。不过，其实低分选手还是可能说谎的，如果低分选手说谎，输出高分选手分数(与题目描述相悖，但是只有这样能过)。
时间复杂度\(O(3^{100}T)\)，实际复杂度远低于上界。
\(T\)为数据组数。
1014
有一个\(n\)层电梯，从第\(i\)层可以向上或向下\(a[i]\)层，不能到达不存在的楼层。求从第\(A\)层到第\(B\)层最少要几次，不能到达则输出\(-1\)
从第\(A\)层开始\(bfs\)，记录当前位置和所用次数，第一次到达第\(B\)层即为答案。
时间复杂度\(O(Tn)\)
\(T\)为数据组数，\(n\)为层数。
1015
给出\(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;
}
最新文章
- 自动布局报错（两条连线冲突）：Unable to simultaneously satisfy constraints
- gulp教程之gulp-htmlmin
- 前端基础 JavaScript~~~ 数据处理 奇技淫巧！！！！！！
- iOS开发之AFN的基本使用
- 关于页面 reflow 和 repaint
- android中掩码的使用
- Shell脚本中判断输入参数个数的方法投稿：junjie 字体：[增加 减小] 类型：转载
- 【深度学习系列2】Mariana DNN多GPU数据并行框架
- CentOS Hadoop安装配置详细
- Android 的Camera架构介绍
- Activiti常见问题解决
- Unix/Linux僵尸进程
- Search an Element in an array
- 将Python 程序打包成 .exe格式入门
- the python challenge闯关记录(0-8)
- Linux 下配置 nginx + 两个 tomcat 的负载均衡
- [matlab] 10.最小覆盖
- 16-使用Selenium模拟浏览器抓取淘宝商品美食信息
- python 字符串的I/O 操作
- OpenGL中的像素包装理解