UOJ Logo AntiLeaf的博客

博客

标签
数据结构 树分治 乱搞 一般图匹配 高斯消元 提交答案
共找到 2 篇包含 “提交答案” 标签的博客：

弱菜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(n2)的递推式怎么玩……不过要我手推O(n3)的递推式的话还是不难的……

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

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

测试点1

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

测试点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(n3)的DP了……有点可惜。

（设fi,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个点……算了算发现边数需要103多一点，手动枚举一波边数就行了。

子任务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算了算发现(nk)才几十万，那直接暴力就好了。

#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即可：fi,j,0/1表示i的子树中选了j个点，是否选了i的方案数，合并的时候搞一搞即可。

数据范围比较小，因此直接写O(n3)的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×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条非树边。大力判一波之后可以发现图确实是连通的，那么35大力枚举每条边的状态之后再套一个O(n2)的树形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在这个坑里摔出*了，此坑已弃

Server time: 2025-04-14 22:22:30