2020牛客暑期多校第六场 | Moonglade

G.Grid-Coloring

算法标签：构造

其实感觉是比较宽松的构造题，比赛的时候没想到判n==1的情况，调了一个多小时没发现，赛后加上就过了，有点伤。。我个人的思路是先用红蓝两种颜色染色，只要每行每列颜色都是交替的就肯定能满足条件了。

然后再用把某一部分蓝色或者红色改变成其他颜色，因为只要保证这个颜色只从蓝色或者只从红色改变而来，改变之后肯定还是满足条件的。

对于k是偶数的情况，恰好可以一半给蓝色，一半给红色，但对于k是奇数的情况，就不可避免会有一种颜色同时从蓝色红色改变而来。此时只需要考虑怎么安排这一种颜色就可以了。。答案是一半选择水平的蓝色，一半选择竖直的红色。对于剩下的，再按照k为偶数的情况分配即可。具体证明涉及一点数学计算，主要是奇偶性方面的，其实也不难推，这里就不浪费时间了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;

int col[N];

int n,k,T;

void sol()
{
    cin>>n>>k;
    int sum=2*n*(n+1);
    for (int i=1;i<=sum;i++) col[i]=0;
    if (sum%k!=0 || k==1 || n==1)
    {
        printf("-1\n");
        return;
    }

    int t1=1,t2=sum/2+1;
    if (k%2==1)
    {
        int tot=sum/k;
        for (int i=1;i<=tot/2;i++) col[i]=k,col[i+sum/2]=k;
        t1+=tot/2;
        t2+=tot/2;
    }
    for (int i=1;i<=k/2*2;i++)
    {
        if (t1<=sum/2)
        {
            for (int j=1;j<=sum/k;j++)
            {
                col[t1]=i;
                t1++;
            }
        }
        else
        {
            for (int j=1;j<=sum/k;j++)
            {
                col[t2]=i;
                t2++;
            }
        }
    }
    t1=1,t2=sum;
    int last=1;
    for (int i=1;i<=n+1;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (last==1)
            {
                printf("%d",col[t1]);
                if (j!=n) printf(" ");
                t1++;
                last=2;
            }
            else
            {
                printf("%d",col[t2]);
                if (j!=n) printf(" ");
                t2--;
                last=1;
            }
        }
        if (n%2==0) last=3-last;
        printf("\n");
    }
    last=1;
    for (int i=1;i<=n+1;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (last==1)
            {
                printf("%d",col[t1]);
                if (j!=n) printf(" ");
                t1++;
                last=2;
            }
            else
            {
                printf("%d",col[t2]);
                if (j!=n) printf(" ");
                t2--;
                last=1;
            }
        }
        if (n%2==0) last=3-last;
        printf("\n");
    }
}

int main()
{
    cin>>T;
    while(T--) sol();
    return 0;
}

H.Harmony-Pairs

算法标签：数位dp

正好有机会学一下数位dp。
数位dp总结 之 从入门到模板

之前一直望而却步，学了一下感觉其实也不是很难理解，但是做题要能熟练用就是另一回事了。

$dp[pos][del][eqb][eqa]$ pos表示当前的数位，del表示当前a和b数位和之差（避免负数取2500为零点），eqb表示当前B是否取到N的最大值，eqa表示当前A是否取到B的最大值。通过eqb和eqa决定转移时数位取值范围。这样一来最终的状态个数也是很有限的。

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;

int digit[20];
int dp[200][5000][2][2];
char n[200];

int dfs(int pos,int del,int eqb,int eqa)
{
    if (pos==-1)
    {
        if (del>2500)
            return 1;
        else return 0;
    }
    if (dp[pos][del][eqb][eqa]!=-1) return dp[pos][del][eqb][eqa];
    int upb=eqb?n[pos]:9;
    int sum=0;
    for (int b=0;b<=upb;b++)
    {
        for (int a=0;a<=(eqa?b:9);a++)
        {
            sum=(sum+dfs(pos-1,del+a-b,eqb&&(b==n[pos]),eqa&&(a==b)))%MOD;
        }
    }
    dp[pos][del][eqb][eqa]=sum;
    return sum;
}

int main()
{
    scanf("%s",n);
    int len=strlen(n);
    reverse(n,n+len);
    for (int i=0;i<len;i++) n[i]-='0';
    memset(dp,-1,sizeof(dp));
    printf("%d",dfs(len-1,2500,1,1));
    return 0;
}