ZJT's Blog

Keep your determination.

集训队作业之AGC018-F

2017-12-18 12:312017-12-18 12:31
集训队作业AtCoder构造二分图

传送门

首先我们可以直接根据每个点的儿子个数来确定这个点权值的奇偶性。如果某个点在两棵树里的奇偶性不一样,则显然无解。否则,我们可以通过以下方法构造出一组解,使得权值为偶数的点全部取$0$,剩下的点要么是$1$要么是$-1$。

对于每棵树,我们可以把所有奇数的点两两配对(由于奇数点的数量是奇数,所以会剩下一个点不参与配对),使得对于每棵子树,设子树中的奇数点有$2k+1$个,我们都可以在子树中找出$k$对配对的奇数点(还有一个点没有在子树内部配对)。则我们可以钦定每对点一个取$1$,一个取$-1$,这样每个子树的权值和的绝对值就是$1$了。

我们把两棵树的配对情况都拿出来连边,这样建出来的图显然是不含奇环的,所以是个二分图。我们直接把二分图左边的点赋成$1$,右边的点赋成$-1$,就能满足条件了。

#include <cstdio>
#include <cstring>
#define MAXN 1000010

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN];

int n,root;
int g[MAXN],nume;
int e2[MAXN][2],nume2;
int d[MAXN],d0[MAXN];
int c[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

int dfs(int x){
    int cnt=0;
    int last=0;
    for(int i=g[x];~i;i=e[i].next){
        cnt^=1;
        int temp=dfs(e[i].to);
        nume2++;
        if(last){
            e2[nume2][0]=last;
            e2[nume2][1]=temp;
            last=0;
        }else last=temp;
    }
    if(!last) last=x;
    d[x]^=cnt;
    d0[x]=cnt;
    return last;
}

void dfs2(int x){
    for(int i=g[x];~i;i=e[i].next)
        if(!c[e[i].to]){
            c[e[i].to]=-c[x];
            dfs2(e[i].to);
        }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d",&n);
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        if(t!=-1) addEdge(t,i);
        else root=i;
    }
    dfs(root);
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        if(t!=-1) addEdge(t,i);
        else root=i;
    }
    dfs(root);
    for(int i=1;i<=n;i++)
        if(d[i]){
            puts("IMPOSSIBLE");
            return 0;
        }
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=1;i<=nume2;i++)
        addEdge(e2[i][0],e2[i][1]),addEdge(e2[i][1],e2[i][0]);
    for(int i=1;i<=n;i++)
        if(!d0[i] && !c[i]){
            c[i]=1;
            dfs2(i);
        }
    puts("POSSIBLE");
    for(int i=1;i<=n;i++)
        if(d0[i]) printf("0 ");
        else printf("%d ",c[i]);
}

查看详细内容

集训队作业之AGC016-C

2017-11-27 13:552017-11-27 14:18
集训队作业AtCoder构造

传送门

这题被我乱搞过掉了。。。记$x=\frac{10^9-1}{wh-1}$,我们在每个$w|i,h|j$的$(i,j)$里面放一个$-(wh-1)x-1$,剩下都放$x$。如果这样放之后总和小于等于0,就说明无解。这个做法的依据大概就是“$10^9$足够大”这个信念吧(雾)。

#include <cstdio>
#include <cstring>
#define MAXN 510
#define LL long long

int W,H,w,h;
LL a[MAXN][MAXN];

int main(){
    scanf("%d%d%d%d",&H,&W,&h,&w);
    if(w*h==1){
        puts("No");
        return 0;
    }
    LL x=999999999/(h*w-1);
    LL s=0;
    for(int i=1;i<=H;i++)
        for(int j=1;j<=W;j++){
            if(i%h || j%w) a[i][j]=x;
            else a[i][j]=-(x*(w*h-1)+1);
            s+=a[i][j];
        }
    if(s<=0) puts("No");
    else{
        puts("Yes");
        for(int i=1;i<=H;i++){
            for(int j=1;j<=W;j++)
                printf("%lld ",a[i][j]);
            puts("");
        }
    }
}

查看详细内容

集训队作业之AGC004-C

2017-10-9 20:72017-10-9 20:7
集训队作业AtCoder构造

传送门

感觉已经没有智商做这种构造题了。。。硬是YY了半天才想到一个靠谱的做法。

直接把第一行全染红,最后一行全染蓝,然后中间每隔一列换个颜色,要求紫色的就都染,这样就能保证联通了。

代码:

#include <cstdio>
#include <cstring>
#define MAXN 510

int n,m;
int a[MAXN][MAXN];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        static char str[MAXN];
        scanf("%s",str+1);
        for(int j=1;j<=m;j++)
            if(str[j]=='#')
                a[i][j]=1;
    }
    for(int j=1;j<=m;j++) putchar('#');
    puts("");
    for(int i=2;i<n;i++){
        for(int j=1;j<=m;j++)
            if((j&1) || a[i][j]) putchar('#');
            else putchar('.');
        puts("");
    }
    for(int j=1;j<=m;j++) putchar('.');
    puts(""); puts("");
    for(int j=1;j<=m;j++) putchar('.');
    puts("");
    for(int i=2;i<n;i++){
        for(int j=1;j<=m;j++)
            if(((~j)&1) || a[i][j]) putchar('#');
            else putchar('.');
        puts("");
    }
    for(int j=1;j<=m;j++) putchar('#');
}

查看详细内容

集训队作业之AGC012-C

2017-9-25 18:102017-9-25 18:10
集训队作业AtCoder构造

传送门

构造不出来很痛苦啊。。。可能我的智商不太能做这样的题啊。。。?

实在构造不出来就看了题解。正解是大力构造,直接钦定答案是形如"$p_1,p_2,p_3,...,p_n,1,2,3,...,n$"的一串东西,其中$\{p_i\}$是$1$~$n$的一个排列。这样的话,重复子序列个数显然是这个排列中单调增的子序列的个数。

考虑往$1$~$n$的某个排列里面加入$n+1$会发生什么。设这个排列原先的单调增子序列个数是$s$,当在序列末尾加入$n+1$时,$s$会变成$2s+1$。而在最前面加入$n+1$时,$s$会变成$s+1$。然后就按照这个逆着推一遍,就得到了长度为$O(log(n))$的一个合法解。

代码:

#include <cstdio>
#include <cstring>
#include <deque>
#define LL long long
using namespace std;

LL n;
int d[210];
deque<int> S;

int main(){
    scanf("%lld",&n);
    int m=0;
    while(n){
        if(n&1){
            n=(n-1)/2;
            d[++m]=1;
        }else{
            n--;
            d[++m]=0;
        }
    }
    for(int i=m;i>=1;i--)
        if(d[i]) S.push_back(m-i+1);
        else S.push_front(m-i+1);
    printf("%d\n",m<<1);
    for(int i=0;i<m;i++)
        printf("%d ",S[i]);
    for(int i=1;i<=m;i++)
        printf("%d ",i);
}

查看详细内容