软件开发网站建设科技有限公司,软件工程就业岗位,简易手工制作,分析公司网站的开发策略文章目录前言题目解析染色计划#xff08;color#xff09;奇度边集#xff08;edges#xff09;猜拳游戏#xff08;guess#xff09;代码T1T2LCT整体二分总结前言
120pts 期望#xff1a;4010020160 实际#xff1a;406020120 rnk 9
我yue了。 怎么又是不可抗力性挂…
文章目录前言题目解析染色计划color奇度边集edges猜拳游戏guess代码T1T2LCT整体二分总结前言
120pts 期望4010020160 实际406020120 rnk 9
我yue了。 怎么又是不可抗力性挂分… ybt的数据锅了点编号竟然有0splay0直接RE到天荒地老。 就这还有人过 但这次这个T2做的还是挺不错的虽然做了两个点但是确实是一道挺难的题。 为什么分都这么高啊qwq 人强我菜。
题目解析
染色计划color
这个题挺妙的。 不是特别难但做完B确实没有太多时间想这个题了。
考虑点分治。 我们每次对于分治重心都强制让它被选取把其颜色的点加入队列。每次弹出队首每次往当前的父亲即重心方向跳将途中未入队的颜色加入队列。如果遇到当前分治联通块以外的点就直接放弃这次更新答案。 关于正确性反过来想对于最优方案必然存在一个点分治过程中的联通块使得最优方案的联通子树出现在一个极大的分治联通块中且经过这个联通块。一开始可以把这个联通块设为全集若不过重心就可以往一个联通块递归
还有一个虚树的做法但pdf讲的很草率我也没明白…但是似乎就是对我写的那个暴力思路的一定优化。
奇度边集edges
大概在九点的时候看到了本题的关键性质合法的充要条件是所有联通块的点数均为偶数。 于是决定这次考试就搞它了。 这个题确实挺难的我以为看到这个性质之后应该就呼之欲出了结果呼了半天也没出来… 想了很多方面由于显然的二分性也想过整体二分但是常规的整体二分做不了之后我就放弃了也是因为整体二分是比较冷门的算法。
LCT的做法似乎还是比较好想的。 从已经存在解的时刻可以并查集简单求出然后开始考虑优化答案。 最优解必然在最小生成森林上这也是LCT的拿手好戏。 然后每次只需要尝试删去权值最大的边这个边可以用 set 来找到。 能删去当且仅当边两侧的联通块都是偶数大小。 个人的做法比较粗暴就是维护虚子树大小然后暴力把边断开看看两遍大小如果不能断就再连回去。 由于每条边只能删一次总复杂度 O(nlogn)O(n\log n)O(nlogn)。 然而修完数据后一交发现T成70啊哈 CF神机尚且给4sybt破机器给1s就离谱。
无奈只好看看整体二分怎么做。 似乎主流说这个做法是sdq分治但个人认为更像整体二分但名字也不重要吧 实现不是特别难但是不太容易想到。和LCT正好反过来 显然但重要的性质答案单调不升。 常规的递归函数 solve(l,r,L,R)solve(l,r,L,R)solve(l,r,L,R)表示 (l,r)(l,r)(l,r) 处理的询问答案属于 [L,R][L,R][L,R]。 需要保证在执行该函数时加入且仅加入了 [1,l−1][1,l-1][1,l−1] 的所有边权属于 [1,L][1,L][1,L] 的边。 尝试求出 midmidmid 的答案。先把 [l,mid][l,mid][l,mid] 边权属于 [1,L][1,L][1,L] 的边加入再从 LLL 开始权值从小到大枚举边把所有 [1,mid][1,mid][1,mid] 的边加入直到符合要求当前边权即 ansmidans_{mid}ansmid。
然后就是递归处理 solve(l,mid−1,ansmid,R),solve(mid1,r,L,ansmid)solve(l,mid-1,ans_{mid},R),solve(mid1,r,L,ans_{mid})solve(l,mid−1,ansmid,R),solve(mid1,r,L,ansmid)注意依然要满足前提保证。 考虑单层复杂度是 O((r−l)(R−L))O((r-l)(R-L))O((r−l)(R−L))由于递归的每层值域和询问区间的大小都是 O(m)O(m)O(m)所以递归树大小为 O(mlogm)O(m\log m)O(mlogm) 需要启发式合并带log的可撤销并查集总复杂度 O(mlogmlogn)O(m\log m\log n)O(mlogmlogn)。
猜拳游戏guess
三进制 FWT神题。 然鹅我FWT已经全忘光乐啊哈 好像还需要一点矩阵相关可我线代还几乎属于知识荒漠… 直接开摆
代码
T1
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N3e5100;int n,m;
int ans2e9;struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;return;
}
vectorintv[N];
int hson[N],S,rt,siz[N],mx[N],vis[N],tag[N],tim,fa[N];
int col[N];
void findrt(int x,int f){siz[x]1;tag[x]tim;mx[x]0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof||vis[to]) continue;findrt(to,x);siz[x]siz[to];if(mx[x]siz[to]) mx[x]siz[to];}mx[x]max(mx[x],S-siz[x]);if(mx[x]mx[rt]) rtx;return;
}
void dfs(int x,int f){fa[x]f;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof||vis[to]) continue;dfs(to,x);}return;
}
int q[N],st,ed,jd[N],inque[N];
bool add(int c){jd[c]tim;for(int x:v[c]){if(tag[x]!tim) return false;q[ed]x;inque[x]tim;//printf( add: %d\n,x);}return true;
}
void calc(int rt){st1;ed0;if(!add(col[rt])) return;int res(0);while(sted){int nowq[st];if(fa[now]) nowfa[now];while(inque[now]!tim){//printf(now%d\n,now);if(jd[col[now]]!tim){if(!add(col[now])) return;res;}nowfa[now];}}ansmin(ans,res);
}
void solve(int x,int nS){tim;SnS;rt0;findrt(x,0);xrt;vis[x]1;dfs(x,0);//printf(x%d\n,x);calc(x);for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(vis[to]) continue;solve(to,nS-mx[to]);}return;
}signed main(){freopen(color.in,r,stdin);freopen(color.out,w,stdout);memset(fi,-1,sizeof(fi));cnt-1;nread();mread();mx[0]2e9;for(int i1;in;i){int xread(),yread();addline(x,y);addline(y,x);}for(int i1;in;i){col[i]read();v[col[i]].push_back(i);}solve(1,n);printf(%d\n,ans);return 0;
}
/*
*/T2
LCT
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
void write(ll x){if(x9) write(x/10);putchar(0x%10);
}
const int N4e5100;int n,m;struct edge{int x,y,w,id;bool operator (const edge oth)const{if(w!oth.w) return woth.w;else return idoth.id;}
}e[N];
setedges;int tr[N][2],f[N],rev[N],val[N],mx[N],tot,siz1[N],siz2[N];
inline bool nroot(int x){return tr[f[x]][0]x||tr[f[x]][1]x;
}
inline bool which(int x){return tr[f[x]][1]x;
}
inline void pushup(int x){mx[x]x;if(tr[x][0]){if(val[mx[tr[x][0]]]val[mx[x]]) mx[x]mx[tr[x][0]];}if(tr[x][1]){if(val[mx[tr[x][1]]]val[mx[x]]) mx[x]mx[tr[x][1]];}siz1[x]siz1[tr[x][0]]siz1[tr[x][1]]siz2[x](xn);return;
}
inline void Rev(int x){if(x){rev[x]^1;swap(tr[x][0],tr[x][1]);}
}
inline void pushdown(int x){if(rev[x]){rev[x]0;Rev(tr[x][0]);Rev(tr[x][1]);}
}
inline void rotate(int x){int faf[x],gfaf[fa];int dwhich(x),sontr[x][d^1];f[x]gfa;if(nroot(fa)) tr[gfa][which(fa)]x;f[fa]x;tr[x][d^1]fa;if(son){f[son]fa;}tr[fa][d]son;pushup(fa);pushup(x);return;
}
int zhan[N];
inline void splay(int x){int y(x),top(0);zhan[top]y;//debug(splay %d\n,x);while(nroot(y)) zhan[top]yf[y];//debug( %d\n,y);while(top) pushdown(zhan[top--]);for(int fa;faf[x],nroot(x);rotate(x)){if(nroot(fa)) which(fa)which(x)?rotate(fa):rotate(x);}
}
inline void access(int x){for(int y(0);x;yx,xf[x]){splay(x);siz2[x]siz1[tr[x][1]];tr[x][1]y;siz2[x]-siz1[tr[x][1]];pushup(x);}
}
inline void makeroot(int x){access(x);splay(x);Rev(x);
}
inline int findroot(int x){access(x);splay(x);while(pushdown(x),tr[x][0]) xtr[x][0];return x;
}
inline void split(int x,int y){makeroot(x);access(y);splay(y);
}
inline void link(int x,int y){//printf(link: %d %d\n,x,y);//assert(findroot(x)!findroot(y));makeroot(x);//makeroot(y);access(y);splay(y);f[x]y;siz2[y]siz1[x];pushup(y);return;
}
inline void cut(int x,int y){//printf(cut: %d %d\n,x,y);split(x,y);//if(tr[y][0]!x||tr[x][1]){// printf(!!\n);// print();// exit(0);//}//assert(tr[y][0]x!tr[x][1]);tr[y][0]f[x]0;pushup(y);return;
}
inline int Siz(int x){makeroot(x);return siz1[x];
}int fa[N],siz[N];
int find(int x){return fa[x]x?x:fa[x]find(fa[x]);
}
inline void merge(int x,int y){xfind(x),yfind(y);if(xy) return;if(siz[x]siz[y]) swap(x,y);fa[x]y;siz[y]siz[x];return;
}int calc(){for(int i1;in;i) fa[i]i,siz[i]1;int numn;for(auto e:s){int xfind(e.x),yfind(e.y);if(x!y(siz[x]1)(siz[y]1)) num-2;merge(x,y);//printf( (%d %d) tot%d\n,x,y,tot);if(!num) return e.w;}return -1;
}
void bf(){for(int i1;im;i){//printf(\ni%d\n,i);e[i](edge){(int)read(),(int)read(),(int)read(),i};s.insert(e[i]);printf(%d\n,calc());}
}
int nam[N],bel[N];
void solve(){for(int i0;in;i) val[i]-1;totn;for(int i1;in;i){fa[i]i,siz[i]siz1[i]1;mx[i]i;}int numn;for(int i1;im;i){//ok;int xread(),yread(),wread();e[i](edge){x,y,w,i};if(x!y){//printf(i%d (%d %d %d) findroot%d %d\n,i,x,y,w,findroot(x),findroot(y));if(find(x)!find(y)){s.insert(e[i]);tot;val[tot]w;link(x,tot);link(y,tot);nam[i]tot;bel[tot]i;}else{split(x,y);int omx[y];if(val[o]w){s.insert(e[i]);makeroot(o);//splay(o);tr[o][0]f[tr[o][0]]0;tr[o][1]f[tr[o][1]]0;s.erase(e[bel[o]]);tot;val[tot]w;link(x,tot);link(y,tot);nam[i]tot;bel[tot]i;}}}if(find(x)!find(y)(siz[find(x)]1)(siz[find(y)]1)) num-2;//printf(x%d y%d find%d %d siz%d %d num%d\n,//x,y,find(x),find(y),siz[find(x)],siz[find(y)],num);merge(x,y);if(num) puts(-1);else{while(1){//debug(1\n);edge o(*s.rbegin());//debug(2\n);int xo.x,yo.y,ko.id,idnam[k]; cut(id,x);cut(id,y);//debug(2\n);//printf( k%d (%d %d) id%d siz%d %d\n,k,x,y,id,Siz(x),Siz(y));if((Siz(x)1)0(Siz(y)1)0){s.erase(s.find(o));}else{//printf(recover\n);link(id,x);link(id,y);printf(%d\n,o.w);break;}}}//print();}return;
}signed main(){freopen(edges.in,r,stdin);freopen(edges.out,w,stdout);nread();mread();if(n1000m3000) bf();else solve();//solve();return 0;
}
/*
*/
整体二分
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N8e5100;
const int M1e6100;int n,m,p,q;int fa[N],siz[N],u[N],v[N],top,num;
int find(int x){return fa[x]x?x:find(fa[x]);
}
inline void merge(int x,int y){if(!x||!y) return;xfind(x);yfind(y);if(xy) return;if((siz[x]1)(siz[y]1)) num-2;if(siz[x]siz[y]) swap(x,y);fa[x]y;siz[y]siz[x];top;u[top]x;v[top]y;//printf(merge: %d %d num%d\n,x,y,num);return;
}
inline void recover(int goal){while(top!goal){int xu[top],yv[top];fa[x]x;siz[y]-siz[x];if((siz[x]1)(siz[y]1)) num2;--top;}return;
}struct edge{int x,y,w,id;
}e[N],E[N];
bool cmp(edge x,edge y){return x.wy.w;
}
int mx;
int ans[N];
void solve(int l,int r,int L,int R){if(lr) return;if(LR){for(int il;ir;i) ans[i]L;return;}//printf(solve: (%d %d) (%d %d)\n,l,r,L,R);int mid(lr)1,pretop;for(int il;imid;i){if(e[i].wE[L].w) merge(e[i].x,e[i].y);}int otop;//recover(pre);for(int iL;iR;i){if(E[i].idmid) merge(E[i].x,E[i].y);if(!num){ans[mid]i;break;}}if(!ans[mid]) ans[mid]m1;//printf(mid%d ans%d\n,mid,ans[mid]);recover(o);solve(mid1,r,L,ans[mid]);recover(pre);for(int iL;imin(m,ans[mid]);i){if(E[i].idl) merge(E[i].x,E[i].y);}solve(l,mid-1,ans[mid],R);recover(pre);
}
signed main(){freopen(edges.in,r,stdin);freopen(edges.out,w,stdout);nread();mread();numn;for(int i1;in;i) fa[i]i,siz[i]1;for(int i1;im;i){e[i]E[i](edge){(int)read(),(int)read(),(int)read(),i};mxmax(mx,e[i].w);//printf((%d %d)\n,e[i].x,e[i].y);}sort(E1,E1m,cmp);solve(1,m,1,m1);for(int i1;im;i) printf(%d\n,ans[i]m?E[ans[i]].w:-1);return 0;
}
/*
*/
总结
没有挂分就还是不错的。 但是今天在T2上花的时间有点过长了… 但是确实没有浪费时间想解法码代码debug对拍过程中一直在做事。 还是要加快节奏吧。
