Codeforces Round 781 (Div. 2 C树上贪心 D二进制+gcd E结论+线段树)

A：直接让gcd和lcm都等于1，让a=n-3即可

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353,K=5e5;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
void solve()
{
   cin>>n;
   cout<<n-3<<" "<<1<<" "<<1<<" "<<1<<"\n";
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

B：

操作题先想操作性质，肯定是操作最多的那个数的

然后操作的时候，无法避免的是都要一个一个从副本换过来

所以换过来是固定次数，然后直接每次换过来之后再复制就行了

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353,K=5e5;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
void solve()
{
   cin>>n;
   for(int i=1;i<=n;i++) cin>>a[i];
   map<int,int> mp;
   for(int i=1;i<=n;i++) mp[a[i]]++;
    sort(a+1,a+1+n,[&](const auto&p,const auto&q){
        return mp[p]>mp[q]; 
    });
    int res=n-mp[a[1]];
    int now=mp[a[1]];
    int cnt=0;
    while(cnt<n-mp[a[1]])
    {
        cnt+=now;
        now*=2;
        res++;
    }
    cout<<res<<"\n";
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

C;

可以观察到兄弟节点染色了才能感染其他节点，

所以先统计每个节点的儿子节点

然后按照数量大小去安排感染先后，

这个时候我们发现我们可以得出来感染完全部需要感染节点后，当前节点剩下还需要感染的点，

我们可以通过额外感染加快时间，直接拿个堆去枚举就行了，最多就n次

top是当前每个子树已经同时感染了多少个兄弟节点

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353,K=5e5;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
vector<int> g[N],dep[N];
void solve()
{
   cin>>n;
   vector<int> sz(n+1);
   for(int i=1;i<n;i++){
       int x;cin>>x;
       sz[x]++;
   }
   sz[0]=1;
   sort(sz.begin(),sz.end());
   for(int i=0;i<=n;i++){
       if(sz[i]==0) continue;
       priority_queue<int> q;
       for(int j=i;j<=n;j++)
       {
           q.push(sz[j]-(j-i+1));
       }
       int ans=n-i+1,top=0;
       while(q.top()>top){
           top++;
           int x=q.top();
           q.pop();
           q.push(x-1);
           ans++;
       }
       cout<<ans<<"\n";return ;
   }
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

D：

30次，可以去往位运算靠

然后从低位到高位去思考

假设要找当前第 i 位是不是1怎么判断呢

因为我们是从低位到高位去思考，所以当前低位的二进制我们都知道了，我们先减去他

然后当前 i-1到0位的二进制都是0了

我们只需要在第i位去加一个2^i

如果第i位是1，那么就会进位到i+1，否则不会进位,第i位通过我们添加一个2^i后会存在2^i

然后这个时候我们直接去用一个数去判断 当前gcd是不是2^(i)即可，是的话就不是

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,mod=998244353,K=5e5;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;

int a[N];
int ask(int x,int y){
	printf("? %lld %lld\n",x,y);
	cout.flush();
	int z;cin>>z;
	return z;
}

void solve()
{
   //cin>>n;
		int ans=0;
		for(int i=1;i<=30;i++){
			int x=ask((1<<(i-1))-ans,(1<<i)+(1<<(i-1))-ans);
			if(x%(1<<(i))==0)
				ans=ans+(1<<(i-1));
		}
		printf("! %lld\n",ans);
		cout.flush();
}
 
signed main()
{
   // cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

?

E：or的最小值只会出现在区间最小的31个数里面

即区间大小位len ，最小值出现在最小的log(len)+1的数中

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,mod=998244353,K=5e5;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
PII tr[N*4];
int a[N];
void modify(int u,int l,int r,int x,int val){
    if(l==r) {
        tr[u]={val,x};
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid) modify(u<<1,l,mid,x,val);
    else modify(u<<1|1,mid+1,r,x,val);
    tr[u]=min(tr[u<<1],tr[u<<1|1]);
}
pair<int,int> query(int c,int l,int r,int x,int y){
	int mid=l+r>>1;
	if(l==x&&r==y) return tr[c];
	else if(y<=mid) return query(c*2,l,mid,x,y);
	else if(x>mid) return query(c*2+1,mid+1,r,x,y);
	else return min(query(c*2,l,mid,x,mid),query(c*2+1,mid+1,r,mid+1,y));
}

void solve()
{
   cin>>n;
   for(int i=1;i<=n;i++) cin>>a[i];
   for(int i=1;i<=n;i++)
    modify(1,1,n,i,a[i]);
    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        vector<PII> now; 
        int lim=min(r-l+1,31ll);
        for(int i=1;i<=lim;i++){
            now.push_back(query(1,1,n,l,r));
            modify(1,1,n,now.back().second,1ll<<31);
        }
        int mn=1ll<<31;
        for(int i=0;i<now.size();i++){
            for(int j=i+1;j<now.size();j++)
                mn=min(mn,now[i].first|now[j].first);
        }
        cout<<mn<<"\n";
        for(auto [p,v]:now){
            modify(1,1,n,v,a[v]);
        }
    }
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}