牛客網暑期ACM多校訓練營（第五場）

---

A. gpa

二分答案，然后就轉化為是否滿足
\(\frac {\sum s[i]c[i]}{\sum s[i]} ≥ D\),

\(\sum s[i]c[i] ≥ \sum s[i]D\),

\(\sum s[i](c[i]-D) ≥ 0\)

顯然科目越少gpa越高，于是去掉最小的k個判斷即可。

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define pb push_back #define PII pair<int,int> #define MP make_pair typedef long long ll; const int N = 1e5 + 7; using namespace std; int n,k;struct node{int s,c;node(){}node(int a,int b) {c=a;s=b;} }a[N];// 1. 2^n 暴力的做法 int ct(int s) {int ans = 0;for(int i=s;i;i-=i&-i)++ans;return ans; } double cal_1() {double ans = 0;rep(s,0,(1<<n)-1) if(ct(s)>=n-k) {int t1 = 0, t2 = 0;rep(i,0,n-1) if(s&(1<<i)) {t1 += a[i+1].s*a[i+1].c;t2 += a[i+1].s;}ans = max(ans,(1.0*t1)/t2);}return ans; }//** double c[N]; double solve(double x) {double ans = 0;rep(i,1,n) c[i] = a[i].s*(a[i].c-x);sort(c+1,c+1+n);rep(i,k+1,n) ans+=c[i];return ans; } double cal_2() {double l = 0, r = 1001.0,mid;rep(ti,1,30) {mid = (l+r)*0.5;if(solve(mid)>=0) l=mid;else r=mid;}return l; } int main() {srand(time(0));scanf("%d%d",&n,&k);rep(i,1,n) scanf("%d",&a[i].s);rep(i,1,n) scanf("%d",&a[i].c); // printf("%.10f\n",cal_1());printf("%.10f\n",cal_2());return 0; }

E. room

考慮新的第i組人住在原來的第j個房間，不改變的人就是兩個集合的交。然后二分圖最大權匹配即可。

#include <iostream> #include <cstring> #include <cstdio> #include <map> using namespace std; const int N = 305; const int inf = 0x3f3f3f3f;int nx,ny,n; int g[N][N],linker[N],lx[N],ly[N]; int slack[N]; bool visx[N], visy[N]; bool dfs(int x) {visx[x] = 1;for(int y = 0; y < ny; ++y) {if(visy[y])continue;int tmp = lx[x] + ly[y] - g[x][y];if(tmp == 0) {visy[y] = 1;if(linker[y] == -1||dfs(linker[y])) {linker[y] = x;return 1;}}else if(slack[y] > tmp)slack[y] = tmp;}return 0; } int KM() {memset(linker,-1,sizeof(linker));memset(ly,0,sizeof(ly));for(int i = 0; i < nx; ++i) {lx[i] = -inf;for(int j = 0; j < ny; ++j)if(g[i][j]>lx[i])lx[i]=g[i][j];}for(int x = 0; x < nx; ++x) {for(int i = 0; i < ny; ++i)slack[i] = inf;while(1) {memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(dfs(x)) break;int d = inf;for(int i = 0; i < ny; ++i)if(!visy[i] && d > slack[i])d = slack[i];for(int i = 0; i < nx; ++i)if(visx[i])lx[i] -= d;for(int i = 0; i < ny; ++i) {if(visy[i]) ly[i] += d;else slack[i] -= d;}}}int res = 0;for(int i = 0; i < ny; ++i)if(linker[i] != -1)res += g[linker[i]][i];return res; } int a[301][4],b[301][4]; map<int,int> M; int cal(int a[],int b[]) {M.clear(); int ans = 0;for (int i = 0; i < 4; ++i) M[a[i]]=1;for (int i = 0; i < 4; ++i) ans += M[b[i]];return ans; } int main() {while (~scanf("%d", &n)) {for (int i = 0; i < n; ++i)for (int j = 0; j < 4; ++j)scanf("%d",&a[i][j]);for (int i = 0; i < n; ++i)for (int j = 0; j < 4; ++j)scanf("%d",&b[i][j]);for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j)g[i][j] = cal(a[i],b[j]);nx = ny = n;printf("%d\n", 4*n-KM());}return 0; }

F.take

考慮每個答案的貢獻，就是\(p_i \Pi_{j<i,a_j>a_i} (1-pj)\)，前綴乘積用樹狀數組維護。

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define pb push_back typedef long long ll; const int N = 2e5 + 7; const ll mod = 998244353; using namespace std; ll q_pow(ll a,ll b) {ll ans = 1;while(b) {if(b&1) ans = (ans*a)%mod;a=(a*a)%mod;b >>= 1LL;}return ans; } ll inv; vector<ll> v; int getid(ll x) {return lower_bound(v.begin(),v.end(),x) - v.begin() + 1; } int cc; ll B[N],b[N]; ll n; ll p[N],a[N]; void init() {rep(i,0,2e5+1)B[i]=1; } ll ask(int x) {ll ans = 1;for(int i=x;i;i-=i&-i)ans=(ans*B[i])%mod;return ans; } void update(int x,ll v) {for(int i=x;i<=cc;i+=i&-i) B[i]=(B[i]*v)%mod; }int main() {inv = q_pow(100LL,mod-2);scanf("%lld",&n);rep(i,1,n) scanf("%lld%lld",&p[i],&a[i]),v.pb(a[i]),p[i]=(p[i]*inv)%mod;sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());cc = v.size();init();ll ans = 0;rep(i,1,n) {ans = (ans + (p[i]*ask(100000-getid(a[i])))%mod)%mod;update(100001-getid(a[i]),(1-p[i]+mod)%mod);}printf("%lld\n",ans);return 0; }

G. max

相當于在[1,n/c]，找最大的兩個互質的數，相鄰的兩個數一定互質，再特判一下1即可。

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define pb push_back typedef long long ll; using namespace std; ll c,n; int main() {scanf("%lld%lld",&c,&n);ll a = (n/c)*c;ll b = (n/c-(n/c!=1))*c;if(__gcd(a,b)==c&&a>=1&&a<=n&&b>=1&&b<=n) printf("%lld\n",a*b);else puts("-1");return 0; }

J. plan

盡量先選性價比最高的，特判幾種情況就行了

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define pb push_back typedef unsigned long long ll; using namespace std; ll n, p2, p3, ans = 0; int main() {scanf("%lld %lld %lld", &n, &p2, &p3);if(2*p3 >= 3*p2) {if(n%2 == 0) {ans = n/2*p2;}else {ans = (n/2+1)*p2;ans = min(ans,(n/2)*p2+p3);if(n>=3)ans = min(ans,(n-3)/2*p2+p3);}}else {if(n%3==0)ans = n/3*p3;else if(n%3==1) {ans = ((n-1)/3+1)*p3;ans = min(ans,((n-1)/3)*p3+p2);if(n>=4) ans = min(ans,(n-4)/3*p3+2*p2);}else if(n%3==2) {ans = (n/3+1)*p3;ans = min(ans,(n/3)*p3+p2);if(n>=2) ans = min(ans,(n-2)/3*p3+p2);}}printf("%lld\n",ans);return 0; }

轉載于:https://www.cnblogs.com/RRRR-wys/p/9428070.html

總結

以上是生活随笔為你收集整理的牛客网暑期ACM多校训练营（第五场）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。