无能狂怒。
部分内容已被和谐。
时间分配不当。又一头栽在最难的$T1$上了。后两题留的时间太少了然后就炸了。。
没啥好说的。$T1$大概想到正解没敢打。这个决策貌似是正确的，因为的确不好打。
考后也调了好久才调出来。有点恶心的一道题。
然而其实T1有不少部分分，会直接写的大概有$50$于是就都写了，然而最后只有$20$分。。。
还是栽在了细节上。。。大长式子没有时间一档一档调试。。。样例过了就交了。。。
剩下俩结论题。真是无聊。。。这种考试怎么应付啊。。。。
然后$T3$写了个假了但是假的不厉害的算法，本来能拿$60$分，然而数组开小了在我知道数据范围是$10^6$的情况下数组开的$10^5$
应该是写的时候着急了少按了个$1?$不知道，我有点蠢。。。最后只剩下$20$
然后$T2$又是个贪心题，写了个假的，只得了特判的$10$分。
烦躁。恼怒。脑子里乱糟糟的。。。
然而依旧，改题还是挺快。因为后两个题都是结论题，有了结论就啥都没剩下了。。。（其实考场上已经想到了一半。。）
T1是道好题，代码不是特别好写，但是弄弄也就出来了。
然后晚上就扑街了。电脑里所有有用的软件都被安全卫士啥的一键卸载了，然后我一晚上就被吃了。
然后就没有然后了。落的那么多视频课可咋整啊。。
T1：战略游戏
大意：求树上选$k$条路径它们有公共边，其余所有边被恰好$0/1$条路径覆盖的方案数。$n,k \le 10^5$
好题。（因为我能做出来，所以不叫神题）
暴力做法就是枚举公共路径的两个端点，然后在两个方向的子树里，每边选出一个儿子随便走，再分配给这$k$个人。
发现路径两端除了方向外互不干扰。
于是我们先考虑两个点不是父子关系的情况，发现就是两个端点在子树内分别选点的方案数相乘。
所以我们设一个点在子树内选点的方案数为$F(u)$那么就可以树形$dp$直接求出。
考虑如何求出$F$。发现过程就是把每个儿子加入的过程，大概就是若干大小$1$种类$size_{son}$的物件，做背包。
背包，想到啥？生成函数。然后发现这道题非常适用生成函数，分治$FFT$乘起来就好了。大小都是$deg_u$级别的所以复杂度是$O(nlog^2n)$
具体而言就是$\prod\limits_{son} (size_{son} x + 1)$。然后次数为$i$的项就是选了$i$个人出去走的方案数。再点积上一个排列数就得到了方案。
然而并没有完，我们还没有考虑祖先-父子关系的点对。对于这样的点对，父亲的贡献不再是子树的贡献，而是除了这棵子树以外的贡献。
这棵子树的贡献除掉，再把外面的乘进来就好了。一次的，暴力乘，单次复杂度线性。
直接这么做肯定是不行的。但是我们可以发现对于大小相同的儿子，乘除的东西是完全一样的。
于是我们对于每种有用的$size$值做一次，$size$相同的直接取用，$size$的种数是$O(\sqrt{size})$的。所以这一部分的复杂度是$O(n\sqrt{n})$的。
虽说平时也压行，但是为啥今天的代码突然丑出天际啊。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 998244353 4 #define S 222222 5 #define poly vector<int> 6 struct P{int sz,p;}_[S]; 7 int len,rev[S],n,k,fir[S],l[S],to[S],ec,deg[S],sz[S],v[S],ans,ctb[S],fac[S],inv[S]; 8 poly t[S],d[S],R; 9 int qp(int b,int t,int a=1){for(;t;t>>=1,b=1ll*b*b%mod)if(t&1)a=1ll*a*b%mod;return a;} 10 void NTT(poly&a,int op=1){ 11 for(int i=1;i<len;++i)rev[i]=rev[i>>1]>>1|(i&1?len>>1:0); 12 for(int i=1;i<len;++i)if(rev[i]>i)swap(a[i],a[rev[i]]); 13 for(int i=1;i<len;i<<=1)for(int j=0,t=qp(3,(mod-1)/2/i*op+mod-1);j<len;j+=i<<1) 14 for(int k=j,x,y,w=1;k<j+i;++k,w=1ll*w*t%mod) 15 x=a[k],y=1ll*w*a[k+i]%mod,a[k]=(x+y)%mod,a[k+i]=(x-y+mod)%mod; 16 if(op<0)for(int iv=qp(len,mod-2),i=0;i<len;++i)a[i]=1ll*a[i]*iv%mod; 17 } 18 void DaC(int p,int l,int r){ 19 if(l>r){d[1].clear();d[1].push_back(1);return;} 20 d[p].clear();int md=l+r>>1; 21 if(l==r){d[p].resize(2);d[p][0]=1;d[p][1]=v[l];return;} 22 DaC(p<<1,l,md);DaC(p<<1|1,md+1,r); 23 len=1;while(len<=r-l+1)len<<=1; 24 d[p].resize(len);d[p<<1].resize(len);d[p<<1|1].resize(len); 25 NTT(d[p<<1]);NTT(d[p<<1|1]); 26 for(int i=0;i<len;++i)d[p][i]=1ll*d[p<<1][i]*d[p<<1|1][i]%mod; 27 NTT(d[p],-1); 28 } 29 void div(poly&a,int x,int l){poly e;e.resize(l);for(int i=l-1;i;--i)e[i-1]=1ll*a[i]*x%mod,a[i-1]=(a[i-1]-e[i-1]+mod)%mod;a=e;} 30 void mul(poly&a,int x,int l){if(!x)return;poly e;e.resize(l);for(int i=l-2;~i;--i)e[i+1]=(e[i+1]+1ll*a[i]*x)%mod,e[i]=a[i];a=e;} 31 void dfs(int p,int fa){ 32 for(int i=fir[p];i;i=l[i])if(to[i]!=fa)dfs(to[i],p),sz[p]+=sz[to[i]], 33 ans=(ans-1ll*ctb[to[i]]*ctb[to[i]]%mod*(mod/2+1))%mod,ctb[p]=(ctb[p]+ctb[to[i]])%mod; 34 sz[p]++; ans=(ans+1ll*ctb[p]*ctb[p]%mod*(mod/2+1))%mod; 35 for(int i=fir[p],c=0;i;i=l[i])if(to[i]!=fa)v[++c]=sz[to[i]],_[c]=(P){sz[to[i]],to[i]}; 36 DaC(1,1,deg[p]-1); swap(t[p],d[1]); 37 for(int i=0;i<deg[p]&&i<=k;++i)ctb[p]=(ctb[p]+1ll*t[p][i]*fac[k]%mod*inv[k-i])%mod; 38 sort(_+1,_+deg[p],[](P a,P b){return a.sz<b.sz;}); 39 for(int i=1,rt;i<deg[p];++i){ 40 if(_[i].sz!=_[i-1].sz){ 41 R=t[p];div(R,qp(_[i].sz,mod-2),deg[p]);mul(R,n-sz[p],deg[p]);rt=0; 42 for(int i=0;i<deg[p]&&i<=k;++i)rt=(rt+1ll*R[i]*fac[k]%mod*inv[k-i])%mod; 43 }ans=(ans+1ll*rt*ctb[_[i].p])%mod; 44 } 45 } 46 void link(int a,int b){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;deg[a]++;} 47 void con(int a,int b){link(a,b);link(b,a);} 48 int main(){ 49 scanf("%d%d",&n,&k); fac[0]=1; 50 if(k==1)return cout<<(n-1ll)*n/2%mod<<endl,0; 51 for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y),con(x,y); 52 for(int i=1;i<=100000;++i)fac[i]=1ll*fac[i-1]*i%mod; 53 inv[100000]=qp(fac[100000],mod-2); 54 for(int i=99999;~i;--i)inv[i]=inv[i+1]*(i+1ll)%mod; 55 deg[1]++; dfs(1,0); cout<<ans<<endl; 56 }
T2：小b爱取模
大意：模$k$意义下长为$n$的数列。每次操作可以区间$+1$并取模。求全$0$最少步数。$n \le 10^7,k \le 4$
先说一下神仙的题解做法。
区间加转化为差分后的两个单点加。我们要求差分数组归零。于是我们维护数列$a$表示每个位置要被加几次。
首先如果每次操作都是对于$[i,n]$的，那么$a=(k-b)mod \ k$.其中$b$是差分数组。这样我们能得到一组可能不优的解。
然后我们对$a$数组的要求就是前缀和时刻非负。每次可以单点减$k$。最后的操作次数就是所有正值和。
其实也就是单点非负后缀减$k$。
于是贪心，从大到小依次对$a$最大的数减，从后向前考虑。证明有点恶心，大力分类讨论可得。复杂度$O()kn$
1 #include<bits/stdc++.h> 2 using namespace std; 3 int k,n,a[11111111],t[11111111],ans;char s[11111111]; 4 int main(){ 5 scanf("%d%s",&k,s+1);s[0]=‘0‘;n=strlen(s+1); 6 for(int i=1;i<=n;++i)a[i]=(k-s[i]+s[i-1])%k; 7 for(int i=1;i<=n;++i)t[i]=a[i]+t[i-1]; 8 for(int x=k-1,mn;mn=111111111,~x;--x){ 9 for(int i=n;i;--i){ 10 mn=min(mn,t[i]); 11 if(mn>=k&&a[i]==x)mn-=k,a[i]-=k; 12 } 13 for(int i=1;i<=n;++i)t[i]=t[i-1]+a[i]; 14 }for(int i=1;i<=n;++i)ans+=max(a[i],0);cout<<ans; 15 }
然而有更简单的做法：直接正着贪心。
还是差分。对于第一位我们一定是花费$k-b$的代价把它加上来，这时候我们就有同样个数的$-1$可以在后面使用了。
能用$-1$就用$-1$。$-1$不够用了就花费$k-b$的代价去买次数（也就是先$+k-b$）。然后留更多的$-1$给后面用。
这个的正确性就可以直接从含义上理解了。
T3：小b爱实数
大意：$01$串，给定小数点后$6$位实数。求一个子区间其$1$的占比尽量与$f$相近。输出满足条件的左端点。$n \le 10^6$
考场上有一个奇妙的思路，就是说对于$1$做出$f-1$贡献对于$0$做出$f$贡献，问题变为寻找贡献和为$0$的子区间。
然后就直接倒着扫，$lower \ lound$啥的找就可以了。时间复杂度也是$O(nlogn)$的
然而这道题不一定存在恰好为$0$的，如果不是$0$那么长度就会对答案产生影响。然后就得到了$60$分的好成绩。（前提是不像我这么蠢）
正解嘛就是列式子$\frac{sum_r - sum_l}{r-l}=f$那么就是$\frac{sum_r - f \times r}{r}=\frac{sum_l = f \times l}{l}$。
于是乎设点$(i,sum_i - f \times i)$。最小化斜率。按纵坐标排序之后考虑相邻元素就好了。时间复杂度$O(nlogn)$
为啥那么多大神考场切啊。。。看来还是我太菜了。。。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 double f,ans=1e9;int a[1111111],n,L;char s[1111111]; 4 struct P{int x;double y;}p[1111111]; 5 int main(){ 6 scanf("%lf%s",&f,s+1);n=L=strlen(s+1); 7 for(int i=1;i<=n;++i)a[i]=a[i-1]+s[i]-48,p[i]=(P){i,f*i-a[i]}; 8 sort(p,p+n+1,[](P a,P b){return a.y<b.y;}); 9 for(int i=0;i<n;++i) 10 if(min(p[i].x,p[i+1].x)<L){if(fabs((p[i].y-p[i+1].y)/(p[i].x-p[i+1].x))-1e-6<ans)ans=fabs((p[i].y-p[i+1].y)/(p[i].x-p[i+1].x)),L=min(p[i].x,p[i+1].x);} 11 else if(fabs((p[i].y-p[i+1].y)/(p[i].x-p[i+1].x))+1e-6<ans)ans=fabs((p[i].y-p[i+1].y)/(p[i].x-p[i+1].x)),L=min(p[i].x,p[i+1].x); 12 cout<<L<<endl; 13 }
原文：https://www.cnblogs.com/hzoi-DeepinC/p/12346594.html
