Arc 135 supplementary report

​​​​​​AtCoder Regular Contest 135 - AtCoder

A - Floor, Ceil - Decomposition

This topic starts with recursion , Then there are a few points that can't pass , And then it's stuck all the time , I think we should use inverse yuan , Then it's too much trouble .

I looked at the code of my teammate ：

One was used map And the queue is done , Change recursion to non empty

#include <iostream>
#include <unordered_map>
#include <queue>
#define int long long
using namespace std;
const int mod = 998244353;

int x;
queue<int> q;
unordered_map<int,int> mp;

int qmi(int m, int k, int p)
{
	int res = 1;
	while(k)
		{
			if(k & 1) res = res * m % p;
			m = m * m % p;
			k >>= 1;
		}
	return res;
}

void solve()
{
	cin>>x;
	q.push(x);
	mp[x]=1;
	int ans = 1;
	while(!q.empty())
	{
		int a=q.front();
		int b = mp[a];
		q.pop();mp[a]=0;
		if(a>=5)
		{
			int m1 = (a + 1)/2;int m2 = a / 2 ;
			if(!mp[m1]) q.push(m1);
			if(!mp[m2]) q.push(m2);
			mp[m1] +=b,mp[m2]+=b;
		}
		else ans = ans * qmi(a,b,mod) % mod;
	}
	cout<<ans<<endl;
}

signed main() {
	solve();
	return 0;
}

B - Sum of Three Terms

First 1 Special judgment is made in this special case , And looking for a[1] Distance from other points , Being with you is actually 3 Choose the smallest of the three points in the back to see if it can form a group greater than 0 Of , If not, just NO

Then seek a[1], seek a[2];

#include <iostream>
#define int long long
using namespace std;
const int N = 3e5+10;
int S[N];
int a[N];
int x,y,z;
//s1,s2,s3
//s2-s1=
//
int presum[N];
signed main() {
	int n;cin>>n;
	for(int i=1;i<=n;i++) scanf("%lld",&S[i]);
	// A special case 
	if(n==1)
	{
		printf("Yes\n");
		printf("0 0 %lld",S[1]);
	}
	else{
		for(int i=2;i<=n;i++)
		{
			a[i+2]=a[i-1]+S[i]-S[i-1];
			//1+a[1]
			//1+a[2]
			//1+a[3]
			int j = i + 2;
			if(j % 3 == 1) x = min(x,a[j]);
			if(j % 3 == 2) y = min(y,a[j]);
			if(j % 3 == 0) z = min(z,a[j]);
		}
		if(S[1] + x + y + z < 0) {printf("No\n");}
		else{
			printf("Yes\n");
			a[1]=max(0LL,-x);
			a[2]=max(0LL,-y);
			a[3]=S[1]-a[1]-a[2];
			for(int i=4;i<=n+2;i++) a[i]=S[i-2]-a[i-1]-a[i-2];
			for(int i=1;i<=n+2;i++)
			{
				printf("%lld",a[i]);
				if(i!=n+2) printf(" ");
			}
			printf("\n");
		}
	}
	return 0;
}

C - XOR to All

Exclusive or , Preprocessing （ Put everyone 0 1 Count the number first ） Then just enumerate directly .

#include <iostream>
#define int long long
using namespace std;
const int N = 300010,M=32;

int n,a[N],bit[M],ans;
signed main() {
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];ans+=a[i];
		int tmp = a[i],tot=0;
		while(tmp)
		{
			if(tmp & 1) bit[tot]++;
			tmp>>=1;tot++;
		}
	}
		for(int i=1;i<=n;i++)
		{
			int sum = 0;
			for(int j=0;j<M;j++)
			{
				// Statistics 0 The number of and 1 The number of , then 0->1 The number of 
				//1->0 The number of 
				if((a[i]>>j) & 1) sum += (1<<j) * (n - bit[j]);
				else sum += (1<<j) * bit[j];
			}
			ans = max(ans,sum);
		}
	cout<<ans<<endl;
	return 0;
}