Educational Codeforces Round 35 (Rated for Div. 2)

2022-12-04 22:46:13

Educational Codeforces Round 35 (Rated for Div. 2)

A

模拟

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<ll>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 5000005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int a[];

 int main(){

     std::ios::sync_with_stdio(false);

     int n;

     cin>>n;

     int x=0x3f3f3f3f;

     for(int i=;i<=n;i++){

         cin>>a[i];

         x=min(x,a[i]);

     }

     int Min=0x3f3f3f3f;

     int pre=-;

     for(int i=;i<=n;i++){

         if(a[i]==x){

             if(pre==-) pre=i;

             else Min=min(Min,i-pre),pre=i;

         }

     }

     cout<<Min<<endl;

 }

B

二分

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<ll>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 5000005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int n,a,b;

 bool Check(int mid){

     int sum=a/mid;

     sum+=b/mid;

     if(sum>=n) return true;

     return false;

 }

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n>>a>>b;

     int L=,R=min(a,b),mid;

     while(L<=R){

         mid=L+R>>;

         if(Check(mid)){

             L=mid+;

         }

         else{

             R=mid-;

         }

     }

     cout<<R<<endl;

 }

C

题意：有三个灯，A将开启这些灯。这些灯一会亮一会不亮。如果第i个灯在第x秒开启，那么它仅在第x,x+ki,x+2*ki……秒时是亮的。 A想要打开灯，使每秒至少有一个灯是亮的。 A想要选择三个整数a，b，c，在第a秒接通第一个灯，在第b秒接通第二个灯，在第c秒接通第三灯，并且在从max（a，b，c）开始的每秒中，至少有一个灯将是亮的。问A是否可以做到。

思路：直接模拟就可以。。

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<ll>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 5000005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int book[];

 int main(){

     std::ios::sync_with_stdio(false);

     int a,b,c;

     cin>>a>>b>>c;

     book[a]++;

     book[b]++;

     book[c]++;

     if(book[]) cout<<"YES"<<endl;

     else if(book[]>=) cout<<"YES"<<endl;

     else if(book[]>=) cout<<"YES"<<endl;

     else if(book[]&&book[]>=) cout<<"YES"<<endl;

     else cout<<"NO"<<endl;

 }

D

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

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

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

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

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

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<ll>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 5000005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int tree[],a[];

 int m,n;

 int lowbit(int x){return x&(-x);}

 void add(int x){while(x<=n){tree[x]+=;x+=lowbit(x);}}

 int ask(int x){int sum=;while(x){sum+=tree[x];x-=lowbit(x);}return sum;}

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n;

     for(int i=;i<=n;i++){

         cin>>a[i];

     }

     int sum=;

     for(int i=n;i;i--){

         sum+=ask(a[i]);

         add(a[i]);

     }

     cin>>m;

     int x,y;

     int ans=sum&;

     for(int i=;i<=m;i++){

         cin>>x>>y;

         int len=y-x+;

         len=len*(len-)/;

         if(len&) ans^=;

         if(ans) cout<<"odd"<<endl;

         else cout<<"even"<<endl;

     }

 }

E

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

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

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<ll>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 5000005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int a[];

 stack<int>st;

 int main(){

     std::ios::sync_with_stdio(false);

     int n,m;

     cin>>n>>m;

     for(int i=;i<=m;i++){

         cin>>a[i];

     }

     int k=n-m;

     int i=;

     int co=;

     int flag=;

     while(i<=m){

         if(co!=a[i]){

             st.push(a[i]);

             i++;

         }

         else{

             co++;

             i++;

             while(!st.empty()&&st.top()==co){

                 co++;

                 st.pop();

             }

         }

     }

     if(!st.empty()){

         int pre=st.top();

         st.pop();

         while(!st.empty()){

             if(pre>st.top()){

                 flag=;

                 break;

             }

             pre=st.top();

             st.pop();

         }

     }

     if(flag==){

         cout<<-<<endl;

     }

     else{

         int i=;

         int co=;

         while(i<=m){

             if(co!=a[i]){

                 st.push(a[i]);

                 i++;

             }

             else{

                 co++;

                 i++;

                 while(!st.empty()&&st.top()==co){

                     co++;

                     st.pop();

                 }

             }

         }

         while(!st.empty()){

             int tmp=st.top();

             st.pop();

             for(i=tmp-;i>=co;i--){

                 a[++m]=i;

             }

             co=tmp+;

         }

         for(int i=n;i>=co;i--) a[++m]=i;

         for(int i=;i<=m;i++){

             cout<<a[i]<<" ";

         }

     }

 }

F

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

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

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<ll>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 200005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int n;

 vector<int>ve[];

 vector<pair<int,pair<int,int> > >ans;

 int deep[],fa[],book[];

 ll sum;

 int pos1,pos2;

 void dfs1(int now,int pre){

     for(int i=;i<ve[now].size();i++){

         if(ve[now][i]!=pre){

             deep[ve[now][i]]=deep[now]+;

             fa[ve[now][i]]=now;

             dfs1(ve[now][i],now);

         }

     }

 }

 void dfs2(int now,int pre,int d){

     if(book[now]) d++;

     for(int i=;i<ve[now].size();i++){

         if(pre!=ve[now][i]){

             dfs2(ve[now][i],now,d);

             if(!book[ve[now][i]]){

                 int dep1=deep[ve[now][i]];

                 int dep2=deep[pos2]+deep[ve[now][i]]-*d;

                 if(dep1>=dep2){

                     sum+=dep1;

                     ans.pb({pos1,{ve[now][i],ve[now][i]}});

                 }

                 else{

                     sum+=dep2;

                     ans.pb({pos2,{ve[now][i],ve[now][i]}});

                 }

             }

         }

     }

 }

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n;

     int u,v;

     for(int i=;i<n;i++){

         cin>>u>>v;

         ve[u].pb(v);

         ve[v].pb(u);

     }

     dfs1(,);

     pos1=,pos2=;

     for(int i=;i<=n;i++){

         if(deep[i]>deep[pos1]){

             pos1=i;

         }

     }

     deep[pos1]=,fa[pos1]=;

     dfs1(pos1,);

     for(int i=;i<=n;i++){

         if(deep[i]>deep[pos2]){

             pos2=i;

         }

     }

     for(int i=pos2;i!=pos1;i=fa[i]) book[i]=;

     dfs2(pos1,,);

     for(int i=pos2;i!=pos1;i=fa[i]){

         ans.pb({pos1,{i,i}});

         sum+=deep[i];

     }

     cout<<sum<<endl;

     for(int i=;i<ans.size();i++){

         cout<<ans[i].first<<" "<<ans[i].second.first<<" "<<ans[i].second.second<<endl;

     }

 }

G

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

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

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define IT set<ll>::iterator

 #define sqr(x) ((x)*(x))

 #define pb push_back

 #define eb emplace_back

 #define maxn 200005

 #define eps 1e-8

 #define pi acos(-1.0)

 #define rep(k,i,j) for(int k=i;k<j;k++)

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll>pll;

 typedef pair<ll,int> pli;

 typedef pair<pair<int,string>,pii> ppp;

 typedef unsigned long long ull;

 const long long MOD=;

 const double oula=0.57721566490153286060651209;

 using namespace std;

 int lazy[maxn<<][];

 int a[maxn];

 int n;

 void build(int l,int r,int rt){

     for(int i=;i<=;i++){

         lazy[rt][i]=i;

     }

     if(l==r) return;

     int mid=l+r>>;

     build(lson);

     build(rson);

 }

 void push_down(int rt){

     for(int i=;i<=;i++){

         lazy[rt<<][i]=lazy[rt][lazy[rt<<][i]];

         lazy[rt<<|][i]=lazy[rt][lazy[rt<<|][i]];

     }

     for(int i=;i<=;i++){

         lazy[rt][i]=i;

     }

 }

 void update(int L,int R,int x,int y,int l,int r,int rt){

     if(L<=l&&R>=r){

         for(int i=;i<=;i++){

             if(lazy[rt][i]==x){

                 lazy[rt][i]=y;

             }

         }

         return;

     }

     push_down(rt);

     int mid=l+r>>;

     if(L<=mid) update(L,R,x,y,lson);

     if(R>mid) update(L,R,x,y,rson);

 }

 void query(int l,int r,int rt){

     if(l==r){

         cout<<lazy[rt][a[l]]<<" ";

         return;

     }

     push_down(rt);

     int mid=l+r>>;

     query(lson);

     query(rson);

 }

 int main(){

     std::ios::sync_with_stdio(false);

     cin>>n;

     for(int i=;i<=n;i++) cin>>a[i];

     build(,n,);

     int q;

     cin>>q;

     int l,r,x,y;

     while(q--){

         cin>>l>>r>>x>>y;

         update(l,r,x,y,,n,);

     }

     query(,n,);

 }

码农公寓

Educational Codeforces Round 35 (Rated for Div. 2)

A

B

C

D

E

F

G

相关文章