Codeforces Round #769 (Div. 2) C D

传送门：

C. Strange Test

D. New Year Concert

C题意：跟你两个数a，b满足a

操作一：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
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=0;i--)
			{
				if((b>>i)&1)
				{
					b1^=(1<>i)&1)
					{
						b1^=(1< 

D题意：定义bad区间为gcd[l,r]==r-l+1，要使得区间内没有bad子区间，最少需要将几个数变为其他任何数。
 
分析：首先对于区间gcd有：对于固定左端点L,向右移动右端点R的区间[L,R]，区间gcd是非递增的。故对于左端点为L的区间来说，bad区间至多有一个。对于此题，我们可以固定R（遍历R），对L，R用双指针来做。
 
代码：
 
#include
using namespace std;
const int maxlog=20;
const int maxn=200005;
int table[maxn][maxlog];
int n;

void pre()
{
	for(int st=1;(1<>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