今天的题目有一多半7月份都是做过的

1 Accidental Victory{

1. 题意：有一组拳击手参加锦标赛，每个人之间都有对应的编号和筹码，筹码越大的人越能打败对手，而筹码相同的人有概率能赢。打赢对手能获得对方的筹码。求最终获胜概率不为0的选手编号

2. 思路：这题首先要先搞清楚什么时候获胜的概率为0.我们都知道如果一个人的筹码值最小，那么他永远不可能成为冠军，同样的，如果一个人的筹码值最大，那么他一定能成为冠军。而实力值相同的人有概率获胜，那么我们先假设他们都是可以获胜的，而获胜后需将他们的筹码值相加。

说到这里想必大家已经看出来了，我们这题需要维护一个排序后的前缀和。

这个前缀和的用处是什么？我们如果在正序遍历前缀的途中，如果前面所有人的筹码值之和都不及下一个人的筹码值，那么前面的人就都是获胜概率为0的人，反之，后面的人就都是获胜概率不为0的人

3. 算法：排序，前缀和

}

核心代码：

 for (int i=1;i<n;i++) {
            pref[i]=pref[i-1]+a[i].sco;//计算筹码前缀和
        }
        int start=0;
        for (int i=n-2;i>=0;i--) {//倒序查找更省时
            if (pref[i]<a[i+1].sco) {//找到第一个前缀和比当前元素小的下标
                start=i+1;
                break;
            }
        }
        vector<int> ans;
        for (int i=start;i<n;i++) {
            ans.push_back(a[i].id);//答案
        }

2 Mocha and Diana{

1. 题意：有两棵树和一些节点，并给出这两棵树的部分边，现可以在这两棵树中同时添加任意条边，但要保证树中无自环，求最多能添加多少条边

2. 思路：这题节点个数不到1000，因此我们可以尽量让所有节点都能连上边。换句话说，如果这两棵树中有两个节点都没有连通，那么这两个节点之间就可以连接一条边，最终的答案就是这些边最多有多少个

3. 算法：并查集

}

核心代码：

  for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
        if(find(fa1,i)!=find(fa1,j)&&find(fa2,i)!=find(fa2,j)){//找到不连通的点
            mp.push_back({i,j});
            merge(fa1,i,j);//合并第一棵树
            merge(fa2,i,j);//合并第二棵树
        }
        }
     }

3 Quests{

1. 题意：有一组任务，每做完第i个任务都会获得其对应的金币ai。有一个整数k约束你，使得你做完该任务后的k天里都不能再做该任务。现给出一个目标金额c和规定天数d,求一个最大的k，使得你能在规定天数内达到目标金额

2. 思路：看到这种求一个最大的k并且k还带有限制因素在内的题目我们就应该想到二分。

为什么能用二分？如果是暴力去求的话我们完全可以枚举k看最终是否能完成任务就行了，但关键就在于这题的数据范围很大，d一度达到2e5,因此我们就需要一步一步地去缩小枚举范围，这也就是二分的思想

因此这题我们的关键就是写出判断答案是否可行的函数。按照题意，我们在枚举第1到d天时判断当前的i%(k+1)是否大于当前的i，如果是则说明时间过了，可以重新加上当前的任务金额。对于每天我们选择的金额需要贪心一个最大的ai,使得我们的损失最小化

3. 算法：贪心，二分，排序

}

核心代码：

bool check(int k){//检测二分答案是否可行
     long long sum=0;
     for(int i=0;i<d;i++){
          int id=i%(k+1);
          if(id<n){
              sum+=m[id];
          }
          if(sum>=c) return true;
     }
     return sum>=c;
}

4 Fight with Monsters{

1. 题意：你和你的朋友在玩一种打怪物的游戏。最开始时你先手，并对怪物造成a点伤害，之后是你的朋友并造成b点伤害，轮流出手。如果最终是你干掉了怪物那么你将获得1点积分，而如果是你的朋友最终干掉了怪物那么双方都不得积分。但你可以使用特殊技能跳过朋友的回合直接出手。现在规定你使用特殊技能的次数k,在使用技能最优的情况下，你最多能获得多少积分

2. 思路：对于轮流来的攻击我们可以看做是你和你的朋友的伤害相加得来，如果最终怪物的血量和伤害总和能互相整除说明你的朋友一定能拿下怪物，此时的技能操作次数为1。如果不能整除操作次数就是伤害值除以自己伤害的余数。

          最终如果每一回的操作次数都没到k，那么积分+1，否则直接放弃循环，输出答案

3. 算法：排序

}

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int main(){
     int n,k,a,b;
     cin>>n>>a>>b>>k;
     long long sum=a+b;
     vector<long long> opu;
     for(int i=0;i<n;i++){
        long long h;
        cin>>h;
        long long res=h%sum;
        if(res==0) opu.push_back((sum-1)/a);
        else opu.push_back((res-1)/a);
}
        int ans=0; 
        sort(opu.begin(),opu.end());
        for(int i=0;i<opu.size();i++){
        if(k>=opu[i]){
                ans++;
                k-=opu[i];
        }
         else break;
      }
      cout<<ans;
}

5 Buy low sell high{

1. 题意：你能预测未来n天的股票价格，在第i天时你可以选择买入或什么事情都不做，如果手头没持有股票那么你不能选择售出，求最终你能获得的最大收益

2. 思路：这题的关键在于我们会不会选择什么事情都不做

答案是不会。因为我们每次在没有股票的时候选择买入，这个股票在未来的某一天就有可能成为高价卖出的选择。因此我们无论遍历到哪一天都选择将股票投入。而当我们当前的价格大于我们已买股票的最小价格时售出获得收益，所以我们要不断维护一个当前所有已买股票的最小价格，在售出时好直接获得最大利润。

3. 算法：反悔贪心，优先队列

}

#include <bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> pq;//维护当前最小成本的堆
int main(){
     int n;
     cin >> n;
     vector<int> a(n+1);
     for(int i=1;i<=n;i++) cin >> a[i];
     long long ans=0;
     for(int i=1;i<=n;i++){
         if(!pq.empty()&&a[i]>pq.top()){//当前持有股票且当前值大于最小值
            ans+=a[i]-pq.top();//最大利润
            pq.pop();
            pq.push(a[i]);
         }
         pq.push(a[i]);//买入
     }
     cout<<ans;
}

6 Alice and bob’s game{

1. 题意：有一个长度为n的棋盘，每个棋盘的位置ai有其对应的数值，现在Alice 先手从第i枚棋子开始走，定义棋子走到的格子内的数值必须大于原格子中的数值，且走的格子数必须等于原格子内的数的倍数，及：|i-j|%ai==0 求对于每个格子i，谁最终是必胜的，输出A或B

2. 思路：这题的关键在于如果Alice能走到Bob的必败点，则Alice 一定必胜，所以我们枚举每一个起始点i,遍历两边的倍数寻找最大的点。只要能够出现比原来点大的点，这个点就一定是Alice的必胜点

3. 算法：博弈

}

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int win[N];
int main(){
    int n;
    cin >> n;
    vector<int> a(n+1),flag(n+1);
    for(int i=1;i<=n;i++){
        cin >> a[i];
        flag[a[i]]=i;
    }
    for(int i=n;i>=1;i--){
            int p=flag[i];
           for(int nxt=p+i;nxt<=n&&!win[p];nxt+=i){
                if(a[nxt]>i&&win[nxt]==0){
                    win[p]=1;
                }
           }
           for(int nxt=p-i;nxt>=1&&!win[p];nxt-=i){
             if(a[nxt]>i&&win[nxt]==0){
                win[p]=1;
             }
           }
     }
     for(int i=1;i<=n;i++){
        if(win[i]) cout<<"A";
        else cout<<"B";
     }
}