2022icpc 南京

G. Inscryption

贪心回溯

在题目中0可以变成策略1，也可以变成策略2，

但策略2是比策略1更加优秀的策略，所以当遇到0时能变成策略2就变成策略2，但是变成策略2可能会让后面的决策无法进行，所以需要回溯，记录前面有多少个0变成了策略2，在后面无法进行时把前面的变成策略2的0变成策略1.

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
 return gcd(b,a%b);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        scanf("%d",&n);    int a;
        int cnt=1,w=1,tmp=0;
        int flag=1;
        for(int i=1;i<=n;i++){
        scanf("%d",&a);
        if(a==1){
            cnt++,w++;
        }
        if(a==-1){
            if(cnt>1){
                cnt--;
            }
            else if(cnt==1){
                if(tmp==0) flag=0;
                else {
                    tmp--;w++,cnt+=1;
                }
            }
        }
        if(a==0){
                if(cnt==1){    
                cnt++,w++;
                }
                else {
                    cnt--;  tmp++;
                }         
        }
        }
        if(flag==1){
        int x=gcd(cnt,w);
            cnt/=x;
            w/=x;
            printf("%d %d\n",w,cnt);
        }
        else {
            printf("-1\n");
        }
    }
    return 0;
}

D. Chat Program

二分+差分

题目求一个序列经过操作之后的第k大值，这种是明显的二分，求值类的问题都可以用二分，那问题就变成了有一个数x，经过操作的序列是否有超过k个数比它大。二分的复杂度是logn，所以check函数最多是nlogn复杂度的。这个问题的解法是一个个数去考虑，如果ai>=x,直接就贡献答案，如果ai<x,那就考虑在它前面什么位置开始操作序列会让它>=x,这样就变成了区间加1，一次查询，用差分+前缀和维护，这样就获得了每一个位置开始操作能让多少个ai(<x)变得>=x。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],l[N],r[N],sum[N];
int n,k,m,c,d;
bool check(int x){
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    memset(sum,0,sizeof(sum));
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]>=x) cnt++;
        else {
            l[i]=i-m+1;
            if(d!=0)
            r[i]=i-ceil((double)(x-a[i]-c)/d);
            else {
                if(a[i]+c>=x)
                r[i]=i;
                else {
                    r[i]=-1e9;
                }
            }    
                    r[i]=min(r[i],i);
                /*cout<<i<<" "<<l[i]<<" "<<r[i]<<endl;*/
            if(l[i]<=r[i]){
                sum[max(1ll,l[i])]++;
                sum[max(0ll,r[i])+1]--;
            } 
        }
    }
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+sum[i];    
        if(sum[i]+cnt>=k) return 1;
    }
    return 0;
}
signed main(){
    cin>>n>>k>>m>>c>>d;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    int l=0,r=1e18;
    
    while(r>l){
        int mid=r+l+1>>1;
        if(check(mid)){
            l=mid;
        }
        else {
            r=mid-1;
        }
    }
    cout<<l;
    return 0;
}

A Stop, Yesterday Please No More

二维差分+经典模型

考虑如果没有洞那么经历操作之后会剩下什么样子的袋鼠。发现上下左右移动可以看成是边界在移动，边界一直保持一个原初的矩形形状，而且上下移动和左右移动没有任何关系。一旦边界移动到了一个位置，这个位置前面的袋鼠都会消失。

所以记录u,d,l,r,表示在移动时所产生的最小矩阵的上下左右边界，这样剩下的袋鼠数量就是有(d-u+1)*(r-l+1)个。

加入有洞的情况，发现洞产生的路径都可以通过平移获得，那么就只维护一条路径，就是从(0,0)点开始的路径，那么所有的点（i，j）的路径就是（0，0）点开始的路径上的点加（i，j）。 那么我们要维护有洞会让袋鼠消失多少，只有在u<=x<=d,l<=y<=r的才是有效被消失的袋鼠，那么就维护mp[i][j]表示从（i，j)点开始会让多少只袋鼠消失，发现对于点(x,y),只会对一个矩形内的数加1，左上角为(u-x,l-y),右下角为（d-x,r-y)的矩形，变成二维差分维护，那么在二维差分中给一个点加1等于给它往右往下的全部点加1.

注意：要去除经过的重复的点，重复点不能重复计算答案，因为他们去除的是同一片袋鼠。

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
string s;
int mp[1005][1005];
 
void solve(){
    map<pair<int,int>,int> vis;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            mp[i][j]=0;
        }
    }
    int u,d,l,r;
    int nowu,nowd,nowl,nowr;
    u=l=nowl=nowu=1;
    nowr=r=m;
    nowd=d=n;
    for(int i=0;i<s.size();i++){
        if(s[i]=='U'){
            nowu++,nowd++;
        }
        if(s[i]=='D'){
            nowu--,nowd--;
        }
        if(s[i]=='L'){
            nowl++,nowr++;
        }
        if(s[i]=='R'){
            nowl--,nowr--;
        }
        l=max(l,nowl);
        r=min(r,nowr);
        u=max(u,nowu);
        d=min(d,nowd);
    }
    if(l>r||u>d){
        if(k==0) cout<<n*m<<endl;
      else     cout<<0<<endl;
        return;
    }
    int all=(d-u+1)*(r-l+1);
    int ans=0;        int x=0,y=0;
        /*   mp[u][l]++;     
        mp[u][r+1]--;
        mp[d+1][l]--;
        mp[d+1][r+1]++;
        vis[{0,0}]=1;*///要记得一开始那个0,0
    for(int i=0;i<=s.size();i++){
            if(vis[{x,y}]==0){
            vis[{x,y}]=1;
        mp[u-x][l-y]++;     
        mp[u-x][r+1-y]--;
        mp[d+1-x][l-y]--;
        mp[d+1-x][r+1-y]++;
        }
        if(i==s.size()) break;
            if(s[i]=='U'){
            x++;
        }
        if(s[i]=='D'){
            x--;
        }
        if(s[i]=='L'){
            y++;
        }
        if(s[i]=='R'){
            y--;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            mp[i][j]+=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
        /*    cout<<i<<" "<<j<<" "<<mp[i][j]<<endl;*/
            if(mp[i][j]==all-k){
                ans++;
            }
        }
    }
  cout<<ans<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
     cin>>n>>m>>k;
  cin>>s;
  solve();    
    }
    return 0;
}