感谢队友带飞，赛后1min过G，经典操作
C——Gerrymandering（枚举）
题意：
求每个地区A和B的无效票，以及所有地区的 efficiency gap 之和。
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const double eps = 1e-8; const int maxn =1e5+7; struct node{ int a,b; int wa,wb; }s[maxn]; int main(){ int n=read,m=read; for(int i=1;i<=n;i++){ int op=read,u=read,v=read; s[op].a+=u,s[op].b+=v; } for(int i=1;i<=m;i++){ if(s[i].a<s[i].b){ cout<<"B "; cout<<s[i].a<<" "; cout<<s[i].b-(s[i].a+s[i].b)/2-1<<endl; s[i].wa=s[i].a; s[i].wb=s[i].b-(s[i].a+s[i].b)/2-1; } else{ cout<<"A "; cout<<s[i].a-(s[i].a+s[i].b)/2-1<<" "; cout<<s[i].b<<endl; s[i].wa=s[i].a-(s[i].a+s[i].b)/2-1; s[i].wb=s[i].b; } } int wsa=0,wsb=0,sum=0; for(int i=1;i<=m;i++){ wsa=wsa+s[i].wa; wsb=wsb+s[i].wb; sum=sum+s[i].a+s[i].b; } printf("%.10lf\n",abs(wsa-wsb)*1.0/sum); return 0; }
G ——Research Productivity Index（概率DP+数学期望）
思路：
用概率dp求出概率，再结合数学期望的定义。
d p [ i ] [ j ] 表示选择前i ii个文章时成功了j jj篇的概率：
转移考虑第i ii篇文章是否成功，如果成功的话说明前i − 1 篇文章只成功了j − 1 篇，不成功的话说明前i − 1篇文章成功了j篇。
注意初始化：前0 00篇成功了0 00篇的概率是1.
期望的话就是∑ p i ∗ x i
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const double eps = 1e-8; const int maxn =110; double dp[110][110],a[110]; bool cmp(double a,double b){ return a>b; } int main(){ int n=read; rep(i,1,n){ int x=read; a[i]=x*0.01; } sort(a+1,a+1+n,cmp); double res=0; dp[0][0]=1; for(int i=1;i<=n;i++){ dp[i][0]=dp[i-1][0]*(1-a[i]); for(int j=1;j<=i;j++) dp[i][j]=dp[i-1][j-1]*a[i]+dp[i-1][j]*(1-a[i]); double tmp=0; for(int j=1;j<=i;j++) tmp=tmp+dp[i][j]*pow(j,1.0*j/i); res=max(res,tmp); } printf("%.9lf\n",res); return 0; }
I——Slow Leak（floyd）
思路：
n只有500，考虑floyd。
先对全图跑一遍floyd得出任意两点的最短距离。
再将起点终点和加油站跑一遍floyd，这样最后的g [ 1 ] [ n ]就是答案。
注意跑第二遍floyd之前对数组g gg再次进行初始化，若g [ i ] [ j ] > d，g [ i ] [ j ] = i n f
这样说明两个加油站之间的距离大于d dd，是无法到达的。
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const ll inf = 1e17; #define PI acos(-1) const double eps = 1e-8; const int maxn =110; ll g[510][510]; vector<int>v[510]; bool vis[510]; int cnt=0,a[510]; int main(){ int n=read,m=read,t=read,d=read; rep(i,1,t){ int x=read; vis[x]=1; a[++cnt]=x; } memset(g,0x3f,sizeof g); for(int i=1;i<=n;i++) g[i][i]=0; for(int i=1;i<=m;i++){ ll u=read,v=read,w=read; g[u][v]=g[v][u]=min(g[u][v],w); } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); a[++cnt]=1;a[++cnt]=n; for(int i=1;i<=cnt;i++) for(int j=1;j<=cnt;j++) if(g[a[i]][a[j]]>d) g[a[i]][a[j]]=inf; for(int k=1;k<=cnt;k++) for(int i=1;i<=cnt;i++) for(int j=1;j<=cnt;j++){ int kk=a[k],ii=a[i],jj=a[j]; g[ii][jj]=min(g[ii][jj],g[ii][kk]+g[kk][jj]); ///if(g[ii][jj]>d) g[ii][jj]=inf; } if(g[1][n]>=inf) puts("stuck"); else cout<<g[1][n]<<endl; return 0; }
