Noip模拟98 2021.11.14
T1 构造字符串
看出是图论，但是没有试着用冰茶姬，然后特判\(-1\)的还多了，就直接挂成\(40pts\)了
然后别人分数都很高就直接底垫垫了。。。。对，又一次底垫垫了
转化题意很简单，要求构造一串字典序最小的序列满足一些数相等，一些数不相等
那么直接分情况讨论，先把要求相等的数按照关系分成一堆联通块，然后每一条不相等的关系当做一条边将联通块连起来
不合法的判断只有一条，并没有我考场上想的那么麻烦，直接就如果联通块内有连边就是不合法
然后建完图之后就是变为了只有不相等的部分分（\(z_i=0\)）的情况，那么直接贪心的按照编号从小往大扫，每次开个桶找个\(mex\)即可
考场上的\(SB\)做法就是因为没有使用冰茶姬合并相同的关系，而是把相同的和不同的放在了一起处理，这样会导致错误，\(Hack\)很好造，我很蠢。。。
说一下刚开始的时候想的假做法，没有保证字典序最小的时候可以对每一条关系整一个边权，不相等的关系边权为\(1\)，相等的为\(0\)，然后每个联通块跑一遍\(dfs\)就行了
str
#include
#define int long long
using namespace std;FILE *wsn;
auto read=[](){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
};
const int NN=2005;
int n,m,ans[NN],bin[NN];
bool vis[NN];
struct node{
int a,b,c;
bool operator<(const node&x)const{
return c>x.c;
}
}op[NN];
vectorS[NN];
namespace DSU{
int fa[NN];
inline int getfa(int x){return fa[x]=((fa[x]==x)?x:getfa(fa[x]));}
inline void merge(int x,int y){
x=getfa(x); y=getfa(y);
if(x==y) return;if(x>y) swap(x,y);
fa[y]=x;
}
}using namespace DSU;
namespace WSN{
inline short main(){
wsn=freopen("str.in","r",stdin);
wsn=freopen("str.out","w",stdout);
n=read(); m=read();
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1,a,b,c;i<=m;i++){
a=read(),b=read(),c=read();
if(a>b) swap(a,b);op[i]=node{a,b,c};
}
sort(op+1,op+m+1);
for(int i=1;i<=m&&op[i].c!=0;i++){
int a=op[i].a,b=op[i].b,c=op[i].c;
for(int j=1,x,y;j<=c;j++)
x=a+j-1,y=b+j-1,merge(x,y);
if(b+c<=n) op[++m]=node{a+c,b+c,0};
}
for(int i=m;i>0&&op[i].c==0;i--){
int a=op[i].a,b=op[i].b,c=op[i].c;
if(getfa(a)==getfa(b))return puts("-1"),0;
S[getfa(a)].push_back(getfa(b));
S[getfa(b)].push_back(getfa(a));
}
for(int i=1;i<=n;i++)if(!vis[getfa(i)]){
int mex=0,x=getfa(i); vis[x]=1;
memset(bin,0,sizeof(bin));
for(auto y:S[x])if(y \(\color{white}{过于之菜了，已经连着好几天没有切题了，而且还都不是不会，就是打不对，很郁闷。。。。}\)
T2 寻宝
非常无脑的\(bfs+dfs\)，切忌把带着数组的判断条件放在判断下标的前面，否则很可能\(RE\)，比如
然后这种送分题都没能切，于是直接底垫垫。。。。。
然后我的打法比较难调，或者说我打的时候比较慌，出了很多zz错误，然后调了好久。。。后面的部分分没来及打，不打挂的话应该能拿\(50\)左右的样子。。。
剩下的思路就不说了，学过信队的，写过最短路的都可以轻松打过（除了我）
treasure
#include
#include T3 序列
李超线段树维护线段
考虑把过\(p\)区间分成右端点在\(p\)的一段最优区间加上左端点在\(p+1\)的一段最优区间
那么每次对答案的统计就变成了固定一个点，找另一个点，这样预计得到\(50\)
那么尝试化简式子
设\(sa_i=\sum_{j=1}^i a_j\)，\(sb_i=\sum_{j=1}^ib_j\)
最优即\(\max_{1\leq l\leq r}\{(sa_{r}-sa_{l-1})-k(sb_{r}-sb_{l-1})\}\)
即\(sa_r-k\cdot sb_{r}-\min_{0\leq l
时间复杂度为\(O(n\log n)\)，常数略大，空间复杂度为\(O(n)\)
seq
#include
#define int long long
using namespace std; FILE *wsn;
auto read=[](){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
};
const int NN=2e6+5,inf=1e18;
const int lim=1e6;
int n,m,a[NN],b[NN],ans[NN],lst;
int sufa[NN],sufb[NN],prea[NN],preb[NN];
struct Query{
int p,k,id;
bool operator<(const Query&x)const{
return p==x.p?k>1)
struct seg{
int k,b;
seg(){k=lim;b=inf;}
seg(int k,int b):k(k),b(b){}
int calc(int x){return k*x+b;}
}tr[NN<<2];
inline void update(seg x,int id=1,int l=-lim,int r=lim){
if(tr[id].calc(mid)>x.calc(mid)) swap(tr[id],x);
if(tr[id].calc(l)>x.calc(l))update(x,lid,l,mid);
if(tr[id].calc(r)>x.calc(r))update(x,rid,mid+1,r);
}
inline int query(int pos,int id=1,int l=-lim,int r=lim){
if(l>pos||r=x.p+1;j--)
update(seg{-sufb[j],sufa[j]});
ans[x.id]+=sufa[x.p+1]-x.k*sufb[x.p+1]-query(x.k);
lst=x.p+1;
}
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}
}
signed main(){return WSN::main();}
T4 构树
正在改。。。咕咕咕
改完了，非常难啊，不过还好题解写得好，很明白，于是改的就快一些，同时还有\(fengwu\)的大力帮助%%%
先粘题解，因为是\(markdown\)格式的嘿嘿嘿，因为写得好
（实际上应该是数树）
给了非多项式算法非常多分吧
Algorithm1：枚举
直接枚举所有的树，一共\(n^{n-2}\)种，根据不同枚举方法会带有不同的\(n^w\)
比如直接枚举prufer序列
Algorithm2：状压dp
假装我们的树是一颗以1为根的有根树，模拟展开dfs子树关系的过程
另\(dp_{i,S,j}\)表示以\(i\)为根，子树里已经已经有\(S\)集合的节点，有\(j\)条边相同
然后为一个\(dp_{i,S,j}\)枚举一个儿子\(v\)以及其子树\(T\)进行合并，注意合并顺序防止重复
（比如可以保证\(S-\{i\}\)中最大编号的点<\(T\)中最大编号的点）
复杂度为\(O(3^n n^w)\)，\(n\leq 15\)是给这个算法的
Algorithm3：Poly算法
要做多项式复杂度的算法，首先需要一点计数的辅助
Cayley公式：一个完全图有\(n^{n-2}\)棵无根生成树，经典问题prufer序列证明
扩展Cayley公式：被确定边分为大小为\(a_1,a_2,\cdots, a_m\)的连通块，则有\(n^{m-2}\prod {a_i}\)种生成树
证明就不再赘述了
那么我们可以通过 强制一条边出现或者是不出现 来统计边数
通过扩展Cayley公式统计强制的边能够得到多少树
比较Naive的想法，我们可以直接在dp中记录连通块大小、相同边数
每次断开一个连通块，乘上一个\(n\)的系数
强制相同的边，直接合并两个连通块即可
\(dp_{u,i,j}\cdot dp_{v,k,l}\rightarrow dp_{u,i+k,j+l+1}\)
强制不同的边，用不合并的-合并的即可得到
\(nk\cdot dp_{u,i,j}\cdot dp_{v,k,l}\rightarrow dp_{u,i,j+l}\)
\(-dp_{u,i,j}\cdot dp_{v,k,l}\rightarrow dp_{u,i+k,j+l}\)
预计分数：不知道
优化
WC数树
首先优化连通块大小，可以通过一个经典的转化：
\(size\)作为系数，转化为在这个连通块中选出一个关键点（很显然\(size\)多大，就有多少中选出一个关键点的方案）
这样这一位被压缩到\(0,1\)，只需要记录是否在这个连通块中选择了关键点
这样复杂度等同于经典树形背包问题，但是空间略紧张
可以将第3维用拉格朗日插值换掉
设答案数列为\(a_i\)，转化为多项式\(A(x)=\sum_{i=0} a_ix^i\)
带入\(x_0=0,1,\cdots ,n\)，求得\(A(x_0)\)的数值，然后插值得到多项式
这样第三维就合并可以直接用\(x_0^k\)换掉
其实上我们只需要会那个扩展Cayley公式的部分就可以过掉这道题，再结合一下题解之外的二项式反演
按照如上的\(dp\)可以打出一个\(O(n^2)\)的树形\(dp\)，空间复杂度\(O(n^2)\)，数组开成\(dp[8001][2][8001]\)，是优化的做法
但是不用拉格朗日插值，使用二项式反演
我们把\(dp\)关于相同边数的那一维变成至少有\(i\)条边，这样转移是不变的，可以感性理解一下，毕竟无法用数学方面的理解方式证明
那么我们做完\(dp\)之后算出至少有\(i\)条边和原树同构的方案数,即\(dp[1][1][i]\times \frac{1}{n}\)，除以一个\(n\)是因为转移的时候累乘的那个\(n\)最后会多成一个
这样就做完了
tree
#include
#define int long long
using namespace std;
namespace AE86{
FILE *wsn;
#define gc() p1==p2 and (p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++
char buf[1<<20],*p1=buf,*p2=buf;
auto read=[](){
int x=0,f=1;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();} return x*f;
};
auto write=[](int x,char opt='\n'){
char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
for(short i=len-1;i>=0;--i){putchar(ch[i]);}putchar(opt);
};
}using namespace AE86;
const int NN=8005,mod=1e9+7;
int n,dp[NN][2][NN],g[NN],h[NN],v[NN],siz[NN];
struct SNOW{int to,next;};SNOW e[NN<<1]; int head[NN],rp;
auto add=[](int x,int y){e[++rp]=SNOW{y,head[x]};head[x]=rp;e[++rp]=SNOW{x,head[y]};head[y]=rp;};
auto qmo=[](int a,int b,int ans=1){for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;};
auto prework=[](){
h[0]=h[1]=1;v[0]=v[1]=1;for(int i=2;i=2;i--)v[i]=v[i+1]*(i+1)%mod;
};auto C=[](int n,int m){return (n