Educational Codeforces Round 35 (Rated for Div. 2)

Educational Codeforces Round 35 (Rated for Div. 2)

https://codeforces.com/contest/911

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 IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int a[100005];
24 
25 
26 int main(){
27     std::ios::sync_with_stdio(false);
28     int n;
29     cin>>n;
30     int x=0x3f3f3f3f;
31     for(int i=1;i<=n;i++){
32         cin>>a[i];
33         x=min(x,a[i]);
34     }
35     int Min=0x3f3f3f3f;
36     int pre=-1;
37     for(int i=1;i<=n;i++){
38         if(a[i]==x){
39             if(pre==-1) pre=i;
40             else Min=min(Min,i-pre),pre=i;
41         }
42     }
43     cout<<Min<<endl;
44 }
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 IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int n,a,b;
24 
25 bool Check(int mid){
26     int sum=a/mid;
27     sum+=b/mid;
28     if(sum>=n) return true;
29     return false;
30 }
31 
32 int main(){
33     std::ios::sync_with_stdio(false);
34     cin>>n>>a>>b;
35     int L=0,R=min(a,b),mid;
36     while(L<=R){
37         mid=L+R>>1;
38         if(Check(mid)){
39             L=mid+1;
40         }
41         else{
42             R=mid-1;
43         }
44     }
45     cout<<R<<endl;
46 }
View Code

C

题意：有三个灯，A将开启这些灯。 这些灯一会亮一会不亮。如果第i个灯在第x秒开启，那么它仅在第x,x+ki,x+2*ki……秒时是亮的。 A想要打开灯，使每秒至少有一个灯是亮的。 A想要选择三个整数a，b，c，在第a秒接通第一个灯，在第b秒接通第二个灯，在第c秒接通第三灯， 并且在从max（a，b，c）开始的每秒中，至少有一个灯将是亮的。 问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 IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int book[1505];
24 
25 int main(){
26     std::ios::sync_with_stdio(false);
27     int a,b,c;
28     cin>>a>>b>>c;
29     book[a]++;
30     book[b]++;
31     book[c]++;
32     if(book[1]) cout<<"YES"<<endl;
33     else if(book[2]>=2) cout<<"YES"<<endl;
34     else if(book[3]>=3) cout<<"YES"<<endl;
35     else if(book[2]&&book[4]>=2) cout<<"YES"<<endl;
36     else cout<<"NO"<<endl;
37 }
View Code

D

题意：给你一个长度为n的序列，有m次操作。每次翻转[l,r]的区间，每次操作后询问序列逆序对个数的奇偶性。

思路：通过多次模拟可以发现一个规律：

1、区间翻转时，区间内的逆序对的个数不影响区间外的逆序对的个数

2、区间翻转，正序对和逆序对数量交换。所以可以判断区间序对数的奇偶性

发现这规律做题就容易了，直接上树状数组搞搞就行

 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 IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int tree[1505],a[1505];
24 int m,n;
25 int lowbit(int x){return x&(-x);}
26 void add(int x){while(x<=n){tree[x]+=1;x+=lowbit(x);}}
27 int ask(int x){int sum=0;while(x){sum+=tree[x];x-=lowbit(x);}return sum;}
28 
29 
30 int main(){
31     std::ios::sync_with_stdio(false);
32     cin>>n;
33     for(int i=1;i<=n;i++){
34         cin>>a[i];
35     }
36     int sum=0;
37     for(int i=n;i;i--){
38         sum+=ask(a[i]);
39         add(a[i]);
40     }
41     cin>>m;
42     int x,y;
43     int ans=sum&1;
44     for(int i=1;i<=m;i++){
45         cin>>x>>y;
46         int len=y-x+1;
47         len=len*(len-1)/2;
48         if(len&1) ans^=1;
49         if(ans) cout<<"odd"<<endl;
50         else cout<<"even"<<endl;
51     }
52 }
View Code

E

题意：给定 n，m（n>=m），先给出m个数，然后让你补全剩下的n-m个数，使的字典序最大且可以通过栈使它变成1-n的顺序序列

思路：先判断给定的数能不能通过模拟栈的方法顺序输出，可以的话就从大到小补全小于栈顶元素且未出现过的数。

 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 IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int a[200005];
24 stack<int>st;
25 
26 int main(){
27     std::ios::sync_with_stdio(false);
28     int n,m;
29     cin>>n>>m;
30     for(int i=1;i<=m;i++){
31         cin>>a[i];
32     }
33     int k=n-m;
34     int i=1;
35     int co=1;
36     int flag=0;
37     while(i<=m){
38         if(co!=a[i]){
39             st.push(a[i]);
40             i++;
41         }
42         else{
43             co++;
44             i++;
45             while(!st.empty()&&st.top()==co){
46                 co++;
47                 st.pop();
48             }
49         }
50     }
51     if(!st.empty()){
52         int pre=st.top();
53         st.pop();
54         while(!st.empty()){
55             if(pre>st.top()){
56                 flag=1;
57                 break;
58             }
59             pre=st.top();
60             st.pop();
61         }
62     }
63     if(flag==1){
64         cout<<-1<<endl;
65     }
66     else{
67         int i=1;
68         int co=1;
69         while(i<=m){
70             if(co!=a[i]){
71                 st.push(a[i]);
72                 i++;
73             }
74             else{
75                 co++;
76                 i++;
77                 while(!st.empty()&&st.top()==co){
78                     co++;
79                     st.pop();
80                 }
81             }
82         }
83         while(!st.empty()){
84             int tmp=st.top();
85             st.pop();
86             for(i=tmp-1;i>=co;i--){
87                 a[++m]=i;
88             }
89             co=tmp+1;
90         }
91         for(int i=n;i>=co;i--) a[++m]=i;
92         for(int i=1;i<=m;i++){
93             cout<<a[i]<<" ";
94         }
95     }
96 }
View Code

F

题意：给你一棵树，每次选这棵树的两个叶子，加上他们之间的距离，然后将其中一个点去掉，问你距离之和最大可以是多少。

思路：要求距离之和最大，肯定是需要把树的直径求出来，然后依次减去非直径上的点，最后减去直径上的点

 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 IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 200005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int n;
24 vector<int>ve[200005];
25 vector<pair<int,pair<int,int> > >ans;
26 int deep[200005],fa[200005],book[200005];
27 ll sum;
28 int pos1,pos2;
29 
30 void dfs1(int now,int pre){
31     for(int i=0;i<ve[now].size();i++){
32         if(ve[now][i]!=pre){
33             deep[ve[now][i]]=deep[now]+1;
34             fa[ve[now][i]]=now;
35             dfs1(ve[now][i],now);
36         }
37     }
38 }
39 
40 void dfs2(int now,int pre,int d){
41     if(book[now]) d++;
42     for(int i=0;i<ve[now].size();i++){
43         if(pre!=ve[now][i]){
44             dfs2(ve[now][i],now,d);
45             if(!book[ve[now][i]]){
46                 int dep1=deep[ve[now][i]];
47                 int dep2=deep[pos2]+deep[ve[now][i]]-2*d;
48                 if(dep1>=dep2){
49                     sum+=dep1;
50                     ans.pb({pos1,{ve[now][i],ve[now][i]}});
51                 }
52                 else{
53                     sum+=dep2;
54                     ans.pb({pos2,{ve[now][i],ve[now][i]}});
55                 }
56             }
57         }
58     }
59 }
60 
61 
62 int main(){
63     std::ios::sync_with_stdio(false);
64     cin>>n;
65     int u,v;
66     for(int i=1;i<n;i++){
67         cin>>u>>v;
68         ve[u].pb(v);
69         ve[v].pb(u);
70     }
71     dfs1(1,0);
72     pos1=0,pos2=0;
73     for(int i=1;i<=n;i++){
74         if(deep[i]>deep[pos1]){
75             pos1=i;
76         }
77     }
78     deep[pos1]=0,fa[pos1]=0;
79     dfs1(pos1,0);
80     for(int i=1;i<=n;i++){
81         if(deep[i]>deep[pos2]){
82             pos2=i;
83         }
84     }
85     for(int i=pos2;i!=pos1;i=fa[i]) book[i]=1;
86     dfs2(pos1,0,0);
87     for(int i=pos2;i!=pos1;i=fa[i]){
88         ans.pb({pos1,{i,i}});
89         sum+=deep[i];
90     }
91     cout<<sum<<endl;
92     for(int i=0;i<ans.size();i++){
93         cout<<ans[i].first<<" "<<ans[i].second.first<<" "<<ans[i].second.second<<endl;
94     }
95 }
View Code

G

题意：给出一个数列,有q个操作,每种操作是把区间[l,r]中等于x的数改成y.输出q步操作完的数列

思路：因为数列中的值为1-100，所以用线段树暴力修改

 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 IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 200005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int lazy[maxn<<2][105];
24 int a[maxn];
25 int n;
26 
27 void build(int l,int r,int rt){
28     for(int i=1;i<=100;i++){
29         lazy[rt][i]=i;
30     }
31     if(l==r) return;
32     int mid=l+r>>1;
33     build(lson);
34     build(rson);
35 }
36 
37 void push_down(int rt){
38     for(int i=1;i<=100;i++){
39         lazy[rt<<1][i]=lazy[rt][lazy[rt<<1][i]];
40         lazy[rt<<1|1][i]=lazy[rt][lazy[rt<<1|1][i]];
41     }
42     for(int i=1;i<=100;i++){
43         lazy[rt][i]=i;
44     }
45 }
46 
47 void update(int L,int R,int x,int y,int l,int r,int rt){
48     if(L<=l&&R>=r){
49         for(int i=1;i<=100;i++){
50             if(lazy[rt][i]==x){
51                 lazy[rt][i]=y;
52             }
53         }
54         return;
55     }
56     push_down(rt);
57     int mid=l+r>>1;
58     if(L<=mid) update(L,R,x,y,lson);
59     if(R>mid) update(L,R,x,y,rson);
60 }
61 
62 void query(int l,int r,int rt){
63     if(l==r){
64         cout<<lazy[rt][a[l]]<<" ";
65         return;
66     }
67     push_down(rt);
68     int mid=l+r>>1;
69     query(lson);
70     query(rson);
71 }
72 
73 int main(){
74     std::ios::sync_with_stdio(false);
75     cin>>n;
76     for(int i=1;i<=n;i++) cin>>a[i];
77     build(1,n,1);
78     int q;
79     cin>>q;
80     int l,r,x,y;
81     while(q--){
82         cin>>l>>r>>x>>y;
83         update(l,r,x,y,1,n,1);
84     }
85     query(1,n,1);
86 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Fighting-sh/p/10633378.html