网站如何做超级链接,旅游论坛网站建设,wordpress 关闭站点,烟台seo推广优化目录 2018.8.8 正睿暑期集训营 Day5总结A 友谊巨轮(线段树 动态开点)B 璀璨光滑C 构解巨树考试代码ABC2018.8.8 正睿暑期集训营 Day5时间#xff1a;3.5h(实际)期望得分#xff1a;602020实际得分#xff1a;202020 比赛链接这里也有一些 总结 线段树#xff01;#xff0… 目录 2018.8.8 正睿暑期集训营 Day5总结A 友谊巨轮(线段树 动态开点)B 璀璨光滑C 构解巨树考试代码ABC 2018.8.8 正睿暑期集训营 Day5 时间3.5h(实际)期望得分602020实际得分202020 比赛链接这里也有一些 总结 线段树[Update]好了现在我已经见什么都想写线段树了。 A 友谊巨轮(线段树 动态开点) 题目链接 开n棵线段树维护最大值及答案动态开点就完了啊。。 //4810ms 71524kb
#include cstdio
#include cctype
#include cstring
#include algorithm
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SSTT(TT(SSIN)fread(IN,1,MAXIN,stdin),SSTT)?EOF:*SS)
typedef long long LL;
const int N1e55;int n,K,m,root[N],Ans;
char IN[MAXIN],*SSIN,*TTIN;
struct Operation
{int a,b,c;
}opt[N];struct Segment_Tree
{#define S N*50//每次最多4次Modify但是有2次之前开过了so N*17*2就够。#define ls son[x][0]#define rs son[x][1]#define lson ls,l,m#define rson rs,m1,rint tot,son[S][2];struct Node{LL mxv; int tm,ans;bool operator (const Node x)const{return mxvx.mxv?tmx.tm:mxvx.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) xtot, lsrs0, t[x](Node){0,0,0};//取maxtm也要清零啊 if(lr) {t[x].mxvv, t[x].tmstd::max(t[x].tm,tm), t[x].ansp; return;}int mlr1;if(pm) Modify(lson,p,v,tm);else Modify(rson,p,v,tm);Update(x);}
}T;inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-0,cgc());return now;
}
void Modify(int a,int b,int c,int tm)
{int befT.t[root[a]].ans;T.Modify(root[a],1,n,b,c,tm);int nowT.t[root[a]].ans;if(befnow) return;if(bef)if(T.t[root[bef]].ansa) Ans;else --Ans;if(now)if(T.t[root[now]].ansa) --Ans;else Ans;
}int main()
{
// freopen(a.in,r,stdin);
// freopen(my.out,w,stdout);T.t[0].tm1000000;for(int Caseread(); Case--; ){memset(root,0,sizeof root);nread(), Kread(), mread(), T.totAns0;for(int i1,a,b,c; iK; i){opt[i](Operation){aread(),bread(),cread()};Modify(a,b,c,i), Modify(b,a,c,i);if(im)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 构解巨树 题目链接 考试代码 A //7.7K...(其实copy了两遍)
//暴力都可以O(n)得到答案非得O(1)。。但是数组改map就可以60了啊
//巨难调。。
#include map
#include queue
#include cstdio
#include cctype
#include cstring
#include algorithm
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SSTT(TT(SSIN)fread(IN,1,MAXIN,stdin),SSTT)?EOF:*SS)
typedef long long LL;
const int N1e55;int n,K,m;
char IN[MAXIN],*SSIN,*TTIN;
struct Operation
{int a,b,c;
}opt[N];inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-0,cgc());return now;
}
namespace Subtask1
{const int S1005;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 mxvx.mxv?tmx.tm:mxvx.mxv;
// }
// };
// struct Heap
// {
// std::priority_queueNode 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 i1; in; i) hp[i].Clear();int ans0; if(mK) mK;for(int i1; in; i) tm[i][0]1000000;for(int i1,a,b,c; im; i){aread(), bread(), cread(), 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]bship[b]!a) ans, alone[a]1;else if(alone[a]ship[ship[a]]a) --ans, alone[a]0;if(!alone[b]ship[b]aship[a]!b) ans, alone[b]1;else if(alone[b]ship[ship[b]]b) --ans, alone[b]0;printf(%d\n,ans);}for(int im1,a,b,c; iK; i){aopt[i-m].a, bopt[i-m].b, copt[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 p0;for(int j1; jn; j) if(val[a][j]val[a][p]||(val[a][j]val[a][p]tm[a][j]tm[a][p])) pj;
// 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 p0;for(int j1; jn; j) if(val[b][j]val[b][p]||(val[b][j]val[b][p]tm[b][j]tm[b][p])) pj;
// 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);aread(), bread(), cread(), 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]bship[b]!a) ans, alone[a]1;else if(alone[a]ship[ship[a]]a) --ans, alone[a]0;if(!alone[b]ship[b]aship[a]!b) ans, alone[b]1;else if(alone[b]ship[ship[b]]b) --ans, alone[b]0;printf(%d\n,ans);}}
}
namespace Subtask2
{//mkint ship[N];LL mx[N];bool alone[N];std::mapint,LL val[N];void Main(){for(int i1; in; i) val[i].clear();memset(mx,0,sizeof mx);memset(ship,0,sizeof ship);memset(alone,0,sizeof alone);int ans0;for(int i1,a,b,c; im; i){aread(), bread(), cread();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]bship[b]!a) ans, alone[a]1;else if(alone[a]ship[ship[a]]a) --ans, alone[a]0;if(!alone[b]ship[b]aship[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::mapint,int tm[N];std::mapint,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 i1; in; i) tm[i].clear(), val[i].clear();int ans0; if(mK) mK;for(int i1; in; i) tm[i][0]1000000;for(int i1,a,b,c; im; i){aread(), bread(), cread(), 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]bship[b]!a) ans, alone[a]1;else if(alone[a]ship[ship[a]]a) --ans, alone[a]0;if(!alone[b]ship[b]aship[a]!b) ans, alone[b]1;else if(alone[b]ship[ship[b]]b) --ans, alone[b]0;printf(%d\n,ans);}for(int im1,a,b,c; iK; i){aopt[i-m].a, bopt[i-m].b, copt[i-m].c;val[a][b]-c, val[b][a]-c;if(ship[a]b){int p0;for(int j1; jn; j) if(val[a][j]val[a][p]||(val[a][j]val[a][p]tm[a][j]tm[a][p])) pj;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 p0;for(int j1; jn; j) if(val[b][j]val[b][p]||(val[b][j]val[b][p]tm[b][j]tm[b][p])) pj;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;}aread(), bread(), cread(), 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]bship[b]!a) ans, alone[a]1;else if(alone[a]ship[ship[a]]a) --ans, alone[a]0;if(!alone[b]ship[b]aship[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 Caseread(); Case--; ){nread(), Kread(), mread();if(mK) {Subtask2::Main(); continue;}if(n1000) {Subtask1::Main(); continue;}Subtask3::Main();
// for(int i1; iK; 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() (SSTT(TT(SSIN)fread(IN,1,MAXIN,stdin),SSTT)?EOF:*SS)
#define mod (1000000007)
typedef long long LL;
const int N5e55,M4e55;int n,m,lim,pw2[N],pw10[N],Enum,H[N],nxt[M],to[M],p[N];
bool vic,use[N];
char IN[MAXIN],*SSIN,*TTIN;inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-0,cgc());return now;
}
inline void AddEdge(int u,int v)
{if(uv) 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 i0,f1; in; i)if((v1i1)^(v2i1))if(f) f0;else return 0;return 1;
}
inline bool OK(int x,int val)
{for(int iH[x]; i; inxt[i])if(!Check(p[to[i]],val)) return 0;return 1;
}
void DFS(int now,LL ans)
{if(vic) return;if(nowlim) {vic1, printf(%lld\n,ans%mod); return;}for(int x0; xlim; x)if(!use[x] OK(now,x)){use[x]1, p[now]x;DFS(now1,ans1ll*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 i0; i18; i) pw2[i]1i;for(int i1; ipw2[12]/*pw2[18]*/; i) pw10[i]1ll*pw10[i-1]*10%mod;for(int Caseread(); Case--; ){nread(), mread(), Enumvic0, limpw2[n];for(int i1; ilim; i) H[i]0;for(int i1; im; i) AddEdge(read()-1,read()-1);DFS(0,0);for(int i0; ilim; i) use[i]0;}return 0;
} C #include cstdio
#include cctype
#include assert.h
#include algorithm
//#define gc() getchar()
#define MAXIN 400000
#define gc() (SSTT(TT(SSIN)fread(IN,1,MAXIN,stdin),SSTT)?EOF:*SS)
#define mod (1000000007)
typedef long long LL;
const int N1e55,M4e55;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],*SSIN,*TTIN;inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-0,cgc());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 N4e65,MN1;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 tmp0;for(int v,iH[x]; i; inxt[i])if((vto[i])!f) DFS(v,x), sz[x]sz[v], tmpsum[v];sum[x](int)((tmpsz[x])%mod);tmp0;for(int v,iH[x]; i; inxt[i])if((vto[i])!f) tmp1ll*(sz[x]-sz[v])*sum[v]%mod;Anstmp%mod;}void Main(){for(int i1; in; i)for(int uread(),vread(),j0; jm; j) AddEdge(j*nu,j*nv);for(int i1,a,b; im; i) aread()-1,bread()-1,AddEdge(b*nread(),a*nread());//mmp忘了 DFS(1,1);printf(%lld\n,Ans%mod);}
}
void DFS(int x,int f)
{sum[x]0, sz[x]1; LL tmp0;for(int v,iH[x]; i; inxt[i])if((vto[i])!f) DFS(v,x), sz[x]sz[v], tmpsum[v];sum[x](int)((tmpsz[x])%mod);tmp0;for(int v,iH[x]; i; inxt[i])if((vto[i])!f) tmp1ll*(sz[x]-sz[v])*sum[v]%mod;Anstmp%mod;
}
void DFS2(int x,int f)
{LL tmp0,sizesz3[x]1;for(int v,iH[x]; i; inxt[i])if((vto[i])!f) DFS(v,x), sizesz[v], tmpsum[v];sz[x](int)(size%mod);sum[x](int)((tmpsz[x]sum3[x])%mod);tmp0;for(int v,iH[x]; i; inxt[i])if((vto[i])!f) tmp1ll*(sz[x]-sz[v])*sum[v]%mod;Anstmp%mod;
}int main()
{freopen(c3.in,r,stdin);
// freopen(.out,w,stdout);nread(), mread();if(1ll*n*m4e6) {Subtask1::Main(); return 0;} for(int i1; in; i) AddEdge(read(),read());DFS(1,1), AnsAns*(m-1)%mod;sum2[1]sum[1], sz2[1]sz[1];for(int i1,a,b,u,v; im; i){aread(), bread(), uread(), vread();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;
}转载于:https://www.cnblogs.com/SovietPower/p/9443847.html
