【CF】#844 div1 T1~T4复健

高考结束，我的人生即将迈入新的阶段。记得哪位退役学长说的话，尽管努力不够，天赋不足，但走进大学校园，我仍将拾起键盘。

所以打了场cf比赛，没想到前几道题都不涉及算法板子，但断断续续做了好几天也才做了四个题。T5终于忍不住找了题解，一看是二分图可惜早已忘光，做不出来。

前四道题不涉及具体的算法，非常适合复健。

T1

题意大概为二人取数，每次取数可取a或者b个(a<b)，没法取的人输掉。问最开始的数是多少的时候后手赢。

乍看是博弈论，实际上是文字游戏，因为先手一开始就取不到就算后手赢。。

所以，a>1的情况下答案就是1，a=1的时候答案就是2 。

T2

给出正整数1~n，其中要求尽可能多的存在mex为质数的区间(l,r)，问如何排列。

这道题还蛮难想的，看到标签有数学想推导出什么结论，发现：

情急之下只能贪心了，根据引理1，1一定在中心，然后直接让质数、合数分别根据贡献从外到内排列，最后处理奇偶问题。

没想到居然一次过了。

#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <algorithm>

#define INF 2147483647
#define MAX 200005
//引理1：符合要求的序列必定包含1
//引理2：越小的质数被包含的次数越少，贡献越大
//引理3：越小的合数被包含的次数越多，贡献越大
//
//因此，可以试作如下策略：
//总使1在中间，将质数从两侧从小到大向中间排列
//然后，将合数从1两侧从小到大向两侧排列。

int prime[MAX],cnt;
bool isprime[MAX];
int n;

int ans[MAX];

void getprime(){
    for(int i = 2;i <= n;i ++){
        if(!isprime[i])
            prime[cnt++] = i;
        for(int j = 0; j < cnt && i*prime[j] <= n;j ++){
            isprime[i*prime[j]] = true;
            if(i % prime[j] == 0){
                break;
            }
        }

    }        

}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        memset(isprime,0,sizeof(isprime));
        cnt = 0;
        scanf("%d",&n);
        if(n == 1){
            printf("1\n");
            continue;
        }
        if(n == 2){
            printf("1 2\n");
            continue;
        }
        getprime();
        int side = 0;//0=left,1=right
        int pcnt[2] = {1,n};
        int mid = n/2+1;
        int npcnt[2] = {mid-1,mid+1};

        int pnum = 0;
        for(int i = 2; i <= n; i ++){
            if(!isprime[i]){
                pnum ++;
                ans[pcnt[side]] = i;
                if(side == 0)
                    pcnt[side] ++;
                else
                    pcnt[side] --;
            
                side = side^1;
            }
        }

        if(n%2 != 0 && pnum%2 != 0) side = 1;
        else if(n%2 != 0 && pnum%2 == 0) side = 0;
        else if(n%2 == 0 && pnum%2 != 0) side = 0;
        else if(n%2 == 0 && pnum%2 == 0) side = 0;

        for(int i = 4; i <= n; i ++){
            if(isprime[i]){
                ans[npcnt[side]] = i;
                if(side == 0)
                    npcnt[side] --;
                else
                    npcnt[side] ++;
            
                side = side^1;
            }
        }
        ans[mid] = 1;
        for(int i = 1; i<= n ; i++)
            printf("%d ",ans[i]);
        printf("\n");

    }    
    return 0;
}

打这段代码的时候手非常流畅，因为思考过很久，所以直接就实现出来了，一次报错都没有。

T3

给出长度为n的整数序列，可以对它其中一个元素进行如下操作：

删除它，然后将它两侧的元素合并相加为一个元素；如果它在序列一侧，那么只删除它。

若干次操作后，问你剩下的唯一一个元素的最大值。

看着好像是dp，但画了几个图发现，无论如何操作，最后剩下的那个元素的前身全部都是原序列中的奇次项，或全都是原序列中的偶次项。

所以事情就简单了，分别计算奇次项和偶次项的和，计算时把其中负的扔掉，注意如果全是负的答案就是0 。最后比较和的大小即可。

T4

给定一个字符串的长度n，n的所有因数为a1,a2,a3...，要求对于所有 ai * (n/ai)的矩阵，构造一个字符串，使得其中的字符按照从左到右从上到下的顺序填进矩阵时，没有相邻单元的字符相同。

看着很唬人，其实是个填色问题。要想让相邻的字符不同，最好的办法就是所有的排列错开。怎么办呢？先考虑简单的情况。

只考虑行之间的情况，

如果列数是奇数，那么两个不同字符交替排列即可错开。

如果列数是偶数，那么三个不同字符交替排列即可错开。

从以上情况发现，如果要列数为奇数、偶数的都错开，那么可以考虑与n的互质数。问题转化为求n的最小互质数。

考虑到字符最多只有26个，并且我打了个表发现，某数的最小互质数往往比它本身少若干数量级。

例如，要想让某数x的最小互质数是26，就需要x > 2*3*5*7*11*17*19*23。这远远超出题目所要求的10^6 。

所以，可以放心使用最小互质数个字符交替排列即可得到答案。