[自家集训]test3

[自家集训]test3

文章目录

• 吐槽
• T1
• T2
• T3

吐槽

毕老爷来了之后一直秒题，全程T1不是什么什么，T2不是啥啥啥嘛，T3你就怎么怎么就好了，ORZ orz题面为什么没写请AK的同学保持安静不要干扰其他同学爆0啊？？能不能给爆0选手留一条活路啊？？然后毒瘤DC没法给我们留饭又不放我们出去让我们中途去吃个饭回来继续考，我回来把T3暴力打了就把程序放ftp上回寝室睡觉了，然鹅李巨只顾和毕老爷谈笑风生并没有帮我交QAQ,于是我就爆0了。
然后一天各种体验非常不好，可能也和身体状态有关然后心情各种烦躁，想想现在这些其实都不重要，重要的只是四月两场考试而已，能进队万事大吉，进不了队一切免谈。

T1

看到相差0,1就开心地差分，然后转换成取小于等于n的互不相等的数凑成m,开心地n^2背包一发，2行for循环就50分到手，美滋滋啊。

醒醒啊你会整数划分问题的根号做法的啊啊宸你不是只会暴力的啊啊啊啊！！！右转这里

//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=1e5+7;
typedef long long LL;
typedef double db;
using namespace std;
LL n,m,p,ans;
LL f[450][N];template<typename T> void read(T &x) {char ch=getchar(); T f=1; x=0;while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') f=-1,ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}int main() {freopen("chl.in","r",stdin);freopen("chl.out","w",stdout);read(n); read(m); read(p);f[0][0]=1; int up=sqrt(2*m)+1;For(i,1,up) {For(v,1,m) {if(v>=i) f[i][v]=(f[i][v-i]+f[i-1][v-(i-1)-1])%p;if(v>=n+1) f[i][v]=(f[i][v]-f[i-1][v-(n+1)]+p)%p;}(ans+=f[i][m])%=p;}printf("%lldn",ans);Formylove;
}

T2

题意转换为将若干区间划分为两个集合，同一集合内的区间只能内含或相离，问方案数。
相交的区间不能在同一集合内，在相交的区间间连边，二分图染色，不能则不存在方案，否则方案数为2的联通块个数次方。

于是我们开始连边了，区间按l排序数据结构中按r维护之前的区间就能找到和当前区间相交的区间，也就是要和我连边的区间了。
然鹅这样边数会达到平方级别，肯定不行，尝试优化一下建边。其实我们只需要知道目前的每个联通块中黑点和白点是否和当前点有边。若只有一种点和当前点有边，则当前点有合法的染色方案，合并联通块。否则不能二分图染色，没有答案。（也就是题解说的只需求这个n^2级别边的图的一个生成树，用其他非树边判断是否有解啦！）
那么对每个联通块的两色点分别按区间的r维护一个数据结构，每次把和我有连边的那些联通块拿出来合并就好啦。
然鹅还需要外层一个数据结构维护所有联通块，才能找到和我相交的联通块。外层的数据结构要按在当前l之后的最前面一个r排序，所以联通块的数据结构要维护所有r,如果用set启发式合并是两个log的，会被卡掉。

啊宸：于是我用线段树合并，美滋滋！
yicongli：(⊙_⊙?)你怎么这么喜欢线段树合并啊？？
啊宸：QAQ因为我（菜）只会线段树合并啊。
线段树：（没错你太菜了）连个query都没有只需要资磁删除最小的和询问最小的就要我屈尊上阵岂不是太大材小用？？
可并堆：不劳烦您老我来了走好咧您～

 //Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=1e6+7,p=998244353;
typedef long long LL;
typedef double db;
using namespace std;
int n,ans,magictag;template<typename T> void read(T &x) {char ch=getchar(); T f=1; x=0;while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') f=-1,ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}LL ksm(LL a,LL b) {LL rs=1,bs=a;while(b) {if(b&1) rs=rs*bs%p;bs=bs*bs%p;b>>=1;}return rs;
}int tot,fa[N<<1],rt[N<<1],v[N],h[N],ch[N][2];
#define lc ch[x][0]
#define rc ch[x][1]
int merge(int x,int y) {if(!(x*y)) return (x^y);if(v[x]>v[y]) swap(x,y);rc=merge(rc,y);if(h[rc]>h[lc]) swap(lc,rc);if(!rc) h[x]=0;else h[x]=h[rc]+1;return x;
}int del(int x) { return merge(lc,rc); }int fcol(int x) { return x<=n?x+n:x-n; }struct train{int l,r;friend bool operator <(const train&A,const train&B) {return A.l<B.l;		}
}tr[N];struct drt{int x,v;friend bool operator<(const drt&A,const drt&B) {return A.v<B.v||(A.v==B.v&&A.x<B.x);}
};
set<drt>s;int main() {freopen("wtx.in","r",stdin);freopen("wtx.out","w",stdout);read(n);For(i,1,n) {read(tr[i].l); read(tr[i].r);}sort(tr+1,tr+n+1);For(i,1,n) {int ql=tr[i].l,qr=tr[i].r;rt[i]=++tot; v[tot]=qr;rt[i+n]=0;fa[i]=i; fa[i+n]=i+n;while(s.size()) {drt t=*s.begin();if(t.v>qr) ase(s.begin());if(fa[t.x]!=t.x) {if(fa[t.x]==i) {magictag=1; break;}continue;}if(t.v<ql) {while(v[rt[t.x]]<ql) {rt[t.x]=del(rt[t.x]);if(!rt[t.x]) break;}if(rt[t.x]) s.insert((drt){t.x,v[rt[t.x]]});}else {rt[i+n]=merge(rt[i+n],rt[t.x]); fa[t.x]=i+n;rt[i]=merge(rt[i],rt[fcol(t.x)]); fa[fcol(t.x)]=i;}}if(magictag==1) break;s.insert((drt){i,v[rt[i]]});if(rt[i+n]) s.insert((drt){i+n,v[rt[i+n]]}); }if(magictag==1) puts("0");else {For(i,1,2*n) if(fa[i]==i) ans++;LL pt=ksm(2,ans/2);printf("%lldn",pt);}//cerr<<clock()<<endl;Formylove;
}

T3

学了一发闵可夫斯基和,不就边分然后合并一发凸包嘛YY一下大力写一波把这题过了。然后发现原题WA了。
还是看看巨佬的优秀题解吧QAQ

不能过原题的垃圾YY代码：

//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=2e5+7;
typedef long double LD;
typedef long long LL;
typedef double db;
using namespace std;
int n,m;template<typename T> void read(T &x) {char ch=getchar(); T f=1; x=0;while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') f=-1,ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}int ecnt,fir[N],nxt[N<<1],to[N<<1],vis[N<<1];
LL val[N<<1],ad[N<<1];
void add(int u,int v,LL w,LL ww) {nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w; ad[ecnt]=ww;nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w; ad[ecnt]=ww;
}#define pr pair<int,pair<LL,LL>>
#define MP make_pair
#define pb push_back
#define se second
#define fi first
vector<pr>son[N];
int tot,sta[N],top;
void rebuild() {sta[++top]=1; tot=n; ecnt=1;memset(fir,0,sizeof(fir));while(top) {int x=sta[top--],up=son[x].size();if(up<=2) {For(i,0,up-1) {add(x,son[x][i].fi,son[x][i].se.fi,son[x][i].se.se);sta[++top]=son[x][i].fi;}}else if(up==3) {For(i,0,up-1) {if(i&1) add(x,son[x][i].fi,son[x][i].se.fi,son[x][i].se.se);else son[tot+1].pb(son[x][i]);}add(x,++tot,0,0);sta[++top]=son[x][1].fi; sta[++top]=tot;}else {For(i,0,up-1) {if(i&1) son[tot+1].pb(son[x][i]);else son[tot+2].pb(son[x][i]);}add(x,++tot,0,0); add(x,++tot,0,0);sta[++top]=tot-1; sta[++top]=tot;}}
}
void dfs1(int x,int fa) {for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) {son[x].pb(MP(to[i],MP(val[i],ad[i])));dfs1(to[i],x);}
}int mxx,eg,sz[N],msz[N];
void get_root(int x,int fa,int tot) {sz[x]=msz[x]=1;for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa&&!vis[i]) {get_root(to[i],x,tot);if(!eg||mxx>msz[to[i]]) eg=i,mxx=msz[to[i]];sz[x]+=sz[to[i]];msz[x]=max(msz[x],sz[to[i]]);					}msz[x]=max(msz[x],tot-sz[x]);
}struct pt{LL x,y;pt(){}pt(LL x,LL y):x(x),y(y){}friend bool operator <(const pt&A,const pt&B) {return A.x&(A.x==B.x&&A.y<B.y);}
}stp[N*20],ham1[N],ham2[N],ham3[N],tpp[N*20];
pt operator -(const pt&A,const pt&B) { return pt(A.x-B.x,A.y-B.y); }
pt operator +(const pt&A,const pt&B) { return pt(A.x+B.x,A.y+B.y); }
LD dot(pt A,pt B) { return (LD)A.x*B.x+(LD)A.y*B.y; }
LD cross(pt A,pt B) { return (LD)A.x*B.y-(LD)A.y*B.x; }
LD lenth(pt A) { return dot(A,A); }void dfs2(int x,int fa,LL k,LL d) {sz[x]=1;stp[++top]=pt(k,d);for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa&&!vis[i]) {dfs2(to[i],x,k+ad[i],d+val[i]);sz[x]+=sz[to[i]];}
}int c1,c2,totpt;
void make_ham(pt ham[],int up,int &cc) {sort(stp+1,stp+up+1);int qr=0;For(i,1,up) {while(qr>1&&cross(stp[i]-ham[qr-1],ham[qr]-ham[qr-1])<=0) qr--;ham[++qr]=stp[i];} cc=qr;
}void merge(int x,int eg) {int n1=2,n2=2,up=0;ham3[++up]=pt(0,0);while(n1<=c1&&n2<=c2) {++up;if(cross(ham1[n1]-ham1[n1-1],ham2[n2]-ham2[n2-1])<=0) { ham3[up]=ham3[up-1]+(ham1[n1]-ham1[n1-1]); ++n1; } else { ham3[up]=ham3[up-1]+(ham2[n2]-ham2[n2-1]); ++n2; }}while(n1<=c1) { ++up; ham3[up]=ham3[up-1]+(ham1[n1]-ham1[n1-1]); ++n1; } while(n2<=c2) { ++up; ham3[up]=ham3[up-1]+(ham2[n2]-ham2[n2-1]); ++n2; }For(i,2,up) tpp[++totpt]=pt(ham3[i].x+ad[eg],ham3[i].y+val[eg]);
}void solve(int x,int tot) {if(tot<=1) return ;eg=0; get_root(x,0,tot);vis[eg]=vis[eg^1]=1;int u=to[eg],v=to[eg^1];top=0; dfs2(u,0,0,0);make_ham(ham1,top,c1);top=0; dfs2(v,0,0,0);make_ham(ham2,top,c2);merge(x,eg);solve(u,sz[u]); solve(v,sz[v]);
}int main() {freopen("yzh.in","r",stdin);freopen("yzh.out","w",stdout);read(n); read(m);LL Fi=0,Se=0;For(i,2,n) {int u,v; LL w,ww;read(u); read(v); read(ww); read(w); add(u,v,w,ww);if(w>Se) Se=w;if(Se>Fi) swap(Fi,Se);}dfs1(1,0);rebuild();solve(1,tot);For(i,1,totpt) stp[i]=tpp[i];make_ham(tpp,totpt,c1);For(i,1,m) {LL t;read(t);LL rs=0;int l=1,r=c1;while(l<=r) {int mid=((l+r)>>1);rs=max(rs,tpp[mid].x*t+tpp[mid].y);if(mid==1||(LD)tpp[mid].y-tpp[mid-1].y>-(LD)t*(tpp[mid].x-tpp[mid-1].x)) l=mid+1;else r=mid-1;}printf("%lldn",rs);}Formylove;
}