Codeforces Round #735 (Div. 2)

https://codeforces.com/contest/1554

A. Cherry

枚举相邻两个乘积即可。

#include <bits/stdc++.h>
using namespace std;

int n,k;
long long a[100005];

void solve()
{
	scanf("%d",&n)	;
	for (int i=1; i<=n; i++) {
		scanf("%lld",&a[i]);
	}
	long long ans=-1;
	for (int i=1; i<n; i++) {
		ans=max(ans,a[i]*a[i+1]);
	}
	printf("%lld\n",ans);
}


int main()
{
	int ttt;
	scanf("%d",&ttt);
	while (ttt--) {
		solve();
	}
	return 0;
}
 
           

B. Cobb

因为 k 很小，所以 i,j 应该大一点才有可能是答案。枚举大一点的 i,j 即可。

#include <bits/stdc++.h>
using namespace std;

int n,k;
long long a[100005];

void solve()
{
	scanf("%d%d",&n,&k)	;
	for (int i=1; i<=n; i++) {
		scanf("%lld",&a[i]);
	}
	long long ans=2-k*(a[1]|a[2]);
	
	// i*j >= n*(n-2*k-1)
	for (long long i=max(1,n-2*k-1); i<=n; i++) {
		long long mj=max(i+1,n*(n-2*k-1)/i-5);
		for (long long j=n; j>=mj; j--) {
			ans=max(ans,i*j-k*(a[i]|a[j]));
		}
	}
	
	/*
	for (long long i=n,ii=0; ii<3000 && i>0; ii++,i--) {
		for (long long j=i+1; j<=n; j++) {
			ans=max(ans,i*j-k*(a[i]|a[j]));
		}
	}
	*/
	printf("%lld\n",ans);
}


int main()
{
	int ttt;
	scanf("%d",&ttt);
	while (ttt--) {
		solve();
	}
	return 0;
}
 
           

C. Mikasa

我这里有两种做法。

第一种是类似树状数组那样分段。我们要求的是 0~m 模 n 的所有值，那么会发现，像

xxx00..0~xxx11..1

这样一个连续区间，模完 n 后所得的集合也是一个连续的区间（前缀相同，后缀是全排列）。那么分出多个这样的连续区间，就变成一个线段覆盖，求最小的没被覆盖到的数的问题了。

#include <bits/stdc++.h>
using namespace std;

long long n,m;

inline long long lowbit(long long x)
{
	return x&(-x);
}

struct node {
	long long l, r;
	node(long long ll, long long rr): l(ll),r(rr) {}
	bool operator< (const node& B) const
	{
		return l==B.l ? r<B.r : l<B.l;
	}
};

void solve()
{
	vector<node> Q;
	scanf("%lld%lld",&n,&m);
	
	if (m<n) {
		puts("0");
		return;
	}
	if (n==0 && m==0) {
		puts("1");
		return;
	}
	if (n==0) {
		printf("%lld\n",m+1);
		return;
	}
	
	while (m>0) {
		long long L,R,LL,RR;
		L=m+1-lowbit(m+1);
		R=m;
		
		if (L!=R) {
			LL=(~(L^R))&(L^n);
			RR=((~(L^R))&(L^n))+(R-L);
		}
		else {
			LL=RR=L^n;
		}
		
		Q.push_back(node(LL,RR));

		m-=lowbit(m+1);
		//printf("[%lld %lld]  (%lld %lld)\n",L,R,LL,RR);
	}
	
	sort(Q.begin(),Q.end());
	int N=Q.size();
	int p=0;
	long long ans=0;
	while (1) {
		while (p<N && Q[p].r<ans)
			p++;
		if (p>=N || Q[p].l>ans) {
			printf("%lld\n",ans);
			return;
		}
		ans=Q[p].r+1;
	}
}


int main()
{
	int ttt;
	scanf("%d",&ttt);
	while (ttt--) {
		solve();
	}
	return 0;
}
           

另一种解法，就是要找最小的数异或 n 之后大于 m 。

#include <bits/stdc++.h>
using namespace std;


void solve()
{
	int n,m;
	int ans=2147483647;
	scanf("%d%d",&n,&m);
	
	for (int i=35,tmp; i>=0; i--) {
		tmp=((n^m)>>i)<<i;
		tmp^=(1ll<<i);
		
		if ((tmp^n)>m) {
			ans=min(ans,tmp);
		}
	}
	
	printf("%d\n",ans);
}


int main()
{
	int ttt;
	scanf("%d",&ttt);
	while (ttt--) {
		solve();
	}
	return 0;
}
 
           

D. Diane

唬人的题……看代码就懂了。

#include <bits/stdc++.h>
using namespace std;


void solve()
{
	int n;
	scanf("%d",&n);
	
	
	if (n<=6) {
		for (int i=0; i<n; i++) printf("%c",'a'+i);
		puts("");
		return;
	}
	
	int tmp=n/2;
	for (int i=1; i<=tmp; i++) printf("a");
	printf("b");
	for (int i=1; i<tmp; i++) printf("a");
	if (n%2==1) printf("c");
	puts("");
}


int main()
{
	int ttt;
	scanf("%d",&ttt);
	while (ttt--) {
		solve();
	}
	return 0;
}
           

E. You