NOIP游寄

KiDDOwithTopTree · 2022-11-25 21:26:05 · 个人记录

某种意义来说，玩的开心即为 AK。热烈庆祝 CHiCO 阿克 NOIP！

开考前一周，我给学弟讲离线扫描线。

提前三天入佛隔离。

在佛山复习了 tarjan 和笛卡尔树。同宿的老炮一直和我讲 dp 和计数思路。

比赛队里有一个初三的，一问发现比我大 20 天。

不得不说玩的很开心。

这次比赛有幸毫无遗憾。

这次比赛允许带水：感天动地。

密码：biu#2019miss，solo@2022（应该吧，我不太记得了。

开看题：T1 不会；T2 不会；T3 不会；T4 不会；

首先胡乱到处想：T1 不会计数；T2 不会思维；T3 不会计数；T4 不会计数。

浅想一手：

T3 有链的分，有树的分，很明显 tarjan 把环缩了做树形 dp。正好复习了，可是不会计数。

T4 一看就是数据结构。min/max 感觉像笛卡尔树，数据随机相当于笛卡尔树树高 log。但是在线确实想不出来，又没有强制在线，那就离线吧！但思维确实跟不上，不会计数，寄！

虽然非常不情愿，但是只能想 T2 了。

k=2n-2 很有意思，一看就是放两层，最后一个用来消除。（但是只有15 pts。

想了一会怎么找到，结果发现不好分配位置和查找在第几层。强行抑制住打平衡树的冲动，冷静一会发现可以 stack 分配位置，桶查找。

打完跑去 T1，对着一堆求和弄了半天，发现可以前缀和优化一下。最开始是正序循环，结果代码越打越乱，跑去想 T2。

发现 k=2n-1 也可以套一套之前的想法，并且发现之前想法的 bug，稍稍改了改。

跑去看 T4，发现可能可以用单调栈代替一手，思考半天完全想不出来，n^2 个区间让我怎么理智！打个 8pts 暴力跑路。

在看 T1，换成倒序循环，结果代码简单多了，心情瞬间舒畅。

测大样例，看着那个 114 514 想骂人：谁大数据给那么水的东西啊。

回去 T2，发现可以把多出来的颜色待定，先考虑后面的，根据后面的卡牌决定这个卡牌的位置。

从上面消除的肯定不能放。
如果从下面消除的，可以把它放在上面，这样高度还是 2 层。
如果有一列直接消没了，那么可以大胆放在空列里，让新消的变成空列。
其他照常。

但是这有一个问题：有可能全部都是消上层，最后只能放在空列，变成 n 个 1 层。这样可能就无解了。感觉自己的做法寄了。（后面想了想发现没寄：最后总有一个多出来的颜色，消上面的不用管，消下面的就让前面的放置第 2 层避开就行了。估计就这一个问题，差点想出来……

bug 有点小多，改到心理崩溃。

后面就是测大样例，不给 spj 我测个毛线啊！

随意构造几组数据，貌似都是对的。

然后想 T3：n=8,m=10 应该是状压分，但是脑子抽了以为 2^8 是 10^6，痛失暴力分。（其实也不算痛失，我也不熟状压。

最后写了个随机数输出，用于碰彩票。

后面想 T4，一脸懵逼地等到考试结束。

难得一次复习的东西都考了，猜知识点很对，但不完全对。（笑

人均切 T2 T3，完全不明白好吧。

心疼 BOBO，初中两次摸到 NOIP 一等线，这次却失手了。

回来还要在家隔离，还有重要考试要考。。。能不能退钱？（貌似没钱可退

期望得分：100+15+0+8=123

放出代码，看看有没有刺可以挑挑：

T1：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e3+10,mod=998244353;
int a[N][N],b[N][N],c[N][N];
long long d[N][N],e[N][N];
string s;
int main(){
    freopen("plant.in","r",stdin);
    freopen("plant.out","w",stdout);
    int t,id;cin>>t>>id;
    while(t--){
        int n,m,k,l;cin>>n>>m>>k>>l;
        for(int i=1;i<=n;i++){
            cin>>s;
            for(int j=1;j<=m;j++)
                a[i][j]=s[j-1]-'0';
        }
        for(int i=1;i<=n;i++){
            for(int j=m;j>=1;j--){
                if(a[i][j]) continue;
                b[i][j]=b[i][j+1]+1;
            }
        }
        for(int j=1;j<=m;j++){
            for(int i=n;i>=1;i--){
                if(a[i][j]) continue;
                c[i][j]=c[i+1][j]+1;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(b[i][j]) b[i][j]--;
                if(c[i][j]) c[i][j]--;
            }
        }
        for(int j=1;j<=m;j++){
            for(int i=n;i>=1;i--){
                if(a[i][j]||c[i][j]<=1) continue;
                d[i][j]=(d[i+1][j]+b[i+2][j])%mod;
                if(c[i][j]<=2) continue;
                e[i][j]=(e[i+1][j]+b[i+2][j]*(c[i][j]-2)%mod)%mod;
            }
        }
        long long a1=0,a2=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(a[i][j]) continue;
                a1=(a1+b[i][j]*d[i][j]%mod)%mod;
                a2=(a2+b[i][j]*e[i][j]%mod)%mod;
            }
        cout<<k*a1<<' '<<l*a2<<'\n';
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a[i][j]=b[i][j]=c[i][j]=d[i][j]=e[i][j]=0;
    }
}
/*
1 0
4 3 1 1
001
010
000
000
*/

T2：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2e6+10;
struct node{
    int opt,s1,s2;
};
node ans[2*N];
int a[N],b[3][N],c[N],d[3][N];
int sta[2*N],top,cnt;
int n,m,k,num;
inline int chk(int x){
    if(b[1][x]) return 1;
    else if(b[2][x]) return 2;
    else return 0;
}
inline int fnd(int opt,int x){
    return b[opt][x];
}
int work(int p){
    int now=++cnt;
    for(int i=p+1;i<=m;i++){
        int opt=chk(a[i]),pos;
        if(opt) pos=fnd(opt,a[i]);
        if(a[i]==a[p]){
            ans[now].opt=1,ans[now].s1=num;
            cnt++;ans[cnt].opt=1,ans[cnt].s1=num;
            return i;
        }
        else if(opt==2&&c[pos]==1){
            ans[now].opt=1,ans[now].s1=num;
            sta[++top]=pos,c[pos]--;
            b[2][a[i]]=0,d[2][pos]=0;
            cnt++;ans[cnt].opt=1,ans[cnt].s1=pos;
            num=pos;
            return i;
        }
        else if(opt==1){
            sta[++top]=pos,c[pos]--;
            b[1][a[i]]=0,d[1][pos]=0;
            cnt++;ans[cnt].opt=1,ans[cnt].s1=pos;
        }
        else if(opt==2){
            sta[++top]=pos;
            b[2][a[i]]=0,d[2][pos]=d[1][pos];
            d[1][pos]=a[p],b[1][d[2][pos]]=0;
            b[2][d[2][pos]]=pos;
            b[1][a[p]]=pos;
            ans[now].opt=1,ans[now].s1=pos;
            cnt++;ans[cnt].opt=1,ans[cnt].s1=num;
            cnt++;ans[cnt].opt=2,ans[cnt].s1=pos,ans[cnt].s2=num;
            return i;
        }
        else{
            pos=sta[top--],c[pos]++;
            b[2-c[pos]+1][a[i]]=pos;
            d[2-c[pos]+1][pos]=a[i];
            cnt++;ans[cnt].opt=1,ans[cnt].s1=pos;
        }
    }
    return m;
}
int main(){
    freopen("meow.in","r",stdin);
    freopen("meow.out","w",stdout);
    int t;cin>>t;
    while(t--){
        cin>>n>>m>>k;num=n;
        for(int i=n-1;i>=1;i--)
            sta[++top]=i,sta[++top]=i;
        for(int i=1;i<=m;i++) cin>>a[i];
        for(int i=1;i<=m;i++){
            int opt=chk(a[i]),pos;
            if(opt) pos=fnd(opt,a[i]);
            if(opt==1){
                sta[++top]=pos,c[pos]--;
                b[1][a[i]]=0,d[1][pos]=0;
                cnt++;ans[cnt].opt=1,ans[cnt].s1=pos;
            }
            else if(opt==2&&c[pos]==1){
                sta[++top]=pos,c[pos]--;
                b[2][a[i]]=0,d[2][pos]=0;
                cnt++;ans[cnt].opt=1,ans[cnt].s1=pos;
            }
            else if(opt==2){
                sta[++top]=pos,c[pos]--;
                b[2][a[i]]=0,d[2][pos]=d[1][pos];
                d[1][pos]=0,b[1][d[2][pos]]=0;
                b[2][d[2][pos]]=pos;
                cnt++;ans[cnt].opt=1,ans[cnt].s1=num;
                cnt++;ans[cnt].opt=2,ans[cnt].s1=pos,ans[cnt].s2=num;
            }
            else if(top){
                pos=sta[top--],c[pos]++;
                b[2-c[pos]+1][a[i]]=pos;
                d[2-c[pos]+1][pos]=a[i];
                cnt++;ans[cnt].opt=1,ans[cnt].s1=pos;
            }
            else i=work(i);
        }
        cout<<cnt<<'\n';
        for(int i=1;i<=cnt;i++)
            if(ans[i].opt==1)
                cout<<ans[i].opt<<' '<<ans[i].s1<<'\n';
            else cout<<ans[i].opt<<' '<<ans[i].s1<<' '<<ans[i].s2<<'\n';
        top=cnt=0;
        for(int i=1;i<=m;i++)
            a[i]=0;
        for(int i=1;i<=n;i++)
            c[i]=d[1][i]=d[2][i]=0;
        for(int i=1;i<=k;i++)
            b[1][i]=b[2][i]=0;
    }
}
/*
2
3 10 5
1 2 3 4 5 2 3 4 5 1
2 4 2
1 2 1 2
*/

T3：

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int N=1e9+7;
int main(){
    freopen("barrack.in","r",stdin);
    freopen("barrack.out","w",stdout);
    cout<<rand()%N<<'\n';
}

T4：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int a[N],b[N],l[2][N],r[2][N];
int main(){
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    int t,n,qq;cin>>t>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    cin>>qq;
    for(int i=1;i<=qq;i++){
        int ll,rr,ans=0;cin>>ll>>rr;
        for(int p=ll;p<=rr;p++){
            int m1=a[p],m2=b[p];
            for(int q=p;q<=rr;q++){
                m1=max(m1,a[q]),m2=max(m2,b[q]);
                ans+=m1*m2;
            }
        }
        cout<<ans<<'\n';
    }
}
/*
0 2
2 1
1 2
1
1 2
*/

希望能混奖吧。。。