iwtgm-23

题目链接

A.

首先，如果只有1个机关（除高度h）那么不需要水晶
试想，无论这个机关在哪里，当它关闭后，下一个机关就会开启...以此类推
反而机关多了情况会更复杂
设i和i-1机关都是打开的，我现在在机关i，然后i和i+1的机关会一起关闭，那么i+2一定要有一个开的机关，若没有，则需要水晶

int main(){
    scanf("%d",&T);
    while(T--){
        int ans=0;
        scanf("%d%d",&h,&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        a[++n]=0;
        for(int i=2;i<=n;i++){
            if(a[i]<=1)break ;
            if(a[i]-a[i+1]>1)ans++;
            else i++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

B.

一种很新的思路，不从整体入手，从局部入手
考虑对于每个最终数（从大到小，因为一个数满足了大数对小数没有影响），记录下它们的位置，看它们之间是否存在最大值比这个数小，若存在，则需要两次魔法，若不存在，一次就好
当要被改变的数比最终数还小，无解，因为只能把数变小
这里用的st表查询区间最大值

int Min[200010][20],Max[200010][20];//f[i][j]表示从i开始，区间长度为1<<j的范围内（i到i+（1<<j）-1）的最大值或最小值。当j为0时，区间长度为1，就是i本身
int n,m;
int a[N],b[N],x[N];
void init() {
    //n是数组元素个数，m是询问个数
    for (int i = 1; i <= n; i++) {
        Min[i][0] = Max[i][0] = b[i];//长度为1，就是i本身
    }
    for (int i = 1; i <= 19; i++) {//i是区间长度，为log（n）（向下取整）
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {//j是左端点，j+(1<<i)-1是右端点<=n
            Min[j][i] = min(Min[j][i - 1], Min[j + (1 << (i - 1))][i - 1]);//2^i=2^(i-1)+2^(i-1)
            Max[j][i] = max(Max[j][i - 1], Max[j + (1 << (i - 1))][i - 1]);//相当于分成两个长度为1<<(i-1)长度的区间
        }
    }
}
int query(int l,int r) {
    int s = __lg(r - l + 1);//所求区间长度
    int ma = max(Max[l][s], Max[r - (1 << s) + 1][s]);//会有重合部分但不影响（避免没有全部覆盖）
    return ma;
}

void solve() {
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    map<int,int>mp;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>x[i];
        mp[x[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(a[i]<b[i]){
            cout<<"NO"<<endl;return ;
        }
    }
    init();
    map<int,vector<int>>v;
    for(int i=1;i<=n;i++){
        if(b[i]!=a[i]){
            v[b[i]].push_back(i);
        }
    }
    for(auto [t,vv]:v){
        int cur=vv.size();
        for(int i=0;i<vv.size()-1;i++){
            int x=vv[i],y=vv[i+1];
            if(x==y-1)cur--;
            else{
                int mx= query(x+1,y-1);
                if(mx<=t)cur--;
            }
        }
        if(cur>mp[t]){
            cout<<"NO"<<endl;return ;
        }
    }
    cout<<"YES"<<endl;
}

C.

一种很新的思路，感觉自己得到了飞升
把数组分成k份，第一份权值是1，第二份权值是2...
换个角度，也可以先把每一份权值都看成k
然后第一份的权值减去（k-1）...
然后因为前缀和，取k-1个不同的前缀和，那么第一份权值一定减了k-1...
也就是说取了k-1个前缀和后，一定会出现k份且权值从1递增
那么现在就是考虑取哪几个前缀和，显然让和最小的权值是1，至此，排序解决

int n,k;
ll a[N],s[N],ans;
void solve() {
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    sort(s+1,s+n);
    for(int i=1;i<k;i++)ans-=s[i];
    ans+=k*s[n];
    cout<<ans;
}