A – Fox And Snake
模拟。
代码如下：
#include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>using namespace std;#define LL __int64#define pi acos(-1.0)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;int main(){int n, m, i, j;while(scanf("%d%d",&n,&m)!=EOF){for(i=0;i<n;i++){if(i%2==0){for(j=0;j<m;j++){printf("#");}puts("");}else{if((i+1)%4==0){printf("#");for(j=1;j<m;j++){printf(".");}puts("");}else{for(j=0;j<m-1;j++){printf(".");}printf("#\n");}}}}return 0;}B – Fox And Two Dots
dfs判环。比赛的时候的flag变量定义了一个全局又定义了一个主函数里的flag，然后调了半小时才找到错误原因。。。跪了。。。
代码如下：#include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>using namespace std;#define LL __int64#define pi acos(-1.0)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;char s[100][100];int vis[100][100], n, m, d[100][100], flag;int jx[]= {0,0,1,-1};int jy[]= {1,-1,0,0};void dfs(int x, int y, char c, int ans){int i, j, a, b;if(flag) return ;for(i=0; i<4; i++) {a=x+jx[i];b=y+jy[i];if(a>=0&&a<n&&b>=0&&b<m&&s[a][b]==c) {if(!vis[a][b]) {d[a][b]=ans+1;vis[a][b]=1;dfs(a,b,c,ans+1);} else if(abs(d[a][b]-d[x][y])>=3) {flag=1;return ;}}}if(flag) return ;}int main(){int i, j, ans;while(scanf("%d%d",&n,&m)!=EOF) {for(i=0; i<n; i++) {scanf("%s",s[i]);}flag=0;for(i=0; i<n; i++) {for(j=0; j<m; j++) {memset(vis,0,sizeof(vis));memset(d,0,sizeof(d));vis[i][j]=1;dfs(i,j,s[i][j],0);if(flag)break;}if(flag) break;}if(flag) printf("Yes\n");else printf("No\n");}return 0;}C – Fox And Names
拓扑排序裸题。。CF居然也出模板题了。。
代码如下：
#include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>using namespace std;#define LL __int64#define pi acos(-1.0)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;char s[200][200];int a[200], head[200], cnt, d[200], c[200], tot;struct node{int u, v, next;}edge[100000];void add(int u, int v){edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;}void topo(){int i, j;queue<int>q;for(i=0;i<26;i++){if(!d[i]){q.push(i);}}while(!q.empty()){int u=q.front();q.pop();c[tot++]=u;d[u]–;for(i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(d[v]!=-1){d[v]–;if(d[v]==0)q.push(v);}}}if(tot<26) puts("Impossible");else {for(i=0;i<26;i++){printf("%c",c[i]+'a');}}}int main(){int n, i, j, len1, len2, flag, f;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++){scanf("%s",s[i]);}memset(a,0,sizeof(a));memset(head,-1,sizeof(head));cnt=0;memset(d,0,sizeof(d));f=0;for(i=1;i<n;i++){len1=strlen(s[i-1]);len2=strlen(s[i]);flag=0;for(j=0;j<len1&&j<len2;j++){if(s[i][j]!=s[i-1][j]){flag=1;add(s[i-1][j]-'a',s[i][j]-'a');d[s[i][j]-'a']++;break;}}if(!flag){if(len1>len2){f=1;break;}}}if(f) puts("Impossible");else{tot=0;topo();}}return 0;}D – Fox And Jumping
暴力。。。要求的是花费最少的集合使得该集合的gcd为1.由于数据只有300，所有的gcd可能出现的情况也不会很多，，所以直接保存所有出现的gcd，然后暴力DP即可。
代码如下：
#include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>using namespace std;#define LL __int64#define pi acos(-1.0)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;map<LL,LL>dp;struct node{LL l, c;}fei[400];LL gcd(LL x, LL y){return y==0?x:gcd(y,x%y);}int main(){int n, i, j;scanf("%d",&n);for(i=0;i<n;i++){scanf("%I64d",&fei[i].l);}for(i=0;i<n;i++){scanf("%I64d",&fei[i].c);}dp[0]=0;map<LL,LL>::iterator it;for(i=0;i<n;i++){for(it=dp.begin();it!=dp.end();it++){LL tmp=gcd(fei[i].l,(*it).first);if(dp.find(tmp)==dp.end()){dp[tmp]=fei[i].c+(*it).second;}else{dp[tmp]=min(dp[tmp],fei[i].c+(*it).second);}}}if(dp.find(1)==dp.end()){printf("-1\n");}else{printf("%I64d\n",dp[1]);}return 0;}
累死累活不说，走马观花反而少了真实体验，
