您的位置: 首页  >  IT文章  >  Codeforces 699

Codeforces 699

分类: IT文章 • 2022-05-27 09:30:48

Problem A Launch of Collider

题目大意

　　在x轴上有n个点，坐标均为偶数。每个点或向左移动或向右移动，每秒移动距离为1。

　　使所有点同时开始移动，求最早有点相遇的时间或无解。

解题分析

　　对于每一个向右移动的点，找右边最近的一个向左的点。向左移动同理。

　　正反扫两遍即可。

参考程序

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 #pragma comment(linker,"/STACK:102400000,102400000")
15 using namespace std;
16 
17 #define         N             200008             
18 #define             V             1008
19 #define        E            60008    
20 #define        lson                l,m,rt<<1
21 #define             rson                m,r+1,rt<<1|1
22 #define        clr(x,v)            memset(x,v,sizeof(x));
23 #define        LL            long long 
24 //#define    debug
25 const int    mo        =        1000000007;
26 const int     inf        =        0x3f3f3f3f;
27 const int     INF       =        2000000000;
28 /**************************************************************************/ 
29 int n;
30 char s[N];
31 int a[N],ans[N];
32 int main(){
33     scanf("%d",&n);
34     scanf("%s",s+1);
35     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
36     int x=-1;
37     for (int i=1;i<=n;i++)
38         if (s[i]=='R') x=a[i];
39         else
40         {
41             if (x==-1) ans[i]=INF; 
42             else ans[i]=(a[i]-x)/2;
43         }
44     x=-1;
45     for (int i=n;i>=1;i--)
46         if (s[i]=='L') x=a[i];
47         else
48         {
49             if (x==-1) ans[i]=INF; 
50             else ans[i]=(x-a[i])/2;
51         }
52     int res=INF;
53     for (int i=1;i<=n;i++) res=min(res,ans[i]);
54     printf("%d
",res==INF ? -1 : res);
55 
56     #ifdef debug 
57     system("pause");
58     #endif
59 }
60
View Code

Problem B One Bomb

题目大意

　　有一个n*m的矩形，每一个格子为空地或者为墙壁。 （n,m<=1000）

　　现在要某点放置一颗炸弹，炸掉所有的墙壁。炸弹的爆炸范围为该点的上下左右两条直线。

　　给出一种方案或无解。

解题分析

　　记录一下每行的墙壁数，每列的墙壁数。

　　枚举每个点是否放置炸弹即可。

参考程序

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 #pragma comment(linker,"/STACK:102400000,102400000")
15 using namespace std;
16 
17 #define             N             1000008             
18 #define             V             1008
19 #define        E            60008    
20 #define        lson                l,m,rt<<1
21 #define             rson                m,r+1,rt<<1|1
22 #define        clr(x,v)            memset(x,v,sizeof(x));
23 #define        LL            long long 
24 //#define     debug
25 const int    mo    =    1000000007;
26 const int     inf =    0x3f3f3f3f;
27 const int     INF =    2000000000;
28 /**************************************************************************/ 
29 
30 int n,m,num;
31 int x[V],y[V],mp[V][V];
32 int main(){
33     scanf("%d%d",&n,&m);
34     num=0;
35     for (int i=1;i<=n;i++){
36         char s[V];
37         scanf("%s",s+1);
38         for (int j=1;j<=m;j++)
39             if (s[j]=='*'){
40                 x[i]++;
41                 y[j]++;
42                 mp[i][j]=1;
43                 num++;
44             }
45     }
46     int ok=0;
47     int tx,ty;
48     for (tx=1;tx<=n;tx++){
49         for (ty=1;ty<=m;ty++){
50             int now;
51             if (mp[tx][ty]) now=x[tx]+y[ty]-1; else now=x[tx]+y[ty];
52             if (now==num){
53                 ok=1;
54                 break;
55             }
56         }
57         if (ok) break;
58     }
59     if (ok) printf("YES
%d %d
",tx,ty); else printf("NO
");
60 
61     #ifdef debug
62     system("pause");
63     #endif
64 }
View Code

Problem C Vacations

题目大意

　　一个小朋友每天可以选择休息或者网上打比赛或者去体育馆玩，但不能两天都刷题或者都玩耍。

　　给定每天是否网上有比赛，体育馆是否开。

　　问小朋友n天内最少需要休息几天。

解题分析

　　dp[i][0~2] 表示第i天干某事的最少休息天数。

　　分情况讨论转移。

参考程序

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 #pragma comment(linker,"/STACK:102400000,102400000")
15 using namespace std;
16 
17 #define         N             100008             
18 #define         V             1008
19 #define        E            60008    
20 #define        lson                l,m,rt<<1
21 #define             rson                m,r+1,rt<<1|1
22 #define        clr(x,v)            memset(x,v,sizeof(x));
23 #define        LL            long long 
24 //#define     debug
25 const int    mo    =    1000000007;
26 const int     inf =    0x3f3f3f3f;
27 const int     INF =    2000000000;
28 /**************************************************************************/ 
29 int min(int x,int y,int z){
30     if (x<=y && x<=z) return x;
31     if (y<=x && y<=z) return y;
32     if (z<=x && z<=y) return z;
33 }
34 int dp[N][3],ok[N][3];
35 int n;
36 int main(){
37     scanf("%d",&n);
38     for (int i=1;i<=n;i++){
39         int x;
40         scanf("%d",&x);
41         if (x==0){
42             ok[i][0]=1;
43             ok[i][1]=0;
44             ok[i][2]=0;
45         }
46         if (x==1){
47             ok[i][0]=1;
48             ok[i][1]=0;
49             ok[i][2]=1;
50         }
51         if (x==2){
52             ok[i][0]=1;
53             ok[i][1]=1;
54             ok[i][2]=0;
55         }
56         if (x==3){
57             ok[i][0]=1;
58             ok[i][1]=1;
59             ok[i][2]=1;
60         }
61     }
62     for (int i=1;i<=n;i++){
63         if (ok[i][0]){
64             dp[i][0]=min(dp[i-1][0],dp[i-1][1],dp[i-1][2])+1;
65         }
66         else dp[i][0]=INF;
67         if (ok[i][1]){
68             dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
69         }
70         else dp[i][1]=INF;
71         if (ok[i][2]){
72             dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
73         }
74         else dp[i][2]=INF;
75     }
76     printf("%d
",min(dp[n][0],dp[n][1],dp[n][2]));
77     #ifdef debug
78     system("pause");
79     #endif
80 }
View Code

Problem D Fix a tree

题目大意

　　有n个点，给定一个序列f[i]表示i号点的父亲为f[i]。

　　要求改变最少的f[i]，使得这n个点形成一棵树。

解题分析

　　从每个为搜索过的点开始沿着f[i]开始搜索，如果与之前的点形成了环，说明这些点形成了一个连通块，若形成的环不是自环，则环中的某个点需要改变f[i]，从而形成一棵树。

　　处理出所有的联通块后，假设有x个。

　　若其中的某个连通块的有自环j，则需改变x-1次，将其他连通块中的某个环中点f[i]改为j。

　　若没有自环，则需改变x次，将某个环中点改为自环，其他同上处理。

参考程序

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 #pragma comment(linker,"/STACK:102400000,102400000")
15 using namespace std;
16 
17 #define             N             200008
18 #define             V             200008             
19 #define        E            60008    
20 #define        lson                    l,m,rt<<1
21 #define             rson                m,r+1,rt<<1|1
22 #define        clr(x,v)            memset(x,v,sizeof(x));
23 #define        LL            long long 
24 //#define     debug
25 const int    mo    =    1000000007;
26 const int     inf =    0x3f3f3f3f;
27 const int     INF =    2000000000;
28 /**************************************************************************/ 
29 int n,tmp,lx=0;
30 int f[V],dfn[V],instack[V];
31 int ans[V];
32 void dfs(int x){
33     if (dfn[x]){
34         if (instack[x]==lx) ans[++ans[0]]=x;
35         return;
36     }
37     instack[x]=lx;
38     dfn[x]=++tmp;
39     dfs(f[x]);
40 }
41 int main(){
42     scanf("%d",&n);
43     for (int i=1;i<=n;i++) scanf("%d",&f[i]);
44 
45     for (int i=1;i<=n;i++){
46         lx++;
47         if (!dfn[i]) dfs(i);
48     }
49     lx=-1;
50     for (int i=1;i<=ans[0];i++)
51         if (f[ans[i]]==ans[i]) lx=ans[i];
52     if (lx==-1){
53         printf("%d
",ans[0]);
54         for (int i=1;i<ans[0];i++)
55             f[ans[i]]=ans[i+1];
56         f[ans[ans[0]]]=ans[ans[0]];
57     }
58     else
59     {
60         printf("%d
",ans[0]-1);
61         for (int i=1;i<=ans[0];i++)
62             f[ans[i]]=lx;
63     }
64     for (int i=1;i<=n;i++) printf("%d%c",f[i],i==n?'
':' ');
65 
66     #ifdef debug
67     system("pause");
68     #endif
69 }
View Code

 

相关推荐