首页 > 其他分享 >NOIP2021 做题笔记

NOIP2021 做题笔记

时间：2024-11-17 17:29:53浏览次数：1  
标签：nxt return int rot2 笔记 mxn NOIP2021 rot

这次又被抓过去写noip2021了\(qaq\)

P7960 [NOIP2021] 报数

可以用类似于质数筛的方法筛一遍，做到 \(\mathcal O(\)值域\()\) 的预处理，以及 \(\mathcal O(1)\) 的查询。


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mxn 10000010
#define mxm 200010
bool vis[mxn];
int nxt[mxn];
inline bool check(int x){
    while(x){
        if(x%10==7)return 1;
        x/=10;
    }
    return 0;
}
void init(){
    for(int i=1;i<=mxn-10;i++){
        if(vis[i])continue;
        if(check(i))
            for(ll j=1;j*i<=mxn-10;j++)
                vis[j*i]=1;
    }
    ll lst=10000001;
    for(int i=mxn-10;i;i--)
        if(!vis[i])nxt[i]=lst,lst=i;
}
void solve(){
    int x;cin>>x;
    if(vis[x])cout<<"-1\n";
    else cout<<nxt[x]<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    int T;cin>>T;while(T--)solve();
    return 0;
}

P7961 [NOIP2021] 数列

这题数据小，考虑使用超大力dp。
设 \(dp[i][j][k][l]\) 为讨论到 \(S\) 的第 \(i\) 位（二进制下），确定了 \(a\) 序列前 \(k\) 个数，\(S\) 前面有 \(k\) 个 \(1\)，且从上一位进位过来的有 \(l\) 位，假设序列上有 \(o\) 个 \(i\)，则有方程：

\[dp[i+1][j+o][k+(o+l)\&1][(o+l)>>1]=dp[i][j][k][l]\times {v_i}^{o}\times C_{n-j}^t \]

暴力转移即可。


#include<bits/stdc++.h>
using namespace std;
#define mxn 40
#define mxm 110
#define ll long long
#define mod 998244353
#define bpop __builtin_popcount
ll n,m,k,c[mxn][mxn],v[mxm];
ll poww[mxm][mxm],dp[mxm][mxn][mxn][mxm];
ll ans;
void init(){
    c[0][0]=1;
    for(int i=1;i<=n;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
    for(int i=0;i<=m;i++){
        poww[i][0]=1;
        for(int j=1;j<=n;j++)
            poww[i][j]=poww[i][j-1]*v[i]%mod;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=0;i<=m;i++)cin>>v[i];
    init();
    //i:讨论到第i位
    //j:确定了前j个数
    //k:前面有k个1
    //l:从上一位进位l个
    //o:给S贡献o个1
    dp[0][0][0][0]=1;
    for(int i=0;i<=m;i++)
        for(int j=0;j<=n;j++)
            for(int kk=0;kk<=k;kk++)
                for(int l=0;l<=n/2;l++)
                    for(int o=0;o<=n-j;o++)
                        dp[i+1][j+o][kk+((l+o)&1)][(l+o)/2]=(   
                        dp[i+1][j+o][kk+((l+o)&1)][(l+o)/2]+
                        dp[i][j][kk][l]*poww[i][o]%mod*c[n-j][o]%mod 
                        )%mod;
    for(int i=0;i<=k;i++)
        for(int j=0;j<=n/2;j++)
            if(i+bpop(j)<=k)
                ans=(ans+dp[m+1][n][i][j])%mod;
    cout<<ans;
}

P7962 [NOIP2021] 方差

什么 \(dp\)？没听说过啊。
考虑到差分数组为单谷函数时方差最小，直接随机化shuffle差分数组搞定！


#include<bits/stdc++.h>
#define ll long long
#define inf 1e15
#define mxn 10100
using namespace std;
ll a[mxn],b[mxn],n;
int main(){
    srand(unsigned(time(0)));
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n; 
    int time=clock();           
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    sort(b+2,b+n+1);
    ll suf=0,sum=0,ans=inf;int mid=(n+1)/2;
    while(1){
        suf=0,sum=0;
        random_shuffle(b+2,b+n+1);
        sort(b+2,b+mid,[](int x,int y){return x>y;}),sort(b+mid+1,b+n+1);
        for(int i=1;i<=n;i++)a[i]=a[i-1]+b[i];
        for(int i=1;i<=n;i++)suf+=n*a[i]*a[i],sum+=a[i];
        ans=min(ans,suf-sum*sum);
        if(clock()-time>=990000)break;
    }
    cout<<ans;
    return 0;
}

P7963 [NOIP2021] 棋局

极其恶心的数据结构题。
首先，对于 \(\rm case\ 1\sim8\)，可以直接暴力。
而对于 \(\rm case\ 9\sim14\)，可以写并查集维护。
接下来来到正解环节。
由于棋子是一个一个加入的，所以连通块是不断分割的，有点难以维护，不妨倒着处理。
我们先写一个并查集，用于维护互通道路组成的连通块，以及直行道路组成的连通块（这里横向和纵向分开处理，原因后面讲）。
这个并查集需要维护连通块的大小，以及块内的编号最大最小值。


struct Dsu{
    int f[mxn],sze[mxn],minn[mxn],maxn[mxn];
    int fu,fv;
    I void init(){
        for(int i=1;i<=n*m;i++)f[i]=minn[i]=maxn[i]=i,sze[i]=1;
    }
    I int fnd(int x){
        return x==f[x]?x:f[x]=fnd(f[x]);
    }
    I void merge(int u,int v,int opt){
        fu=fnd(u),fv=fnd(v);
        if(fu==fv)return;
        if(sze[fu]>sze[fv])swap(fu,fv);
        f[fu]=fv,sze[fv]+=sze[fu];
        maxn[fv]=maxn[fu]>maxn[fv]?maxn[fu]:maxn[fv];
        minn[fv]=minn[fu]<minn[fv]?minn[fu]:minn[fv];
        if(opt)Merge(fu,fv);
    }
}dsu[3];

那吃子怎么办呢？
如果是走互通道路，则对于每一个联通块，可以开一个线段树（当然要动态开点），把连通块周围能吃掉的棋子存进去（要分两个颜色维护），若是黑色棋子，查询能吃到的白色棋子的数量即可。

如果是普通或直行道路，那最多吃四个子，直接判断就行了。

当合并连通块时，可以将两个联通块的线段树也合并进去。

这里可以按照加入棋子的顺序离散化每个棋子的等级，使每个棋子的等级不同。


//就像这样
struct Chess{
    int lvl,col,x,y,id;
}ch[mxn],ch2[mxn];
void solve(){
    sort(ch2+1,ch2+q+1,[](Chess a,Chess b){return a.lvl==b.lvl?a.id<b.id:a.lvl<b.lvl;});
    for(int i=1;i<=q;i++)ch[ch2[i].id]=ch2[i],ch[ch2[i].id].lvl=i;
}

线段树：


struct Seg{
    int ls[mxm],rs[mxm],cnt,rt[mxn<<1],sum[mxm];
    I void init(){
        memset(rt,0,sizeof(rt));
        for(int i=1;i<=cnt;i++)ls[i]=rs[i]=sum[i]=0;
        cnt=0;
    }
    I void push_up(int rot){
        sum[rot]=sum[ls[rot]]+sum[rs[rot]];
    }
    I int insert(int rot,int l,int r,int x){//单点插入
        if(!rot)rot=++cnt;//动态开店
        if(l==r){
            if(!sum[rot])sum[rot]++;
            return rot;
        }
        int mid=(l+r)>>1;
        if(mid>=x)ls[rot]=insert(ls[rot],l,mid,x);
        else rs[rot]=insert(rs[rot],mid+1,r,x);
        push_up(rot);
        return sum[rot]?rot:0;
    }
    I int remove(int rot,int l,int r,int x){//单点删除
        if(!rot)rot=++cnt;
        if(l==r)return 0;
        int mid=(l+r)>>1;
        if(mid>=x)ls[rot]=remove(ls[rot],l,mid,x);
        else rs[rot]=remove(rs[rot],mid+1,r,x);
        push_up(rot);
        return sum[rot]?rot:0;
    }
    I int merge(int rot1,int rot2,int l,int r){//线段树合并
        if(!rot1||!sum[rot1])return rot2;
        if(!rot2||!sum[rot2])return rot1;
        if(l==r){
            sum[rot2]=min(sum[rot1]+sum[rot2],1);
            return rot2;
        }
        int mid=(l+r)>>1;
        ls[rot2]=merge(ls[rot1],ls[rot2],l,mid);
        rs[rot2]=merge(rs[rot1],rs[rot2],mid+1,r);
        push_up(rot2);
        return rot2;
    }
    I int query(int rot,int l,int r,int x,int y,int opt=0){//区间求和
        if(!rot||y<l||x>r)return 0;
        if(l>=x&&r<=y)return sum[rot];
        int mid=(l+r)>>1,ret=0;
        if(x<=mid)ret+=query(ls[rot],l,mid,x,y,opt);
        if(y>mid)ret+=query(rs[rot],mid+1,r,x,y,opt);
        return ret;
    }
}Scol[2];

但是这样还不够，因为有可能一个点可以同时从直行道路和互通道路走到。所以要去重。

考虑同一行/列的点是连续的，所以可以按两种方式编号（就是之前讲的横向纵向分开处理），再插到线段树里，去重的时候直接区间查询就行了。

首先是预处理环节：


for(int i=1;i<=q;i++)vis[get1(ch[i].x,ch[i].y)]=i;
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        int id=get1(i,j),nxt;
        if(vis[id])continue;//如果这个点上有棋子直接跳过
        for(int k=1;k<=4;k++){
            int fx=i+dir[k][0],fy=j+dir[k][1];
            if(fx<1||fy<1||fx>n||fy>m)continue;
            nxt=get1(fx,fy);
            if(vis[nxt])continue;
            if(edge[id][k]==2)dsu[k%2+1].merge(id,nxt,0);//如果为直行道路，分行/列放到并查集里
            if(edge[id][k]==3)dsu[0].merge(id,nxt,0);//如果为互通道路
        }
    }
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        int id1=get1(i,j),id2=get2(i,j),id=dsu[0].fnd(id1),nxt,col;//按两种方式编号
        Sdir[0].rt[id]=Sdir[0].insert(Sdir[0].rt[id],1,n*m,id1);//分别插进两个线段树里
        Sdir[1].rt[id]=Sdir[1].insert(Sdir[1].rt[id],1,n*m,id2);
        for(int k=1;k<=4;k++){
            int fx=i+dir[k][0],fy=j+dir[k][1];
            if(edge[id1][k]!=3||fx<1||fy<1||fx>n||fy>m)continue;
            nxt=get1(fx,fy);//如果是互通道路
            if(!vis[nxt])continue;
            col=ch[vis[nxt]].col;//按颜色，将每个棋子的等级插进去
            Scol[col].rt[id]=Scol[col].insert(Scol[col].rt[id],1,q,ch[vis[nxt]].lvl);
        }
    }

接下来，首先是计算互通道路的贡献：


for(int j=1;j<=4;j++){
    if(edge[id][j]!=3)continue;
    fx=X+dir[j][0],fy=Y+dir[j][1];
    if(fx<1||fy<1||fx>n||fy>m)continue;
    nxt=dsu[0].fnd(get1(fx,fy));
    Scol[col].remove(Scol[col].rt[nxt],1,q,ch[i].lvl);
    //之后这个棋子就不在了，不能被吃掉，所以要移除
}
for(int j=1;j<=4;j++){
    if(edge[id][j]!=3)continue;
    fx=X+dir[j][0],fy=Y+dir[j][1];
    if(fx<1||fy<1||fx>n||fy>m)continue;
    nxt=get1(fx,fy);
    if(vis[nxt]&&vis[nxt]<i)continue;
    dsu[0].merge(id,nxt,1);
    //将这个棋子合并进周围的连通块里
}
fid1=dsu[0].fnd(id);
ans[i]+=dsu[0].sze[fid1]-1;//-1是因为去掉棋子所在点的贡献
ans[i]+=Scol[!col].query(Scol[!col].rt[fid1],1,q,1,ch[i].lvl,i==4?1:0);//能吃的棋子数

然后是直行道路：


for(int j=1;j<=4;j++){
    if(edge[id][j]!=2)continue;
    fx=X+dir[j][0],fy=Y+dir[j][1];
    if(fx<1||fy<1||fx>n||fy>m)continue;
    nxt=get1(fx,fy);
    if(vis[nxt]&&vis[nxt]<i)continue;
    dsu[j%2+1].merge(id,nxt,0);//横向/纵向的合并
}
fid2=dsu[2].fnd(id);
int maxn,minn;
maxn=dsu[2].maxn[fid2],minn=dsu[2].minn[fid2];
ans[i]+=maxn-minn+1;//先算横向的贡献
ans[i]-=Sdir[0].query(Sdir[0].rt[fid1],1,n*m,minn,maxn);//去重，将minn~maxn范围内互通道路能走到的点的数量去掉
if(edge[minn][1]==2&&eat(i,vis[minn-1])&&Scol[!col].query(Scol[!col].rt[fid1],1,q,ch[vis[minn-1]].lvl,ch[vis[minn-1]].lvl)==0)ans[i]++;
if(edge[maxn][3]==2&&eat(i,vis[maxn+1])&&Scol[!col].query(Scol[!col].rt[fid1],1,q,ch[vis[maxn+1]].lvl,ch[vis[maxn+1]].lvl)==0)ans[i]++;
//计算吃子数，注意这里计算时要看这个子能不能从互通道路走过去吃掉
fid2=dsu[1].fnd(id);
maxn=dsu[1].maxn[fid2],minn=dsu[1].minn[fid2];
ans[i]+=(maxn-minn)/m+1;//纵向同理
if(edge[minn][2]==2&&eat(i,vis[minn-m])&&Scol[!col].query(Scol[!col].rt[fid1],1,q,ch[vis[minn-m]].lvl,ch[vis[minn-m]].lvl)==0)ans[i]++;
if(edge[maxn][4]==2&&eat(i,vis[maxn+m])&&Scol[!col].query(Scol[!col].rt[fid1],1,q,ch[vis[maxn+m]].lvl,ch[vis[maxn+m]].lvl)==0)ans[i]++;
fx=getx(maxn),fy=gety(maxn),maxn=get2(fx,fy);
fx=getx(minn),fy=gety(minn),minn=get2(fx,fy);
ans[i]-=Sdir[1].query(Sdir[1].rt[fid1],1,n*m,minn,maxn);

最后是普通道路：


for(int j=1;j<=4;j++){
    if(edge[id][j]!=1)continue;
    fx=X+dir[j][0],fy=Y+dir[j][1];
    if(fx<1||fy<1||fx>n||fy>m)continue;
    nxt=get1(fx,fy);
    if(vis[nxt]&&vis[nxt]<i){
        if(eat(i,vis[nxt])&&Scol[!col].query(Scol[!col].rt[fid1],1,q,ch[vis[nxt]].lvl,ch[vis[nxt]].lvl)==0)ans[i]++;
    }//这里计算时要看这个子能不能从互通道路走过去吃掉
    else if(dsu[0].fnd(id)!=dsu[0].fnd(nxt))ans[i]++;//如果是在一个块里，说明互通道路可以走到，不计算
}

最后的最后，献上完整代码：


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mxn 200010
#define mxm 5000010
#define I inline
int n,m,q,edge[mxn][5],vis[mxn],ans[mxn];
int dir[5][2]={{0,0},{0,-1},{-1,0},{0,1},{1,0}};
char str[mxn];
I int get1(int x,int y){return (x-1)*m+y;}
I int get2(int x,int y){return (y-1)*n+x;}
I int getx(int x){return (x-1)/m+1;}
I int gety(int x){return (x-1)%m+1;}
I void Merge(int u,int v);
struct Chess{
    int lvl,col,x,y,id;
}ch[mxn],ch2[mxn];
struct Dsu{
    int f[mxn],sze[mxn],minn[mxn],maxn[mxn];
    int fu,fv;
    I void init(){
        for(int i=1;i<=n*m;i++)f[i]=minn[i]=maxn[i]=i,sze[i]=1;
    }
    I int fnd(int x){
        return x==f[x]?x:f[x]=fnd(f[x]);
    }
    I void merge(int u,int v,int opt){
        fu=fnd(u),fv=fnd(v);
        if(fu==fv)return;
        if(sze[fu]>sze[fv])swap(fu,fv);
        f[fu]=fv,sze[fv]+=sze[fu];
        maxn[fv]=maxn[fu]>maxn[fv]?maxn[fu]:maxn[fv];
        minn[fv]=minn[fu]<minn[fv]?minn[fu]:minn[fv];
        if(opt)Merge(fu,fv);
    }
}dsu[3];
struct Seg{
    int ls[mxm],rs[mxm],cnt,rt[mxn<<1],sum[mxm];
    I void init(){
        memset(rt,0,sizeof(rt));
        for(int i=1;i<=cnt;i++)ls[i]=rs[i]=sum[i]=0;
        cnt=0;
    }
    I void push_up(int rot){
        sum[rot]=sum[ls[rot]]+sum[rs[rot]];
    }
    I int insert(int rot,int l,int r,int x){
        if(!rot)rot=++cnt;
        if(l==r){
            if(!sum[rot])sum[rot]++;
            return rot;
        }
        int mid=(l+r)>>1;
        if(mid>=x)ls[rot]=insert(ls[rot],l,mid,x);
        else rs[rot]=insert(rs[rot],mid+1,r,x);
        push_up(rot);
        return sum[rot]?rot:0;
    }
    I int remove(int rot,int l,int r,int x){
        if(!rot)rot=++cnt;
        if(l==r)return 0;
        int mid=(l+r)>>1;
        if(mid>=x)ls[rot]=remove(ls[rot],l,mid,x);
        else rs[rot]=remove(rs[rot],mid+1,r,x);
        push_up(rot);
        return sum[rot]?rot:0;
    }
    I int merge(int rot1,int rot2,int l,int r){
        if(!rot1||!sum[rot1])return rot2;
        if(!rot2||!sum[rot2])return rot1;
        if(l==r){
            sum[rot2]=min(sum[rot1]+sum[rot2],1);
            return rot2;
        }
        int mid=(l+r)>>1;
        ls[rot2]=merge(ls[rot1],ls[rot2],l,mid);
        rs[rot2]=merge(rs[rot1],rs[rot2],mid+1,r);
        push_up(rot2);
        return rot2;
    }
    I int query(int rot,int l,int r,int x,int y,int opt=0){
        if(!rot||y<l||x>r)return 0;
        if(l>=x&&r<=y)return sum[rot];
        int mid=(l+r)>>1,ret=0;
        if(x<=mid)ret+=query(ls[rot],l,mid,x,y,opt);
        if(y>mid)ret+=query(rs[rot],mid+1,r,x,y,opt);
        return ret;
    }
}Scol[2],Sdir[2];
I void init(){
    memset(edge,0,sizeof(edge));
    memset(ans,0,sizeof(ans));
    memset(vis,0,sizeof(vis));
    dsu[0].init(),dsu[1].init(),dsu[2].init();
    Scol[0].init(),Scol[1].init();
    Sdir[0].init(),Sdir[1].init();
}
I void Merge(int u,int v){
    Scol[0].rt[v]=Scol[0].merge(Scol[0].rt[u],Scol[0].rt[v],1,q);
    Scol[1].rt[v]=Scol[1].merge(Scol[1].rt[u],Scol[1].rt[v],1,q);
    Sdir[0].rt[v]=Sdir[0].merge(Sdir[0].rt[u],Sdir[0].rt[v],1,n*m);
    Sdir[1].rt[v]=Sdir[1].merge(Sdir[1].rt[u],Sdir[1].rt[v],1,n*m);
}
I bool eat(int x,int y){
    return ch[x].col!=ch[y].col&&ch[x].lvl>ch[y].lvl;
}
I void solve(){
    cin>>n>>m>>q;
    init();
    for(int i=1;i<=n;i++){
        cin>>str+1;
        for(int j=1;j<m;j++){
            edge[get1(i,j+1)][1]=str[j]-'0';
            edge[get1(i,j)][3]=str[j]-'0';
        }
    }
    for(int i=1;i<n;i++){
        cin>>str+1;
        for(int j=1;j<=m;j++){
            edge[get1(i,j)][4]=str[j]-'0';
            edge[get1(i+1,j)][2]=str[j]-'0';
        }
    }
    for(int i=1;i<=q;i++)
        cin>>ch[i].col>>ch[i].lvl>>ch[i].x>>ch[i].y,ch[i].id=i,ch2[i]=ch[i];
    sort(ch2+1,ch2+q+1,[](Chess a,Chess b){return a.lvl==b.lvl?a.id<b.id:a.lvl<b.lvl;});
    for(int i=1;i<=q;i++)ch[ch2[i].id]=ch2[i],ch[ch2[i].id].lvl=i;
    for(int i=1;i<=q;i++)vis[get1(ch[i].x,ch[i].y)]=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int id=get1(i,j),nxt;
            if(vis[id])continue;
            for(int k=1;k<=4;k++){
                int fx=i+dir[k][0],fy=j+dir[k][1];
                if(fx<1||fy<1||fx>n||fy>m)continue;
                nxt=get1(fx,fy);
                if(vis[nxt])continue;
                if(edge[id][k]==2)
                    dsu[k%2+1].merge(id,nxt,0);
                if(edge[id][k]==3)dsu[0].merge(id,nxt,0);
            }
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int id1=get1(i,j),id2=get2(i,j),id=dsu[0].fnd(id1),nxt,col;
            Sdir[0].rt[id]=Sdir[0].insert(Sdir[0].rt[id],1,n*m,id1);
            Sdir[1].rt[id]=Sdir[1].insert(Sdir[1].rt[id],1,n*m,id2);
            for(int k=1;k<=4;k++){
                int fx=i+dir[k][0],fy=j+dir[k][1];
                if(edge[id1][k]!=3||fx<1||fy<1||fx>n||fy>m)continue;
                nxt=get1(fx,fy);
                if(!vis[nxt])continue;
                col=ch[vis[nxt]].col;
                Scol[col].rt[id]=Scol[col].insert(Scol[col].rt[id],1,q,ch[vis[nxt]].lvl);
            }
        }
    for(int i=q;i;i--){
        int fx,fy,nxt,id=get1(ch[i].x,ch[i].y),col=ch[i].col,X=ch[i].x,Y=ch[i].y;
        int fid1,fid2;

        for(int j=1;j<=4;j++){
            if(edge[id][j]!=3)continue;
            fx=X+dir[j][0],fy=Y+dir[j][1];
            if(fx<1||fy<1||fx>n||fy>m)continue;
            nxt=dsu[0].fnd(get1(fx,fy));
            Scol[col].remove(Scol[col].rt[nxt],1,q,ch[i].lvl);
        }
        for(int j=1;j<=4;j++){
            if(edge[id][j]!=3)continue;
            fx=X+dir[j][0],fy=Y+dir[j][1];
            if(fx<1||fy<1||fx>n||fy>m)continue;
            nxt=get1(fx,fy);
            if(vis[nxt]&&vis[nxt]<i)continue;
            dsu[0].merge(id,nxt,1);
        }
        fid1=dsu[0].fnd(id);
        ans[i]+=dsu[0].sze[fid1]-1;
        ans[i]+=Scol[!col].query(Scol[!col].rt[fid1],1,q,1,ch[i].lvl,i==4?1:0);

        for(int j=1;j<=4;j++){
            if(edge[id][j]!=2)continue;
            fx=X+dir[j][0],fy=Y+dir[j][1];
            if(fx<1||fy<1||fx>n||fy>m)continue;
            nxt=get1(fx,fy);
            if(vis[nxt]&&vis[nxt]<i)continue;
            dsu[j%2+1].merge(id,nxt,0);
        }
        fid2=dsu[2].fnd(id);
        int maxn,minn;
        maxn=dsu[2].maxn[fid2],minn=dsu[2].minn[fid2];
        ans[i]+=maxn-minn+1;
        ans[i]-=Sdir[0].query(Sdir[0].rt[fid1],1,n*m,minn,maxn);
        if(edge[minn][1]==2&&eat(i,vis[minn-1])&&Scol[!col].query(Scol[!col].rt[fid1],1,q,ch[vis[minn-1]].lvl,ch[vis[minn-1]].lvl)==0)ans[i]++;
        if(edge[maxn][3]==2&&eat(i,vis[maxn+1])&&Scol[!col].query(Scol[!col].rt[fid1],1,q,ch[vis[maxn+1]].lvl,ch[vis[maxn+1]].lvl)==0)ans[i]++;
        fid2=dsu[1].fnd(id);
        maxn=dsu[1].maxn[fid2],minn=dsu[1].minn[fid2];
        ans[i]+=(maxn-minn)/m+1;
        if(edge[minn][2]==2&&eat(i,vis[minn-m])&&Scol[!col].query(Scol[!col].rt[fid1],1,q,ch[vis[minn-m]].lvl,ch[vis[minn-m]].lvl)==0)ans[i]++;
        if(edge[maxn][4]==2&&eat(i,vis[maxn+m])&&Scol[!col].query(Scol[!col].rt[fid1],1,q,ch[vis[maxn+m]].lvl,ch[vis[maxn+m]].lvl)==0)ans[i]++;
        fx=getx(maxn),fy=gety(maxn),maxn=get2(fx,fy);
        fx=getx(minn),fy=gety(minn),minn=get2(fx,fy);
        ans[i]-=Sdir[1].query(Sdir[1].rt[fid1],1,n*m,minn,maxn);

        for(int j=1;j<=4;j++){
            if(edge[id][j]!=1)continue;
            fx=X+dir[j][0],fy=Y+dir[j][1];
            if(fx<1||fy<1||fx>n||fy>m)continue;
            nxt=get1(fx,fy);
            if(vis[nxt]&&vis[nxt]<i){
                if(eat(i,vis[nxt])&&Scol[!col].query(Scol[!col].rt[fid1],1,q,ch[vis[nxt]].lvl,ch[vis[nxt]].lvl)==0)ans[i]++;
            }
            else if(dsu[0].fnd(id)!=dsu[0].fnd(nxt))ans[i]++;
        }
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;cin>>T;while(T--)solve();
    return 0;
}

标签：nxt,return,int,rot2,笔记,mxn,NOIP2021,rot
From： https://www.cnblogs.com/nagato--yuki/p/18543033

相关文章

  • GObject学习笔记（一）类和实例
    前言最近阅读Aravis源码，其中大量运用了GObject，于是打算学习一下。此系列笔记仅主要面向初学者，不会很深入探讨源码的细节，专注于介绍GObject的基本用法。此系列笔记参考GObjectTutorialforbeginners本文可在个人博客中阅读，体验更加套个盾：文中定义的名词只是为了更好地理解GO......
  • python学习笔记1
    *args:不定长参数，特点：可以接受[0.+无穷大）的实参print(*values,sep='',end='\n',file=sys.stdout,flush=False)values:会将实参转换成字符串，再输出sep:输出多个对象时用什么间隔，默认为一个空格字符，若要改变其他方式间隔，则需要关键词参数。end:用什么结尾，默认为换行‘\n’......
  • 计算机网络技术02141考试笔记【第三章考试重点笔记】
    第三章 网络协议和体系结构【重点】第一节 网络协议和体系结构概述一、网络协议的概念    为了保证通信正常进行，必须事先做一些规定，而且通信双方要正确执行这些规定。同时，只有通信双方在这些规定上达成一致，彼此才能够互相“理解”，从而确保通信的正常进行。这种通信......
  • 从零开始的 LLM: nanoGPT 学习笔记（2/2）
    上篇：从零开始的LLM:nanoGPT学习笔记（1/2）尝试了完整的训练的过程，nanoGPT仓库中还有复现GPT2的代码，可惜对计算资源要求太高（基于OpenWebText数据集，8卡A100，训练4天），不是个人电脑玩的转了，只能跳过这一步，尝试后面的finetuning。finetuning1.训练数据跟pre-train一样......
  • 小米笔记本Pro15锐龙版(R7 5800H/15G RAM/512G SSD)拆机单固态硬盘SSD扩容，无损迁移Win
    1.准备工作1.1梅花头螺丝刀2.72米 1.2新的固态硬盘三星980nvmem2固态硬盘，官方说读取速度能到3.5G，实测能到3.3G。小米笔记本Pro15锐龙版的M.2插槽支持的是PCIE3.0,三星980支持的就是PCIE3.0,够用了。三星980Pro支持的是PCIE4.0，读取能到7G，但接口不支持，只能降到PCIE......
  • 笔记
    简介《C++Primer中文版（第5版）》学习仓库，包括笔记和课后练习答案。环境System:Ubuntu16.04IDE:VSCodeCompiler:g++熟悉编译器g++:编译：g++--std=c++11ch01.cpp-omain运行：./prog1查看运行状态：echo$?编译多个文件：g++ch2.cppSales_item.cc-omain输入g++......
  • YOLOv7-0.1部分代码阅读笔记-torch_utils.py
    torch_utils.pyutils\torch_utils.py目录torch_utils.py1.所需的库和模块2.deftorch_distributed_zero_first(local_rank:int): 3.definit_torch_seeds(seed=0): 4.defdate_modified(path=__file__): 5.defgit_describe(path=Path(__file__).parent): 6.def......
  • 【C++笔记】一维数组元素处理
    目录1.插入元素方法代码2.删除元素方法代码3.交换元素方法代码1.插入元素方法概念：插入元素是指在数组的某个位置添加一个新元素，并将原来的元素向后移动。例如，将5插入到数组[1,2,4,6]的第二个位置，结果变为[1,5,2,4,6]。关键点：确定插入位置：首先要明......
  • 从零开始的 LLM: nanoGPT 学习笔记（1/2）
    项目地址：nanoGPT作者是OpenAI的元老人物AndrejKarpathy，以非常通俗易懂的方式将LLM的pre-train娓娓道来，YouTube上也有对应的视频：Let'sbuildGPT:fromscratch,incode,spelledout.其中高赞回复是这样的，总结非常精辟：justforfun,droppingonYouTubethebesti......
  • 线性回归学习笔记
    线性回归概述线性回归是一种基本的监督学习算法，用于解决回归问题。它通过拟合数据点，找出特征与目标变量之间的线性关系。其目标是预测连续数值输出。模型公式线性回归模型的数学表达式为：\[y=\mathbf{w}^\top\mathbf{x}+b\]或展开为：\[y=w_1x_1+w_2x_2+\cdot......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99