assert(0);
不嘻嘻。
T1 棋局
首先不难列出 dp 方程 \(f[i][j]\) 表示玩了 \(i\) 局 A 赢了 \(j\) 局的方案数（我们这里钦定玩了 \(R_m+R_h\) 局 A 赢了 \(R_m\) 局），转移 \(f[i][j]\times \frac{j}{i}\to f[i+1][j+1],f[i][j]\times\frac{i-j}{i}\to f[i+1][j]\)，仔细思考/画图/大眼观察后发现系数是固定的，预处理逆元/阶乘/阶乘逆元之后直接乘就行了，还要乘一个钦定的组合数。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(register int i=l; i<=r; ++i)
#define dn(i,r,l) for(register int i=r; i>=l; --i)
using namespace std;
const int N=4000005, P=147744151;
int t, xx, yy, x, y, Ans, mul[N], inv[N], fac[N];
int C(int n,int m) {
if(m<0||n<m) return 0;
return mul[n]*fac[m]%P*fac[n-m]%P;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
mul[0]=inv[0]=inv[1]=fac[0]=1;
up(i,1,4000000) mul[i]=mul[i-1]*i%P;
up(i,2,4000000) inv[i]=inv[P%i]*(P-P/i)%P;
up(i,1,4000000) fac[i]=fac[i-1]*inv[i]%P;
cin >> t;
while(t--) {
cin >> xx >> yy >> x >> y;
Ans=C(xx+yy,xx), xx+=x, yy+=y;
Ans=Ans*fac[xx+yy-1]%P*mul[x+y-1]%P;
Ans=Ans*mul[xx-1]%P*fac[x-1]%P;
Ans=Ans*mul[yy-1]%P*fac[y-1]%P;
cout << Ans << '\n';
}
return 0;
}
T2 庆典
拆成两个问题，到一个点的距离最长是多少，定向到这个点代价是多少，注意到每个点上都有游客所以问题是一个分讨的简单问题，马上做完了。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(register int i=l; i<=r; ++i)
#define dn(i,r,l) for(register int i=r; i>=l; --i)
#define pb push_back
using namespace std;
const int N=200005;
int n, d, f[N], g[N], Ans=1e18;
struct node { int v, w, opt; };
vector<node> to[N];
void dfs(int x,int fad) {
for(node p:to[x]) {
int y=p.v, w=p.w;
if(y==fad) continue;
dfs(y,x);
f[x]=max(f[x],f[y]+w);
g[x]+=g[y]+(!p.opt);
}
}
void solve(int x,int fad,int pre,int val) {
int sum=0;
vector<int> L, R;
L.pb(0), R.pb(0);
for(node p:to[x]) {
int y=p.v, w=p.w;
if(y==fad) continue;
L.pb(f[y]+w);
R.pb(f[y]+w);
}
L.pb(0), R.pb(0);
up(i,1,L.size()-1) L[i]=max(L[i-1],L[i]);
dn(i,R.size()-2,0) R[i]=max(R[i+1],R[i]);
int cnt=0;
for(node p:to[x]) {
int y=p.v, w=p.w;
if(y==fad) continue;
++cnt;
solve(y,x,max(pre,max(L[cnt-1],R[cnt+1]))+w,val+g[x]-g[y]-(!p.opt)+p.opt);
}
if(max(f[x],pre)<=d) Ans=min(Ans,n-1-g[x]-val);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> d;
up(i,2,n) {
int u, v, w;
cin >> u >> v >> w;
to[u].pb((node){v,w,1});
to[v].pb((node){u,w,0});
}
dfs(1,0), solve(1,0,0,0);
if(Ans==1e18) Ans=-1;
cout << Ans;
return 0;
}
T3 游戏
考虑到固定一个左端点之后往右拓展只会有 \(\log V\) 种本质不同的 \(\gcd\)，我们先枚举被删除的最左边的数 \(i\) 那会有一个 \(\gcd(a_l,\dots,a_{i-1})\) 的贡献，这种贡献本质不同的段数显然也是 \(\log\) 的，我们考虑把这一段一起考虑，发现取最右边的最好，因为左边贡献一致的情况下可以尽可能让后面的 \(\gcd\) 更大。按照这个思路进行枚举枚举量最多是 \(\log^3 V\) 的，写 st 表+二分 gcd 可以做到 3 只，但因为常数小 \(O(n\log^4V)\) 可以通过，太牛了。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(register int i=l; i<=r; ++i)
#define dn(i,r,l) for(register int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
using namespace std;
const int N=400005, M=log2(N)+1;
int n, q, t, a[N], f[N][M], lg[N];
vector<pii> L[N], lyl, lsy;
inline int gcd(int a,int b) {
if(a==0||b==0) return a|b;
int az=__builtin_ctz(a), bz=__builtin_ctz(b), z=min(az,bz), dif;
b>>=bz;
while(a) {
a>>=az, dif=b-a;
az=__builtin_ctz(dif);
if(a<b) b=a;
a=dif<0?-dif:dif;
}
return b<<z;
}
inline int qur(int l,int r) {
if(l>r) return 0;
int k=lg[r-l+1];
return gcd(f[l][k],f[r-(1<<k)+1][k]);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q, t=log2(n);
up(i,1,n) cin >> a[i], f[i][0]=a[i], lg[i]=log2(i);
up(j,1,t) up(i,1,n) f[i][j]=gcd(f[i][j-1],f[i+(1<<j-1)][j-1]);
dn(i,n,1) {
int lst=0;
for(pii p:lyl) {
int x=p.first, d=gcd(p.second,a[i]);
if(d!=lst) lst=d, lsy.pb(mp(x,d));
}
if(i==n||a[i+1]%a[i]) lsy.pb(mp(i,a[i]));
lyl=lsy, lsy.clear();
for(pii p:lyl) L[i].pb(mp(p.first+1,p.second));
L[i].pb(mp(i,0)), reverse(L[i].begin(),L[i].end());
}
while(q--) {
int l, r, k;
cin >> l >> r >> k;
k=(r-l+1)-k;
if(k==0) {
cout << qur(l,r) << '\n';
}
if(k==1) {
int Ans=qur(l,r-1);
for(pii p:L[l]) {
int i=p.first;
if(i>=r) break;
Ans=max(Ans,gcd(p.second,qur(i+1,r)));
}
cout << Ans << '\n';
}
if(k==2) {
int Ans=qur(l,r-1);
for(pii p:L[l]) {
int i=p.first;
if(i>=r) break;
Ans=max(Ans,gcd(p.second,qur(i+1,r-1)));
for(pii q:L[i+1]) {
int j=q.first;
if(j>=r) break;
Ans=max(Ans,gcd(gcd(p.second,q.second),qur(j+1,r)));
}
}
cout << Ans << '\n';
}
if(k==3) {
int Ans=qur(l,r-1);
for(pii p:L[l]) {
int i=p.first;
if(i>=r) break;
Ans=max(Ans,gcd(p.second,qur(i+1,r-1)));
for(pii q:L[i+1]) {
int j=q.first;
if(j>=r) break;
Ans=max(Ans,gcd(gcd(p.second,q.second),qur(j+1,r-1)));
for(pii t:L[j+1]) {
int k=t.first;
if(k>=r) break;
Ans=max(Ans,gcd(gcd(p.second,q.second),gcd(t.second,qur(k+1,r))));
}
}
}
cout << Ans << '\n';
}
}
return 0;
}
T4 吃豆人
首先先二分一个速度 \(v\) 转化成判定性问题，位置二元组难以维护但是注意到 \(pos_{i-1}\) 一定在里面，所以我们维护合法的另一点即可，容易分讨做到 \(O(n\log n)\) 的判定，但是会超时，注意到一个时刻合法的另一个端点是区间（可以观察后通过分讨做法推得），纯度分讨 \(O(n)\) 判定即可。
#include<bits/stdc++.h>
#define int long long
#define db long double
#define up(i,l,r) for(register int i=l; i<=r; ++i)
#define dn(i,r,l) for(register int i=r; i>=l; --i)
using namespace std;
const int N=100005;
const db eps=1e-10;
int n; db t[N], pos[N];
bool check(db v) {
db l=0, r=0;
up(i,0,n-1) {
db len=(t[i+1]-t[i])*v;
bool L=l-len<=pos[i+1]&&pos[i+1]<=r+len;
bool R=pos[i]-len<=pos[i+1]&&pos[i+1]<=pos[i]+len;
if(L&&R) l=min(l-len,pos[i]-len), r=max(r+len,pos[i]+len);
else if(R) l-=len, r+=len;
else if(L) l=pos[i]-len, r=pos[i]+len;
else return 0;
}
return 1;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
up(i,1,n) cin >> t[i] >> pos[i];
db l=0, r=1e7;
while(l+eps<r) {
db mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
cout << fixed << setprecision(10) << l;
return 0;
}