本文共 25256 字，大约阅读时间需要 84 分钟。
A.有向图缩点成DAG图，找入度为0的数量
很显然这个N <=100的数据范围和题目给的一条线上的限制可以一百倍的简化这个题，但是架不住我脑子不好使，上去就只想缩点。
一个有趣的问题是如果左右两兄弟距离相同，传给靠左边兄弟的做法才可以AC，似乎是数据有问题或者我的算法有问题？
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 100010;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;int a[maxn];struct Edge{ int to,next;}edge[maxn * 2];int head[maxn],tot;void init(){ for(int i = 0; i <= N ; i ++) head[i] = -1; tot = 0;}void add(int u,int v){ edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;}int Low[maxn],dfn[maxn],Stack[maxn],Belong[maxn],num[maxn];int Index,top,scc;bool Instack[maxn];void Tarjan(int u){ int v; Low[u] = dfn[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];~i ; i = edge[i].next){ int v = edge[i].to; if(!dfn[v]){ Tarjan(v); if(Low[u] > Low[v]) Low[u] = Low[v]; }else if(Instack[v] && Low[u] > dfn[v]) Low[u] = dfn[v]; } if(Low[u] == dfn[u]){ scc++; do{ v = Stack[--top]; Instack[v] = false; Belong[v] = scc; num[scc]++; }while(v != u); }}int ind[maxn];int main(){ Sca(N); init(); for(int i = 1; i <= N ; i ++){ Sca(a[i]); } if(N == 1){puts("1");return 0;} sort(a + 1,a + 1 + N); for(int i = 1; i <= N ; i ++){ if(i == 1) add(i,i + 1); else if(i == N) add(i,i - 1); else{ if(abs(a[i] - a[i - 1]) > abs(a[i] - a[i + 1])){ add(i,i + 1); }else{ add(i,i - 1); } } } for(int i = 1; i <= N ; i ++) if(!dfn[i]) Tarjan(i); for(int i = 1; i <= N ; i ++){ for(int j = head[i]; ~j ; j = edge[j].next){ int v = edge[j].to; if(Belong[v] != Belong[i]) ind[Belong[v]]++; } } int ans = 0; for(int i = 1; i <= scc;i ++) if(!ind[i]) ans++; Pri(ans); return 0;}
B.所有情况列出来比较一下谁最优秀
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 110;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;int main(){ int a,b,x,y; cin >> a >> b >> x>> y; int ans = abs(a - b); ans = min(ans,abs(a - x) + abs(b - y)); ans = min(ans,abs(a - y) + abs(b - x)); Pri(ans); return 0;}
C.当不存在传送们的时候，答案是∑（di - si),显然传送门让他其中的一部分路线变得近了，也就是产生了贡献，我们需要计算他的最大总贡献
分类讨论，假设终点在正半轴，那所有终点在负半轴的线条都不考虑
分为起点在正半轴和起点在负半轴两种情况，假设起点在负半轴，1 - di上的所有点以此产生1,2,3,4,5....di的贡献，di + 1到2 * di的点依次产生di - 1.di - 2....2.1的贡献
假设起点在正半轴，情况又变成了si * 2 - di 到di上的点产生的贡献递增，后面对称递减
加上了所有贡献之后，问题就变成了取贡献最大的其中一个点作为最终答案，1e8的范围注定了不能用数据结构维护全体，考虑前缀和不行之后发现可以维护一个前缀和的前缀和关键点则必定在前缀和的前缀和的关键点上。
终点在负半轴情况同理
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;PII a[maxn];PLL flag[maxn * 3];LL solve(){ int cnt = 0; for(int i = 1; i <= N; i ++){ if(a[i].se <= 0) continue; if(a[i].fi <= 0){ flag[++cnt] = mp(1,1); flag[++cnt] = mp(a[i].se + 1,-2); flag[++cnt] = mp(a[i].se * 2 + 1,1); }else{ if(a[i].fi * 2 >= a[i].se) continue; flag[++cnt] = mp(2 * a[i].fi + 1,1); flag[++cnt] = mp(a[i].se + 1,-2); flag[++cnt] = mp(a[i].fi * 2 + (a[i].se - a[i].fi * 2) * 2 + 1,1); } } sort(flag + 1,flag + 1 + cnt); int p = 1; for(int i = 2; i <= cnt; i ++){ if(flag[i].fi == flag[p].fi){ flag[p].se += flag[i].se; }else{ flag[++p] = flag[i]; } } LL pre = 0,la = 0,sum = 0; LL MAX = 0; for(int i = 1; i <= p; i ++){ sum += pre * (flag[i].fi - la); MAX = max(MAX,sum); la = flag[i].fi; pre += flag[i].se; } return MAX;}int main(){ Sca(N); for(int i = 1; i <= N ; i ++) Sca2(a[i].fi,a[i].se); LL ans = solve(); LL sum = 0; for(int i = 1; i <= N ; i ++){ a[i].fi = -a[i].fi; a[i].se = -a[i].se; sum += abs(a[i].fi - a[i].se); } ans = max(solve(),ans); Prl(sum - ans); return 0;}
D.前缀和维护一下就好了。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 110;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;int a[5][3];int ans[5];int main(){ for(int i = 1; i <= 4; i ++){ Sca2(a[i][1],a[i][2]); a[i][2] -= a[i][1]; for(int j = 1; j < i ; j ++) ans[j] += a[i][2]; } for(int i = 1; i <= 3; i ++) Pri(ans[i]); return 0;}
E.起点1车辆的限制由起点到最右边的平路决定，终点N的车辆限制由终点到最左边的平路决定。
一个类似区间贪心的东西就可以了，100的数据范围时间复杂度竟然是O(n),我怀疑是放了一个网络流的烟雾弹
题目不难但不知道为什么没什么人过
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 110;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;struct road{ int op,l,r;}r[maxn];int main(){ Sca(N); for(int i = 1; i <= N ; i ++){ char op[5]; scanf("%s%d%d",op,&r[i].l,&r[i].r); if(op[0] == 'n') r[i].op = 1; else if(op[1] == 'n') r[i].op = 2; else r[i].op = 3; } int f = 0; for(int i = N ; i >= 1; i --){ if(r[i].op == 1){ f = i; break; } } int L = r[f].l,R = r[f].r; for(int i = f - 1; i >= 1; i --){ if(r[i].op == 1){ R = min(R,r[i].r); L = max(L,r[i].l); }else if(r[i].op == 2){ R -= r[i].l; R = max(R,0); L -= r[i].r; L = max(L,0); }else{ L += r[i].l; R += r[i].r; } } printf("%d %d\n",L,R); for(int i = 1; i <= N; i ++){ if(r[i].op == 1){ f = i; break; } } L = r[f].l,R = r[f].r; for(int i = f + 1; i <= N; i ++){ if(r[i].op == 1){ R = min(R,r[i].r); L = max(L,r[i].l); }else if(r[i].op == 3){ R -= r[i].l; R = max(R,0); L -= r[i].r; L = max(L,0); }else{ L += r[i].l; R += r[i].r; } } printf("%d %d\n",L,R); return 0;}
F.dp维护从这个点开始往回跳的最大值，维护一个正数的前缀和，贪心的发现如果往回跳从i跳到j，其中的正数一定会被全部取掉。
写出一个N ^ 2的dp之后上单调队列降复杂度即可。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 3e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;LL a[maxn];LL dp[maxn];LL pre[maxn];LL Queue[maxn];int main(){ Sca2(N,K); for(int i = 1; i <= N ; i ++){ Scl(a[i]); if(a[i] <= 0) pre[i] = pre[i - 1]; else pre[i] = pre[i - 1] + a[i]; } int f = 1,t = 0; for(int j = 2; j <= N ; j ++){ //dp[i] + a[i + 1] - pre[i + 1] while(f <= t && Queue[f] < j - K) f++; if(j - 2 >= 0){ while(f <= t && dp[Queue[t]] - pre[Queue[t]] <= dp[j - 2] - pre[j - 2]) t--; Queue[++t] = j - 2; } dp[j] = dp[Queue[f]] - pre[Queue[f]] + a[j] + a[j - 1] + pre[j - 2]; } LL ans = dp[1] + pre[min(1 + K,N)]; for(int i = 2; i <= N ; i ++){ dp[i] += pre[min(i + K - 1,N)] - pre[i]; ans = max(ans,dp[i]); //if(i < N) ans = max(ans,dp[i] + a[i + 1]); } Prl(ans); return 0;}
G.暴力预处理两两之间的异或，搞出一张完全图之后答案就是在图上寻找一颗最大生成树。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 2010;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;LL a[maxn];struct Edge{ int u,v; LL w; Edge(){} Edge(int u,int v,LL w):u(u),v(v),w(w){}}edge[maxn * maxn];bool cmp(Edge a,Edge b){ return a.w > b.w;}int fa[maxn];void init(){ for(int i = 1; i <= N ; i ++) fa[i] = i;}int find(int p){ if(p == fa[p]) return fa[p]; return fa[p] = find(fa[p]);}void Union(int a,int b){ a = find(a); b = find(b); fa[a] = b;}int main(){ Sca(N); init(); for(int i = 1; i <= N ; i ++) Scl(a[i]); int cnt = 0; for(int i = 1; i <= N ; i ++){ for(int j = i + 1; j <= N ; j ++){ edge[++cnt] = Edge(i,j,a[i] ^ a[j]); } } sort(edge + 1,edge + 1 + cnt,cmp); int num = 0; LL ans = 0; for(int i = 1; i <= cnt && num < N - 1; i ++){ if(find(edge[i].u) == find(edge[i].v)) continue; num++; ans += edge[i].w; Union(edge[i].u,edge[i].v); } Prl(ans); return 0;}
H.显然推断两人手上的牌，自己手上的牌较大的一半放在前面用，较小的一半放在后面用，贪心算一下积分
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;bool vis[maxn];int a[maxn],b[maxn];int main(){ Sca(N); for(int i = 1; i <= N ; i ++){ Sca(a[i]); vis[a[i]] = 1; } int cnt = 0; for(int i = 2 * N; i >= 1 ; i --) if(!vis[i]) b[++cnt] = i; int m = N / 2; sort(a + 1,a + 1 + m); sort(b + 1,b + 1 + m); sort(a + 1 + m,a + 1 + N); sort(b + 1 + m,b + 1 + N); int ans = 0,p = 1; for(int i = 1; i <= m ; i ++){ if(b[i] > a[p]){ ans++; p++; } } p = N; for(int i = N; i >= m + 1; i --){ if(b[i] < a[p]){ p--; ans++; } } Pri(ans); return 0;}
I.二分答案，随便check
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;LL t[maxn];bool check(LL x){ LL e = t[1] + x; int ans = 1; int num = K; for(int i = 1; i <= N; i ++){ if(t[i] <= e && num){ num--; }else{ e = t[i] + x; num = K - 1; ans++; } } return ans <= M;}LL solve(){ LL l = 0,r = INF; LL ans = INF; while(l <= r){ LL m = l + r >> 1; if(check(m)){ r = m - 1; ans = m; }else{ l = m + 1; } } return ans;}int main(){ Sca3(N,M,K); for(int i = 1; i <= N; i ++) Scl(t[i]); sort(t + 1,t + 1 + N); Prl(solve()); return 0;}
J.dp[i]表示1-i之间的奶牛被分组完成之后的答案，递推式就是 dp[j] = ∑dp[i] + max(i,j) * (j - i + 1) ( j >= i - k + 1 && j <= i)
静态区间最大值搞个ST表维护下就行了。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 1e4 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;const int SP = 20;int MAX[maxn][SP];int mm[maxn];void initRMQ(int n,LL b[]){ mm[0] = -1; for(int i = 1; i <= n; i ++){ mm[i] = ((i & (i - 1)) == 0)?mm[i - 1] + 1:mm[i - 1]; MAX[i][0] = b[i]; } for(int j = 1; j <= mm[n]; j ++){ for(int i = 1; i + (1 << j) - 1 <= N; i ++){ MAX[i][j] = max(MAX[i][j - 1],MAX[i + (1 << (j - 1))][j - 1]); } }}int rmq(int x,int y){ int k = mm[y - x + 1]; return max(MAX[x][k],MAX[y - (1 << k) + 1][k]);}LL a[maxn];LL dp[maxn];int main(){ Sca2(N,K); for(int i = 1; i <= N ; i ++) Scl(a[i]); initRMQ(N,a); for(int i = 1; i <= N ; i ++){ for(int j = max(1,i - K + 1); j <= i ; j ++){ dp[i] = max(dp[i],dp[j - 1] + rmq(j,i) * (i - j + 1)); } } Prl(dp[N]); return 0;}
K.将询问的有向边加上，首先拓扑排序判断是否存在答案。
处理出dfs序，线段树维护每个点的可行性，对于每个查找，倘若y不是x的孩子，则将x的整颗子树染色，否则倍增查找同时为y的祖先，x的儿子的那个点u,除了u的子树外全部染色。
被染色的点都是不可行的点，最后线段树查找就可以。
感觉我做麻烦了
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 2e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;int N,M,K;struct Edge{ int to,next;}edge[maxn * 2];int head[maxn],tot;void init(){ for(int i = 0 ;i <= N ; i ++) head[i] = -1; tot = 0;}void add(int u,int v){ edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;}const int SP = 20;PII pos[maxn];int fa[maxn][SP],dep[maxn];int cnt = 0;void dfs(int t,int la){ pos[t].fi = ++cnt; fa[t][0] = la; for(int i = 1; i < SP; i ++) fa[t][i] = fa[fa[t][i - 1]][i - 1]; for(int i = head[t]; ~i; i = edge[i].next){ int v = edge[i].to; if(v == la) continue; dep[v] = dep[t] + 1; dfs(v,t); } pos[t].se = ++cnt;}struct Tree{ int l,r,sum,lazy;}tree[maxn << 4];void Pushup(int t){ tree[t].sum = tree[t << 1].sum + tree[t << 1 | 1].sum;}void Build(int t,int l,int r){ tree[t].l = l; tree[t].r = r; tree[t].lazy = 0; if(l == r){ tree[t].sum = 1; return; } int m = l + r >> 1; Build(t << 1,l,m);Build(t << 1 | 1,m + 1,r); Pushup(t);}void Pushdown(int t){ if(tree[t].lazy){ tree[t << 1].lazy = tree[t << 1 | 1].lazy = 1; tree[t << 1].sum = tree[t << 1 | 1].sum = 0; tree[t].lazy = 0; }}void update(int t,int l,int r){ if(r < l) return; if(tree[t].sum == 0) return; if(l <= tree[t].l && tree[t].r <= r){ tree[t].sum = 0; tree[t].lazy = 1; return; } Pushdown(t); int m = (tree[t].l + tree[t].r) >> 1; if(r <= m) update(t << 1,l,r); else if(l > m) update(t << 1 | 1,l,r); else{ update(t << 1,l,m); update(t << 1 | 1,m + 1,r); } Pushup(t);}int query(int t,int p){ if(tree[t].sum == 0) return 0; if(tree[t].l == tree[t].r) return 1; Pushdown(t); int m = tree[t].l + tree[t].r >> 1; if(p <= m) return query(t << 1,p); else return query(t << 1 | 1,p);}int ind[maxn];int val[maxn],vis[maxn];int main(){ Sca2(N,M); init(); for(int i = 1; i <= N - 1; i ++){ int u,v; Sca2(u,v); ind[u]++; ind[v]++; add(u,v); add(v,u); } int root = 1; dep[0] = 0; dep[root] = 1; dfs(root,0); Build(1,1,cnt); for(int i = 1; i <= M ; i ++){ int x,y; Sca2(x,y); add(x,y); ind[y]++; if(pos[x].fi <= pos[y].fi && pos[y].se <= pos[x].se){ for(int j = SP - 1; j >= 0 ; j --){ int u = fa[y][j]; if(dep[u] <= dep[x]) continue; y = u; } update(1,1,pos[y].fi - 1); update(1,pos[y].se + 1,cnt); }else{ update(1,pos[x].fi,pos[x].se); } } for(int i = 1; i <= N ; i ++) val[i] = query(1,pos[i].fi); queue Q; for(int i = 1; i <= N ; i ++){ if(ind[i] == 1) Q.push(i); } while(!Q.empty()){ int u = Q.front(); Q.pop(); vis[u] = 1; for(int i = head[u]; ~i ; i = edge[i].next){ int v = edge[i].to; ind[v]--; if(ind[v] == 1) Q.push(v); } } for(int i = 1; i <= N ; i ++){ if(!vis[i]){ for(int i = 1; i <= N ; i ++) puts("0"); return 0; } } for(int i = 1; i <= N ; i ++) Pri(val[i]); return 0;}
L.一个性质是一棵树上的点，距离他最远的距离一定是直径的两个端点之一。
那么直接维护出这个森林每棵树的两直径端点，查找的时候输出较远的距离就可以了。
提供一种思路是离线处理出整棵树，然后树链剖分维护树上最远的孩子，不过我觉得常数更大写起来更麻烦。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se secondtypedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;const int SP = 20;int N,M,K;int Q;int pa[maxn][SP];int fa[maxn],dep[maxn];PII t[maxn];int lca(int u,int v){ if(dep[u] < dep[v]) swap(u,v); int t = dep[u] - dep[v]; int ans = dep[u] + dep[v]; for(int i = 0 ; i < SP; i ++) if(t & (1 << i)) u = pa[u][i]; for(int i = SP - 1; i >= 0; i --){ int uu = pa[u][i],vv = pa[v][i]; if(uu != vv){ u = uu; v = vv; } } int l = (u == v?u:pa[u][0]); return ans - 2 * dep[l];}int main(){ Sca(Q); int cnt = 0; while(Q--){ char op[2]; int x; scanf("%s%d",op,&x); if(op[0] == 'B'){ cnt++; if(x == -1){ fa[cnt] = cnt; t[cnt].fi = t[cnt].se = cnt; pa[cnt][0] = cnt; dep[cnt] = 1; }else{ fa[cnt] = fa[x]; pa[cnt][0] = x; dep[cnt] = dep[x] + 1; } for(int i = 1; i < SP; i ++) pa[cnt][i] = pa[pa[cnt][i - 1]][i - 1]; int d1 = lca(t[fa[cnt]].fi,t[fa[cnt]].se); int d2 = lca(t[fa[cnt]].fi,cnt); int d3 = lca(t[fa[cnt]].se,cnt); if(d2 >= max(d1,d3)) t[fa[cnt]].se = cnt; else if(d3 >= max(d1,d2)) t[fa[cnt]].fi = cnt; }else{ Pri(max(lca(x,t[fa[x]].fi),lca(x,t[fa[x]].se))); } } return 0;}
转载于:https://www.cnblogs.com/Hugh-Locke/p/10994038.html
