刚放假回来，好困……
赛时rank 38，T1 100,T2 0,T3 0,T4 0
打了T1后迷迷糊糊，半睡不睡的。
这还能抢一个T1首切?
T1 BA
烙饼问题。
答案是\(\max(\max(a_i),\left\lceil\frac{\sum_{i=1}^na_i}{\min(n,m)}\right\rceil)\)
还有一个二分答案的做法。
但我们好像没有人写……
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e6 + 10;
int n,m,a[N];
inline void solve(){
cin>>n>>m;
ll sum = 0;
for(int i = 1;i <= n; ++i) cin>>a[i],sum += a[i];
sort(a+1,a+1+n);
ll ans1 = ceil(1.0*sum/min(n,m));
cout<<max(1ll*a[n],ans1);
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T2 BB
其实不算很难，但太困了，遂寄
设A所选的点集为\(A\)，B所选的点集为\(B\)，\(f(x,y)\)表示 [x支配y]
\[\begin{aligned} Ans&=\sum_{u\in A}\sum_{v\in B}f(u,v)-\sum_{u\in A}\sum_{v\in B}f(v,u)-\sum_{x\in A}w_x\\ &=\sum_{u\in A}(\sum_{v\in B}f(u,v)+\sum_{v\in A}f(u,v))-\sum_{u\in A}(\sum_{v\in B}f(v,u)+\sum_{v\in A}f(v,u))-\sum_{x\in A}w_x\\ &=\sum_{x\in A}siz_x-dep_x-w_x \end{aligned}\]将其排序，选第奇数个即可
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2e5 + 10;
struct EDGE{int to,next;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v){
edge[++cnt] = {v,head[u]};
head[u] = cnt;
}
int fa[N],n,w[N],siz[N],dep[N],p[N];
void dfs(int x){
siz[x] = 1;
dep[x] = dep[fa[x]] + 1;
for(int i = head[x]; i;i = edge[i].next){
int y = edge[i].to;
dfs(y);
siz[x] += siz[y];
}
}
inline void solve(){
cin>>n;
for(int i = 1;i <= n; ++i) cin>>w[i];
for(int i = 2;i <= n; ++i) cin>>fa[i],add(fa[i],i);
for(int i = 1;i <= n; ++i) p[i] = i;
dfs(1);
sort(p+1,p+1+n,[](int x,int y){return siz[x]-dep[x]-w[x] > siz[y]-dep[y]-w[y];});
ll ans = 0;
for(int i = 1;i <= n; i += 2) ans += siz[p[i]]-dep[p[i]]-w[p[i]];
cout<<ans;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T3 BC
T4 BD
这俩不会(其实是懒得调了)