（cf）Codeforces Round #825 (Div. 2)ABC（BC详细解释）

目录

A. Make A Equal to B

 B. Playing with GCD

 C1. Good Subarrays (Easy Version)

---

这一场wa了n发，醉了，明天再补一场

A. Make A Equal to B

You are given two arrays aa and bb of nn elements, each element is either 00 or 11.

You can make operations of 22 kinds.

• Pick an index ii and change aiai to 1−ai1−ai.
• Rearrange the array aa however you want.

Find the minimum number of operations required to make aa equal to bb.

Input

Each test contains multiple test cases. The first line contains a single integer tt (1≤t≤4001≤t≤400) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤1001≤n≤100) — the length of the arrays aa and bb.

The second line of each test case contains nn space-separated integers a1,a2,…,ana1,a2,…,an (aiai is 00 or 11), representing the array aa.

The third line of each test case contains nn space-separated integers b1,b2,…,bnb1,b2,…,bn (bibi is 00 or 11), representing the array bb.

Output

For each test case, print the minimum number of operations required to make aa equal to bb.

 比较简单，不详细说了

#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N],b[N];
int main()
{
    int t;
    cin>>t;
    int n;
    while(t--)
    {
        scanf("%d",&n);
        int cnt1=0,cnt0=0,cnt11=0,cnt00=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]==1)
            cnt1++;
            else cnt0++;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            if(b[i]==1)
            cnt11++;
            else cnt00++;
        }
        int minn=abs(cnt11-cnt1)+1;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=b[i])
            cnt++;
        }
        printf("%d\n",min(minn,cnt));
    }
    return 0;
}

 B. Playing with GCD

You are given an integer array aa of length nn.

Does there exist an array bb consisting of n+1n+1 positive integers such that ai=gcd(bi,bi+1)ai=gcd(bi,bi+1) for all ii (1≤i≤n1≤i≤n)?

Note that gcd(x,y)gcd(x,y) denotes the greatest common divisor (GCD) of integers xx and yy.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1051≤t≤105). Description of the test cases follows.

The first line of each test case contains an integer nn (1≤n≤1051≤n≤105) — the length of the array aa.

The second line of each test case contains nn space-separated integers a1,a2,…,ana1,a2,…,an representing the array aa (1≤ai≤1041≤ai≤104).

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output

For each test case, output "YES" if such bb exists, otherwise output "NO". You can print each letter in any case (upper or lower).

题意：给你长度为n的数组a，问你能不能构造出一个长度为n+1的序列b，使每个a[i]=gcd(b[i],b[i+1]),输出NO,YES;

思路：因为a[i]=gcd(b[i],b[i+1]),a[i+1]=gcd(b[i+1],b[i+2]),所以b[i+1]是a[i]和a[i+1]的公倍数，同时因为b和a之间是最大公因数的关系，所以反过来说b[i+1]应该是a[i]和a[i+1]的最小公倍数。

所以我们可以先根据这个构造一个b序列，然后反过来看b序列是不是a的最大公因数。

需要注意一点，b[1]的值要构造为a[1],b[n+1]的值构造为a[n],因为一个数最大的因子就是他自己。

#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N];
int b[N];
int f(int x,int y)
{
    return x*y/__gcd(x,y);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        b[1]=a[1];
        for(int i=2;i<=n;i++)
        {
            b[i]=f(a[i-1],a[i]);
        }
        b[n+1]=a[n];
        int i;
        for(i=1;i<=n;i++)
        {
            if(a[i]!=__gcd(b[i],b[i+1]))
            {
                break;
            }
        }
        if(i<=n)
        printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

 C1. Good Subarrays (Easy Version)

This is the easy version of this problem. In this version, we do not have queries. Note that we have multiple test cases in this version. You can make hacks only if both versions of the problem are solved.

An array bb of length mm is good if for all ii the ii-th element is greater than or equal to ii. In other words, bb is good if and only if bi≥ibi≥i for all ii (1≤i≤m1≤i≤m).

You are given an array aa consisting of nn positive integers. Find the number of pairs of indices (l,r)(l,r), where 1≤l≤r≤n1≤l≤r≤n, such that the array [al,al+1,…,ar][al,al+1,…,ar] is good.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤2⋅1051≤t≤2⋅105). Description of the test cases follows.

The first line of each test case contains an integer nn (1≤n≤2⋅1051≤n≤2⋅105), the length of the array aa.

The second line of each test case contains nn space-separated integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n), representing the array aa.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, print the number of suitable pairs of indices.

题意： 给你一个长度为n的序列，要是一段序列里面对于每一个a[i]的值都>=i,那么这就是一个好序列，问你一个序列里面有多少个好序列。

每一段序列的从下标1开始。

思路：双指针法，一个指针i表示序列的开始位置，一个指针j表示  序列的结束位置-1，我们可以看出，如果序列长的时候（或者说开始位置离他远的时候）这个数是好的，那么序列短的时候它也一定是好的。

所以我们只要让指针j一直往后判断就可以了。

#include 
using namespace std;
const int N=200010;
int a[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int k;
        for(int i=1;i<=n;i++)
        {
            k=i;
            if(a[i]
            {
                break;
            }
        }
        if(k==n&&a[n]>=n)
        k++;//k指向的永远是当前第一个不满足条件的数的下标，如果超过n就指向n+1。
        long long int ans=0;
        k=max(2,k);//k最小是2
        for(int i=1;i<=n;i++)
        {
            while(k<=n)
            {
                if(a[k]+i-1>=k)
                k++;
                else break;
            }
            ans+=k-i;
            if(k==i+1)//这里防止k指针跑到i前面的情况
            k++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}