2022高考集训2

本文主要是介绍2022高考集训2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

大悲

A. 交通

发现如果删掉一条边$x->y$，那么$z->y$一定不能删，也就是说$z->p$一定要删，给边打个标记，对没有标记过的边进行“删除”，将与其“绑定”的边一块标记，最后得到的删除次数能求出答案，$2^{进入标记的次数/2}$

code

#include<cstdio>
#include<cstring>

#define rep(i,a,b,c) for(int i=a;i<=b;c)
#define in(a) scanf("%d",&a)
typedef long long ll;
using namespace std;
const int maxn=300005;
const int mod=998244353;
int n,e[maxn][2];
struct node{
    int r1,r2,c1,c2;
}d[maxn];
bool flag=0;
bool vis[maxn];

ll qpow(int x,int y){
    ll ans=1;
    for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)ans=ans*1ll*x%mod;
    return ans;
}

void dfs(int x){
    vis[x]=1;
    int bz=e[x][1];
    int y=d[bz].r1==x?d[bz].r2:d[bz].r1;
    int t=e[y][0];
    int p=d[t].c1==y?d[t].c2:d[t].c1;
    if(vis[p])return ;
    else dfs(p);
}

int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    in(n);
    rep(i,1,n+n,++i){
        int u,v;in(u);in(v);
        if(d[u].c1)d[u].c2=i;
        else d[u].c1=i;
        if(d[v].r1)d[v].r2=i;
        else d[v].r1=i;
        e[i][0]=u;e[i][1]=v;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        if(!vis[d[i].c1]){
            dfs(d[i].c1),++ans;
        }
        if(!vis[d[i].c2]){
            dfs(d[i].c2),++ans;
        }
    }
    printf("%lld\n",qpow(2,ans/2));
    return 0;
}

$垃圾(bushi)数据生成器$

#include<bits/stdc++.h>
using namespace std;

const int maxn=500005;
int rem[maxn],n,cnt;
int re[maxn];
bool vis[maxn];

int main(){
    // freopen("a.in","w",stdout);
    srand(time(NULL));
    n=5;
    printf("%d\n",n);
    for(int i=1;i<=n;++i){
        rem[i*2]=rem[i*2-1]=i;
        re[i*2]=re[i*2-1]=i;
    }
    for(int i=1;i<=n+n;++i)swap(re[i],re[rand()%(n+n)+1]);
    bool flag=1;
    while(flag){
        flag=0;
        for(int i=1;i<=n+n;++i){
            while(re[i]==rem[i]){
                swap(re[i],re[rand()%(n+n)+1]);
                flag=1;
            }
        }
    }
    for(int i=1;i<=n+n+n+n;++i){
        int x=rand()%(n+n)+1;
        if(vis[x])continue;
        vis[x]=1;
        printf("%d %d\n",rem[x],re[x]);
    }
    for(int i=1;i<=n+n;++i){
        if(!vis[i])printf("%d %d\n",rem[i],re[i]);
    }
}

B. 冒泡排序

一个位置只会操作一次，那么如果$a[i]==i$，无解，因为换走就换不回来了

同理，如果一个数需要向前/后移动，那么它到目标位置之间的操作就必须有严格的先后顺序

这样，我们就可以搞出一个形如$<<>><<><><$的序列，表示操作的先后顺序，如果转成图，就是一个$DAG$上不同的拓扑序的数量

好像很复杂？

但是这个$DAG$拉开是个链

其实还是线性$DP$

$dp[i][j]$表示第$i$个点，在拓扑序$j$的方案数

开始只有一个点，它只能在第一个位置（只有一个位置）

$f[1][1]=1$

考虑$i-1$和$i$的关系

$i-1$先于$i$

$\displaystyle f[i][j]=\sum_{k=1}^{j-1}f[i-1][k]$

$i-1$晚于$i$

$\displaystyle f[i][j]=\sum_{k=j}^{i}f[i-1][k]$

为啥是从$j$开始，而不是$j+1$呢？因为我们把序列拓展了$1$，新的点是插进原序列的

3 $i-1$与$i$没有关系

$\displaystyle f[i][j]=\sum_{k=1}^{i}[k!=j]f[i-1][k]$

就这样。。。

code

#include<cstdio>
#include<cstring>
#include<algorithm>

#define rep(i,a,b,c) for(int i=a;i<=b;c)
#define in(a) scanf("%d",&a)

using namespace std;

typedef long long ll;
const int mod=1e9+7;
const int maxn=5005;

int a[maxn],n,xh[maxn];
int dp[maxn][maxn];

bool check(){
    rep(i,1,n,++i){
        if(a[i]==i)return false;
        if(a[i]<i){
            if(xh[i]==2&&i!=1&&i!=n)return false;
            xh[i]=1;
            rep(j,a[i]+1,i-1,++j)
              if(xh[j]==1&&j!=1&&j!=n)return false;
              else xh[j]=2;
        }
        if(a[i]>i){
            if(xh[i]==1&&i!=1&&i!=n)return false;
            xh[i]=2;
            rep(j,i+1,a[i]-1,++j)
                if(xh[j]==2&&j!=1&&j!=n)return false;
                else xh[j]=1;
        }
    }
    return true;
}
void work(){
    dp[1][1]=1;
    rep(i,2,n-1,++i){ 
        if(xh[i]==1){
            rep(j,1,i,++j)dp[i][j]=(dp[i][j-1]+dp[i-1][j-1])%mod;
        }
        if(xh[i]==2){
            for(int j=i;j>=1;--j)dp[i][j]=(dp[i][j+1]+dp[i-1][j])%mod;
        }
        if(xh[i]==0){
            int su=0;
            rep(j,1,i,++j)su=(su+dp[i-1][j])%mod;
            rep(j,1,i,++j)dp[i][j]=(su-dp[i-1][j]+mod)%mod;
        }
    }
}
int main(){
    freopen("mp.in","r",stdin);
    freopen("mp.out","w",stdout);
    in(n);
    rep(i,1,n,++i)in(a[i]);
    rep(i,1,n,++i)++a[i];
    if(check()){
        work();
        int ans=0;
        rep(i,1,n,++i)ans=(ans+dp[n-1][i])%mod;
       
        printf("%d\n",ans);
    }else printf("0\n"); 
    return 0;
}

C. 矩阵

这种构造操作的题，一定要研究一下大样例，有人模仿样例推出了解法。。。

首先解出前两行和前两列是很简单的

大概这个样子，，，每次清零一个数，不影响已经清零的数

然后我们证明此时的矩阵如果不是全$0$，一定非法

在$3\times 3$的矩形中，绿色减红色=蓝色减黄色

那么从左上角开始取$3\times 3$，可以不停的确定一个位置为$0$

code

#include<cstdio>
#include<cstring>
#include<vector>

#define rep(i,a,b,c) for(int i=a;i<=b;c)
#define in(a) scanf("%lld",&a)
typedef long long ll;
using namespace std;
#define int long long
const int maxn=1005;

ll n,m,mp[maxn][maxn];
vector<int>v[4],vv[4];


bool work(){
    for(int i=m;i>=1;--i){
        v[1].push_back(i);
        vv[1].push_back(-mp[1][i]);
        for(int j=n;j>=1;--j)mp[j][i]-=mp[1][i];
        v[3].push_back(i-2);
        vv[3].push_back(-mp[2][i]);
        ll x=mp[2][i];
        int k=i-2;
        for(int j=max(1ll,1-k);j<=n;++j)if(j+k<=m)mp[j][j+k]-=x;
    }
    rep(i,3,n,++i){
        v[2].push_back(i);
        vv[2].push_back(-mp[i][2]);
        ll x=mp[i][2];
        rep(j,1,m,++j)mp[i][j]-=x;
        v[3].push_back(1-i);
        vv[3].push_back(-mp[i][1]);
        x=mp[i][1];int k=1-i;
        for(int j=max(1ll,1-k);j<=n;++j)if(j+k<=m)mp[j][j+k]-=x;
    }
    rep(i,1,n,++i)
    rep(j,1,m,++j)
    if(mp[i][j]!=0)return false;
    return true;
}
signed main(){
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    in(n);in(m);
    rep(i,1,n,++i)rep(j,1,m,++j)in(mp[i][j]);
    if(n==1){printf("%lld\n",m);rep(i,1,m,++i)printf("2 %lld %lld\n",i,-mp[1][i]);}
    else {
        if(work()){
            printf("%lld\n",(int)(v[1].size()+v[2].size()+v[3].size()));
            int s=v[1].size();
            rep(i,0,s-1,++i)printf("2 %lld %lld\n",v[1][i],vv[1][i]);
            s=v[2].size();
            rep(i,0,s-1,++i)printf("1 %lld %lld\n",v[2][i],vv[2][i]);
            s=v[3].size();
            rep(i,0,s-1,++i)printf("3 %lld %lld\n",v[3][i],vv[3][i]);
        }else printf("-1\n");
    }
    return 0;
}

D. 花瓶

斜率优化，。

奇妙，没有单调性的可以排序确定$DP$顺序强制满足单调性

题解说的很详细了，就是具体实现时候

先按照前缀和排序，然后枚举的是中间点$j$,这样

然后因为斜率算的时候有分母为零的，所以可以移项变成乘法

需要注意的是入队的时候弹出条件必须写等号，至于为啥，留坑待补

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,b,c) for(ll i=a;i<=b;c)
#define in(a) scanf("%lld",&a)
typedef long long ll;
using namespace std;
const int maxn=5005;
ll n,a[maxn],p[maxn],q[maxn],head,tail;
ll f[maxn][maxn],sum[maxn];
bool cmp(int x,int y){return sum[x]<sum[y];}
signed main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    memset(f,-0x80,sizeof(f));
    in(n);
    rep(i,1,n,++i)in(a[i]);
    rep(i,1,n,++i)sum[i]=sum[i-1]+a[i];
    rep(i,0,n,++i)p[i]=i;
    sort(p,p+n+1,cmp);
    rep(i,1,n,++i)f[i][0]=f[i][i]=0;
    rep(i,1,n,++i){
        head=1;tail=0;
        rep(j,0,n,++j){
            if(p[j]>=i)continue;
            while(head<tail&&(f[i][p[j]]-f[i][q[tail]])*(sum[q[tail]]-sum[q[tail-1]])>=(f[i][q[tail]]-f[i][q[tail-1]])*(sum[p[j]]-sum[q[tail]]))--tail;
            q[++tail]=p[j];
        }
        for(int j=n;j>=0;--j){
            if(p[j]<=i)continue;
            while(head<tail&&(f[i][q[head+1]]-f[i][q[head]])>=(sum[p[j]]-sum[i])*(sum[q[head+1]]-sum[q[head]]))++head;
            f[p[j]][i]=max(f[p[j]][i],f[i][q[head]]+1ll*(sum[p[j]]-sum[i])*(sum[i]-sum[q[head]]));
        }
    }
    ll ans=0;
    rep(i,0,n,++i)ans=max(ans,f[n][i]);
    printf("%lld\n",ans);
    return 0;
}

这篇关于2022高考集训2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程