CF的Educational Round (Div.2)，质量还是蛮高的。

A: 水题

#include
#include
typedef long long ll;
ll T,x,y,k,ans;

template
inline void read(T &x){
char ch = getchar(); x = 0; int f = 1;
for(;ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') f = -1; for(;ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
x *= f;
}
int main(){
read(T);
while(T--){
read(x); read(y); read(k);
ans = y * k + k - 1; x--;
if(ans % x == 0) printf("%lld\n",ans / x + k);
else printf("%lld\n",ans / x + k + 1);
}
return 0;
}

B: 降序排序没被固定的元素，挨个替换没被固定的元素。

#include
#include
#include
typedef long long ll;
int T,n,m,t = 0;
int a[110],b[110];
bool vis[110];

template
inline void read(T &x){
char ch = getchar(); x = 0; int f = 1;
for(;ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') f = -1; for(;ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48; x *= f; } int main(){ read(T); while(T--){ read(n); m = t = 0; for(int i = 1;i <= n; i++) read(a[i]); for(int i = 1;i <= n; i++) read(vis[i]); for(int i = 1;i <= n; i++) if(!vis[i]) b[++m] = a[i]; std::sort(b + 1,b + m + 1,std::greater ());
for(int i = 1;i <= n; i++)
if(!vis[i])
a[i] = b[++t];
for(int i = 1;i <= n; i++) printf("%d ",a[i]);
printf("\n");
}
return 0;
}

C: 显而易见的dp。

#include
#include
typedef long long ll;
const int M = 200010;
int T,n;
int a[M];
int dp[M][2];//0表示当前是我到达这里,1表示是朋友到达

template
inline void read(T &x){
char ch = getchar(); x = 0; int f = 1;
for(;ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') f = -1; for(;ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
x *= f;
}
int main(){
read(T);
while(T--){
read(n);
for(int i = 1;i <= n; i++) read(a[i]), dp[i][0] = dp[i][1] = M;
dp[1][1] = a[1]; dp[2][1] = a[1] + a[2];
dp[2][0] = a[1];
for(int i = 3;i <= n; i++){
dp[i][0] = std::min(dp[i - 2][1],dp[i - 1][1]);
dp[i][1] = std::min(dp[i - 2][0] + a[i - 1] + a[i],dp[i - 1][0] + a[i]);
}
printf("%d\n",std::min(dp[n][1],dp[n][0]));
}
return 0;
}

D: 结论非常明显，由于是删除一个位置所有的垃圾，所以可以用可以去重的set存下当前有垃圾的位置。

然后因为要求聚拢垃圾到不超过2个堆里，则可以转换为相邻垃圾间的距离，即为dis[i] = set[i + 1] - set[i]，可以用multiset存储。

所以对于每一个状态，答案便是*set.(--s.end()) - *s.begin() - *(--ms.end()) 。

细节看代码。

#include
#include
#include
typedef long long ll;
const int M = 100010;
int n,q;
int a[M];

template
inline void read(T &x){
char ch = getchar(); x = 0; int f = 1;
for(;ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') f = -1; for(;ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48; x *= f; } std::set s;
std::multiset ms;
int main(){
read(n); read(q);
for(int i = 1;i <= n; i++) read(a[i]), s.insert(a[i]); std::sort(a + 1,a + n + 1); for(int i = 2;i <= n; i++) ms.insert(a[i] - a[i - 1]); printf("%d\n",(s.size() <= 2) ? 0 : *(--s.end()) - *s.begin() - *(--ms.end())); while(q--){ int t,x; read(t); read(x); if(t == 0){ std::set ::iterator it = s.find(x), l = it, r = it;
l--; r++;
if(it != s.begin()) ms.erase(ms.find(x - *l));
if(it != --s.end()) ms.erase(ms.find(*r - x));
if(it != s.begin() && it != --s.end()) ms.insert(*r - *l);
s.erase(it);
}
else{
s.insert(x);
std::set ::iterator it = s.find(x), l = it, r = it;
l--; r++;
if(it != s.begin()) ms.insert(x - *l);
if(it != --s.end()) ms.insert(*r - x);
if(it != s.begin() && it != --s.end()) ms.erase(ms.find(*r - *l));
}
printf("%d\n",(s.size() <= 2) ? 0 : *(--s.end()) - *s.begin() - *(--ms.end()));
}
return 0;
}

E: 思想非常明显，直接lower_bound二分出所有比防御力高的怪的数量，然后分类计算。

细节见代码。

#include
#include
typedef long long ll;
const int M = 200010, mod = 998244353;
int n, q, dura, def, ans;
int a[M],sum[M];

template
inline void read(T &x){
char ch = getchar(); x = 0; int f = 1;
for(;ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') f = -1; for(;ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48; x *= f; } inline int q_pow(int x,int num){ int ret = 1; for(;num; num >>= 1){
if(num & 1) ret = 1ll * ret * x % mod;
x = 1ll * x * x % mod;
}
return ret;
}
int main(){
read(n); read(q);
for(int i = 1;i <= n; i++) read(a[i]);
std::sort(a + 1,a + n + 1);
for(int i = 1;i <= n; i++) sum[i] = (sum[i - 1] + a[i]) % mod;
while(q--){
read(dura); read(def); ans = 0;
int x = std::lower_bound(a + 1,a + n + 1,def) - a;
int smallsum = sum[x - 1], bigsum = sum[n] - sum[x - 1];
x = n - x + 1;//可以破防的数目
if(dura <= x){
ans = 1ll * bigsum * (x - dura) % mod * q_pow(x,mod - 2) % mod;
ans = (ans + 1ll * smallsum * (x - dura + 1) % mod * q_pow(x + 1,mod - 2)) % mod;
}
printf("%d\n",ans);
}
return 0;
}

F: 不会。。。

G: 想法太假了，没想到线段树上。