地址 https://codeforces.com/gym/105158/attachments

B 扫雷1
题意大致为n轮扫雷，每个位置都可购买扫雷币且每个位置购买不限次数，要求扫雷币购买最多。考虑贪心，假设下如果后面有更便宜的扫雷币那么我一定不会购买前面的扫雷币，也就是说我们需要维护一段区间的最小值，也就是在一段区间内贪心，然后将答案累加起来，我思路是对输入做一遍预处理，然后寻找区间最小值，在最小值处购买,对每个区间依次累加求全局最小值（贪心不会证明）。

# include <bits/stdc++.h>
using namespace std;
int n;
const int N=2e5+10;
int c[N],f[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>c[i],f[i+1]=0x3f3f3f3f;
    }
    for(int i=n;i>=1;i--)
    {
    f[i]=min(f[i+1],c[i]);
    }
    int l=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
    l++;
    if(f[i]==c[i]&&l>=c[i])
    {
    cnt+=l/c[i];
    l-=(l/c[i])*c[i];
    }
    }
    cout<<cnt;
    return 0;

}

J排列与合数
题意大致为输入一个五位数且各个数位上数子不相同，要求我们重新排列每一位是其为合数，考虑下每个位上数字一共是十种可能，末尾以偶数结尾的必定为合数，0~9偶数共5个.如果给出数的每一位都是奇数就直接输出样例中给出的97531，否则根据鸽巢原理必有一位为偶数，那么只需将偶数放到最后一位即可（注意前导0）

# include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
    string s,s1;
    cin>>s;
    int p=-1;
    for(int i=0;i<s.size();i++)
    {
    if((s[i]-'0')%2==0)
    {
    p=i;
    break;
    }
    }
    if(p==-1)
    cout<<97531;
    else 
    {
    for(int i=0;i<s.size();i++)
    {
    if(i==p)
    continue;
    s1+=s[i];
    }
    s1+=s[p];
    if(s1[0]=='0')
    swap(s1[0],s1[4]);
    cout<<s1;
    }
    cout<<endl;
    }
    return 0;

}

随机栈H
2n次操作，每次对应取出或插入，询问取出序列递增概率，要求每次取出的数递增（非严格），对于取出操作那么我们可以想到小根堆维护，每次取出最小值，用数组或者map统计每个数出现次数，每次取出概率为堆顶数的出现次数除以堆中元素的数量，然后用快速幂求逆元对答案取模即可

#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#define endl '\n'
# define int long long
using namespace std;
const int mod = 998244353;
map<int, int> m;
int pow1(int a, int b) 
{
    int res = 1;
    while(b)
    {
        if (b & 1)res = res * a % mod;
        a = a * a % mod;
        b>>=1;
    }
    return res % mod;
}
signed  main()
{
    priority_queue<int, vector<int>, greater<int> > p;//小顶堆
    int n,num,l = -1,s = 1,x = 1;

    cin >> n;
    for (int i = 0; i < 2 * n; i++) 
    {
    cin >> num;
    if (num == -1) 
    {
    s = s * m[p.top()] % mod;//分子，可以选择的数字
    x = x * p.size() % mod;//分母，队列里数字个数
    if (p.top() < l) 
    {
    cout<<0;
    return 0;
    }
    else
    {
    l = p.top();
    m[p.top()]--;
    p.pop();
    }
    } 
    else 
    {
    p.push(num);
    m[num]++;
    }
    }
    int ans = s * pow1(x, mod - 2) % mod;//除法取模
    cout << ans << endl;
}

有效算法
题意要求操作后a[i]相同，对于第i个数能取得的范围为[ai−k×bi,ai+k×bi]，考虑二分k,k越大每个i对应区间越大，区间相交可能性越大。K越小区间，相交越少满足条件答案越少。k满足一定边界条件可二分。枚举每个区间取交集，左端点去最大值，右端点最小值才可堆所有区间都满足

# include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long LL;
LL n,a[N],b[N];
bool check(LL mid)
{
    LL ml=-0x3f3f3f3f,mr=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
    LL ll=a[i]-mid*b[i],rr=a[i]+mid*b[i];
    ml=max(ml,ll);
    mr=min(rr,mr);
    }
    if(ml>mr)return false;
    return  true;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    cin>>b[i];
    LL l=0,r=1e9;
    while(l<r)
    {
    LL mid=l+r>>1;
    if(check(mid))
    r=mid;
    else 
    l=mid+1;
    }
    cout<<l<<endl;
    }



    return 0;

}

树上问题
题目要求选取树上一点作为根，当且仅当该节点作为根时，对于除根节点以外的所有节点，其点权都不小于其父亲节点的点权的一般，求一棵树上满足其性质的点
思路

换根dp
相当于儿子节点值的二倍大于等于父节点的值。当我们认定了一个根节点后，其下的所有边都会满足这样一种情况。
一个边的这个满足关系只和它两端的点有关系，而且是有向的（即远离根的一端的点的值的二倍大于等于靠近根的一端的点的值）。所以当我们的根向旁边一个点移动的时候，除了这两个点之间的边有可能会发生转变（也就是原先有贡献，结果变成没有贡献，或者反过来），其他的边则不会受到影响。
因此考虑换根DP。不妨设 1号点是根节点，设 cnt[i] 为以点i为根节点的子树的合法边的个数，我们去计算以每个点为整个树的根节点时合法边的个数，统计一下有几个点的答案为n-1即可。显然1号点我们已经计算好了，我们计算好点u的答案，需要去计算儿子节点v的答案。注意换根之后需要减去原有根的贡献加上现有点对根的贡献

# include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int idx,h[N],e[N*2],ne[N*2];
int cnt[N],ans[N],w[N];
int n;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs1(int u,int fa)
{
    int res=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
    int j=e[i];
    if(j==fa)
    continue;
    dfs1(j,u);
    if(2*w[j]>=w[u])
    res+=cnt[j]+1;
    else res+=cnt[j];
    }
    cnt[u]=res;
}
void dfs2(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa)
        continue;
        ans[j]=ans[u]-(2*w[j]>=w[u])+(2*w[u]>=w[j]);
        dfs2(j,u);
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
    int sum=0;
    idx=0;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    cin>>w[i],sum+=w[i];
    for(int i=0;i<n-1;i++)
    {
    int a,b;
    cin>>a>>b;
    add(a,b);
    add(b,a);
    }
    dfs1(1,-1);
    ans[1]=cnt[1];
    dfs2(1,-1);
    int t=0;
    for(int i=1;i<=n;i++)
    if(ans[i]==n-1)
    t++;
    cout<<t;
    cout<<endl;
    }


    return 0;

}

优秀字符串
模拟即可

# include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    int cnt = 0;
    while (n --) {
        string s; cin >> s;
        if (s.size() != 5) continue;
        if (s[2] != s[4]) continue;
        bool flag = 1;
        for (int i = 0; i < 4; i ++) for (int j = i + 1; j < 4; j ++) {
            if (s[i] == s[j]) flag = 0;
        }
        if (flag) cnt ++;
    }
    cout << cnt << endl;
}