优秀网站网址,制作一个交易平台网站,一家只做直购的网站,广东购物网站建设牛客网暑期ACM多校训练营#xff08;第五场#xff09; A. gpa 二分答案#xff0c;然后就转化为是否满足\(\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越高#xff0c;于是去掉最小的k个判断… 牛客网暑期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 ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
#define PII pairint,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) {ca;sb;}
}a[N];// 1. 2^n 暴力的做法
int ct(int s) {int ans 0;for(int is;i;i-i-i)ans;return ans;
}
double cal_1() {double ans 0;rep(s,0,(1n)-1) if(ct(s)n-k) {int t1 0, t2 0;rep(i,0,n-1) if(s(1i)) {t1 a[i1].s*a[i1].c;t2 a[i1].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(c1,c1n);rep(i,k1,n) ansc[i];return ans;
}
double cal_2() {double l 0, r 1001.0,mid;rep(ti,1,30) {mid (lr)*0.5;if(solve(mid)0) lmid;else rmid;}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];
mapint,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_{ji,a_ja_i} (1-pj)\)前缀乘积用树状数组维护。 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;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(b1) ans (ans*a)%mod;a(a*a)%mod;b 1LL;}return ans;
}
ll inv;
vectorll 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,2e51)B[i]1;
}
ll ask(int x) {ll ans 1;for(int ix;i;i-i-i)ans(ans*B[i])%mod;return ans;
}
void update(int x,ll v) {for(int ix;icc;ii-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 ia;ib;i)
#define per(i,a,b) for(int ia;ib;--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)ca1anb1bn) printf(%lld\n,a*b);else puts(-1);return 0;
}J. plan 尽量先选性价比最高的特判几种情况就行了 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--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/21)*p2;ans min(ans,(n/2)*p2p3);if(n3)ans min(ans,(n-3)/2*p2p3);}}else {if(n%30)ans n/3*p3;else if(n%31) {ans ((n-1)/31)*p3;ans min(ans,((n-1)/3)*p3p2);if(n4) ans min(ans,(n-4)/3*p32*p2);}else if(n%32) {ans (n/31)*p3;ans min(ans,(n/3)*p3p2);if(n2) ans min(ans,(n-2)/3*p3p2);}}printf(%lld\n,ans);return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9428070.html
