Codeforces Round #769 (Div. 2) (A~D)

手速场，淦！直接寄汤来了。

u1s1这场真的挺难的感觉，打的时候E真的没什么好思路，而且被C卡了下。

A. ABC（思维+暴力）

我们可以发现对于n>=3的情况代表庇佑两个数相同，那么一定能组成回文串

因此只需讨论n=1、2的情况即可

#include 
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define Ma 1000005
#define mod 1000000007
using namespace std;
ll a[Ma];


int main()
{
	ll tt;
	scanf("%lld",&tt);
	while (tt--)
	{
		ll n;
		cin>>n;
		string s;
		cin>>s;
		ll x=0,y=0;
		for (ll i=0;i 
B. Roof Construction (思维)
 
我们可以把这些数转换成二进制，假设所有数中最多有k位，我们可以将其分为第k位为0/1的两类数，因此他的最小值将>=(1<<(k-1))，因此我们只需将0与(1<<(k-1))作为两类数的链接口即可 
 
#include 
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define Ma 1000005
#define mod 1000000007
using namespace std;
ll a[Ma];


ll lowbit(ll x)
{
	return x&(-x);
}

ll ask(ll x)
{
	while (x!=lowbit(x))
		x-=lowbit(x);
	return x;
}

int main()
{
	ll tt;
	scanf("%lld",&tt);
	while (tt--)
	{
		ll n;
		scanf("%lld",&n);
		ll y=ask(n-1);
		for (ll i=y+1;i 
 
 C. Strange Test(思维+贪心)
 
首先操作的顺序最优一定是2、1、3，因此我们对b进行枚举计算即可
 
时间复杂度o(1e6<<2)
 
 
 
#include 
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define Ma 1000005
#define mod 1000000007
using namespace std;
ll x,y;

ll ask(ll a,ll b)
{
	ll cmp=b,ans=0;
	for (ll i=30;i>=0;i--)
		if (b&(1ll< 
D. New Year Concert(线段树/st表+二分)
 
U1S1交这题的时候真的很没有把握，因为算出来复杂度是O(nlogn(loglogn))，感觉会炸，但最后还是过了。
 
首先我们可以发现对于已经满足条件的[1,l]上，我们只需判断l+1是否满足即可
 
若l+1不满足，就将其修改（变成完美数，即对于任意gcd都为1（除本身））
 
若l+1满足，就进行以上操作
 
因此该题为贪心操作，但对于判断，我们发现r-l+1呈递增，gcd([l,r])呈递减，且符合条件的点最多只有1个，因此可以进行二分查询，对于gcd（[l,r]）可用线段树/st表/莫队进行
 
#include 
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define Ma 1000005
#define mod 1000000007
using namespace std;
ll a[Ma];
ll le=1,ans=0;

struct node
{
	ll l,r,w;
}t[Ma];


void build(ll p,ll l,ll r)
{
	t[p].l=l,t[p].r=r;
	if (l==r)
	{
		t[p].w=a[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	t[p].w=__gcd(t[ls].w,t[rs].w);
	return;
}

ll ask(ll p,ll l,ll r)
{
	if(l<=t[p].l&&r>=t[p].r)return t[p].w;
	ll mid=(t[p].l+t[p].r)>>1;
	ll val=0;
	if(l<=mid)val=__gcd(val,ask(ls,l,r));
	if(r>mid)val=__gcd(val,ask(rs,l,r));
	return val;
}

void sol(ll l,ll r)
{
	ll rp=r;
	while (l<=r)
	{
		ll mid=(l+r)>>1;
		ll w=ask(1,mid,rp);
		if (w>rp-mid+1)
			r=mid-1;
		else 
			l=mid+1;
	}
	if (ask(1,r,rp)==rp-r+1)
	{
		ans++;
		le=rp+1;
	}
	return;
}


int main()
{
	ll n;
	scanf("%lld",&n);
	for (ll i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	build(1,1,n);
	for (ll i=1;i<=n;i++)
	{
		sol(le+1,i);
		printf("%lld ",ans);
	}
	return 0;
}
 
PS：又要掉大分了