c 统计有几个cool单词，cool的定义就是至少两个字母，每个字母出现的次数都不同。
1 #include<cstdio> 2 #include<cstring> 3 #include<set> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 set<int> s; 7 char a[32]; 8 int b[32]; 9 int test(){ 10 mt(b,0); 11 for(int i=0;a[i];i++){ 12 b[a[i]-'a']++; 13 } 14 s.clear(); 15 int c=0; 16 for(int i=0;i<26;i++){ 17 if(b[i]){ 18 c++; 19 s.insert(b[i]); 20 } 21 } 22 return s.size()==c&&c>1; 23 } 24 int main(){ 25 int n,cas=1; 26 while(~scanf("%d",&n)){ 27 int ans=0; 28 while(n--){ 29 scanf("%s",a); 30 ans+=test(); 31 } 32 printf("Case %d: %d ",cas++,ans); 33 } 34 return 0; 35 }
d 有向图，两个人从1走到n，问花费之和最小。一条边第一次走花费是d，第二次走花费是d+a。
最小费用最大流 ，两个人相当于流量2，原来一条边变为两条，流量都为1，费用一个d，一个d+a，源点连1，流量2，费用0，n连汇点，流量2，费用0.
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 class MaxFlowMinCost { ///最小费用最大流 o(ME) 8 typedef int typef;///流量的类型 9 typedef int typec;///费用的类型 10 static const int ME=10010;///边的个数 11 static const int MV=510;///点的个数 12 queue<int> q; 13 int cur[MV],pre[MV]; 14 bool used[MV],sign[MV]; 15 typef flow; 16 typec cost,dist[MV]; 17 bool spfa(int s,int t) { 18 mt(used,0); 19 mt(sign,0); 20 mt(dist,0); 21 used[s]=sign[s]=true; 22 while(!q.empty()) q.pop(); 23 q.push(s); 24 while(!q.empty()) { 25 int u=q.front(); 26 q.pop(); 27 used[u]=false; 28 for(int i=g.head[u]; ~i; i=g.e[i].next) { 29 if(g.e[i].flow<1) continue; 30 int v=g.e[i].v; 31 typec c=g.e[i].cost; 32 if(!sign[v]||dist[v]>dist[u]+c) { 33 dist[v]=dist[u]+c; 34 sign[v]=true; 35 pre[v]=u; 36 cur[v]=i; 37 if(used[v]) continue; 38 used[v]=true; 39 q.push(v); 40 } 41 } 42 } 43 return sign[t]; 44 } 45 struct G { 46 struct E { 47 int v,next; 48 typef flow; 49 typec cost; 50 } e[ME]; 51 int le,head[MV]; 52 void init() { 53 le=0; 54 mt(head,-1); 55 } 56 void add(int u,int v,typef flow,typec cost) { 57 e[le].v=v; 58 e[le].flow=flow; 59 e[le].cost=cost; 60 e[le].next=head[u]; 61 head[u]=le++; 62 } 63 } g; 64 public: 65 void init() { 66 g.init(); 67 } 68 void add(int u,int v,typef flow,typec cost) { 69 g.add(u,v,flow,cost); 70 g.add(v,u,0,-cost); 71 } 72 void solve(int s,int t) { 73 flow=cost=0; 74 while(spfa(s,t)) { 75 int temp=t; 76 typef now=inf; 77 while(temp!=s) { 78 now=min(now,g.e[cur[temp]].flow); 79 temp=pre[temp]; 80 } 81 flow+=now; 82 temp=t; 83 while(temp!=s) { 84 int id=cur[temp]; 85 cost+=now*g.e[id].cost; 86 g.e[id].flow-=now; 87 g.e[id^1].flow+=now; 88 temp=pre[temp]; 89 } 90 } 91 } 92 typef getflow() { 93 return flow; 94 } 95 typec getcost() { 96 return cost; 97 } 98 }g; 99 int main(){ 100 int n,m,u,v,d,a,cas=1; 101 while(~scanf("%d%d",&n,&m)){ 102 g.init(); 103 while(m--){ 104 scanf("%d%d%d%d",&u,&v,&d,&a); 105 g.add(u,v,1,d); 106 g.add(u,v,1,d+a); 107 } 108 int s=0,t=n+1; 109 g.add(s,1,2,0); 110 g.add(n,t,2,0); 111 g.solve(s,t); 112 printf("Case %d: %d ",cas++,g.getcost()); 113 } 114 return 0; 115 }
e 计算led灯的花费，根据输入算时间差乘上这段时间内比分所需的led灯数量，模拟一下
1 #include<cstdio> 2 #include<cstring> 3 const int M=16; 4 char a[M],b[M]; 5 char s[]="START"; 6 char e[]="END"; 7 int get_val(char a,char b){ 8 return (a-'0')*10+(b-'0'); 9 } 10 int get_time(){ 11 return get_val(b[0],b[1])*3600+get_val(b[3],b[4])*60+get_val(b[6],b[7]); 12 } 13 int c[]={6,2,5,5,4,5,6,3,7,6}; 14 int get_cost(int x){ 15 if(!x) return 6; 16 int res=0; 17 while(x){ 18 res+=c[x%10]; 19 x/=10; 20 } 21 return res; 22 } 23 int main(){ 24 int x,pre,now,ans,home,guest,cas=1; 25 while(~scanf("%s%s",a,b)){ 26 pre=now; 27 now=get_time(); 28 if(!strcmp(a,s)){ 29 ans=home=guest=0; 30 continue; 31 } 32 ans+=(get_cost(home)+get_cost(guest))*(now-pre); 33 if(!strcmp(a,e)){ 34 printf("Case %d: %d ",cas++,ans); 35 continue; 36 } 37 scanf("%s%d",a,&x); 38 if(a[0]=='h'){ 39 home+=x; 40 } 41 else{ 42 guest+=x; 43 } 44 } 45 return 0; 46 }
h 机器人有3种操作，左转右转前进一步，LRF，如果是？则可能是三种中任意一种，问操作完后x坐标和y坐标可能达到的最大值最小值分别是多少。
dp[i][j][k] 表示第i个操作后，求j方向，当前在k方向的最值。 0123表示东北西南。j=0求x最大值，j=1求y最大值，j=2求x最小值，j=3求y最小值。
k是指当前方向。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int inf=0x3f3f3f3f; 6 const int M=1024; 7 int dp[M][4][4]; 8 char a[M]; 9 int turn_left(int x){ 10 return (x+1)%4; 11 } 12 int turn_right(int x){ 13 return (x+4-1)%4; 14 } 15 void update_turn(int i,int j,int k,int next){ 16 if(j<2){ 17 dp[i+1][j][next]=max(dp[i+1][j][next],dp[i][j][k]); 18 } 19 else{ 20 dp[i+1][j][next]=min(dp[i+1][j][next],dp[i][j][k]); 21 } 22 } 23 void update_left(int i,int j,int k){ 24 int next=turn_left(k); 25 update_turn(i,j,k,next); 26 } 27 void update_right(int i,int j,int k){ 28 int next=turn_right(k); 29 update_turn(i,j,k,next); 30 } 31 int get_cost(int x,int y){ 32 if(x==y) return 1; 33 if((x+y)&1) return 0; 34 return -1; 35 } 36 void update_front(int i,int j,int k){ 37 if(j<2){ 38 dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]+get_cost(j,k)); 39 } 40 else{ 41 dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]-get_cost(j,k)); 42 } 43 } 44 int la; 45 int get_min(int j){ 46 int res=inf; 47 for(int k=0;k<4;k++){ 48 res=min(res,dp[la][j][k]); 49 } 50 return res; 51 } 52 int get_max(int j){ 53 int res=-inf; 54 for(int k=0;k<4;k++){ 55 res=max(res,dp[la][j][k]); 56 } 57 return res; 58 } 59 int main(){ 60 int cas=1; 61 while(~scanf("%s",a)){ 62 la=strlen(a); 63 for(int i=0;i<=la;i++){ 64 for(int j=0;j<4;j++){ 65 for(int k=0;k<4;k++){ 66 dp[i][j][k]=inf; 67 if(j<2){ 68 dp[i][j][k]=-inf; 69 } 70 } 71 } 72 } 73 for(int j=0;j<4;j++){ 74 dp[0][j][0]=0; 75 } 76 for(int i=0;i<la;i++){ 77 for(int j=0;j<4;j++){ 78 for(int k=0;k<4;k++){ 79 if(dp[i][j][k]==inf||dp[i][j][k]==-inf) continue; 80 if(a[i]=='L'){ 81 update_left(i,j,k); 82 } 83 else if(a[i]=='R'){ 84 update_right(i,j,k); 85 } 86 else if(a[i]=='F'){ 87 update_front(i,j,k); 88 } 89 else{ 90 update_left(i,j,k); 91 update_right(i,j,k); 92 update_front(i,j,k); 93 } 94 } 95 } 96 } 97 printf("Case %d: %d %d %d %d ",cas++,get_min(2),get_max(0),get_min(3),get_max(1)); 98 } 99 return 0; 100 }
i 纯bfs题
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int M=16; 7 struct Q{ 8 int x,y,step; 9 }A,B,C,pre,now; 10 queue<Q> q; 11 bool vis[M][M]; 12 int dx[]={-1,0,1,1,1,0,-1,-1}; 13 int dy[]={-1,-1,-1,0,1,1,1,0}; 14 bool inside(int x,int y){ 15 return x>=1&&x<=8&&y>=1&&y<=8; 16 } 17 int bfs(){ 18 mt(vis,0); 19 vis[A.x][A.y]=true; 20 A.step=0; 21 while(!q.empty()) q.pop(); 22 q.push(A); 23 while(!q.empty()){ 24 pre=q.front(); 25 q.pop(); 26 if(pre.x==B.x&&pre.y==B.y) return pre.step; 27 if(pre.x==C.x&&pre.y==C.y) continue; 28 for(int i=0;i<8;i++){ 29 int tx=pre.x+dx[i]; 30 int ty=pre.y+dy[i]; 31 if(!inside(tx,ty)||vis[tx][ty]) continue; 32 vis[tx][ty]=true; 33 now.x=tx; 34 now.y=ty; 35 now.step=pre.step+1; 36 q.push(now); 37 } 38 } 39 return -1; 40 } 41 int main(){ 42 int cas=1; 43 while(~scanf("%d%d%d%d%d%d",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y)){ 44 printf("Case %d: %d ",cas++,bfs()); 45 } 46 return 0; 47 }
k 暴力就2的10次方，所以dfs是可以接受的，注意确定赢了就不要在继续射了。
1 #include<cstdio> 2 #include<cstring> 3 #define mt(a,b) memset(a,b,sizeof(a)) 4 double a[16],b[16]; 5 char c[16]; 6 double mat[8][8]; 7 void dfs(int A,int B,int ca,int cb,double p){ 8 if(ca==5&&cb==5){ 9 mat[A][B]+=p; 10 return ; 11 } 12 if(A>B){ 13 if(A-B>5-cb){ 14 mat[A][B]+=p; 15 return ; 16 } 17 } 18 if(B>A){ 19 if(B-A>5-ca){ 20 mat[A][B]+=p; 21 return ; 22 } 23 } 24 if(ca==cb){ 25 dfs(A+1,B,ca+1,cb,p*a[ca+1]); 26 dfs(A,B,ca+1,cb,p*(1-a[ca+1])); 27 } 28 else{ 29 dfs(A,B+1,ca,cb+1,p*b[cb+1]); 30 dfs(A,B,ca,cb+1,p*(1-b[cb+1])); 31 } 32 } 33 int main(){ 34 int cas=1; 35 while(~scanf("%lf",&a[1])){ 36 for(int i=2;i<=5;i++){ 37 scanf("%lf",&a[i]); 38 } 39 for(int i=1;i<=5;i++){ 40 scanf("%lf",&b[i]); 41 } 42 scanf("%s",c); 43 mt(mat,0); 44 dfs(0,0,0,0,1); 45 printf("Case %d: %.2f%% ",cas++,mat[c[0]-'0'][c[2]-'0']*100); 46 } 47 return 0; 48 }
end