首页 > 代码库 > 记次浙大月赛 134 - ZOJ Monthly, June 2014

记次浙大月赛 134 - ZOJ Monthly, June 2014

2024-07-06 21:13:05   226人阅读

链接

虽做出的很少，也记录下来，留着以后来补。。浙大题目质量还是很高的

B

并查集的一些操作，同类和不同类我是根据到根节点距离的奇偶判断的，删点是直接新加一个点，记得福大月赛也做过类似的，并差集的这类关系题目还是比较常见的，有空深究一下。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 600010
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 int fa[N],res[N],mp[N];
18 int dis[N];
19 int find(int x)
20 {
21     if(fa[x]!=x)
22     {
23         int ro = find(fa[x]);
24         dis[x]+=dis[fa[x]];
25         return fa[x] = ro;
26     }
27     else
28     return x;
29 }
30 int main()
31 {
32     int n,m,i;
33     char s[10];
34     while(scanf("%d%d",&n,&m)!=EOF)
35     {
36         for(i = 1; i <= n+m; i++)
37         {
38             fa[i] = i;
39             res[i] = 1;
40             mp[i] = i;
41             dis[i] = 0;
42         }
43         int g = n+1;
44         while(m--)
45         {
46             int x,y;
47             scanf("%s",s);
48             if(s[0]==‘L‘)
49             {
50                 scanf("%d%d",&x,&y);
51                 x = mp[x];
52                 y = mp[y];
53                 int tx = find(x);
54                 int ty = find(y);
55                 if(tx!=ty)
56                 {
57                     //cout<<x<<" "<<y<<" "<<tx<<" "<<ty<<endl;
58                     fa[tx] = ty;
59                     res[ty]+=res[tx];
60                     dis[x] = dis[y]+1;
61                 }
62             }
63             else if(s[0]==‘Q‘)
64             {
65                 scanf("%d%d",&x,&y);
66                 x = mp[x];
67                 y = mp[y];
68                 int tx = find(x);
69                 int ty = find(y);
70                 if(tx!=ty)
71                 {
72                     printf("Unknown\n");
73                     continue;
74                 }
75                 if((dis[x]-dis[y])%2==0)
76                 printf("Same\n");
77                 else
78                 printf("Different\n");
79             }
80             else if(s[0]==‘S‘)
81             {
82                 scanf("%d",&x);
83                 x = mp[x];
84                 int tx = find(x);
85                 printf("%d\n",res[tx]);
86             }
87             else
88             {
89                 scanf("%d",&x);
90                 int xx = mp[x];
91                 int tx = find(xx);
92                 res[tx]-=1;
93                 mp[x] = ++g;
94             }
95         }
96     }
97     return 0;
98 }
View Code

 

C

离散化一下，枚举所有值所在的区间段，从左到右走一遍，采用边删边走的形式。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 #include<map>
11 using namespace std;
12 #define N 100010
13 #define LL long long
14 #define INF 0xfffffff
15 const double eps = 1e-8;
16 const double pi = acos(-1.0);
17 const double inf = ~0u>>2;
18 map<int,int>f;
19 vector<int>ed[N];
20 vector<int>dd[N];
21 int c[N];
22 int main()
23 {
24     int n,k,i,j;
25     while(scanf("%d%d",&n,&k)!=EOF)
26     {
27         f.clear();
28         int g = 0;
29         for(i = 1; i <= n; i++)
30         {
31             ed[i].clear();
32             dd[i].clear();
33         }
34         for(i = 1; i <=n ;i++)
35         {
36             scanf("%d",&c[i]);
37             if(!f[c[i]]) f[c[i]] = ++g;
38             if(i==1)
39             {
40                 dd[f[c[i]]].push_back(i);
41                 continue;
42             }
43             int tg = f[c[i-1]];
44             if(c[i]!=c[i-1])
45             {
46                 ed[tg].push_back(i-1);
47                 dd[f[c[i]]].push_back(i);
48             }
49         }
50         ed[f[c[n]]].push_back(n);
51         int ans = 0;
52         for(i = 1; i <= g; i++)
53         {
54             int tk = 0,st=0,ss=0;
55             ss += ed[i][0]-dd[i][0]+1;
56             ans =  max(ans,ss);
57 
58             for(j = 1 ;j < ed[i].size() ; j++)
59             {
60                 tk+=(dd[i][j]-ed[i][j-1]-1);
61                 ss+=(ed[i][j]-dd[i][j]+1);
62                 while(tk>k&&st<j)
63                 {
64                     tk-=(dd[i][st+1]-ed[i][st]-1);
65                     ss-=(ed[i][st]-dd[i][st]+1);
66                     st++;
67                 }
68 
69                 ans = max(ans,ss);
70             }
71         }
72         printf("%d\n",ans);
73     }
74     return 0;
75 }
View Code

 

F

这题有点逗，看了半个多小时终于看懂了啥意思，然后。。一份更逗的AC代码，全部输出1.

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 100000
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 int main()
18 {
19     int t,b,e;
20     cin>>t;
21     while(t--)
22     {
23         cin>>b>>e;
24         cout<<"1\n";
25     }
26     return 0;
27 }
View Code

 

 

 


联系
我们