首页 > 代码库 > 【Mutual Training for Wannafly Union #1 】

【Mutual Training for Wannafly Union #1 】

A.Phillip and Trains

CodeForces 586D

题意:过隧道,每次人可以先向前一格,然后向上或向下或不动,然后车都向左2格。问能否到达隧道终点。

题解:dp,一开始s所在列如果前方为‘.‘则dp[i]=1。r[i]代表上一次的dp[i]值。

如果该行当前可行,那么它就可以更新它上下两行(如果有),必须用r[i]去更新。

再判断每行在当前时间是否会发生撞车:看看位置 i+t*2,i+t*2+1,i+t*2+2 是否有车。

#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define ll long longusing namespace std;int t,n,k,dp[5],r[5];char s[4][101];bool ck(int i,int j){//j行i列不可行	return i<n&&s[j][i]!=‘.‘;}int main() {	scanf("%d",&t);	while(t--){		scanf("%d%d",&n,&k);		for(int i=1;i<=3;i++){			scanf("%s",s[i]);			r[i]=dp[i]=s[i][1]==‘.‘&&s[i][0]==‘s‘;		}		for(int t=0,i=1;i<n;i++,t++){			for(int j=1;j<=3;j++)if(!ck(i+t*2,j)){				dp[j+1]=max(r[j],dp[j+1]);				dp[j-1]=max(r[j],dp[j-1]);			}			for(int j=1;j<=3;r[j]=dp[j],j++)			if(ck(i+t*2,j)||ck(i+t*2+1,j)||ck(i+t*2+2,j))				dp[j]=0;		}		if(dp[1]||dp[2]||dp[3])puts("YES");		else puts("NO");	}	return 0;}

B - Mr. Kitayuta‘s Gift

CodeForces 505A 

题意:插入一个字符是否能使字符串变成回文串。

题解:长度10,可以暴力枚举所有位置所有字母。我是用O(n)的算法。代码写得比较奇怪。

#include<cstdio>#include<cstring>char s[15];int main(){    scanf("%s",s);    int len=strlen(s),i=0,j;    for(;i<len/2&&s[i]==s[len-i-1];i++);    if(s[i]!=s[len-i-1]){//如果有不同的        for(j=i;j<len/2&&s[j]==s[len-j-2];j++);        //尝试在i前面插入一个s[len-i-1]后是否变成回文        if(j==len/2) printf("%.*s%c%s",i,s,s[len-i-1],s+i);        else{//尝试在len-i-1后面插入一个s[i]是否变成回文            for(j=i+1;j<=len/2&&s[j]==s[len-j];j++);            if(j>len/2)                printf("%.*s%c%s",len-i,s,s[i],s+len-i);            else printf("NA");        }    }else printf("%.*s%c%s",len/2,s,s[len/2],s+len/2);    //本身是回文,只要中间插入一个s[len/s]    return 0;}    

D - Vasya and Chess

 CodeForces 493D

题意:n*n的棋盘,白棋先动,可以走没走过的位置或吃黑棋,八方向。如果最后谁先不能走就输了。求白棋能否胜利,若能输出她的第一步。

题解:如果n是奇数,白棋走了,黑棋对称着走就可以了。所以黑棋必胜。n是偶数,白棋右走一步后,相当于奇数棋盘的后手了。

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n;int main(){    scanf("%d",&n);    if(n%2){        printf("black");    }else        printf("white\n1 2");    return 0;}

F - Guess a number!

CodeForces 416A

题意:四种猜数字方式和两种回答:>=/<=/>/< d Y/N ,给出多个这样的问答,求任意一个符合条件的数字。

题解:二分,改变l的条件是有‘>‘,回答是Y,或者有<回答是N,可以异或一下。然后是开区间还是闭区间,就看是否有‘=‘,回答是Y,或者没有‘=‘,回答是N,也可以异或一下。注意l和r的初始值。

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define inf 2000000000char s[10];int n,ans,d,l=-inf,r=inf;void work(int i,int j){    if(i)l=max(l,d+j);    else r=min(r,d-j);}int main(){    scanf("%d",&n);    while(n--){        scanf("%s %d %c",s,&d,&s[2]);        work((s[0]==‘>‘)^(s[2]==‘N‘),(s[1]==‘=‘)^(s[2]==‘Y‘));        if(l>r)ans=-1;    }    if(ans==-1)printf("Impossible");    else printf("%d",l);    return 0;}

 

【Mutual Training for Wannafly Union #1 】