game

推一遍期望即可。

两个特判留保底分用的qwq

#include
    
     #include
     
      using namespace std;int n;double p[1001][1001], ans, g[1001][1001];int main(){    freopen("game.in", "r", stdin);    freopen("game.out", "w", stdout);    scanf("%d", &n);    for(int i=1; i<=n; i++)        for(int j=0; j
     
    

cake

meet in middle。分成两半枚举子集双指针判断即可。

(阿克王poorpool的代码！：

#include 
    
     #include 
     
      #include 
      
       using namespace std;int n, X, a[25], b[25], aa, bb, cnta, cntb, vala[1048595], valb[1048595], tmp;int main(){    freopen("cake.in", "r", stdin);    freopen("cake.out", "w", stdout);    cin>>n>>X;    aa = n / 2;    bb = n - aa;    for(int i=1; i<=aa; i++)        scanf("%d", &a[i]);    for(int i=1; i<=bb; i++)        scanf("%d", &b[i]);    for(int i=0; i<(1<
       
        X)   break;            }        if(tmp<=X)  vala[++cnta] = tmp;    }    for(int i=0; i<(1<
        
         X)   break;            }        if(tmp<=X)  valb[++cntb] = tmp;    }    sort(vala+1, vala+1+cnta);    sort(valb+1, valb+1+cntb);    int i=1, j=cntb, ans=X;    for(; i<=cnta; i++){        while(vala[i]+valb[j]>X && j>0)    j--;        if(!j)  break;        ans = min(ans, X-vala[i]-valb[j]);    }    cout<
         
          <
         
        
       
      
     
    

grid

骗到50分即可。

road

显然以s为根建树。我们只需考虑选择变化x到LCA还是y到LCA的路径。分别求出取max。

考虑倍增。用前缀和\(sum(i)\)存点\(i\)到根的边权和，\(f(i,j)\)存\(i\)往上跳\(2^j\)次到达的点，\(fsum(i, j)\)存从\(i\)点到\(f(i,j)\)点的边权和，\(road(i,j)\)存从\(i\)点到\(f(i,j)\)点的路径上，选择最优的\(c\)所得到的最⼩的从\(i\)到\(c\)的路径上边权和。

处理好这些每次询问都很简单了。

#include
    
     #include
     
      #define maxn 2000001using namespace std;inline int qr(){    int x=0, f=1;    char ch=getchar();    for(;!isdigit(ch); ch=getchar()) if(ch=='-') f=-1;    for(; isdigit(ch); ch=getchar()) x=(x<<3)+(x<<1)+ch-48;    return x*f;}int n, head[maxn], tot;int q, s;struct edge{    int to, nxt, val;}e[maxn];int f[maxn][20], dep[maxn];int sum[maxn];int road[maxn][20];int fsum[maxn][20];void add(int u, int v, int w){    e[++tot].nxt=head[u];    e[tot].to=v;    e[tot].val=w;    head[u]=tot;}void LCA_fst(int u, int fa){    dep[u]=dep[fa]+1;    for(int i=0; i<18; i++){        f[u][i+1]=f[f[u][i]][i];        fsum[u][i+1]=fsum[f[u][i]][i]+fsum[u][i];        road[u][i+1]=min(road[u][i], fsum[u][i]+road[f[u][i]][i]);    }    for(int i=head[u]; i; i=e[i].nxt){        int v=e[i].to;        if(v==fa)continue;        f[v][0]=u;        sum[v]=sum[u]+e[i].val;        fsum[v][0]=e[i].val;        road[v][0]=min(0, e[i].val);        LCA_fst(v, u);    }}int LCA(int x, int y){    if(dep[x]
      
       =0; i--)        if(f[x][i]!=0&&dep[f[x][i]]>=dep[y])            x=f[x][i];    if(x==y)return x;    for(int i=18; i>=0; i--)        if(f[x][i]!=0&&f[y][i]!=0&&f[x][i]!=f[y][i])            x=f[x][i], y=f[y][i];    return f[x][0];}int solve(int x, int y){    int ans=0, road_sum=0;    for(int i=18; i>=0; i--){        if(f[x][i]!=0&&dep[f[x][i]]>=dep[y]){            ans=min(ans, road_sum+road[x][i]);            road_sum+=fsum[x][i];            x=f[x][i];        }    }    return ans;}int main(){    freopen("road.in", "r", stdin);    freopen("road.out", "w", stdout);    n=qr(), q=qr(), s=qr();    int a, b, c;    for(int i=1; i
      
     
    

bride

两层枚举。先枚举可能贿赂的人，再枚举每个人支持与否，求概率取min即可。

不知道为什么错了一个点。

90pts：

#include
    
     #include
     
      #include
      
       using namespace std;inline int qr(){    int x=0, f=1;    char ch=getchar();    for(;!isdigit(ch); ch=getchar()) if(ch=='-') f=-1;    for(; isdigit(ch); ch=getchar()) x=(x<<3)+(x<<1)+ch-48;    return x*f;}int n, k, a;int w[10], h[10];double ans, P;void dfs2(double pro, int cur, int sum, int support){    if(cur==n+1){        if(support>0) P+=pro*a/(a+sum);        else P+=pro;    }else{        dfs2(pro*h[cur]/100, cur+1, sum+w[cur], support+1);        dfs2(pro*(100-h[cur])/100, cur+1, sum, support-1);    }}void dfs(int cur, int used){    if(used==k){        P=0.0;        dfs2(1.0, 1, 0, 0);        ans=max(ans, P);        return;    }    for(int i=cur; i<=n; i++){        if(h[i]>=10){            h[i]-=10;            dfs(i, used+1);            h[i]+=10;        }    }}int main(){    freopen("bride.in", "r", stdin);    freopen("bride.out", "w", stdout);    n=qr(), k=qr(), a=qr();    for(int i=1; i<=n; i++)        w[i]=qr(), h[i]=qr();    dfs(1, 0);    printf("%.6f", 1.0-ans);    return 0;}
      
     
    

climb

各种诡异暴力艹即可骗分。（实际上这题是D2最可做的题qwq