【2020牛客寒假基础算法训练营】第四场总结

A 签到
B 签到括号匹配栈
C 子段乘积注意不能除0
D
- 题意：给出序列，求多少个区间异或值为0
- 思路：遍历序列的同时记录当前前缀异或值，用map统计当前前缀异或值之前出现次数，用这个次数更新答案。初始mp[0]=1。
E 贪心
- 思路：给出一串加号和1-9的数字组成的字符串，如：23984692+238752+2+34+，求重组后表达式的结果的最小值是多少
- 思路：有n个加号就有n+1个数字相加(记最终要进行相加数字为V)，要想使最后的结果最小，那么这些数字就应该尽量均匀的分配到V中，且V的低位数值大，高位数值小。故对所有的数字降序排列，每n+1个为一组从低位到高位分配给V，并计算最终结果，注意最高位可能还有进位。
- ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+10;
const ll mod = 998244353;
vector<int> v[maxn];
vector<int> ans;
vector<int> s;
char ss[maxn];
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%s", ss+1);
    int len = strlen(ss+1);
    int div = 1;
    for(int i = 1; i <= len; i++)
    {
        if(ss[i]=='+') div++;
        else s.push_back(ss[i]-'1'+1);
    }
    sort(s.begin(), s.end(), greater<int>());
    int SIZE = 0;
    for(int i = 0; i < s.size(); i++)
        v[i%div].push_back(s[i]), SIZE = max(SIZE, (int)v[i%div].size());
    int ca = 0, sum;
    for(int i = 0; i < SIZE; i++)
    {
        sum = ca;
        for(int j = 0; j < div; j++)
            if(i<v[j].size()) sum += v[j][i];
        ans.push_back(sum%10);
        ca = sum/10;
    }
    if(ca!=0) ans.push_back(ca);
    for(int i = ans.size()-1; i >= 0; i--) printf("%d", ans[i]);
    return 0;
}

F 博弈
- 题意：现有一个 n 个点，n-1条边组成的树，其中 1 号点为根节点。
  牛牛和牛妹在树上玩游戏，他们在游戏开始时分别在树上两个不同的节点上。
  在游戏的每一轮，牛牛先走一步，而后牛妹走一步。他们只能走到没有人的空节点上。如果谁移动不了，就输掉了游戏。现在牛牛和牛妹决定随机选择他们分别的起点，于是他们想知道，有多少种游戏开始的方式，使得牛牛存在一种一定获胜的最优策略。
  两种开始方式相同，当且仅当在两种开始方式中牛牛，牛妹的开始位置是分别相同的，否则开始方式就被视作不同的。
- 思路：通过归纳可以发现，两人每走一步都会改变两人之间距离的奇偶性，且要想使牛牛赢，那么牛妹最后走的时候两人之间的距离为1（奇数）。所以如果最初两人的距离为偶数的话那么牛牛一定会赢。只需要分别统计树中所在层数为奇数和偶数的点的数目，所在层数同为奇/偶那么之间的距离一定是偶数。
- ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
const ll mod = 998244353;
int n, f;
int d[maxn];
ll cnt[3];
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    d[1] = 1;
    cnt[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        scanf("%d", &f);
        d[i] = d[f]+1;
        cnt[d[i]&1]++;
    }
    ll ans = cnt[0]*(cnt[0]-1)+cnt[1]*(cnt[1]-1);
    printf("%lld\n", ans);
    return 0;
}

G 二分
- 题意：n个学生，10|n，给出平时成绩（均高于90分），期末成绩在[0,90]之间等概率打出，问期末成绩要占百分之多少才能保证优秀率恰好在10%。最终分数≥90为优秀
- 思路：（1）二分
                直接二分答案，判断当前占比下，优秀的人数的期望值是否为 $\frac{n}{10}$
                (2)直接计算
                设平时分数是s，期末占比x，期末分数为y，若最终为优秀则有：
                 $<mstyle displaystyle="true" scriptlevel="0"> s (1 - x) + y x \geq 90 \Rightarrow y \geq \frac{90 - s (1 - x)}{x} </mstyle>$
                那么最终这个人为优秀的概率为： $<mstyle displaystyle="true" scriptlevel="0"> \frac{90 - \frac{90 - s (1 - x)}{x}}{90} \Rightarrow \frac{(s - 90) (1 - x)}{90 x} </mstyle>$ （这也可以解释为什么平时成绩x保证>90了）
                题意要求： $<mstyle displaystyle="true" scriptlevel="0"> <munderover> \sum i = 1 n </munderover> \frac{(s - 90) (1 - x)}{90 x} = 0.1 n \Rightarrow x = \frac{<munderover> \sum i = 1 n </munderover> (s_{i} - 90)}{9 n + <munderover> \sum i = 1 n </munderover> (s_{i} - 90)} </mstyle>$
  另外注意输出。。。我🚮了
- ac代码：

//二分
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
const ll mod = 998244353;
const double eps = 1e-9;
int n;
int a[maxn];
double ans = 0;
bool check(double x)
{
    double res = 0, p = 0;
    for(int i = 1; i <= n*10; i++)
    {
        p = (90.0-a[i]*(1-x))/x;
        res += (90-p)/90;
    }
    return res > n;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    n/=10;
    double l = 0, r = 1;
    while((r-l)>1e-7)
    {
        double mid = (l+r)/2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    //cout << ans << endl;
    printf("%.2lf%%", r*100);
    return 0;
}

H 思维
- 题意：
- 思路：维护每个颜色对当前答案的贡献。依次遍历每节车厢，第i节车厢和第i-1节车厢最多影响两个颜色的变化，所以在遍历过程中动态维护每种颜色的变化，再求对答案有贡献的颜色。相当于线段树单点修改和区间查询，线段树叶子x结点记录的是到当前遍历位置i时，pre[x]*suf[x]，即i前面x出现的次数和i后面x出现的次数。但是用线段树比较容易T。
  用树状数组更好些也更快一些，同样是单点修改和区间查询。
- ac代码：

//线段树
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+10;
struct Tree{
    int l, r;
    ll sum;
}tree[maxn<<2];
struct node{
    int col, l, r;
}a[maxn];
int n;
ll all[maxn], now[maxn];
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = - 1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 3ll) + (s << 1ll) + (ch ^ 48ll));
    return s * f ;
}
inline void out(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) out(x/10);
    putchar(x%10+'0');
}
void build(int id, int l, int r)
{
    tree[id].l = l; tree[id].r = r;
    if(l==r) {tree[id].sum = 0;  return ;}
    int mid = (l+r)>>1;
    build(id<<1, l, mid);
    build(id<<1|1, mid+1, r);
}
void push_up(int id)
{
    tree[id].sum = tree[id<<1].sum+tree[id<<1|1].sum;
}
void insert(int id, int pos, ll val)
{
    if(tree[id].l==tree[id].r) {tree[id].sum = val; return ;}
    int mid = (tree[id].l+tree[id].r)>>1;
    if(pos<=mid) insert(id<<1, pos, val);
    else insert(id<<1|1, pos, val);
    push_up(id);
}
ll query(int id, int ql, int qr)
{
    if(ql>qr) return 0;
    if(ql<=tree[id].l && tree[id].r<=qr) return tree[id].sum;
    ll ans = 0;
    int mid = (tree[id].l+tree[id].r)>>1;
    if(ql<=mid) ans += query(id<<1, ql, qr);
    if(qr>=mid+1) ans += query(id<<1|1, ql, qr);
    return ans;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    n = read();
    int mm = 0;
    for(int i = 1; i <= n; i++)
    {
        a[i].col = read(); a[i].l = read(); a[i].r = read();
        mm = max(mm, max(a[i].r, a[i].l));
        all[a[i].col]++;
    }
    build(1, 1, mm);
    printf("0");
    for(int i = 2; i <= n; i++)
    {
        now[a[i-1].col]++;
        insert(1, a[i-1].col, now[a[i-1].col]*(all[a[i-1].col]-now[a[i-1].col]));
        insert(1, a[i].col, now[a[i].col]*(all[a[i].col]-now[a[i].col]-1));
       // printf(" ");
        putchar(' ');
        out(query(1, a[i].l, a[i].r));
    }
    return 0;
}

//树状数组
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+10;
#define lowbit(x) (x&(-x))
struct node{
  int col, l, r;
}a[maxn];
ll c[maxn], all[maxn], now[maxn];
int n;
void update(int nn, int pos, ll val)
{
    for(int i = pos; i <= nn; i += lowbit(i))
        c[i] += val;
}
ll query(int pos)
{
    ll ans = 0;
    for(int i = pos; i > 0; i -= lowbit(i))
        ans += c[i];
    return ans;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    int mm = 0;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d %d", &a[i].col, &a[i].l, &a[i].r);
        all[a[i].col]++;
        mm = max(mm, max(a[i].l, a[i].r));
    }
    printf("0");
    for(int i = 2; i <= n; i++)
    {
        if(a[i-1].col==a[i].col) update(mm, a[i-1].col, -2*now[a[i-1].col]+all[a[i-1].col]-2);
        else
        {
            update(mm, a[i-1].col, -now[a[i-1].col]+all[a[i-1].col]-1);
            update(mm, a[i].col, -now[a[i].col]);
        }
        now[a[i-1].col]++;
        printf(" %lld", query(a[i].r)-query(a[i].l-1));
    }
    return 0;
}

I 思维
- 题意：
  
  $z \in 0, 1$
- 思路：按照x升序，z升序排列，当遇到z=0的星星，就把它的y值加入候选的mulset中，遇到z=1的星星时，就在mulset中找到第一个小于当前y的y值，并删除计数。
- ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+10;
#define lowbit(x) (x&(-x))
struct node{
    int x, y, z;
    friend bool operator < (node a, node b)
    {
        return a.x==b.x ? a.z>b.z : a.x<b.x;
    }
}a[maxn];
int n;
multiset<int> s;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
    sort(a+1, a+1+n);
    multiset<int>::iterator it;
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(a[i].z)
        {
            it = s.lower_bound(a[i].y);
            if(it!=s.begin())
            {
                it--;
                s.erase(it);
                ans++;
            }
        }
        else s.insert(a[i].y);
    }
    printf("%d\n", ans);
    return 0;
}

J 有点难
- 题意：
- 思路：emmm这魔幻的题目描述。。。题目是想告诉我们不关心y轴，当前x轴坐标是x， $x \Rightarrow x + 1$ 有3种方案， $x \Rightarrow x$ 有1种方案， $x \Rightarrow x - 1$ 有2种方案。
  
  具体推一下题解的后半部分：
  $G (i) = f (n - i, L_{i}) + f (n - i, L_{i} + 1) + . . . + f (n - i, R_{i} - 1) + f (n - i, R_{i})$
  $G (i - 1) = f (n - i + 1, L_{i - 1}) + f (n - i + 1, L_{i - 1} + 1) + . . . + f (n - i + 1, R_{i - 1} - 1) + f (n - i + 1, R_{i - 1})$
  
  $2 G (i) = 2 f (n - i, L_{i}) + 2 f (n - i, L_{i} + 1) + . . . + 2 f (n - i, R_{i} - 1) + 2 f (n - i, R_{i})$
  $3 G (i) = 3 f (n - i, L_{i}) + 3 f (n - i, L_{i} + 1) + . . . + 3 f (n - i, R_{i} - 1) + 3 f (n - i, R_{i})$
  错位加：
  
  $5 G (i) = 2 f (n - i, L_{i}) + 3 f (n - i, R_{i}) + f (n - i + 1, L_{i} + 1) + . . + f (n - i + 1, R_{i} - 1) + f (n - i + 1, R_{i})$
  $3 f (n - i, L_{i} - 1) + 2 f (n - i, R_{i} + 1) + 5 G (i) = G (i - 1) \sum_{a = L_{i}}^{R_{i} + 1}$
  这样由G(i)就可以推得G(i-1)中的大多项，再根据 $(L_{i - 1}, R_{i - 1})$ 和 $(L_{i}, R_{i} + 1)$ 对已求得的G(i-1)中的项就行增减，得到 $(L_{i - 1}, R_{i - 1})$ 对应的项之和
- ac代码：

//someone的代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+20;
const int mod=998244353;
typedef long long ll;
ll n,m,f2[N],f3[N],q[N],p[N],G[N];
ll qmi(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
ll c(ll a,ll b){
    return q[a]*p[b]%mod*p[a-b]%mod;
}
ll f(ll a,ll b){
    if(a<b||b<0)return 0;
    return c(a,b)*f3[b]%mod*f2[a-b]%mod;
}
int main()
{
    cin>>n>>m;
    f2[0]=f3[0]=q[0]=1;
    for(int i=1;i<=n;i++){
        f2[i]=f2[i-1]*2%mod;
        f3[i]=f3[i-1]*3%mod;
        q[i]=q[i-1]*i%mod;
    }
    p[n]=qmi(q[n],mod-2);
    for(int i=n-1;i>=0;i--)p[i]=p[i+1]*(i+1)%mod;
    ll ans=1,l=0,r=0;
    for(int i=n;i>=0;i--)
    {
        int ql=max((n-i-m+1)/2,0ll),qr=min((n-i+m)/2,n-i);
        while(l<ql)ans=(ans-f(n-i,l)+mod)%mod,l++;
        while(l>ql)l--,ans=(ans+f(n-i,l))%mod;
        while(r<qr)r++,ans=(ans+f(n-i,r))%mod;
        while(r>qr)ans=(ans-f(n-i,r)+mod)%mod,r--;
        G[i]=ans;
        ans=(ans*5)%mod;
        ans=(ans+3*f(n-i,l-1)+2*f(n-i,r+1))%mod;
        r++;
    }
    ans=0;
    for(int i=n;i>=0;i--)ans=(ans+G[i]*c(n,i)%mod)%mod;
    cout<<ans<<endl;
}