Educational Codeforces Round 95 补题报告

A. Buying Torches
分析：
签到题，但是题面改来改去的，也是因为这题导致unrate，思路就是先把所需要的煤都转化成棍子，再看达成这么多棍子需要换多少次
代码：

int main()
{
 ll T,n,m,k;
 cin>>T;
 while(T--)
 {
  cin>>n>>m>>k;
  ll ans=k*m;
  ans+=k-1;
  ll qwe=ans/(n-1);
  if(ans%(n-1))
  {
   qwe++;
  }
  cout<<qwe+k<<"\n";
 }
 return 0;
}

B. Negative Prefixes
分析： 定位置的既然动不了就不考虑，既然需要使前缀和<0的部分尽可能少，那肯定就是大的尽量放前面，把可以动的元素按从大到小排序再插入回去
代码：

ll T,a[maxn],b[maxn],c[maxn];
ll n;
int cmp(int a,int b)
{
 return a>b;
}
int main()
{
 cin>>T;
 while(T--)
 {
  cin>>n;
  rep(i,1,n+1)
  {
   cin>>a[i];
  }
  int cnt=0;
  rep(i,1,n+1)
  {
   cin>>b[i];
   if(!b[i])
   c[++cnt]=a[i];
  }
  sort(c+1,c+cnt+1,cmp);
  int qwe=1;
  rep(i,1,n+1)
  {
   if(!b[i])
   {
    a[i]=c[qwe++];   
   }  
  }
  rep(i,1,n+1)
  cout<<a[i]<<" ";
  cout<<"\n";
 }
 return 0;
}

C. Mortal Kombat Tower
分析： 和你朋友每次都要消除，你的朋友可能会产生额外消耗，而你们俩每次最少动1，最多动2，那就直接dp了
dp[i][j] i=0表示你朋友的回合，i=1表示你的回合，j表示当前消除到哪个位置了
以及我为了方便判断每次消除时是否有1，用c数组来存储1的前缀和

代码：

int c[maxn];
int a[maxn];
int dp[3][maxn];
int n;
int main()
{
 iossync
 int T;
 cin>>T;
 while(T--)
 {
  cin>>n;
  rep(i,1,n+1)
  {
   cin>>a[i];
   c[i]=c[i-1]+a[i];
  }
  dp[0][1]=a[1];
  if(n==1)
  {
   cout<<a[1]<<"\n";
   continue;
  }
  if(n>=2)
  {
   dp[0][2]=c[2]-c[0];
   dp[1][2]=dp[0][1];
  }
  rep(i,3,n+1)
  {
   if(i>=4)
   dp[0][i]=min(dp[1][i-1]+c[i]-c[i-1],dp[1][i-2]+c[i]-c[i-2]);
   else
   dp[0][i]=dp[1][2]+c[3]-c[2];
   dp[1][i]=min(dp[0][i-1],dp[0][i-2]);
  }
  cout<<min(dp[0][n],dp[1][n])<<"\n"; 
 }
 return 0;
}

D. Trash Problem
分析： 题，读题都读了半天，才弄懂啥意思
我们可以渐进的理解这题，假如现在有n个点，最后都要扫到一个点，那肯定花费a[n]-a[1]的代价
那么现在拓展到2个点，肯定是左边的全部扫到靠近左边的点，右边的全部扫到靠近右边的点，并且易得这2个点肯定是在这些垃圾点的
粗略证明：假设左边点不在垃圾点上，在x位置，那根据之前的定义，这个点左边的所有垃圾都要扫到他这里，而他右边的自然去右边点，所以当他偏离左边最靠近的点时，属于白白增加距离，还不如去跟左边最远的点重合，右边同理
所以最后的花费就是(a[x]-a[1])+(a[n]-a[y])，也就是(a[n]-a[1])+(a[x]-a[y])，x和y是连续的，且是垃圾点，a[n]-a[1]找最大最小就可以了，那么只需要求出最大的两点距离就好，multiset就可，自动排序，每次加入新的点的时候，把旧的间隔去掉，添加2个新的，删除点的时候就是删去2个旧的，添加一个新的，具体可以见代码

代码：

set<int> s1;
multiset<int> s2;
inline void add(int x)
{
 //删1加2
 auto it = s1.insert(x).first;
 if(next(it) !=s1.end() && it!=s1.begin())
 {
  s2.erase(s2.find(*next(it)-*prev(it)));
 }
 if(next(it)!=s1.end())
 {//非max 
  s2.insert(*next(it)-*it);
 }
 if(it!=s1.begin())
 {//非min 
  s2.insert(*it-*prev(it));
 }
}
inline void del(int x)
{
 //删2加1 
 auto it = s1.find(x);
 if(next(it)!=s1.end())
 {//非max 
  s2.erase(s2.find(*next(it)-*it));
 }
 if(it!=s1.begin())
 {//非min 
  s2.erase(s2.find(*it-*prev(it)));
 }
 if(next(it) !=s1.end() && it!=s1.begin())
 {
  s2.insert(*next(it)-*prev(it));
 }
 s1.erase(x);
}
inline void show()
{
 //max-min - 最大间隔 
 if(!s2.empty())
 cout<<*prev(s1.end())-*s1.begin()-*prev(s2.end())<<"\n";
 else
 cout<<"0\n";
}
inline int read()
{
    int x=0;
    char f=1,c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,x,y;
int main()
{
 iossync 
 n=read();
 m=read();
 rep(i,0,n)
 {
  x=read();
  add(x);
 }
 show();
 rep(i,0,m)
 {
  x=read();
  y=read(); 
  switch(x)
  {
   case 1:{
    add(y);
    break;
   }
   case 0:{
    del(y);
    break;
   }
  }
  show();
 }
 return 0;
}

E. Expected Damage
分析： 群里大佬说了个这难度是区域赛签到题，呜呜呜呜呜，简单来说就是插入，先找>=b的数量，这里可以预处理d，先从大到小排序，然后lower_bound就好，记大于等于b的boss数量有ans个，因为随机排，所以受到每个boss伤害的概率是相等的，都是ans-a/ans，假如a>=ans，那肯定直接输出0了，当a<ans的时候，剩余的n-ans个boss就可以随意插入这ans个boss中，一共有ans+1个空，前a个空插入进去都不会受到伤害，后面都会受到伤害，因为a个后，盾牌已经烂掉了，所以受到伤害的概率是ans+1-a/(ans+1)，所以每次查找出ans的大小就好，其他部分直接前缀和预处理即可
代码：

ll qpow(ll a,ll b,ll mod)
{
 ll ans=1;
 while(b)
 {
  if(b&1)
  ans=a*ans%mod;
  b>>=1;
  a=a*a%mod;
 }
 return ans;
}
ll a[maxn],b[maxn];
ll n,m;
ll c,d;
int main()
{
 cin>>n>>m;
 rep(i,1,n+1)
 {
  cin>>a[i];
 }
 sort(a+1,a+n+1);
 rep(i,1,n+1)
 {
  b[i]=(b[i-1]+a[i])%mod;
 }
 rep(i,1,m+1)
 {
  cin>>c>>d;
  int ans=lower_bound(a+1,a+n+1,d)-a-1;
  int qwe=n-ans;
  if(qwe<c)
  {
   cout<<0<<"\n";
   continue;
  }
  //ans-c/ans
  //ans+1-c/(ans+1)
  ll sum=(b[n]-b[ans])%mod*(qwe-c)%mod*qpow(qwe,mod-2,mod)%mod;
  (sum+=b[ans]*(qwe+1-c)%mod*qpow(qwe+1,mod-2,mod)%mod)%=mod;
  cout<<(sum+mod)%mod<<"\n";
 }
 return 0;
}

F. Equal Product
3000分的题，emmmmm，告辞