Codeforces Round #520 (Div. 2)

时间：2023-12-12 20:39:20

Codeforces Round #520 (Div. 2)

https://codeforces.com/contest/1062

A

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #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<long long,int>pli;

 typedef pair<int,char> pic;

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

 typedef unsigned long long ull;

 const long long mod=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int a[];

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     int n;

     cin>>n;

     if(n==) {

         cout<<<<endl;

         return ;

     }

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

     a[]=,a[n+]=;

     int ans=,Max=;

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

         if(a[i]-a[i-]==){

             Max++;

         }

         else{

             ans=max(ans,Max-);

             Max=;

         }

     }

     ans=max(ans,Max-);

     cout<<ans<<endl;

 }

B

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #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<long long,int>pli;

 typedef pair<int,char> pic;

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

 typedef unsigned long long ull;

 const long long mod=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int a[];

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     ll n;

     cin>>n;

     ll tmp=n;

     ll num=;

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

         if(tmp%i==){

             num*=i;

             while(tmp%i==){

                 tmp/=i;

             }

         }

     }

     ll ans=;

     tmp=num;

     while(num%n){

         num*=num;

         ans++;

     }

     cout<<tmp<<" "<<(ans+(num>n))<<endl;

 }

C

数论+推公式

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #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<long long,int>pli;

 typedef pair<int,char> pic;

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

 typedef unsigned long long ull;

 const long long mod=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 string str;

 ll sum[];

 ll pow_mul(ll a,ll b){

     ll ans=;

     while(b){

         if(b&)

             ans=ans*a%mod;

         b>>=;

         a=a*a%mod;

     }

     return ans;

 }

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     int n,q;

     cin>>n>>q;

     cin>>str;

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

         sum[i+]=sum[i]+str[i]-'';

     }

     int l,r;

     while(q--){

         cin>>l>>r;

         ll ans=pow_mul(,sum[r]-sum[l-])-;

         if(ans==-) ans+=mod;

         ans=(ans+ans*(pow_mul(,r-l++sum[l-]-sum[r])-+mod)%mod)%mod;

         cout<<ans<<endl;

     }

 }

D

数论

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #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<long long,int>pli;

 typedef pair<int,char> pic;

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

 typedef unsigned long long ull;

 const long long mod=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     int n;

     cin>>n;

     ll ans=;

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

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

             ans+=j/i;

         }

     }

     cout<<ans*<<endl;

 }

E

lca+线段树+倍增

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 100005

 #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<long long,int>pli;

 typedef pair<int,char> pic;

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

 typedef unsigned long long ull;

 const long long mod=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 //int phi[maxn];

 vector<int>ve[maxn];

 int dep[maxn],parent[maxn][],n,cnt;

 int Max[maxn<<],Min[maxn<<],id[maxn],s[maxn];

 void dfs(int now,int fa,int deep){

     dep[now]=deep;

     parent[now][]=fa;

     s[now]=++cnt;

     id[cnt]=now;

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

         dfs(ve[now][i],now,deep+);

     }

 }

 void Init(){

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

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

             parent[i][j]=parent[parent[i][j-]][j-];

         }

     }

 }

 int lca(int x,int y){

     if(dep[x]<dep[y]) swap(x,y);

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

         if(dep[parent[x][i]]>=dep[y]){

             x=parent[x][i];

         }

     }

     if(x==y) return dep[x]-;

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

         if(parent[x][i]!=parent[y][i]){

             x=parent[x][i];

             y=parent[y][i];

         }

     }

     return dep[parent[x][]]-;

 }

 int query1(int L,int R,int l,int r,int rt){

     if(L<=l&&R>=r) return Max[rt];

     int mid=l+r>>;

     int ans=;

     if(L<=mid) ans=max(ans,query1(L,R,lson));

     if(R>mid) ans=max(ans,query1(L,R,rson));

     return ans;

 }

 int query2(int L,int R,int l,int r,int rt){

     if(L<=l&&R>=r) return Min[rt];

     int mid=l+r>>;

     int ans=0x3f3f3f3f;

     if(L<=mid) ans=min(ans,query2(L,R,lson));

     if(R>mid) ans=min(ans,query2(L,R,rson));

     return ans;

 }

 void push_up(int rt){

     Max[rt]=max(Max[rt<<],Max[rt<<|]);

     Min[rt]=min(Min[rt<<],Min[rt<<|]);

 }

 void update(int L,int v,int l,int r,int rt){

     if(l==r){

         Max[rt]=Min[rt]=v;

         return;

     }

     int mid=l+r>>;

     if(L<=mid) update(L,v,lson);

     else update(L,v,rson);

     push_up(rt);

 }

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     std::ios::sync_with_stdio(false);

     int q;

     cin>>n>>q;

     int x,y;

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

         cin>>x;

         ve[x].pb(i);

     }

     dfs(,,);

     Init();

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

         update(i,s[i],,n,);

     }

     while(q--){

         cin>>x>>y;

         int min1=query2(x,y,,n,);

         int max1=query1(x,y,,n,);

         update(id[min1],0x3f3f3f3f,,n,);

         int min2=query2(x,y,,n,);

         update(id[min1],min1,,n,);

         update(id[max1],,,n,);

         int max2=query1(x,y,,n,);

         update(id[max1],max1,,n,);///?

         int ans1=lca(id[min1],id[max2]),ans2=lca(id[min2],id[max1]);

         if(ans1>=ans2){

             cout<<id[max1]<<" "<<ans1<<endl;

         }

         else{

             cout<<id[min1]<<" "<<ans2<<endl;

         }

     }

 }

F

拓扑排序

参考博客：https://www.cnblogs.com/yqgAKIOI/p/10012279.html

 #include<bits/stdc++.h>

 using namespace std;

 #define lson l,mid,rt<<1

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

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

 #define pb push_back

 #define eb emplace_back

 #define maxn 300005

 #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<long long,int>pli;

 typedef pair<int,char> pic;

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

 typedef unsigned long long ull;

 const long long mod=1e9+;

 /*#ifndef ONLINE_JUDGE

         freopen("1.txt","r",stdin);

 #endif */

 int n,m;

 int a[maxn],b[maxn],d[maxn],cnt[maxn];

 vector<int>ve[maxn];

 void topsort(int a[],int b[]){

     for(int i=;i<n;i++) ve[i].clear();

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

         ve[a[i]].pb(b[i]);

         d[b[i]]++;

     }

     int num=n;

     queue<int>Q;

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

         if(!d[i]){

             Q.push(i);

             num--;

         }

     }

     while(!Q.empty()){

         int now=Q.front();

         Q.pop();

         if(Q.empty()) cnt[now]+=num;

         else if(Q.size()==){

             int tmp=;

             for(int i=,y=Q.front();i<ve[y].size();i++){

                 tmp&=(d[ve[y][i]]>);

             }

             cnt[now]+=num*tmp;

         }

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

             if(!--d[ve[now][i]]){

                 Q.push(ve[now][i]);

                 num--;

             }

     }

 }

 int main(){

     #ifndef ONLINE_JUDGE

      //   freopen("1.txt","r",stdin);

     #endif

     std::ios::sync_with_stdio(false);

     cin>>n>>m;

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

         cin>>a[i]>>b[i];

         a[i]--,b[i]--;

     }

     topsort(a,b);

     topsort(b,a);

     int ans=;

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

         ans+=(cnt[i]+>=n);

     cout<<ans<<endl;

 }

相关文章