Codeforces Round 875 (Div. 2)B-D

原题链接：https://codeforces.com/contest/1831

原文：https://www.cnblogs.com/edgrass/p/17440602.html

(B) Array merging

主体思想是找到ab数组的最长相同字串（c中操作可实现连续）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     int t;
 5     cin>>t;
 6     while(t--){
 7         int n;
 8         cin>>n;
 9         vector<int>a(n+1);
10         vector<int>b(n+1);
11         for(int i=1;i<=n;i++)cin>>a[i];
12         for(int i=1;i<=n;i++)cin>>b[i];
13         vector<int>ma(n+1+n);
14         vector<int>mb(n+1+n);
15         int q=1;
16         for(int i=2;i<=n;++i){
17             if(a[i]!=a[i-1]){ma[a[i-1]]=max(ma[a[i-1]],(i-q));
18             q=i;
19                 }        }
20          ma[a[n]] = max(ma[a[n]], n - q + 1);
21          q=1;
22          for(int i=2;i<=n;i++){
23             if(b[i]!=b[i-1]){mb[b[i-1]]=max(mb[b[i-1]],(i-q));
24             q=i;}
25         }
26          mb[b[n]] = max(mb[b[n]], n - q + 1);
27          int ans=0;
28          for(int i=1;i<=n+n;i++){
29             ans=max(ans,ma[i]+mb[i]);
30          }
31          cout<<ans<<endl;
32     }
33 }

(C) Copil Copac Draws Trees

根据编号判断

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=901100;
 4 int h[N],e[N],ne[N],w[N],idx;
 5 bool st[N];
 6 int mapp[N];
 7 void add(int a,int b,int c){
 8     e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
 9 }
10 void dfs(int a,int wn){
11     st[a]=true;
12     int wa;
13     for(int i=h[a];i!=-1;i=ne[i]){
14         int j=e[i],wa=w[i];
15         if(!st[j]){
16             if(wa<wn)mapp[j]=mapp[a]+1;
17             else mapp[j]=mapp[a];
18             dfs(j,wa);
19         }
20     }
21 }
22 int main(){
23     int t;
24     cin>>t;
25     while(t--){
26     idx=0;
27     memset(h, -1, sizeof h);
28     int n;
29     cin>>n;
30     for(int i=1;i<=n;i++)st[i]=false;
31     int ans=0;
32     for(int i=1;i<n;i++){
33         int a,b,c;
34         cin>>a>>b;
35         add(a,b,i);
36         add(b,a,i);
37     }
38     dfs(1,0x3f3f3f3f);
39     for(int i=1;i<=n;i++){
40         ans=max(ans,mapp[i]);
41     }
42     cout<<ans<<endl;
43     }
44 }

(D) The BOSS Can Count Pairs

#include<bits/stdc++.h>//b[i]*b[j]<=2n
#define PII pair<int,int>
#define int long long
using namespace std;
const int N=2e5+10;
PII p[N];//一定要写成全局变量
int ans=0;
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        ans=0;
        cin>>n;
        int a[N];
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }       
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            p[i]={a[i],x};
        }
        sort(p+1,p+1+n);
        for(int i=1;i*i<=n*2;i++){
            vector<int> a(n+1);
            for(int j=1;j<=n;j++){
                int num=i*p[j].first-p[j].second;//题中的关系式
                if(num>=1&&num<=n)ans+=a[num];
                if(i==p[j].first)a[p[j].second]++;
            }
        }
        cout<<ans<<endl;
    }
}