UOJ Logo AntiLeaf的博客

博客

弱菜AntiLeaf的提答练习计划

2017-07-12 06:30:03 By AntiLeaf

还有几天就是NOI了,还有5个晚上可以在学校做题,这5个晚上我决定好好练习一下平常没怎么注意过的提答题,为NOI做准备。

计划每天晚上做一道题(为什么昨天没有呢?因为太颓了),为了防止自己偷懒,每做完一道题我会在这里发(我拿到的分的)伪题解。

同时为了防止偷懒,提前列好计划:

(后两道题还要感谢 @bzoj 的提醒)

(7.17和7.18的话……留出来敲板子和复习好了……)


7.12 UOJ#208 UOIP十合一

我的最后提交

我还是Naive……测试点6想到了答案就是$n$个点的有标号DAG个数,然而并没有记住$O(n^2)$的递推式怎么玩……不过要我手推$O(n^3)$的递推式的话还是不难的……

感觉新发一篇博客可能有点占UOJ博客的版面,那我还是都写在这里好了……

(感觉贴代码有点占地方,毕竟这里还要写好几天……所以就不贴代码了)

测试点1

一眼看去感觉像是出点编号$\le$入点编号,判了一发发现的确是对的,去掉自环就好了……

测试点2

观察一波之后感觉比较有规律,写个程序判一下发现每个弱连通块都正好有5个点10条边,那么对每个连通块分别暴力就行了。

测试点3

不难发现每个点恰有一条出边,那么找出所有的环之后对每个连通块减去选环的方案数再乘起来就行了……

测试点4

这个……因为一眼看着感觉没什么规律,就没往分层图上想……

我还是Naive了啊……第二次被分层图坑了……(上一次是UOJ#259 子集计数问题

测试点5

一眼看上去也没啥规律,不过反正我在做测试点2的时候写了一个Tarjan,直接搬过来判一下发现每个SCC的边数都很少,那么对每个SCC暴力之后乘起来,最后乘上不属于SCC内部的边的贡献就行了。

测试点6

一眼看过去发现是一个$n=100$的完全图,但是一开始NC了,没发现答案就是$n$个点的有标号DAG个数……不过瞎xx暴力了前几项之后发现一个熟悉的数字:543……这个数好像在我写DAG计数的时候见过,那看来答案就是$n$个点的有标号DAG个数了。

然而我是在最后才想起来答案就是这个的,并没有时间再写$O(n^3)$的DP了……有点可惜。

(设$f_{i,j}$表示$i$个点且有$j$个点入度为0的DAG个数,转移的时候瞎xx搞一搞就能搞出$O(n)$的转移了)

测试点7~10

……后4个测试点以我现在的能力是做不出来的……(我没写过测试点7这种类型的子集DP……)

所以……略吧(逃

总结

其实前6个测试点对我来说都是很可做的范围的……然而最后只拿到了40分,看来自己提答经验还是不够,并且做的实在太慢了。

没关系,今晚上还有UOJ#215 【UNR #1】果冻运输,再接再厉……

ps:一会儿还要去UNR……


7.13 UOJ#215 【UNR #1】果冻运输

我的最后提交

这题……有毒……

真的没啥可写的……我的分都是纯手玩……

玩了两个小时只玩出了40分……主要是因为没有直接看一遍所有数据,早知道都这么小我就去写暴搜了啊QAQ……

ps:这种考察选手玩游戏能力的题真的好吗QAQ……


7.14 UOJ#109 【APIO2013】TASKSAUTHOR

我的最后提交

因为某些事情耽误了一点时间,做题的时候心也不静,然后就33分滚粗了QAQ……

子任务1

想卡Floyd很简单嘛……造一个$101$个点没有边的图就行了,至于询问随便打一个即可。

子任务2

要让Bellman-Ford达到$(n-1)m$的上界很简单,反着造(正着造会因为循环顺序的原因一遍更新完)一个边权为$1$的链,其余边边权设成一个很大的数就行了。

为了不让Floyd TLE,最多只能有$100$个点……算了算发现边数需要$10^3$多一点,手动枚举一波边数就行了。

子任务3

……正常情况下子任务1的输出应该正好有$105$个整数,所以直接把子任务1的答案粘过来即可……

子任务5

……我还是Naive

直接把子任务2粘过来了,结果只有4分……后来才想起来因为前面是Dijkstra所以点数可以大一些……QAQ

子任务7

显然后面的问题必须恰好$71$个点和$1500$条边才能满分,随机了几个图发现暴搜都会TLE,随便交一个就好了……

(这个点是真·送分点)

总结

听说这个提答很简单啊……然而分还是这么低,不知道是因为心不静还是能力不够。

还有两道提答,再接再厉。

UOJ#259 子集计数问题 题解(雾

2017-07-11 15:21:07 By AntiLeaf

话说为什么没找到题解咧……算了我自己写一个好了……

由于弱菜AntiLeaf能力有限,部分测试点无法通过,见谅……


测试点1

一眼看见$n=24$,$k=8$,用Python算了算发现$n\choose k$才几十万,那直接暴力就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=35;
bool a[maxn][maxn],b[maxn];
int n,m,k,p;
int main(){
    freopen("subset1.in","r",stdin);
    freopen("subset1.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&k,&p);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    for(int i=1;i<=k;i++)b[i]=true;
    next_permutation(b+1,b+n+1);
    int ans=0;
    do{
        bool ok=true;
        for(int i=1;i<=n;i++)if(b[i]){
            for(int j=i+1;j<=n;j++)if(b[j]&&a[i][j]){
                ok=false;
                break;
            }
        }
        if(ok)ans++;
    }while(next_permutation(b+1,b+n+1));
    printf("%d",ans%p);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

测试点2

$n=40$,$k=11$,看上去不太好搞……?

其实只要在暴搜的时候判一下加上这个点是否合法就行了……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=55;
void dfs(int,int);
bool a[maxn][maxn];
int n,m,k,p,v[maxn],ans=0;
int main(){
    freopen("subset2.in","r",stdin);
    freopen("subset2.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&k,&p);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    dfs(1,0);
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void dfs(int x,int t){
    if(t==k){
        if(++ans==p)ans=0;
        return;
    }
    if(x==n+1)return;
    bool ok=true;
    for(int i=1;i<=t;i++)if(a[x][v[i]]){
        ok=false;
        break;
    }
    if(ok){
        v[t+1]=x;
        dfs(x+1,t+1);
    }
    dfs(x+1,t);
}

测试点3

$n=100$,$k=32$,看来暴搜没戏……

不过注意到$m=n-1$,猜想这是一棵树,仔细观察之后发现它确实是一棵树,那么跑一个树形DP即可:$f_{i,j,0/1}$表示$i$的子树中选了$j$个点,是否选了$i$的方案数,合并的时候搞一搞即可。

数据范围比较小,因此直接写$O(n^3)$的DP也可以过。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=105;
void dfs(int);
void add(int,int);
vector<int>G[maxn];
int n,m,k,p,f[maxn][maxn][2],g[maxn][2];
int main(){
    freopen("subset3.in","r",stdin);
    freopen("subset3.out","w",stdout);
    scanf("%d%*d%d%d",&n,&k,&p);printf("n=%d\n",n);
    for(int i=2,x;i<=n;i++){
        scanf("%d%*d",&x);
        G[x].push_back(i);
    }
    dfs(1);
    printf("%d",(f[1][k][0]+f[1][k][1])%p);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void dfs(int x){
    f[x][0][0]=f[x][1][1]=1;
    for(int i=0;i<(int)G[x].size();i++){
        dfs(G[x][i]);
        add(x,G[x][i]);
    }
}
void add(int x,int y){
    memset(g,0,sizeof(g));
    for(int i=0;i<=n;i++)for(int j=0;i+j<=n;j++){
        g[i+j][0]=(g[i+j][0]+(long long)f[x][i][0]*(f[y][j][0]+f[y][j][1]))%p;
        g[i+j][1]=(g[i+j][1]+(long long)f[x][i][1]*f[y][j][0])%p;
    }
    memcpy(f[x],g,sizeof(g));
}

测试点4

不难发现这也是一棵树,那继续用上面的树形DP即可。

为了压内存,用vector开DP数组,同时在合并之后清空原数组即可。

(注释掉了的那些东西是为了防止被卡内存写的找直径后DP每个子树最后再DP序列的做法,然而好像写挂了,WA……换成直接DP就过了,浪费了我十分钟……并不知道直接暴力空间对不对,不过我跑的时候并没有费很多的内存)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100005;
struct DP{
    vector<int>f[2];
    DP(){}
    void operator+=(DP&);
}f[maxn];
void bfs(int);
void dfs(int);
vector<int>G[maxn];
bool vis[maxn];
int n,k,mod,p[maxn],d[maxn],vec[maxn],q[maxn];
int main(){
    freopen("subset4.in","r",stdin);
    freopen("subset4.out","w",stdout);
    scanf("%d%*d%d%d",&n,&k,&mod);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    /*bfs(1);
    int u=1;
    for(int i=1;i<=n;i++)if(d[i]>d[u])u=i;
    bfs(u);
    int v=1;
    for(int i=1;i<=n;i++)if(d[i]>d[v])v=i;
    bfs(v);
    int cnt=0;
    while(u){
        vec[++cnt]=u;
        vis[u]=true;
        u=p[u];
    }
    fprintf(stderr,"u=%d v=%d cnt=%d\n",vec[1],vec[cnt],cnt);
    for(int i=1;i<=cnt;i++){
        dfs(vec[i]);
        fprintf(stderr,"i=%d dfs(%d) OK\n",i,vec[i]);
    }fprintf(stderr,"OK...\n");
    DP ans=f[vec[1]];
    for(int i=2;i<=cnt;i++)ans+=f[vec[i]];
    printf("%d",(ans.f[0][k]+ans.f[1][k])%mod);*/
    dfs(1);
    printf("%d",(f[1].f[0][k]+f[1].f[1][k])%mod);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void bfs(int x){
    int head=0,tail=0;
    q[tail++]=x;
    p[x]=d[x]=0;
    while(head!=tail){
        x=q[head++];
        for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=p[x]){
            p[G[x][i]]=x;
            d[G[x][i]]=d[x]+1;
            q[tail++]=G[x][i];
        }
    }
}
int cnt=0;
void dfs(int x){
    vis[x]=true;fprintf(stderr,"%d\n",++cnt);
    f[x].f[0].resize(2);
    f[x].f[1].resize(2);
    f[x].f[0][0]=f[x].f[1][1]=1;
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
        dfs(G[x][i]);
        f[x]+=f[G[x][i]];
    }
}
#include<cassert>
void DP::operator+=(DP &b){
    DP c;
    c.f[0].resize(min(k+1,(int)(f[0].size()+b.f[0].size())-1));
    c.f[1].resize(min(k+1,(int)(f[0].size()+b.f[0].size())-1));
    for(int i=0;i<(int)f[0].size();i++)for(int j=0;j<(int)b.f[0].size()&&i+j<(int)c.f[0].size();j++){
            /*if(j>=(int)b.f[0].size())fprintf(stderr,"a=%d b=%d c=%d\n",f[0].size(),b.f[0].size(),c.f[0].size());
              assert(j<(int)b.f[0].size());*/
        c.f[0][i+j]=(c.f[0][i+j]+(long long)f[0][i]*(b.f[0][j]+b.f[1][j]))%mod;
        c.f[1][i+j]=(c.f[1][i+j]+(long long)f[1][i]*b.f[0][j])%mod;
    }
    f[0].clear();
    f[1].clear();
    b.f[0].clear();
    b.f[1].clear();
    *this=c;
}

测试点5

$n=144$,$k=20$,暴搜肯定也没戏……(之后直接忽略暴搜)

手动观察一下输入数据可以发现一些规律,比如缺某条边的点是等距分布的,再写个东西瞎xx判一下就可以发现这其实是一个$12\times 12$的网格图缺了一些边,然后写一个状压DP就好了。

判断程序:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
using namespace std;
const int maxn=255;
bool a[maxn][maxn];
int n,m,k,p,ans=0,id[35][35];
int main(){
    freopen("subset5.in","r",stdin);
    //freopen("what.out","w",stdout);
    int r=12,c=12,n=0;
    for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)id[i][j]=++n;
    scanf("%*d%d%d%d",&m,&k,&p);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    for(int i=1;i<=r;i++)for(int j=1;j<=c;j++){
            if(i){
                a[id[i][j]][id[i-1][j]]=false;
                a[id[i-1][j]][id[i][j]]=false;
            }
            if(j){
                a[id[i][j]][id[i][j-1]]=false;
                a[id[i][j-1]][id[i][j]]=false;
            }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)assert(!a[i][j]);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

状压DP:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool a[255][255],down[75][255],right[75][255],ok[25][5005];
int n=12,m=12,e,k,p,id[75][255],f[25][5005][25];
int main(){
    freopen("subset5.in","r",stdin);
    freopen("subset5.out","w",stdout);
    int cnt=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)id[i][j]=++cnt;
    scanf("%*d%d%d%d",&e,&k,&p);
    while(e--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    for(int i=1;i<n;i++)for(int j=1;j<=m;j++)if(a[id[i][j]][id[i+1][j]])down[j][i-1]=true;
    for(int i=1;i<=n;i++)for(int j=1;j<m;j++)if(a[id[i][j]][id[i][j+1]])right[j][i-1]=true;
    for(int j=1;j<=m;j++){
        for(int s=0;s<(1<<n);s++){
            bool bad=false;
            for(int i=0;i<n-1;i++)if(down[j][i]&&((s>>i)&1)&&((s>>(i+1))&1)){
                bad=true;
                break;
            }
            ok[j][s]=!bad;
        }
    }
    ok[0][0]=true;
    f[0][0][0]=1;
    for(int j=0;j<m;j++)for(int s=0;s<(1<<n);s++)if(ok[j][s]){
                //for(int l=0;l<=k;l++)if(f[j][s][l])fprintf(stderr,"f[%d][%d][%d]=%d\n",j,s,l,f[j][s][l]);
        for(int t=0;t<(1<<n);t++)if(ok[j+1][t]){
            bool bad=false;
            for(int i=0;i<n;i++)if(right[j][i]&&(((s&t)>>i)&1)){
                bad=true;
                break;
            }
            if(bad)continue;
            int siz=__builtin_popcount(t);
            for(int l=0;l+siz<=k;l++)f[j+1][t][l+siz]=(f[j+1][t][l+siz]+f[j][s][l])%p;
        }
    }
    int ans=0;
    for(int s=0;s<(1<<n);s++)ans=(ans+f[m][s][k])%p;
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

UPD:

我好像逗比了……这个网格图是满的,并不缺边……囧囧囧,我还是太菜了……


测试点7

点数和边数都比较大,不过发现$m-n$才有$4$,猜想这个图可以表示成任意一棵生成树+5条非树边。大力判一波之后可以发现图确实是连通的,那么$3^5$大力枚举每条边的状态之后再套一个$O(n^2)$的树形DP即可。

这次跑的时间比较长,为了不浪费时间,可以在跑暴力的时候来一发tetris(逃

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
using namespace std;
const int maxn=6005;
int findroot(int);
void mergeset(int,int);
void dfs(int);
void add(int,int);
vector<int>G[maxn];
bool vis[maxn];
int n,m,K,p,a[maxn],size[maxn],f[maxn][maxn][2],anc[maxn];
int main(){
    freopen("subset7.in","r",stdin);
    freopen("subset7.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&K,&p);
    for(int i=1;i<=n;i++)anc[i]=i;
    int u[55]={0},v[55]={0},cnt=0;
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(findroot(x)==findroot(y)){
            u[cnt]=x;
            v[cnt]=y;
            fprintf(stderr,"(%d,%d) cnt=%d\n",u[cnt],v[cnt],cnt);
            cnt++;
        }
        else{
            G[x].push_back(y);
            G[y].push_back(x);
            mergeset(x,y);
        }
    }
    memset(a,-1,sizeof(a));
    int ans=0;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)for(int l=0;l<3;l++)for(int m=0;m<3;m++){
                        if((!u[0]&&i)||(!u[1]&&j)||(!u[2]&&k)||(!u[3]&&l)||(!u[4]&&m))continue;
        memset(a,-1,sizeof(a));
        fprintf(stderr,"i=%d j=%d k=%d l=%d m=%d\n",i,j,k,l,m);

        if(i==0){
            a[u[0]]=1;
            a[v[0]]=0;
        }
        else if(i==1){
            a[u[0]]=0;
            a[v[0]]=1;
        }
        else a[u[0]]=a[v[0]]=0;

        if(j==0){
            a[u[1]]=1;
            a[v[1]]=0;
        }
        else if(j==1){
            a[u[1]]=0;
            a[v[1]]=1;
        }
        else a[u[1]]=a[v[1]]=0;

        if(k==0){
            a[u[2]]=1;
            a[v[2]]=0;
        }
        else if(k==1){
            a[u[2]]=0;
            a[v[2]]=1;
        }
        else a[u[2]]=a[v[2]]=0;

        if(l==0){
            a[u[3]]=1;
            a[v[3]]=0;
        }
        else if(l==1){
            a[u[3]]=0;
            a[v[3]]=1;
        }
        else a[u[3]]=a[v[3]]=0;

        if(m==0){
            a[u[4]]=1;
            a[v[4]]=0;
        }
        else if(m==1){
            a[u[4]]=0;
            a[v[4]]=1;
        }
        else a[u[4]]=a[v[4]]=0;

        memset(vis,0,sizeof(vis));
        memset(f,0,sizeof(f));
        memset(size,0,sizeof(size));
        dfs(1);assert(size[1]==n);
        ans=(ans+(f[1][K][0]+f[1][K][1])%p)%p;
        fprintf(stderr,"ans+=%d\n",(f[1][K][0]+f[1][K][1])%p);
    }
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
int findroot(int x){return x==anc[x]?x:(anc[x]=findroot(anc[x]));}
void mergeset(int x,int y){anc[findroot(x)]=findroot(y);}
void dfs(int x){
    //memset(f[x],0,sizeof(int)*(n+3));
    vis[x]=true;
    size[x]=1;
    if(a[x]==0)f[x][0][0]=1;
    else if(a[x]==1)f[x][1][1]=1;
    else f[x][0][0]=f[x][1][1]=1;
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
            dfs(G[x][i]);
            add(x,G[x][i]);
        }
}
void add(int x,int y){
    static int g[maxn][2];
    memset(g,0,sizeof(g));
    for(int i=0;i<=size[x];i++)for(int j=0;j<=size[y];j++){
        g[i+j][0]=(g[i+j][0]+(long long)f[x][i][0]*((f[y][j][0]+f[y][j][1])%p)%p)%p;
        g[i+j][1]=(g[i+j][1]+(long long)f[x][i][1]*f[y][j][0]%p)%p;
    }
    //for(int i=0;i<=size[x];i++)printf("(%d,%d) ",f[x][i][0],f[x][i][1]);printf("\n");
    //for(int i=0;i<=size[y];i++)printf("(%d,%d) ",f[y][i][0],f[y][i][1]);printf("\n");
    memcpy(f[x],g,sizeof(g));
    size[x]+=size[y];
    //for(int i=0;i<=size[x];i++)printf("(%d,%d) ",f[x][i][0],f[x][i][1]);printf("\n\n");
}

话说在这个点上因为几个NC错误卡了至少一个小时,我是不是菜得没救了……


好吧……还是高估了我的水平,除了这6个点之外剩下的似乎并不会做……

(其实测试点8是可以%论文来做的,然而我懒得学了,毕竟感觉NOI不一定用得上,还是好好复习比较好……逃)


由于填坑人弱菜AntiLeaf在这个坑里摔出*了,此坑已弃

#79 一般图最大匹配 求hack

2017-05-26 16:34:40 By AntiLeaf

前两天学了学高斯消元版的一般图最大匹配,抄了抄各位dalao们的代码

今天重新看自己写的代码,发现有一个地方抄错了

//In function Gauss(int A[][maxn],int B[][maxn],n)
if(B){
    swap(id[i],id[j]);
    for(int k=1;k<=n;k++)swap(B[i][k],B[j][k]);
}

而代码里对Gauss这个函数的两次调用分别是这样的

Gauss(A,NULL,n);
......
Gauss(A,B,n);

第一次高斯消元是为了找出所有在最大匹配中的点,但由于高斯消元的过程中可能会进行行的交换,因此需要维护一个id数组表示每个点对应的行号

(讲真其实还是没明白为啥这个东西是每个点对应的行号,不应该是每行对应的点的编号么……然而这样又解释不清代码在写什么了,囧囧囧……)

然而正常的写法应该是在第一次高斯消元时维护id[],第二次高斯消元时维护与否都无所谓了,显然我这个是搞反了

但是还是可以过掉所有的数据和hack数据,手动构造了几组也卡不掉,感觉很神奇

这个代码应该是错的了,数据的构造思路应该是找一个点$x$($x>1$)使得$x$和$1$之间有连边但$x$不可能在最大匹配中,但是想了想并没有找到满足这种情况的数据

因此写了这篇博客,虚心请求诸位dalao提供一组hack数据,以解心中疑问,如有dalao愿意相助,不胜感激……

搞了一波事情

2017-03-24 15:00:02 By AntiLeaf

两三个月之前写了紫荆花之恋,bzoj上跑过去了,交到uoj上死活MLE

昨天闲的没事又卡了卡内存,然而还是MLE了

感觉很不开心,于是刚才造了一波极限数据去hack

然后就hack了一波 @yyhslyz 的代码,结果不小心hack成功了= =

http://uoj.ac/hack/3192

让我静静……

UPD:

重评完辣,世界又恢复和平辣

大概看了看,好像这波hack卡掉了将近二十份代码,其中有不少MLE的

感觉心理平衡多了233333

UPD:

下午重写了一遍,终于过了

http://uoj.ac/submission/138458

感觉心情舒畅了许多呢~

(不要问我后来的几次hack是怎么回事

话说#288去哪儿了

2017-02-22 15:02:40 By AntiLeaf

是不是vfk觉得出题人太**于是就把这题给ban了……

AntiLeaf Avatar