CF-1110 (2019/02/08)

CF-1110

A. Parity

快速幂的思想，考虑最后一位即可

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll b,k;

ll a[100010];

int main(){

    scanf("%lld%lld",&b,&k);

    for(int i=0;i<k;i++)

        scanf("%lld",&a[i]);

    ll ans = 0;

    ll base = 1;

    for(int i=0;i<k;i++){

        ans = (ans+a[k-i-1]*base)%10;

        base = base*b%10;

    }

    if(ans%2)puts("odd");

    else puts("even");

    return 0;

}

可以再多想一想。

$$n = a_1\cdot b^{k-1} + a_2\cdot b^{k-2} + \cdots + a_{k-1} \cdot b + a_k$$

b为偶数时，n的奇偶性只与$a_k$ 有关
b为奇数时，$b^k$ 为奇数，所有n的奇偶性只与 a 序列中奇数个数有关。

#include<bits/stdc++.h>

using namespace std;

int b,k,i,x,y;

int main(){

    for(cin>>b>>k;i<k;i++)

        cin>>x,y+=x%2;

    cout<<((b%2?y%2:x%2)?"odd":"even");

}

B. Tape

n == k 时直接输出 n 就好

n <= k 时，一些点要合并，由于合并产生的操作可能会使一段上面有多个点，所以我们要先把 k 个点都用长度为 1 的去填好。之后合并的时候只需要考虑点与点之间的距离即可（YY一下，你就知道）

当 k 等于 n，则直接输出 n
当 k 小于 n，则先把k段用长度为1补齐，再加上 (n-k) 段比较小的距离。

#include <bits/stdc++.h>

using namespace std;

int n,m,k;

int a[100010];

int main(){

    scanf("%d%d%d",&n,&m,&k);

    for(int i=0;i<n;i++)

        scanf("%d",&a[i]);

    for(int i=n-1;i>0;i--)

        a[i] = a[i]-a[i-1];

    sort(a+1,a+n);

    int ans = k;

    for(int i=1;i<=(n-k);i++)

        ans += a[i];

    cout<<ans<<endl;

    return 0;

}

C. Meaningless Operations

根据 Note 可以得知只要凑出一个 0 ，就可能得到最大的gcd。

当 $a\neq (2^x -1)$ , 则一定可以找到一个 b 使得
- $ a \oplus b = 2^x -1$ , $a \& b = 0$
当 $a = (2^x - 1)$ ，则可以发现

$$gcd( a\oplus b, a&b) = gcd(2^x-1-b,b) = gcd(2^x-1,b)$$
- 因为 $gcd(x,x+y) = gcd(x,y)$
- 所以只需要找到 a 的最大因数（非a) 即可。
复杂度$O(q\sqrt m)$ 。但是可以打表做（也可以直接暴力求）

#include <bits/stdc++.h>

using namespace std;

int po[30];

int res[30] = {0,1,1,1,5,1,21,1,85,73,341,89,1365,1,5461,4681,21845,1,87381,1,349525,299593,1398101,178481,5592405,1082401,22369621};

void init(){

    po[0] = 1;

    for(int i=1;i<30;i++)

        po[i] = po[i-1]*2;

}

bool check(int x){

    for(int i=1;i<30;i++)

        if(x==po[i]-1)

            return true;

    return false;

}

int calc(int x){

    int num =0;

    while(x)

    {

        x/=2;

        num++;

    }

    return num;

}

int main(){

    init();

    int q;

    cin>>q;

    while(q--){

        int n;

        cin>>n;

        if(check(n)){

            int num = calc(n);

            cout<<res[num]<<endl;

        }

        else{

            for(int i=1;i<30;i++){

                if(n>=po[i]&&n<po[i+1]){

                    cout<<po[i+1]-1<<endl;

                    break;

                }

            }

        }

    }

}

D. Jongmah

(好难的dp，其实早在 HDU-6188 就出现过了
首先这个题或许可以贪心，但是目前没找到正确的贪心策略（几乎都是dp

首先考虑什么状态（我不是自己想到的，但是知道这样做之后慢慢琢磨确实应该这么做

状态需要转移，那么我们需要保留那些结果？
d[i][j][k] ：j 个 [i-1,i,i+1] ，k 个 [i,i+1,i+2] 时的最大组合数
转移：d[i+1][k][l] = max( d[i+1][k][l], d[i][j][k] + l + (a[i+1]-j-k-l)/3) )
答案为d[m+1][0][0] ，（总长度为m）

#include <bits/stdc++.h>

using namespace std;

int n,m;

int a[1000100];

int d[1000100][3][3];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=0,x;i<n;i++){

        scanf("%d",&x);

        a[x]++;

    }

    int ans = 0;

    d[0][0][0] = 0;

    for(int i=0;i<=m;i++)

        for(int j=0;j<3;j++)

            for(int k=0;k<3;k++)

                for(int l=0;l<3&&l+k+j<=a[i+1];l++)

                    d[i+1][k][l] = max(d[i+1][k][l],d[i][j][k]+l+(a[i+1]-j-k-l)/3);

    cout<<d[m+1][0][0]<<endl;

    return 0;

}

E. Magic Stones

考虑差分：$d_i = c_{i+1} - c_i$

交换前后：$ c_j -> c_j^{’} = c_{j+1} + c_{j-1} - c_j$

$d_{j-1}^{'} = c_j^{'} -c_{j-1} = c_{j+1} + c_{j-1} - c{j} - c_{j-1} = c_{j+1}-c_j = d_j$
$d_j^{'} = c_{j+1}-c_j^{'} = c_{j+1} - (c_{j+1} + c_{j-1} -c_j) = c_j - c_{j-1} = d_{j-1}$

只需比较 c 和 d 的差分序列是否相同即可。等等，你还需要注意一点，头和尾是不能变化的

#include <bits/stdc++.h>

using namespace std;

int n;

int c[100010],d[100010];

multiset<int> s1,s2;

int main(){

    scanf("%d",&n);

    for(int i=0;i<n;i++){

        scanf("%d",&c[i]);

        if(i)s1.insert(c[i]-c[i-1]);

    }

    for(int i=0;i<n;i++){

        scanf("%d",&d[i]);

        if(i)s2.insert(d[i]-d[i-1]);

    }

    if(c[0]!=d[0]||c[n-1]!=d[n-1])puts("No");

    else if(s1==s2)puts("Yes");

    else puts("No");

    return 0;

}

summary ：

B题想太多了，一开始考虑合并覆盖点很复杂。看到过的人逐渐增多意识到自己想多了，直接莽了一发中了。至于证明时后来才想的
做C题时才发现自己原来不会打表。总共只有25个特殊数据直接一个数组搞定而我一开始却是在打表找规律？最后意识到太蠢之后竟然抄数字还抄错
D题dp，一言难尽。慢慢积累吧
E题差分，前几天刚做了差分，然而这道题当时没时间仔细想了。不过并不难的，看到序列中出现相邻作差的操作就要考虑差分了。

巴特西