目錄

• 2018.8.8 正睿暑期集訓(xùn)營(yíng) Day5
  • 總結(jié)
  • A 友誼巨輪(線(xiàn)段樹(shù) 動(dòng)態(tài)開(kāi)點(diǎn))
  • B 璀璨光滑
  • C 構(gòu)解巨樹(shù)
  • 考試代碼
    • A
    • B
    • C

---

2018.8.8 正睿暑期集訓(xùn)營(yíng) Day5

時(shí)間：3.5h(實(shí)際)
期望得分：60+20+20
實(shí)際得分：20+20+20

比賽鏈接
這里也有一些

總結(jié)

線(xiàn)段樹(shù)！！！
[Update]好了現(xiàn)在我已經(jīng)見(jiàn)什么都想寫(xiě)線(xiàn)段樹(shù)了。

A 友誼巨輪(線(xiàn)段樹(shù) 動(dòng)態(tài)開(kāi)點(diǎn))

題目鏈接

開(kāi)n棵線(xiàn)段樹(shù)，維護(hù)最大值及答案，動(dòng)態(tài)開(kāi)點(diǎn)就完了啊。。

//4810ms 71524kb #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> //#define gc() getchar() #define MAXIN 300000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) typedef long long LL; const int N=1e5+5;int n,K,m,root[N],Ans; char IN[MAXIN],*SS=IN,*TT=IN; struct Operation {int a,b,c; }opt[N];struct Segment_Tree {#define S N*50//每次最多4次Modify，但是有2次之前開(kāi)過(guò)了，so N*17*2就夠。#define ls son[x][0]#define rs son[x][1]#define lson ls,l,m#define rson rs,m+1,rint tot,son[S][2];struct Node{LL mxv; int tm,ans;bool operator <(const Node &x)const{return mxv==x.mxv?tm<x.tm:mxv<x.mxv;}}t[S];#define Update(x) t[x]=std::max(t[ls],t[rs])void Modify(int &x,int l,int r,int p,LL v,int tm){if(!x) x=++tot, ls=rs=0, t[x]=(Node){0,0,0};//取max，tm也要清零啊 if(l==r) {t[x].mxv+=v, t[x].tm=std::max(t[x].tm,tm), t[x].ans=p; return;}int m=l+r>>1;if(p<=m) Modify(lson,p,v,tm);else Modify(rson,p,v,tm);Update(x);} }T;inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } void Modify(int a,int b,int c,int tm) {int bef=T.t[root[a]].ans;T.Modify(root[a],1,n,b,c,tm);int now=T.t[root[a]].ans;if(bef==now) return;if(bef)if(T.t[root[bef]].ans==a) ++Ans;else --Ans;if(now)if(T.t[root[now]].ans==a) --Ans;else ++Ans; }int main() { // freopen("a.in","r",stdin); // freopen("my.out","w",stdout);T.t[0].tm=1000000;for(int Case=read(); Case--; ){memset(root,0,sizeof root);n=read(), K=read(), m=read(), T.tot=Ans=0;for(int i=1,a,b,c; i<=K; ++i){opt[i]=(Operation){a=read(),b=read(),c=read()};Modify(a,b,c,i), Modify(b,a,c,i);if(i>m)Modify(opt[i-m].a,opt[i-m].b,-opt[i-m].c,i-m), Modify(opt[i-m].b,opt[i-m].a,-opt[i-m].c,i-m);printf("%d\n",Ans);}}return 0; }

B 璀璨光滑

題目鏈接

C 構(gòu)解巨樹(shù)

題目鏈接

考試代碼

A

//7.7K...(其實(shí)copy了兩遍) //暴力都可以O(shè)(n)得到答案，非得O(1)。。但是數(shù)組改map就可以60了啊 //巨難調(diào)。。 #include <map> #include <queue> #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> //#define gc() getchar() #define MAXIN 300000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) typedef long long LL; const int N=1e5+5;int n,K,m; char IN[MAXIN],*SS=IN,*TT=IN; struct Operation {int a,b,c; }opt[N];inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } namespace Subtask1 {const int S=1005;int ship[S],tm[S][S];LL mx[S],val[S][S];bool alone[S]; // struct Node // { // int mxv,tm,id; // bool operator <(const Node &x)const{ // return mxv==x.mxv?tm<x.tm:mxv<x.mxv; // } // }; // struct Heap // { // std::priority_queue<Node> q; // inline void Clear() {while(!q.empty()) q.pop();} // }hp[S];void Main(){memset(mx,0,sizeof mx);memset(tm,0,sizeof tm);memset(val,0,sizeof val); // memset(tag,0,sizeof tag);memset(ship,0,sizeof ship);memset(alone,0,sizeof alone); // for(int i=1; i<=n; ++i) hp[i].Clear();int ans=0; if(m>K) m=K;for(int i=1; i<=n; ++i) tm[i][0]=1000000;for(int i=1,a,b,c; i<=m; ++i){a=read(), b=read(), c=read(), opt[i]=(Operation){a,b,c};tm[a][b]=tm[b][a]=i;if((val[a][b]+=c)>=mx[a] && ship[a]!=b){if(ship[ship[a]]==a) ++ans, alone[ship[a]]=1;mx[a]=val[a][b], ship[a]=b;}if((val[b][a]+=c)>=mx[b] && ship[b]!=a){if(ship[ship[b]]==b) ++ans, alone[ship[b]]=1;mx[b]=val[b][a], ship[b]=a;}if(!alone[a]&&ship[a]==b&&ship[b]!=a) ++ans, alone[a]=1;else if(alone[a]&&ship[ship[a]]==a) --ans, alone[a]=0;if(!alone[b]&&ship[b]==a&&ship[a]!=b) ++ans, alone[b]=1;else if(alone[b]&&ship[ship[b]]==b) --ans, alone[b]=0;printf("%d\n",ans);}for(int i=m+1,a,b,c; i<=K; ++i){a=opt[i-m].a, b=opt[i-m].b, c=opt[i-m].c;val[a][b]-=c, val[b][a]-=c; // printf("Now:%d bef:%d a:%d b:%d\n",i,i-m,a,b);if(ship[a]==b){int p=0;for(int j=1; j<=n; ++j) if(val[a][j]>val[a][p]||(val[a][j]==val[a][p]&&tm[a][j]>tm[a][p])) p=j; // printf("a: ship[%d]=%d p:%d\n",a,b,p);if(!p){if(alone[a]) --ans, alone[a]=0;ship[a]=mx[a]=0;}else if(p!=b){if(ship[b]==a) ++ans, alone[b]=1;ship[a]=p, mx[a]=val[a][p];if(ship[p]==a){--ans, alone[p]=0;if(alone[a]) --ans, alone[a]=0;}else if(!alone[a]) ++ans, alone[a]=1;}else mx[a]-=c;} // printf("aa: %d\n",ans);if(ship[b]==a){int p=0;for(int j=1; j<=n; ++j) if(val[b][j]>val[b][p]||(val[b][j]==val[b][p]&&tm[b][j]>tm[b][p])) p=j; // printf("b: ship[%d]=%d p:%d\n",b,a,p);if(!p){if(alone[b]) --ans, alone[b]=0;ship[b]=mx[b]=0;}else if(p!=a){if(ship[a]==b) ++ans, alone[a]=1;ship[b]=p, mx[b]=val[b][p];if(ship[p]==b){--ans, alone[p]=0;if(alone[b]) --ans, alone[b]=0;}else if(!alone[b]) ++ans, alone[b]=1;}else mx[b]-=c;} // printf("bb: %d\n",ans);a=read(), b=read(), c=read(), opt[i]=(Operation){a,b,c};tm[a][b]=tm[b][a]=i;if((val[a][b]+=c)>=mx[a] && ship[a]!=b){if(ship[ship[a]]==a) ++ans, alone[ship[a]]=1;mx[a]=val[a][b], ship[a]=b;}if((val[b][a]+=c)>=mx[b] && ship[b]!=a){if(ship[ship[b]]==b) ++ans, alone[ship[b]]=1;mx[b]=val[b][a], ship[b]=a;}if(!alone[a]&&ship[a]==b&&ship[b]!=a) ++ans, alone[a]=1;else if(alone[a]&&ship[ship[a]]==a) --ans, alone[a]=0;if(!alone[b]&&ship[b]==a&&ship[a]!=b) ++ans, alone[b]=1;else if(alone[b]&&ship[ship[b]]==b) --ans, alone[b]=0;printf("%d\n",ans);}} } namespace Subtask2 {//m=kint ship[N];LL mx[N];bool alone[N];std::map<int,LL> val[N];void Main(){for(int i=1; i<=n; ++i) val[i].clear();memset(mx,0,sizeof mx);memset(ship,0,sizeof ship);memset(alone,0,sizeof alone);int ans=0;for(int i=1,a,b,c; i<=m; ++i){a=read(), b=read(), c=read();if((val[a][b]+=c)>=mx[a] && ship[a]!=b){if(ship[ship[a]]==a) ++ans, alone[ship[a]]=1;mx[a]=val[a][b], ship[a]=b;}if((val[b][a]+=c)>=mx[b] && ship[b]!=a){if(ship[ship[b]]==b) ++ans, alone[ship[b]]=1;mx[b]=val[b][a], ship[b]=a;}if(!alone[a]&&ship[a]==b&&ship[b]!=a) ++ans, alone[a]=1;else if(alone[a]&&ship[ship[a]]==a) --ans, alone[a]=0;if(!alone[b]&&ship[b]==a&&ship[a]!=b) ++ans, alone[b]=1;else if(alone[b]&&ship[ship[b]]==b) --ans, alone[b]=0;printf("%d\n",ans);}} } namespace Subtask3 {int ship[N];LL mx[N];std::map<int,int> tm[N];std::map<int,LL> val[N];bool alone[N];void Main(){memset(mx,0,sizeof mx);memset(ship,0,sizeof ship);memset(alone,0,sizeof alone);for(int i=1; i<=n; ++i) tm[i].clear(), val[i].clear();int ans=0; if(m>K) m=K;for(int i=1; i<=n; ++i) tm[i][0]=1000000;for(int i=1,a,b,c; i<=m; ++i){a=read(), b=read(), c=read(), opt[i]=(Operation){a,b,c};tm[a][b]=tm[b][a]=i;if((val[a][b]+=c)>=mx[a] && ship[a]!=b){if(ship[ship[a]]==a) ++ans, alone[ship[a]]=1;mx[a]=val[a][b], ship[a]=b;}if((val[b][a]+=c)>=mx[b] && ship[b]!=a){if(ship[ship[b]]==b) ++ans, alone[ship[b]]=1;mx[b]=val[b][a], ship[b]=a;}if(!alone[a]&&ship[a]==b&&ship[b]!=a) ++ans, alone[a]=1;else if(alone[a]&&ship[ship[a]]==a) --ans, alone[a]=0;if(!alone[b]&&ship[b]==a&&ship[a]!=b) ++ans, alone[b]=1;else if(alone[b]&&ship[ship[b]]==b) --ans, alone[b]=0;printf("%d\n",ans);}for(int i=m+1,a,b,c; i<=K; ++i){a=opt[i-m].a, b=opt[i-m].b, c=opt[i-m].c;val[a][b]-=c, val[b][a]-=c;if(ship[a]==b){int p=0;for(int j=1; j<=n; ++j) if(val[a][j]>val[a][p]||(val[a][j]==val[a][p]&&tm[a][j]>tm[a][p])) p=j;if(!p){if(alone[a]) --ans, alone[a]=0;ship[a]=mx[a]=0;}else if(p!=b){if(ship[b]==a) ++ans, alone[b]=1;ship[a]=p, mx[a]=val[a][p];if(ship[p]==a){--ans, alone[p]=0;if(alone[a]) --ans, alone[a]=0;}else if(!alone[a]) ++ans, alone[a]=1;}else mx[a]-=c;}if(ship[b]==a){int p=0;for(int j=1; j<=n; ++j) if(val[b][j]>val[b][p]||(val[b][j]==val[b][p]&&tm[b][j]>tm[b][p])) p=j;if(!p){if(alone[b]) --ans, alone[b]=0;ship[b]=mx[b]=0;}else if(p!=a){if(ship[a]==b) ++ans, alone[a]=1;ship[b]=p, mx[b]=val[b][p];if(ship[p]==b){--ans, alone[p]=0;if(alone[b]) --ans, alone[b]=0;}else if(!alone[b]) ++ans, alone[b]=1;}else mx[b]-=c;}a=read(), b=read(), c=read(), opt[i]=(Operation){a,b,c};tm[a][b]=tm[b][a]=i;if((val[a][b]+=c)>=mx[a] && ship[a]!=b){if(ship[ship[a]]==a) ++ans, alone[ship[a]]=1;mx[a]=val[a][b], ship[a]=b;}if((val[b][a]+=c)>=mx[b] && ship[b]!=a){if(ship[ship[b]]==b) ++ans, alone[ship[b]]=1;mx[b]=val[b][a], ship[b]=a;}if(!alone[a]&&ship[a]==b&&ship[b]!=a) ++ans, alone[a]=1;else if(alone[a]&&ship[ship[a]]==a) --ans, alone[a]=0;if(!alone[b]&&ship[b]==a&&ship[a]!=b) ++ans, alone[b]=1;else if(alone[b]&&ship[ship[b]]==b) --ans, alone[b]=0;printf("%d\n",ans);}} }int main() { // freopen("a2.in","r",stdin); // freopen("my.out","w",stdout);for(int Case=read(); Case--; ){n=read(), K=read(), m=read();if(m==K) {Subtask2::Main(); continue;}if(n<=1000) {Subtask1::Main(); continue;}Subtask3::Main(); // for(int i=1; i<=K; ++i) opt[i]=(Operation){read(),read(),read()};}return 0; }

B

#include <cstdio> #include <cctype> #include <cstring> #include <algorithm> //#define gc() getchar() #define MAXIN 400000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) #define mod (1000000007) typedef long long LL; const int N=5e5+5,M=4e5+5;int n,m,lim,pw2[N],pw10[N],Enum,H[N],nxt[M],to[M],p[N]; bool vic,use[N]; char IN[MAXIN],*SS=IN,*TT=IN;inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } inline void AddEdge(int u,int v) {if(u<v) std::swap(u,v);to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;//big->small } inline bool Check(int v1,int v2) {for(int i=0,f=1; i<=n; ++i)if((v1>>i&1)^(v2>>i&1))if(f) f=0;else return 0;return 1; } inline bool OK(int x,int val) {for(int i=H[x]; i; i=nxt[i])if(!Check(p[to[i]],val)) return 0;return 1; } void DFS(int now,LL ans) {if(vic) return;if(now==lim) {vic=1, printf("%lld\n",ans%mod); return;}for(int x=0; x<lim; ++x)if(!use[x] && OK(now,x)){use[x]=1, p[now]=x;DFS(now+1,ans+1ll*x*pw10[now]%mod);if(vic) return;use[x]=0;} }int main() { // freopen("b1.in","r",stdin); // freopen(".out","w",stdout);pw10[0]=1;for(int i=0; i<=18; ++i) pw2[i]=1<<i;for(int i=1; i<=pw2[12]/*pw2[18]*/; ++i) pw10[i]=1ll*pw10[i-1]*10%mod;for(int Case=read(); Case--; ){n=read(), m=read(), Enum=vic=0, lim=pw2[n];for(int i=1; i<=lim; ++i) H[i]=0;for(int i=1; i<=m; ++i) AddEdge(read()-1,read()-1);DFS(0,0);for(int i=0; i<lim; ++i) use[i]=0;}return 0; }

C

#include <cstdio> #include <cctype> #include <assert.h> #include <algorithm> //#define gc() getchar() #define MAXIN 400000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) #define mod (1000000007) typedef long long LL; const int N=1e5+5,M=4e5+5;int n,m,Enum,H[N],nxt[M],to[M],sz[N],sum[N],sz2[N],sum2[N],sz3[N],sum3[N]; LL Ans; char IN[MAXIN],*SS=IN,*TT=IN;inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } inline void AddEdge(int u,int v) {to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum; } namespace Subtask1 {const int N=4e6+5,M=N<<1;int Enum,H[N],nxt[M],to[M],sz[N],sum[N];LL Ans;inline void AddEdge(int u,int v){ // printf("%d->%d\n",u,v);to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;}void DFS(int x,int f){sz[x]=1; LL tmp=0;for(int v,i=H[x]; i; i=nxt[i])if((v=to[i])!=f) DFS(v,x), sz[x]+=sz[v], tmp+=sum[v];sum[x]=(int)((tmp+sz[x])%mod);tmp=0;for(int v,i=H[x]; i; i=nxt[i])if((v=to[i])!=f) tmp+=1ll*(sz[x]-sz[v])*sum[v]%mod;Ans+=tmp%mod;}void Main(){for(int i=1; i<n; ++i)for(int u=read(),v=read(),j=0; j<m; ++j) AddEdge(j*n+u,j*n+v);for(int i=1,a,b; i<m; ++i) a=read()-1,b=read()-1,AddEdge(b*n+read(),a*n+read());//mmp忘了 DFS(1,1);printf("%lld\n",Ans%mod);} } void DFS(int x,int f) {sum[x]=0, sz[x]=1; LL tmp=0;for(int v,i=H[x]; i; i=nxt[i])if((v=to[i])!=f) DFS(v,x), sz[x]+=sz[v], tmp+=sum[v];sum[x]=(int)((tmp+sz[x])%mod);tmp=0;for(int v,i=H[x]; i; i=nxt[i])if((v=to[i])!=f) tmp+=1ll*(sz[x]-sz[v])*sum[v]%mod;Ans+=tmp%mod; } void DFS2(int x,int f) {LL tmp=0,size=sz3[x]+1;for(int v,i=H[x]; i; i=nxt[i])if((v=to[i])!=f) DFS(v,x), size+=sz[v], tmp+=sum[v];sz[x]=(int)(size%mod);sum[x]=(int)((tmp+sz[x]+sum3[x])%mod);tmp=0;for(int v,i=H[x]; i; i=nxt[i])if((v=to[i])!=f) tmp+=1ll*(sz[x]-sz[v])*sum[v]%mod;Ans+=tmp%mod; }int main() {freopen("c3.in","r",stdin); // freopen(".out","w",stdout);n=read(), m=read();if(1ll*n*m<=4e6) {Subtask1::Main(); return 0;} for(int i=1; i<n; ++i) AddEdge(read(),read());DFS(1,1), Ans=Ans*(m-1)%mod;sum2[1]=sum[1], sz2[1]=sz[1];for(int i=1,a,b,u,v; i<m; ++i){a=read(), b=read(), u=read(), v=read();if(!sz2[v]) DFS(v,v);sz3[u]+=sz2[v], sz3[u]>=mod&&(sz3[u]-=mod);sum3[u]+=(sum2[v]+sz2[v])%mod, sum3[u]>=mod&&(sum3[u]-=mod);}DFS2(1,1);printf("%lld\n",Ans%mod);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/SovietPower/p/9443847.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的8.8 正睿暑期集训营 Day5的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。