Codeforces717 Div2

A题

题意：n个数，每次选择两个数，第一个数-1，第二个数+1，但要保证操作后两个数非负，最多操作k次，问最小的序列

解：前面能减则减

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int maxn = 2e3 + 10;
int t,n,k,a[maxn];
 
void solve()
{
    for(int i = 1;i < n; ++i)
    {
        if(k < a[i])
        {
            a[i] -= k;
            a[n] += k;
            break;
        }
        else
        {
            k -= a[i];
            a[n] += a[i];
            a[i] = 0;
        }
    }
    for(int i = 1;i <= n; ++i)
        printf("%d%c",a[i],i == n?'\n':' ');
}
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i = 1;i <= n; ++i) cin>>a[i];
        solve();
    }
    return 0;
}

B题

题意：n个数，每次选两个相邻的数x,y扔掉，然后放进去x^y,问最后能不能得到一个长度>=2的元素都相等的数组

解：刚开始没看到相邻wa了好久，异或和ans为0必然可以，否则就看ans在异或过程中出现过几次

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int maxn = 2e3 + 10;
int t,n,k,a[maxn],b[100],ans;
 
bool check()
{
    int s = 0,e = 0;
    for(int i = 1;i <= n; ++i)
    {
        s ^= a[i];
        if(s == ans)
        {
            e++;
            s = 0;
            if(e > 1) return 1;
        }
    }
    return 0;
}
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n;
        ans = 0;
        for(int i = 1;i <= n; ++i)
        {
            cin>>a[i];
            ans ^= a[i];
        }
        if(!ans || check()) printf("YES\n");
            else printf("NO\n");
    }
    return 0;
}

C题

题意：问怎删除序列里的数字，使得序列无法分成和相等的两部分

解：1）一个数组能否分成和相等的两部分

bool check()
{
    int x = sum / 2;   ///分成和都为x的两部分
    dp[0] = 1;
    for(int i = 1;i <= n; ++i) 
    {
        int u = x;
        while(u >= a[i])
            dp[u] += dp[u - a[i]],u--;
    }
    if(dp[x] >= 2) return 1;
}

2）和为奇数肯定不可以分成

没有想到的点是除最大公因数，因为想的是如果有奇数删奇数就可以，没有奇数的话就不知道该怎么处理，除了最大公因数之后，必然不会出现全部是偶数的现象。

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

int a[105],dp[200010];
int n,d;

int main()
{
	cin>>n;
	d = 0;
	for(int i=1;i<=n;i++)
    {
		scanf("%d",&a[i]);
		d = __gcd(d,a[i]);
	}
	int S = 0;
	for(int i=1;i<=n;i++) a[i]/=d,S += a[i];
	dp[0]=1;
	int id=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]&1)id=i;
		for(int j=S;j>=a[i];j--)dp[j]|=dp[j-a[i]];
	}
	if(S % 2==1||dp[S/2]==0)printf("0");
	else printf("1\n%d",id);
}

D题

题意：每次选择一个区间，将区间里的数分成若干个连续的区间，使每个区间内的lcm等于组内数的乘积，最少分成多少组

解：最少的组数肯定是出现次数最多的质数的出现次数（含有相同因子代表gcd不为1，肯定不能分到一组）

首先对于l，向右能扩展到r,那么对于L>l,扩展到的R>=r

所以我们可以用双指针用O(n)复杂度预处理每个数能向右扩展多远

问题转化为[l,r]中间包含多少个这样长的子区间

倍增处理 f[i][j] = f[f[i][j - 1] + 1][j - 1]

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

const int maxn = 1e5 + 10;
bool vis[maxn];
vector<int>v[maxn];
int a[maxn],prim[maxn],f[maxn][20];
int n,q,tot,l,r;

void init()   ///预处理
{
    vis[0] = vis[1] = 1;
    tot = 1;
    for(int i = 2;i <= 100000; ++i)
    {
        if(!vis[i]) prim[tot++] = i;
        for(int j = 1;j < tot && prim[j] * i <= 100000; ++j)
        {
            vis[prim[j] * i] = 1;
            if(i % prim[j] == 0) break;
        }
    }
    for(int i = 1; i < tot; ++i)
		for(int x = prim[i]; x <= 100000; x += prim[i])
			v[x].push_back(i);
}

int main()
{
    std::ios::sync_with_stdio(false);
    init();
    cin>>n>>q;
    memset(vis,0,sizeof(vis));
    for(int i = 1;i <= n; ++i) cin>>a[i];
    for(int i = 1,r = 0;i <= n; ++i)
    {
        for(; r < n; ++r)
        {
            int flag = 1;
            for(auto x: v[a[r + 1]])
            {
                if(vis[x])
                {
                    flag = 0;
                    break;
                }
            }
            if(!flag) break;
            for(auto x:v[a[r + 1]]) vis[x] = 1;
        }
        f[i][0] = r;
        for(auto x: v[a[i]]) vis[x] = 0;
    }
    for(int i = 1;i < 20; ++i)
        for(int j = 1;j <= n; ++j)
            if(f[j][i - 1]) f[j][i] = f[f[j][i - 1] + 1][i - 1];
    while(q--)
    {
        cin>>l>>r;
        int ans = 0,x = l;
        for(int i = 19;i >= 0;--i)
            if(f[x][i] && f[x][i] <= r)
                x = f[x][i] + 1,ans += 1 << i;
        cout<<ans + (x <= r)<<endl;
    }
    return 0;
}