第十五屆北京師范大學程序設計競賽決賽（網絡同步賽）
B. Borrow Classroom
題意：一棵樹，點 1為根，一個人從點 b到 點 c再到點 1，第二個人從點 a出發，問第二個人能否截住第一個人。
tags：lca搞上去就行，第二個只要在第一個人到點 1之前能到點 1即可。注意題目，如果兩人到點1時間相同，要再判斷第二個人能否在到點1之前遇上第一個人。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 100005;int q;int n; vector<int > G[N]; int dep[N], p[N][30]; void dfslca(int u, int fa) {dep[u]=dep[fa]+1, p[u][0]=fa;for(int i=0; i<G[u].size(); ++i)if(G[u][i]!=fa) dfslca(G[u][i], u); } void Initlca() {memset(p,-1,sizeof(p)); memset(dep,0,sizeof(dep)); dep[0]=-1;dfslca(1, 0); int i, j;for(j=1; (1<<j)<=n; ++j)for(i=1; i<=n; ++i) if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1]; } int lca(int a, int b) {int i, j;if(dep[a]<dep[b]) swap(a, b);for(i=0; (1<<i)<=dep[a]; ++i); --i;for(j=i; j>=0; --j)if(dep[a]-(1<<j)>=dep[b])a=p[a][j];if(a==b) return a;for(j=i; j>=0; --j)if(p[a][j]!=-1 && p[a][j]!=p[b][j])a=p[a][j], b=p[b][j];return p[a][0]; }void solve(int a, int b, int c) {int t=lca(b, c), s1=dep[b]-dep[t]+dep[c]-dep[t]+dep[c];if(s1<dep[a]) puts("NO");else if(s1>dep[a]) puts("YES");else {if(lca(a, c)==1) puts("NO");else puts("YES");} } int main() {int T; scanf("%d", &T);while(T--){scanf("%d %d", &n, &q);rep(i,1,n) G[i].clear();int a, b, c;rep(i,1,n-1) {scanf("%d %d", &a, &b);G[a].push_back(b); G[b].push_back(a);}Initlca();rep(i,1,q) {scanf("%d %d %d", &a, &b, &c);solve(a, b, c);}}return 0; }
D. Disdain Chain
題意：n 個人，任意兩人
和
，要么鄙視，要么鄙視。問最長鄙視鏈(好腦洞的名字)分別為1~n的可能方案數。
tags：多畫幾個圖或者打個表很快能發現規律，2333。。因為要么鄙視，要么鄙視，即為競賽圖，好像有個性質：n>=2的競賽圖一定有哈密頓路徑。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 200005;int main() {int T; scanf("%d", &T);while(T--) {int n; scanf("%d", &n);rep(i,1,n) {if(i<n) printf("0\n");else {printf("%d\n", 1<<(n*(n-1)/2));}}}return 0; }
?
