AK的感觉真好233
T1
$\large m*(m-1)^{n-1}$
#include#include #include #include #include #include using namespace std;#define reg register#define int long longinline int read() { int res=0;char c=getchar();bool f=0; while(!isdigit(c)) { if(c=='-')f=1;c=getchar();} while(isdigit(c))res=(res<<3)+(res<<1)+(c^48),c=getchar(); return f?-res:res;}#define mod 1000000007int n, m;inline int ksm(int x, int y){ int res = 1; while(y) { if (y & 1) res = res * x % mod; x = x * x % mod; y >>= 1; } return res;}signed main(){ n = read(), m = read(); printf ("%lld\n", (ksm(m - 1, n - 1) * m) % mod); return 0;}
T2
就是dfs一遍求出以1为根的每个子树的siz，然后答案就是1的所有儿子的siz的最大值。
#include#include #include #include #include #include using namespace std;#define reg registerinline int read() { int res=0;char c=getchar();bool f=0; while(!isdigit(c)) { if(c=='-')f=1;c=getchar();} while(isdigit(c))res=(res<<3)+(res<<1)+(c^48),c=getchar(); return f?-res:res;}int n;struct edge{ int nxt, to;}ed[1000005*2];int head[1000005], cnt;inline void add(int x, int y){ ed[++cnt] = (edge){head[x], y}; head[x] = cnt;}int siz[1000005];int deg[1000005];void dfs(int x, int fa){ siz[x] = 1; for (reg int i = head[x] ; i ; i = ed[i].nxt) { int to = ed[i].to; if (to == fa) continue; dfs(to, x); siz[x] += siz[to]; }}int ans;int main(){ n = read(); for (reg int i = 1 ; i < n ; i ++) { int x = read(), y = read(); add(x, y), add(y, x); } dfs(1, 0); for (reg int i = head[1] ; i ; i = ed[i].nxt) ans = max(ans, siz[ed[i].to]); cout< <
T3
线段树上二分不想说了。
#include#include #include #include #include #include using namespace std;#define reg registerinline int read() { int res=0;char c=getchar();bool f=0; while(!isdigit(c)) { if(c=='-')f=1;c=getchar();} while(isdigit(c))res=(res<<3)+(res<<1)+(c^48),c=getchar(); return f?-res:res;}#define N 1000005int n, m;int n1, n2;char a[N];int ans;struct Segment { int num1, num2;}t[N<<2];#define ls(o) o << 1#define rs(o) o << 1 | 1#define s1(o) t[o].num1#define s2(o) t[o].num2inline void update(int o){ s1(o) = s1(ls(o)) + s1(rs(o)); s2(o) = s2(ls(o)) + s2(rs(o));}void Build(int l, int r, int o){ if (l == r) { if (a[l] == 'R') s1(o) = 1, n1++; else s2(o) = 1, n2++; return ; } int mid = l + r >> 1; Build(l, mid, ls(o)); Build(mid + 1, r, rs(o)); update(o);}void query1(int l, int r, int o, int kt){ if (l == r) { ans = l; return ; } int mid = l + r >> 1; if (s1(ls(o)) >= kt) query1(l, mid, ls(o), kt); else query1(mid + 1, r, rs(o), kt - s1(ls(o)));}void query2(int l, int r, int o, int kt){ if (l == r) { ans = l; return ; } int mid = l + r >> 1; if (s2(ls(o)) >= kt) query2(l, mid, ls(o), kt); else query2(mid + 1, r, rs(o), kt - s2(ls(o)));}int main(){ n = read(), m = read(); for (register int i = 1 ; i <= n ; i ++) cin >> a[i]; Build(1, n, 1); while(m--) { char typ; int k; ans = 0; cin >> typ; k = read(); if (typ == 'R') { if (n1 < k) {puts("-1");continue;} query1(1, n, 1, k); printf("%d\n", ans); } else { if (n2 < k) {puts("-1");continue;} query2(1, n, 1, k); printf("%d\n", ans); } } return 0;}
T4
dfs一遍就行。
#include#include #include #include #include #include using namespace std;#define reg registerinline int read() { int res=0;char c=getchar();bool f=0; while(!isdigit(c)) { if(c=='-')f=1;c=getchar();} while(isdigit(c))res=(res<<3)+(res<<1)+(c^48),c=getchar(); return f?-res:res;}#define N 50005int n;struct edge{ int nxt, to, val;}ed[N*2];int head[N], cnt;int deg[N];inline void add(int x, int y, int z){ ed[++cnt] = (edge){head[x], y, z}; head[x] = cnt;}int rt, ans;void dfs(int x, int fa, int sum){ ans = max(ans, sum); for (reg int i = head[x] ; i ; i = ed[i].nxt) { int to = ed[i].to; if (to == fa) continue; dfs(to, x, sum + ed[i].val); }}int main(){ n = read(); for (reg int i = 1 ; i < n ; i ++) { int x = read(), y = read(), z = read(); add(y, x, z); deg[x]++; } for (reg int i = 1 ; i <= n ; i ++) if (deg[i] == 0) {rt = i;break;} dfs(rt, 0, 0); printf("%d\n", ans); return 0;}
T5
建边spfa
#include#include #include #include #include #include using namespace std;#define reg registerinline int read() { int res=0;char c=getchar();bool f=0; while(!isdigit(c)) { if(c=='-')f=1;c=getchar();} while(isdigit(c))res=(res<<3)+(res<<1)+(c^48),c=getchar(); return f?-res:res;}#define N 500int n, m;struct edge{ int nxt, to, val;}ed[N*2];int head[N], cnt;inline void add(int x, int y, int z){ ed[++cnt] = (edge){head[x], y, z}; head[x] = cnt;}int dis[N];bool ex[N];inline void spfa(){ memset(dis, 0x3f, sizeof dis); queue q; dis[0] = 0; q.push(0); while(!q.empty()) { int x = q.front();q.pop(); ex[x] = 0; for (reg int i = head[x] ; i ; i = ed[i].nxt) { int to = ed[i].to; if (dis[to] > dis[x] + 1) { dis[to] = dis[x] + 1; if (!ex[to]) ex[to] = 1, q.push(to); } } }}int main(){ m = read(), n = read(); for (reg int i = 0 ; i <= m ; i ++) add(i, i + 1, 1), add(i + 1, i, 1); for (reg int i = 1 ; i <= n ; i ++) { int x = read(), y = read(); add(x, y, 1); } spfa();// for (int i = 1 ; i <= m ; i ++) printf("%d %d\n", i, dis[i]); printf("%d\n", dis[m]); return 0;}
T6
直接n^2做， 虽然不知道为什么能过。
%:pragma GCC optimize(3)%:pragma GCC optimize("Ofast")%:pragma GCC optimize("inline")%:pragma GCC optimize("-fgcse")%:pragma GCC optimize("-fgcse-lm")%:pragma GCC optimize("-fipa-sra")%:pragma GCC optimize("-ftree-pre")%:pragma GCC optimize("-ftree-vrp")%:pragma GCC optimize("-fpeephole2")%:pragma GCC optimize("-ffast-math")%:pragma GCC optimize("-fsched-spec")%:pragma GCC optimize("unroll-loops")%:pragma GCC optimize("-falign-jumps")%:pragma GCC optimize("-falign-loops")%:pragma GCC optimize("-falign-labels")%:pragma GCC optimize("-fdevirtualize")%:pragma GCC optimize("-fcaller-saves")%:pragma GCC optimize("-fcrossjumping")%:pragma GCC optimize("-fthread-jumps")%:pragma GCC optimize("-funroll-loops")%:pragma GCC optimize("-fwhole-program")%:pragma GCC optimize("-freorder-blocks")%:pragma GCC optimize("-fschedule-insns")%:pragma GCC optimize("inline-functions")%:pragma GCC optimize("-ftree-tail-merge")%:pragma GCC optimize("-fschedule-insns2")%:pragma GCC optimize("-fstrict-aliasing")%:pragma GCC optimize("-fstrict-overflow")%:pragma GCC optimize("-falign-functions")%:pragma GCC optimize("-fcse-skip-blocks")%:pragma GCC optimize("-fcse-follow-jumps")%:pragma GCC optimize("-fsched-interblock")%:pragma GCC optimize("-fpartial-inlining")%:pragma GCC optimize("no-stack-protector")%:pragma GCC optimize("-freorder-functions")%:pragma GCC optimize("-findirect-inlining")%:pragma GCC optimize("-fhoist-adjacent-loads")%:pragma GCC optimize("-frerun-cse-after-loop")%:pragma GCC optimize("inline-small-functions")%:pragma GCC optimize("-finline-small-functions")%:pragma GCC optimize("-ftree-switch-conversion")%:pragma GCC optimize("-foptimize-sibling-calls")%:pragma GCC optimize("-fexpensive-optimizations")%:pragma GCC optimize("-funsafe-loop-optimizations")%:pragma GCC optimize("inline-functions-called-once")%:pragma GCC optimize("-fdelete-null-pointer-checks")#include #include #include #include #include #include using namespace std;#define reg registerinline int read() { int res=0;char c=getchar();bool f=0; while(!isdigit(c)) { if(c=='-')f=1;c=getchar();} while(isdigit(c))res=(res<<3)+(res<<1)+(c^48),c=getchar(); return f?-res:res;}#define mod 19260817int n, m;int f[50005];int main(){ n = read(), m = read(); f[0] = 1; for (reg int i = 1 ; i <= n ; i ++) { int v = read(); for (reg int j = v ; j <= m ; j ++) { f[j] = f[j-v] + f[j]; if (f[j] >= mod) f[j] -= mod; } } int ans = 0; for (reg int i = 1 ; i <= m ; i ++) { ans += f[i]; if (ans >= mod) ans -= mod; } printf("%d\n", ans); return 0;}