D1T1潜入行动：
大水题，可是本菜鸡手一抖MLE了，GG
#include<iostream> #include<cstdio> #define llint long long int using namespace std; const llint maxn = 200005; const llint maxk = 107; const llint modd = 1e9+7; llint n, k; struct atree {//choose safe int dp[100005][maxk][2][2]; llint st[maxn], to[maxn], nx[maxn], tm, up[maxn], tt; void adde(llint aa, llint bb) { tm++; nx[tm]=st[aa]; to[tm]=bb; st[aa]=tm; return; } void count(llint x, llint fa) { //cout<<x<<endl; llint i, y, j, p, tt, t[2][2]; dp[x][0][0][0]=1; dp[x][1][1][0]=1; up[x]=1; for(i=st[x]; i != 0; i=nx[i]) { y=to[i]; if(y == fa) continue; count(y, x); for(j=up[x]; j >= 0; j--) { t[0][0]=dp[x][j][0][0]; t[0][1]=dp[x][j][0][1]; t[1][0]=dp[x][j][1][0]; t[1][1]=dp[x][j][1][1]; dp[x][j][0][0]=dp[x][j][0][1]=dp[x][j][1][0]=dp[x][j][1][1]=0; for(p=min(up[y], k-j); p >= 0; p--) { up[x]=max(up[x], j+p); tt=dp[x][j+p][0][0]; tt+=t[0][0]*dp[y][p][0][1]%modd; tt%=modd; dp[x][j+p][0][0]=tt; tt=dp[x][j+p][0][1]; tt+=t[0][0]*dp[y][p][1][1]%modd; tt+=t[0][1]*dp[y][p][0][1]%modd; tt+=t[0][1]*dp[y][p][1][1]%modd; tt%=modd; dp[x][j+p][0][1]=tt; tt=dp[x][j+p][1][0]; tt+=t[1][0]*dp[y][p][0][1]%modd; tt+=t[1][0]*dp[y][p][0][0]%modd; tt%=modd; dp[x][j+p][1][0]=tt; tt=dp[x][j+p][1][1]; tt+=t[1][0]*dp[y][p][1][1]%modd; tt+=t[1][0]*dp[y][p][1][0]%modd; tt+=t[1][1]*dp[y][p][0][0]%modd; tt+=t[1][1]*dp[y][p][0][1]%modd; tt+=t[1][1]*dp[y][p][1][0]%modd; tt+=t[1][1]*dp[y][p][1][1]%modd; tt%=modd; dp[x][j+p][1][1]=tt; } } } return; } } T; int main() { llint i, ta, tb, tt; cin>>n>>k; for(i=1; i < n; i++) { cin>>ta>>tb; T.adde(ta, tb); T.adde(tb, ta); } T.count(1, 0); tt=T.dp[1][k][0][1]*1ll+T.dp[1][k][1][1]*1ll; cout<<((tt)%modd+modd)%modd<<endl; }
D2T3列队：
蛮水的吧，可是我Naive地认为卡卡常直接二分能过
卡了很久以后才想起来写主席树上二分.
loj稳过，luogu迷之TLE
#include<iostream> #include<cstdio> #define llint long long int using namespace std; const llint maxn = 20000005; llint mp; llint a[maxn]; struct atree { llint num[maxn]; int tn, st[maxn], ls[maxn], rs[maxn], tm; void build(int x, int l, int r) { num[x]=0; if(l == r) return; int mid=(l+r)/2; tm++; ls[x]=tm; build(ls[x], l, mid); tm++; rs[x]=tm; build(rs[x], mid+1, r); return; } void add_do(int x1, int x2, int l, int r, int p1, llint num1) { if(l == r) {num[x1]=num[x2]+num1; return;} int mid=(l+r)/2; if(p1 <= mid) { tm++; ls[x1]=tm; rs[x1]=rs[x2]; add_do(ls[x1], ls[x2], l, mid, p1, num1); } else { tm++; rs[x1]=tm; ls[x1]=ls[x2]; add_do(rs[x1], rs[x2], mid+1, r, p1, num1); } num[x1]=num[ls[x1]]+num[rs[x1]]; return; } inline void add(int p1, llint num1) { tn++; tm++; st[tn]=tm; add_do(st[tn], st[tn-1], 0, mp, p1, num1); } llint ask_do(int x1, int x2, int l, int r, int pl, int pr) { if(r < pl || pr < l) return 0; if(num[x2]-num[x1] == 0) return 0; if(pl <= l && r <= pr) return num[x2]-num[x1]; int mid=(l+r)/2; llint anst; anst= ask_do(ls[x1], ls[x2], l, mid, pl, pr) + ask_do(rs[x1], rs[x2], mid+1, r, pl, pr); return anst; } inline llint ask(int b1, int b2, int pl, int pr) { if(pr > mp) pr=mp; if(pl > pr) return 0; return ask_do(st[b1-1], st[b2], 0, mp, pl, pr); } llint find_it(int x1, int x2, int l, int r, llint tk) { if(r == l) return l; int mid=(l+r)/2; if(num[ls[x2]]-num[ls[x1]] > (mid-tk+1)) return find_it(rs[x1], rs[x2], mid+1, r, tk+num[ls[x2]]-num[ls[x1]]); else return find_it(ls[x1], ls[x2], l, mid, tk); } inline llint find(int b1, int b2, llint tk) { return find_it(st[b1-1], st[b2], 0, mp, tk); } } T1, T2; inline llint csum(llint l, llint r) { if(l > r) return 0; return (l+r)*(r-l+1ll)/2ll; } inline llint read(){ llint s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } inline void write( llint x ) { char F[2000] ; if(x == 0) putchar('0'); llint tmp = x > 0 ? x : -x ; if( x < 0 ) putchar( '-' ) ; int cnt = 0 ; while( tmp > 0 ) { F[ cnt ++ ] = tmp % 10 + '0' ; tmp /= 10 ; } while( cnt > 0 ) putchar( F[ -- cnt ] ) ; } int main() { //freopen("line.in", "r", stdin); //freopen("line.out", "w", stdout); T1.tm=1; T1.tn=0; T1.st[0]=1; T2.tm=1; T2.tn=0; T2.st[0]=1; llint i, ta, tb, tk, ans, ansp, n, m; n=read(), m=read(); for(i=1; i <= n; i++) { a[i]=read(); } mp=1000005; T2.build(1, 0, mp); T1.build(1, 0, mp); //cout<<T1.tm<<endl; for(i=1; i <= n; ++i) { T1.add(a[i], 1); T2.add(a[i], a[i]); } for(i=1; i <= m; ++i) { ta=read(); tb=read(); tk=read(); ans=0; ansp=T1.find(ta, tb, tk); if(ansp == 1000005) ansp=tk+tb-ta; ans+=csum(tk, ansp)-T2.ask(ta, tb, 1, ansp); ans+=T2.ask(ta, tb, ansp+1, mp)-csum(ansp+1, tk+tb-ta); write(ans); putchar('\n'); } return 0; }
D1T3绝地反击：
想出来爬山+二分了，结果没敢想网络流
不行，我还是Too Young，Too Simple