学习笔记12：牛客周赛21

?

https://ac.nowcoder.com/acm/contest/73239

C

我们假设(x,y)是每次要删的方格(不一定存在)

记录一下每一列被删了几个

观察得出如果被删的行x>h[y]才是?有效删除

#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std ;
const int N=1000010;
int h[1010];
bool st[1010][1010];
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++) h[i]=n;
    for(int i=1;i<=k;i++){
        int x,y;
        cin>>x>>y;
        if(x>n-h[y])h[y]--;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i>n-h[j]) cout<<"*";
            else cout<<".";
        }
        cout<<endl;
    }
 }
signed main(){
    int t=1;
   // cin>>t;
    while(t--){
        solve();
    }
}

D

双指针

#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std ;
#define int long long
const int N=1000010;
int a[N];
void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int l=0;
    int ans=0;
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=a[i];
        while(l<=i && sum>=k){
            
            sum-=a[l];l++;
        }
        ans+=l;
    }
    cout<<ans<<endl;
 }
signed main(){
    int t=1;
   // cin>>t;
    while(t--){
        solve();
    }
}

E

一共四种情况

奇奇偶

奇偶奇

偶奇奇

偶偶偶

?一旦确定了开头后续的状态也是确定的

所以只有一种简单计算一下即可

#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std ;
#define int long long
const int N=1000010,mod=1e9+7;
int a[N];
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
void solve(){
    int n,k;
    cin>>n>>k;
    int j=k/2+(k&1);
    int o=k/2;
    int cnt=n/3;
    int cnt1=(n+1)/3;
    int cnt2=(n+2)/3;
    int cnt3=n/3;
    int res1=((qmi(j,cnt1)*qmi(o,cnt2))%mod * qmi(j,cnt3))%mod;
    int res2=((qmi(j,cnt1)*qmi(j,cnt2))%mod * qmi(o,cnt3))%mod;
    int res3=((qmi(o,cnt1)*qmi(j,cnt2))%mod * qmi(j,cnt3))%mod;
    int res4=((qmi(o,cnt1)*qmi(o,cnt2)%mod)*qmi(o,cnt3))%mod;
    int ans=((res1+res2)%mod+(res3+res4)%mod)%mod;
    cout<<ans<<endl;
 }
signed main(){
    int t=1;
   // cin>>t;
    while(t--){
        solve();
    }
}

?F

离散化+树状数组

分析：如果a[i]数据比较小(而实际上我们也只需要离散化一下就可以了)

公式变形

变形

我们对于每一个前缀和1求有几个其他前缀和是符合这个公式的，这就可以用树状数组（离散化后的数据，添加和查询，都是对排序并且去重的数组下标进行的。找到第一个大于的前缀和，下标减1就是所要求的位置），在添加到树状数组中时，要注意下标0不能直接添加，可以加一个偏移量。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long 
const int N=100010;
int tr[N];
int a[N];
int sum[N];
int lowbit(int x){
    return x&(-x);
}
void add(int x){
    x+=1;
    for(int i=x;i<N;i+=lowbit(i)){
        tr[i]++;
    }
}
int query(int x){
    x+=1;
    int res=0;
    for(int i=x;i;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;
}
int get();
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int>v;
    v.push_back(0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        v.push_back(sum[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int len=v.size();
    int ans=0;
    add(lower_bound(v.begin(),v.end(),0)-v.begin());
    for(int i=1;i<=n;i++){
        int l=query(upper_bound(v.begin(),v.end(),sum[i]-k)-v.begin()-1);
        ans+=l;
        add(lower_bound(v.begin(),v.end(),sum[i])-v.begin());
    }
    cout<<ans<<endl;
}
signed main(){
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}