noip模拟测试6

T1：那一天我们许下约定

n块饼干，d天内分完，每天分的块数小于m，求方案数。

( n,m<=2000 , d<=10¹²)

　1：dp ，设计状态发 f[i][j] 表示前i天分j块的方案数，f[i][j]= ∑ f[i-1][k] ( j-m < k < j )

　　发现复杂度为 O ( nd ) ,由于d过大，复杂度爆炸，30分再见;

　　发现实际中状态大多数是冗余的（因为好多天都不会分饼干）

　　所以更改状态设计，f[i][j] 表示前 i 个分了饼干的天，总共分出 j 块的方案数。

　　答案为 ∑ f[i][n]*C(d,i)

　　复杂度 O ( n² )

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 #define ll long long
 8 using namespace std;
 9 const int MAXN=2005,D=998244353;
10 ll n,m,d,ans;
11 
12 ll f[MAXN][MAXN],g[MAXN][MAXN];
13 
14 ll fac[MAXN],inv[MAXN];
15 
16 ll qpow(ll x,ll k)
17 {
18     ll ret=1;
19     while(k)
20     {
21         if(k&1) ret=(ret*x)%D;
22         x=(x*x)%D;
23         k>>=1;
24     }
25     return ret%D;
26 }
27 
28 ll C(ll x,ll y)
29 {
30     ll tmp=1;
31     for(int i=0;i<y;i++)
32         tmp=(tmp*((d-i)%D))%D;
33     return (tmp*inv[y])%D;
34 }
35 
36 int main()
37 {
38     while(1)
39     {
40         scanf("%lld%lld%lld",&n,&d,&m);
41         if(!n&&!m&&!d) break;
42         
43         for(int i=0;i<=n;i++) g[0][i]=1;
44         for(int i=1;i<=min(n,d);i++)
45         {
46             for(int j=1;j<=n;j++)
47                 if(j-m>=0) f[i][j]=((g[i-1][j-1]-g[i-1][j-m])%D+D)%D;
48                 else f[i][j]=g[i-1][j-1];
49             for(int j=1;j<=n;j++)
50                 g[i][j]=(g[i][j-1]+f[i][j])%D;
51         }
52         
53         fac[0]=inv[0]=fac[1]=1;
54         for(int i=2;i<=n;i++)
55             fac[i]=(fac[i-1]*i)%D;
56         inv[n]=qpow(fac[n],D-2);
57         for(int i=n-1;i>=1;i--)
58             inv[i]=(inv[i+1]*(i+1))%D;
59         
60         ans=0;
61         for(int i=1;i<=min(n,d);i++)
62             ans=(ans+f[i][n]*C(d,i))%D;
63         printf("%lld
",ans);
64         memset(f,0,sizeof(f));
65         memset(g,0,sizeof(g));
66     }
67     return 0;
68 }

t1 Code

　2：机房某大佬 TKJ 指出，这不就是组合加容斥吗？

　　简单说一下

　　枚举分饼干的天数，利用1中的优化可将复杂度优化到 O ( n )　

　　先插板法计算如果没有每天小于m的限制的答案。

　　再容斥计算出有m限制的答案。

　　具体不细说了

　　详情见大佬TKJ的博客：zto TKJ orz

T2：那一天她离我而去

　　n个点m条边的无向图，求经过点1的最小环，保证没有重边、自环

　　 $( n,m \leq 104$ )

　　一脸懵比？

　　floyd最小环？？

　　n³过一万？？？

　　于是爆0，gg

　1：先想暴力怎么做 ( floyd )

　　因为必须经过1节点，所以这个环的路径应该是1->x---最短路--->y->1（x与y均与1相连）

　　哦，那吼了，暴力枚举和1相连的点，全跑一遍不经过1的最短路

　　复杂度O ( n²logm)，继续爆炸

　　怎么优化？

　　仔细一想会发现刚刚暴力枚举点会有很多冗余

　　所以从枚举这里优化

　　首先想如果把所有与1相连的点分成两组，其中一组为起点，另一组为终点

　　　　（在跑最短路时，将所有起点的距离初值设为它到1的距离，最后用所有终点的 [最短路值 + 到1的距离] 来更新答案）

　　这样我们就有了一种对于两组点之间的计算方法

　　这时我们只要考虑如何将这些与1相连的点分成两组，且对于任意两点，一定会被至少一次分在两个不同的组中

　　哦，然后就是一种船新的思路——二进制拆分

　　我们把所有与1相连的点标号

　　然后枚举标号二进制下的每一位，将该位为0的分为一组，1的分为另一组

　　因为对于任意两个点，它们的标号一定不同，所以一定至少一次被分到两个组中

　　所以正确，那就没了。

　　复杂度为 O ( n logm logn )

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<vector>
  8 using namespace std;
  9 const int MAXN=10005,MAXM=40005;
 10 int T;
 11 int n,m,ans;
 12 
 13 struct node
 14 {
 15     int to,nxt,dis;
 16 }mp[MAXM*2];
 17 int h[MAXN],tot;
 18 void add(int x,int y,int z)
 19 {
 20     mp[++tot].nxt=h[x];
 21     mp[tot].to=y;
 22     mp[tot].dis=z;
 23     h[x]=tot;
 24 }
 25 
 26 inline int R()
 27 {
 28     int a=0;char c=getchar();
 29     while(c>'9'||c<'0') c=getchar();
 30     while(c>='0'&&c<='9') a=a*10+c-'0',c=getchar();
 31     return a;
 32 }
 33 
 34 int vec[MAXN],vd[MAXN],cnt,s[MAXN],sd[MAXN],ps,t[MAXN],td[MAXN],pt;
 35 
 36 int dis[MAXN];
 37 bool vis[MAXN];
 38 
 39 void dijikstra()
 40 {
 41     memset(vis,0,sizeof(vis));
 42     memset(dis,0x3f,sizeof(dis));
 43     priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
 44     for(int i=1;i<=ps;i++)
 45         q.push(make_pair(sd[i],s[i])),dis[s[i]]=sd[i];
 46     vis[1]=1;
 47     while(!q.empty())
 48     {
 49         int u=q.top().second; q.pop();
 50         if(vis[u]) continue;
 51         vis[u]=1;
 52         for(int i=h[u];i;i=mp[i].nxt)
 53         {
 54             int v=mp[i].to,ds=mp[i].dis;
 55             if(vis[v]) continue;
 56             if(dis[v]>dis[u]+ds)
 57             {
 58                 dis[v]=dis[u]+ds;
 59                 q.push(make_pair(dis[v],v));
 60             }
 61         }
 62     }
 63     for(int i=1;i<=pt;i++)
 64         ans=min(ans,dis[t[i]]+td[i]);
 65 }
 66 
 67 void first()
 68 {
 69     ans=0x3f3f3f3f;
 70     cnt=tot=0;
 71     memset(h,0,sizeof(h));
 72 }
 73 
 74 int main()
 75 {
 76     T=R();
 77     while(T--)
 78     {
 79         first();
 80         n=R();m=R();
 81         for(int i=1,aa,bb,cc;i<=m;i++)
 82         {
 83             aa=R();bb=R();cc=R();
 84             add(aa,bb,cc);
 85             add(bb,aa,cc);
 86         }
 87         for(int i=h[1];i;i=mp[i].nxt)
 88             vec[++cnt]=mp[i].to,vd[cnt]=mp[i].dis;
 89         
 90         if(!cnt)
 91         {
 92             printf("-1
");
 93             continue;
 94         }
 95         
 96         for(int i=1,j=1;j<=15;i<<=1,j++)
 97         {
 98             ps=pt=0;
 99             for(int j=1;j<=cnt;j++)
100                 if(j&i) s[++ps]=vec[j],sd[ps]=vd[j];
101                 else t[++pt]=vec[j],td[pt]=vd[j];
102             if(!ps||!pt) continue;
103             dijikstra();
104         }
105         if(ans!=0x3f3f3f3f) printf("%d
",ans);
106         else printf("-1
");
107     }
108     return 0;
109 }

t2 Code

　　T3：哪一天她能重回我身边

　　给定n张牌，每张牌正反面分别有一个数字，通过反转使所有正面的数字各不相同，求最小反转次数和方案数

　　( n <= 10⁵数字<=2*n )

　1：不知为什么想到建图

　　然后在牌正反面的数字间连边，会惊奇的发现反转卡牌等价与反转边的方向，而结果是要使所有点的出度都小于等于1

　　原图应为多个联通块

　　考虑一个联通块，会发现只有边数小于等于点数才会有解

　　所以只可能是树或基环树

　　发现一种合法的反转应该是使所有的边都指向父亲（基环树是所有的边都指向环，环上的边同为顺时针或逆时针）

　　于是想到换根dp

　　第一次dp出以任意点u的答案（只需要计算让所有边都指向父亲需要反转多少次）

　　第二次dp出以每个点为根的答案

　　取最小值，统计最小值的方案次数

　　特别的: 基环树的方案只可能有1或两种，只需要判断顺逆时针的反转次数是否相同即可

　　　　　　（具体来说只需要判断以环上相邻两点分别为根的答案是否相等即可）

　　最后将每个联通块的最小值相加，方案数相乘

　　复杂度为 O ( n )

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<vector>
  7 #define ll long long
  8 using namespace std;
  9 const int MAXN=100100,D=998244353;
 10 int T;
 11 int n;
 12 
 13 struct node
 14 {
 15     int to,nxt;
 16 }mp[MAXN*2];
 17 int h[MAXN*2],tot;
 18 void add(int x,int y)
 19 {
 20     mp[++tot].nxt=h[x];
 21     mp[tot].to=y;
 22     h[x]=tot;
 23 }
 24 
 25 bool flag;
 26 int vcnt,ecnt;
 27 
 28 bool vis[MAXN*2];
 29 
 30 void dfs(int u)
 31 {
 32     vcnt++;vis[u]=1;
 33     for(int i=h[u];i;i=mp[i].nxt)
 34     {
 35         int v=mp[i].to;
 36         ++ecnt;
 37         if(vis[v]) continue;
 38         dfs(v);
 39     }
 40 }
 41 
 42 int s,nxt,id;
 43 ll num,f[MAXN*2],g[MAXN*2],ans,anscnt;
 44 
 45 void dfs1(int u,int fa)
 46 {
 47     vis[u]=1;
 48     for(int i=h[u];i;i=mp[i].nxt)
 49     {
 50         int v=mp[i].to;
 51         if(v==fa) continue;
 52         if(vis[v])
 53             s=u,nxt=v,id=i;
 54         else
 55         {
 56             dfs1(v,u);
 57             f[u]+=f[v]+(i&1);
 58         }
 59     }
 60 }
 61 
 62 vector<int> vv;
 63 
 64 void dfs2(int u,int fa)
 65 {
 66     vv.push_back(g[u]);
 67     for(int i=h[u];i;i=mp[i].nxt)
 68     {
 69         int v=mp[i].to;
 70         if(v==fa) continue;
 71         if(i==id||i==(id^1)) continue;
 72         g[v]=g[u]+((i&1)?-1:1);
 73         dfs2(v,u);
 74     }
 75 }
 76 
 77 int main()
 78 {
 79     scanf("%d",&T);
 80     while(T--)
 81     {
 82         tot=1;flag=0;
 83         memset(h,0,sizeof(h));
 84         memset(vis,0,sizeof(vis));
 85         scanf("%d",&n);
 86         for(int i=1,aa,bb;i<=n;i++)
 87         {
 88             scanf("%d%d",&aa,&bb);
 89             add(bb,aa);add(aa,bb);
 90         }
 91         for(int i=1;i<=2*n;i++)
 92             if(!vis[i])
 93             {
 94                 vcnt=ecnt=0;
 95                 dfs(i);
 96                 if(ecnt/2>vcnt)
 97                 {
 98                     printf("-1 -1
");
 99                     flag=1;
100                     break;
101                 }
102             }
103         if(flag) continue;
104         memset(vis,0,sizeof(vis));
105         memset(f,0,sizeof(f));
106         memset(g,0,sizeof(g));
107         ans=0;anscnt=1;
108         for(int i=1;i<=2*n;i++)
109             if(!vis[i])
110             {
111                 vv.clear();
112                 s=nxt=id=0;
113                 num=0;
114                 
115                 dfs1(i,0);
116                 g[i]=f[i];
117                 dfs2(i,0);
118                 
119                 if(!id)
120                 {
121                     sort(vv.begin(),vv.end());
122                     for(int j=0;j<vv.size();j++)
123                         if(vv[j]!=vv[0]) break;
124                         else ++num;
125                     ans+=vv[0];
126                 }
127                 else
128                 {
129                     id&=1;
130                     if(g[s]+(id^1)==g[nxt]+id) num=2;
131                     else num=1;
132                     ans+=min(g[s]+(id^1),g[nxt]+id); 
133                 }
134                 anscnt=anscnt*num%D;
135             }
136         printf("%lld %lld
",ans,anscnt);
137     }
138     return 0;
139 }

t3 View