Codeforces Round #541 (Div. 2)

A

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000005
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 
14 int main(){
15     #ifndef ONLINE_JUDGE
16       //  freopen("input.txt","r",stdin);
17     #endif
18     std::ios::sync_with_stdio(false);
19     ll w1,h1,w2,h2;
20     cin>>w1>>h1>>w2>>h2;
21     ll tmp1=(w2+2)*(h2+2);//上面的
22     ll tmp2=(w1+2)*(h1+2);
23     ll tmp3=w1*h1+w2*h2;
24     ll ans=tmp1+tmp2-tmp3-2*(w2+2);
25     cout<<ans<<endl;
26 }

View Code

B

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000005
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 int main(){
14     #ifndef ONLINE_JUDGE
15      //   freopen("input.txt","r",stdin);
16     #endif
17     std::ios::sync_with_stdio(false);
18     int n;
19     cin>>n;
20     ll a,b,x,y;
21     x=0,y=0;
22     ll ans=1;
23     for(int i=1;i<=n;i++){
24         cin>>a>>b;
25         ans+=max(0LL,min(a,b)-max(x,y)+(x!=y));
26         x=a,y=b;
27     }
28     cout<<ans<<endl;
29 }

View Code

C

sort排序，然后从小到大依次左右各添一个向中间添加。。。在比赛的时候第一感觉这就是正解，但是不会证明为什么。。。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000005
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 int a[105];
14 int ans[105];
15 
16 int main(){
17     #ifndef ONLINE_JUDGE
18       //  freopen("input.txt","r",stdin);
19     #endif
20     std::ios::sync_with_stdio(false);
21     int n;
22     cin>>n;
23     for(int i=1;i<=n;i++) cin>>a[i];
24     sort(a+1,a+n+1);
25     int L=1,R=n;
26     int i=1;
27     while(L<=R){
28         if(i%2)
29             ans[L++]=a[i];
30         else
31             ans[R--]=a[i];
32         i++;
33     }
34     for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
35 }

View Code

D

用并查集把相同的点连在一起，然后剩下的点用拓扑排序即可

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define lson l,mid,rt<<1
  4 #define rson mid+1,r,rt<<1|1
  5 #define sqr(x) ((x)*(x))
  6 #define pb push_back
  7 #define eb emplace_back
  8 #define maxn 2005
  9 #define rep(k,i,j) for(int k=i;k<j;k++)
 10 typedef long long ll;
 11 typedef unsigned long long ull;
 12 
 13 int n,m;
 14 char str[1005][1005];
 15 
 16 int fa[maxn];
 17 int d[maxn];
 18 int vis[maxn];
 19 int ans[maxn];
 20 vector<int>ve[maxn];
 21 
 22 int Find(int x){
 23     int r=x,y;
 24     while(x!=fa[x]){
 25         x=fa[x];
 26     }
 27     while(r!=x){
 28         y=fa[r];
 29         fa[r]=x;
 30         r=y;
 31     }
 32     return x;
 33 }
 34 
 35 void join(int x,int y){
 36      int xx=Find(x);
 37      int yy=Find(y);
 38      fa[xx]=yy;
 39 }
 40 
 41 void add(int x,int y){
 42     int xx=Find(x);
 43     int yy=Find(y);
 44     if(xx!=yy){
 45         d[xx]++;
 46         ve[yy].pb(xx);
 47     }
 48     else{
 49         cout<<"NO"<<endl;
 50         exit(0);
 51     }
 52 }
 53 
 54 void topsort(){
 55     queue<pair<int,int> >Q;
 56     rep(i,1,n+m+1){
 57         int xx=Find(i);
 58         if(!d[xx]&&!vis[xx]){
 59             vis[xx]=1;
 60             Q.push(make_pair(xx,1));
 61         }
 62     }
 63     pair<int,int>pp;
 64     while(!Q.empty()){
 65         pp=Q.front();
 66         Q.pop();
 67         int pos=pp.first;
 68         int v=pp.second;
 69         ans[pos]=v;
 70         rep(i,0,ve[pos].size()){
 71             int w=ve[pos][i];
 72             d[w]--;
 73             if(!d[w]){
 74                 Q.push(make_pair(w,v+1));
 75             }
 76         }
 77     }
 78     rep(i,1,n+m+1){
 79         if(d[i]){
 80             cout<<"NO"<<endl;
 81             exit(0);
 82         }
 83     }
 84 }
 85 
 86 int main(){
 87     #ifndef ONLINE_JUDGE
 88         freopen("input.txt","r",stdin);
 89     #endif
 90     std::ios::sync_with_stdio(false);
 91     cin>>n>>m;
 92     rep(i,1,n+m+1) fa[i]=i;
 93     rep(i,1,n+1) cin>>(str[i]+1);
 94     rep(i,1,n+1){
 95         rep(j,1,m+1){
 96             if(str[i][j]=='='){
 97                 join(Find(i),Find(j+n));
 98             }
 99         }
100     }
101     rep(i,1,n+1){
102         rep(j,1,m+1){
103             if(str[i][j]=='>'){
104                 add(i,n+j);
105             }
106             else if(str[i][j]=='<'){
107                 add(n+j,i);
108             }
109         }
110     }
111     topsort();
112     cout<<"YES"<<endl;
113     rep(i,1,n+1) cout<<ans[Find(i)]<<" ";
114     cout<<endl;
115     rep(i,1,m+1) cout<<ans[Find(i+n)]<<" ";
116 }

View Code

E

类似模拟的方法

找出字符串的连续前缀，连续后缀和中间最长连续子串

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000005
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 int ans=0;
14 string s[100005];
15 
16 int main(){
17     #ifndef ONLINE_JUDGE
18        // freopen("input.txt","r",stdin);
19     #endif
20     std::ios::sync_with_stdio(false);
21     int n;
22     cin>>n;
23     for(int i=0;i<n;i++){
24         cin>>s[i];
25     }
26     for(int c=0;c<26;c++){
27         int l=0,r=0,all=1;
28         for(int i=n-1;i>=0;i--){
29             int cnt=0,pf=0,sf=0,tt=0;
30             while(pf<s[i].length()&&s[i][pf]=='a'+c) ++pf;
31             while(sf<s[i].length()&&s[i][s[i].length()-1-sf]=='a'+c) ++sf;
32             for(int j=0;j<s[i].length();j++){
33                 if(s[i][j]=='a'+c){
34                     cnt=max(cnt,++tt);
35                 }
36                 else{
37                     tt=0;
38                 }
39             }
40             if(all){
41                 ans=max(ans,(cnt+1)*(l+1)-1);
42                 l=(pf+1)*(l+1)-1;
43                 r=(sf+1)*(r+1)-1;
44                 if(pf!=s[i].length()){
45                     all=0;
46                 }
47             }
48             else{
49                 if(cnt){
50                     ans=max(ans,l+r+1);
51                 }
52             }
53         }
54     }
55     cout<<ans<<endl;
56 }

View Code

比赛的时候犯傻了，一直在想建图，然后找度为1的点，然后深搜的错误性。。没想出来。后来才知道了错误性

正解应该是：并查集，合并就完事了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000005
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 vector<int>ve[150005];
14 
15 int fa[150005];
16 
17 int Find(int x){
18     int r=x,y;
19     while(x!=fa[x]){
20         x=fa[x];
21     }
22     while(r!=x){
23         y=fa[r];
24         fa[r]=x;
25         r=y;
26     }
27     return x;
28 }
29 
30 
31 void join(int x,int y){
32     int xx=Find(x);
33     int yy=Find(y);
34     if(ve[xx].size()>ve[yy].size()){
35         swap(xx,yy);
36     }
37     rep(i,0,ve[xx].size()){
38         ve[yy].pb(ve[xx][i]);
39         fa[ve[xx][i]]=yy;
40     }
41 }
42 
43 int main(){
44     #ifndef ONLINE_JUDGE
45         freopen("input.txt","r",stdin);
46     #endif
47     std::ios::sync_with_stdio(false);
48     int n;
49     cin>>n;
50     rep(i,1,n+1) fa[i]=i,ve[i].pb(i);
51     int u,v;
52     rep(i,1,n){
53         cin>>u>>v;
54         join(u,v);
55     }
56     int pos=Find(1);
57     rep(i,0,ve[pos].size()){
58         cout<<ve[pos][i]<<" ";
59     }
60 
61 }

View Code