The 2019 China Collegiate Programming Contest Harbin Site-----E,Exchanging Gifts

Meaning:

There are n sequences \ (s {i} \).
With n lines of input, there are two operations to get \ (s {i} \).
1, 1 m \(s_{i1}\) \(s_{i2}\) ...... \(s_{im}\) .
2. 2 x y means that this array is generated by the combination of arrays X and y.
Q: after rearrangement, the final array \ (s {n} \) can have at most several elements different from the original \ (s {n} \).

Idea:

First, let's look at the final answer. Obviously, after rearrangement, if the number of elements in the array that appear the most times is less than half of the length of the original array, the answer is the length of the original array. Otherwise, the answer is (array length - number of repetitions) * 2.

Method 1:
We need to look at the contribution times of each known array to the final array to get the final array. The number of contributions is required, and the contributions of the array are directly enumerated from n~1. After knowing the number of contributions, we can facilitate all the arrays we need, and then use map to record the number of all elements. Finally, you can find the total number of elements in the final array and the number of occurrences of the number with the most occurrences. The answer can be obtained (the complexity is greater than O(n), which is slower)

Method 2:
When calculating the contribution times of each array, directly enumerate the contribution of the array from n~1, and use an O (n) method to calculate the mode to calculate the occurrence times of the element with the most occurrences in the array. (O(n)).

You'd better read this question quickly, otherwise it's easy tle.

code:

Method 1:

//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define ll long long
#define MOD 1000000007
#define pdd pair<double,double>
#define mem(a,x) memset(a,x,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const double eps=1e-6;
const int maxn=1000005; 
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(int &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}

int flag[maxn],in[maxn];
bool vis[maxn];
ll cnt[maxn];
int n,m;
vector<int>co[maxn];
vector<int>G[maxn];
map<int,ll>ans;
queue<int>q;
int op[maxn][3];
void init()
{
   for(int i=1;i<=n;i++){
      co[i].clear();
      G[i].clear();
      vis[i]=in[i]=cnt[i]=0;
      if(!q.empty())q.pop();
   }
   ans.clear();
}
void gao()
{
    for(int i=n;i>=1;i--){
      if(flag[i]==2){
         cnt[op[i][1]]+=cnt[i];
         cnt[op[i][2]]+=cnt[i];
      }
    }
    for(int i=1;i<=n;i++){
       if(cnt[i]!=0&&flag[i]==1){
          for(auto j:co[i]){
             ans[j]+=cnt[i];
          }
       }
    }
    ll sum=0,maxx=0;
    for(auto &i:ans){
        sum+=i.second;
        if(i.second>maxx)maxx=i.second;
    }
    if(maxx*2>=sum){
       printf("%lld\n",(sum-maxx)*2);
    }else{
       printf("%lld\n",sum);
    }
}

int main()
{
   int T;
   IO;
   read(T);
   while(T--){
       read(n);
       init();
       for(int i=1;i<=n;i++){
          read(flag[i]);
          if(flag[i]==1){
             read(m);
             for(int j=1;j<=m;j++){
                 int x;
                 read(x);
                 co[i].push_back(x);
             }
          }else{
             read(op[i][1]);
             read(op[i][2]);
          }
       }
       cnt[n]=1;
       gao();
   }
   return 0;
}
 

Method 2:

//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define ll long long
#define MOD 1000000007
#define pdd pair<double,double>
#define mem(a,x) memset(a,x,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const double eps=1e-6;
const int maxn=1000005; 
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(int &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}

int n,m;
vector<int>co[maxn];
ll cnt[maxn];
int flag[maxn];
int op[maxn][3];

void solve()
{
   cnt[n]=1;
   for(int i=n;i>=1;i--){
      if(flag[i]==2){
         cnt[op[i][1]]+=cnt[i];
         cnt[op[i][2]]+=cnt[i];
      }
   }
   //
   ll tot=0,val=0;
   ll all=0;
   for(int i=1;i<=n;i++){
       if(flag[i]==1&&cnt[i]>0){
          for(auto x:co[i]){
             if(val==0){
                tot+=cnt[i];
                val=x;
                continue;
             }else if(val==x){
                tot+=cnt[i];
             }else{
                tot-=cnt[i];
                if(tot<0){
                   tot=-tot;
                   val=x;
                }
             }
          }
          all+=co[i].size()*cnt[i];
       }
   }
   tot=0;
   for(int i=1;i<=n;i++){
      if(cnt[i]>0&&flag[i]==1){
         for(auto v:co[i]){
            if(v==val)tot+=cnt[i];
         }
      }
      
   }
   //cout<<"aa"<<all<<" "<<tot<<endl;
   if(tot*2>=all){
      cout<<(all-tot)*2<<endl;
   }else{
      cout<<all<<endl;
   }
}
int main()
{
   IO;
   int T;
   read(T);
   while(T--){
       read(n);
       for(int i=1;i<=n;i++){
           co[i].clear();
           cnt[i]=0;
           read(flag[i]);
           if(flag[i]==1){
              read(m);
              for(int j=1;j<=m;j++){
                 int x;
                 read(x);
                 co[i].push_back(x);
              }
           }else{
              read(op[i][1]);
              read(op[i][2]);
           }
       }
       solve();
   }
   return 0;
}

Posted by grayson on Fri, 13 May 2022 13:57:39 +0300