[数据结构与算法]Codeforces Round #769 (Div. 2) C D

传送门：

C. Strange Test

D. New Year Concert

C题意：跟你两个数a，b满足a<b，现在有三种操作：

操作一：a++

操作二：b++

操作三：a|=b

求使得a=b的最小操作次数。

分析：首先看看操作三是什么：

1.操作三会使得a变大（+0）。

2.完成操作三之后，a>=b。此时要使得a=b，只能进行操作二。

3.要使得操作次数最少，操作三最多使用一次。

我们分类讨论：

1.如果不用操作三：那么操作次数即为b-a。

2.如果用操作三：我们可以在a1，b1（a1>=a,b1>=b）等于任意值时操作。操作次数为a1-a+b1-b+1+(a1|b1)-b1=a1+(a1|b1)+1-a-b，其中1-a-b是常数，我们需要最小化a1+(a1|b1)。考虑枚举a1，b1按a1和b的位分类讨论（以下b1，a1，b均为从高到低的当前位）：

b=1,a1=1,b1=1

b=1,a1=0,b1=1

b=0,a1=0,b1=0

b=0,a1=1,b1=1,break;

代码：

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

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int a,b;
		cin>>a>>b;
		int ans=b-a;
		for(int a1=a;a1<b;a1++)
		{
			int b1=0;
			for(int i=21;i>=0;i--)
			{
				if((b>>i)&1)
				{
					b1^=(1<<i);
				}
				else
				{
					if((a1>>i)&1)
					{
						b1^=(1<<i);
						break;
					}
				}
			}
			ans=min(ans,a1+(a1|b1)+(1-a-b));
		}
		cout<<ans<<endl;
	}
}

D题意：定义bad区间为gcd[l,r]==r-l+1，要使得区间内没有bad子区间，最少需要将几个数变为其他任何数。

分析：首先对于区间gcd有：对于固定左端点L,向右移动右端点R的区间[L,R]，区间gcd是非递增的。故对于左端点为L的区间来说，bad区间至多有一个。对于此题，我们可以固定R（遍历R），对L，R用双指针来做。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxlog=20;
const int maxn=200005;
int table[maxn][maxlog];
int n;

void pre()
{
	for(int st=1;(1<<st)<=n;st++) 
	{
        for(int i=1;i+(1<<st)-1<=n;i++)
		{
            table[i][st]=__gcd(table[i][st-1],table[i+(1<<(st-1))][st-1]);
        }
    }
}

int get_gcd(int l, int r) 
{
    int st=__lg(r-l+1);
    return __gcd(table[l][st],table[r-(1<<st)+1][st]);
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>table[i][0];
	}
	pre();
	int ans=0;
    int maxr=0;
    int p=1;
    for(int i=1;i<=n;i++)
	{
        while(p<i&&get_gcd(p,i)<i-p+1) p++;
        if(get_gcd(p,i)==i-p+1)
		{
			if(p<=maxr) continue;//如果bad区间的左端点p在maxr之前 显然是个假的bad区间 
            ans++;
            maxr=i;//修改a[i]使其变成一个大素数 maxr之前的区间都不存在bad子区间 
        }
        cout<<ans<<" ";
    }
}