[游记]2022高考集训2-2022.6.6

爆零了，开心快乐

先写教训：

T1 推出来性质了，写伪了（考试结束前半个小时和Sakura大佬厕所偶遇交流了一下：T1不就是判个环么

然后判了重边

T2 暴力模拟写挂了，swap用错送走40pts

T3 为什么SPJ把我的卡掉了啊？？？40分扔掉

T4 推出了普通动规，然后以为自己交了，开始写斜率优化

然后？就没有然后了，考试就结束了，丢掉50分

总共挂分130分+

算了，终究还是自己太弱了

A. 交通

B. 冒泡排序

C. 矩阵

D. 花瓶

 

 就直接写考后了

A. 交通

这多么像是一道二分图……

#include
#include
#include<string>
#define WR WinterRain
#define int long long
#define Traffic signed
using namespace std;
const int WR=1001000,mod=998244353;
struct Edge{
    int pre,to;
}edge[WR];
int n,ans;
int ipt[WR][3],opt[WR][3];
int fa[WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
int quick_pow(int a,int b){
    int base=a,res=1;
    while(b){
        if(b&1) res=res*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return res;
}
int getfa(int x){
    if(x==fa[x]) return x;
    return fa[x]=getfa(fa[x]);
}
Traffic main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    n=read();
    for(int i=1;i<=n*2;i++) fa[i]=i;
    for(int i=1;i<=n*2;i++){
        int u=read(),v=read();
        opt[u][++opt[u][0]]=i;
        ipt[v][++ipt[v][0]]=i;
    }
    for(int i=1;i<=n;i++){
        int u=ipt[i][1],v=ipt[i][2];
        int fu=getfa(u),fv=getfa(v);
        fa[fv]=fu;
        u=opt[i][1],v=opt[i][2];
        fu=getfa(u),fv=getfa(v);
        fa[fv]=fu;
    }
    for(int i=1;i<=n*2;i++) if(getfa(i)==i) ans++;
    printf("%lld",quick_pow(2,ans));
    fclose(stdin);
    fclose(stdout);
    return 0;
}
AC代码

B. 冒泡排序

 注意一个巨大的坑点：$p_i$ 是不能重复的

考试的时候我以为可以重复硬推式子推不出来……

引入优先级的概念，如果要在 $a$ 之前先把 $b$ 调整那么 $b$ 的优先级大于 $a$

比如 $1 4 3 2$ 必须要把 $4$ 在 $3$ 之前调换不然 $4$ 是过不去的

 然后可以推 $DP$ 式子

设第一维表示目前到了哪个节点，第二维表示拓扑序，数组存储方案数

对于一个点 $i+1$ ，如果 $i$ 是依赖于它的，那么

$dp[i+1][d] = \sum\limits_{j=d+1}^{n}dp[i][j]$

这是因为如果 $i$ 依赖于 $i+1$ 那么 $i$ 必然在 $i+1$ 之后才能被遍历到

同理，如果对于一个点 $i+1$ ，如果它依赖于 $i$ ，那么有

$dp[i+1][d] = \sum\limits_{j=1}^{d}dp[i][j]$

当然如果这两个点没有依赖关系那么

$dp[i+1][d] = \sum\limits_{j=1}^{n}dp[i][j]$

统计答案即可

#include
#include
#include<string>
#define WR WinterRain
#define int long long
#define Bubble signed
using namespace std;
const int WR=5050,mod=1e9+7;
int n,cnt;
int a[WR];
int res;
int tree1[WR],tree2[WR];
int st1[WR],st2[WR];
int dp[WR][WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
int lowbit(int x){
    return x&(-x);
}
void modify(int x,int v,int *tree){
    for(int i=x;i<=n;i+=lowbit(i)){
        tree[i]+=v;
    }
}
int query(int x,int s){
    if(s==1) return tree1[x]+st1[x-lowbit(x)];
    else return tree2[x]+st2[x-lowbit(x)];
}
Bubble main(){
    freopen("mp.in","r",stdin);
    freopen("mp.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read()+1;//如果存在a[i]=i则无解，因为需要换n-2次，必须把它换走
        if(a[i]==i){printf("0");return 0;}//换走了就换不回来了
        else if(a[i]>i){//否则差分约束建树
            modify(i,1,tree1);//引入优先级的概念
            //如果要在a之前先把b调整那么b的优先级大于a
            modify(a[i]-1,-1,tree1);
        }else{
            modify(a[i],1,tree2);
            modify(i-1,-1,tree2);//树状数组维护
        }
    }
    for(int i=1;i){
        st1[i]=query(i,1);
        st2[i]=query(i,2);
        if(st1[i]&&st2[i]){printf("0");return 0;}
    }
    dp[1][1]=1;
    for(int i=2,j=1;i){
        if(st1[j]){//第一维表示当前是哪个点，第二维表示优先级
            for(int k=2;k<=i;k++){
                dp[i][k]=(dp[i][k-1]+dp[j][k-1])%mod;
            }
        }else if(st2[j]){
            for(int k=j;k;k--){
                dp[i][k]=(dp[i][k+1]+dp[j][k])%mod;
                //在i-1个点中第i-1个点的拓扑序为j 那么把i插入到i-1之前 
                //i-1拓扑序变为j+1 所以 f[i][j]可以由f[i-1][j]递推
                //因为f[i-1][j]中的j是指在i-1的点里的拓扑序  ---------Sakura大佬
            }
        }else{
            for(int k=1;k<=j;k++){
                dp[i][1]=(dp[i][1]+dp[j][k])%mod;
            }
            for(int k=2;k<=i;k++){
                dp[i][k]=dp[i][k-1];
                //这里注意 i 的父亲只能是 i-1 或 i+1
            }
        }
    }
    for(int i=1;i){
        res=(res+dp[n-1][i])%mod;
    }
    printf("%lld",res);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
AC代码

C. 矩阵

 这其实就是模拟

 然鹅这个怎么证明还存疑，因为Kaguya大佬指出一共有 $2n+2m-3$ 个未知数，却有 $2n-2m-4$ 个方程

会有无穷多组解……

如何证明消去前两行前两列就能得出一组解还是一个有趣的问题

#include
#include
#include<string>
#define int long long
#define WR WinterRain
#define Matrix signed
using namespace std;
const int WR=1010;
struct Node{
    int id,v;
}cc[WR<<3],bb[WR<<3],aa[WR<<3];
int n,m,ans;
int cntd,cntb,cntc;
int mp[WR][WR],b[WR<<3],a[WR<<3],c[WR<<3];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
Matrix main(){
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            mp[i][j]=read();
        }
    }
    a[1]=mp[2][2]-mp[1][1];
    c[n]=-mp[2][2];//分别将前2行和前2列暴力修改为0
    for(int i=2;i<=n;i++){//删每一行
        c[n-i+1]=-(mp[i][1]+a[i]);
        a[i+1]=-(mp[i+1][2]+c[n-i+1]);
    }
    for(int i=2;i<=m;i++){//删每一列
        c[n+i-1]=-(mp[1][i]+a[1]+b[i]);
        b[i+1]=-(mp[2][i+1]+c[n+i-1]);
    }
    bool flag=false;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){//每个位置模拟一遍判断有无解
            if(mp[i][j]+a[i]+b[j]+c[n-(i-j)]) flag=true;
        }
    }
    if(flag) printf("-1");
    else{
        for(int i=1;i<=n;i++) if(a[i]) aa[++cntc]={i,a[i]};
        for(int i=1;i<=m;i++) if(b[i]) bb[++cntb]={i,b[i]};
        for(int i=1;i<=n+m;i++) if(c[i]) cc[++cntd]={i-n,c[i]};
        printf("%lld\n",cntd+cntb+cntc);
        for(int i=1;i<=cntc;i++) printf("1 %lld %lld\n",aa[i].id,aa[i].v);
        for(int i=1;i<=cntb;i++) printf("2 %lld %lld\n",bb[i].id,bb[i].v);
        for(int i=1;i<=cntd;i++) printf("3 %lld %lld\n",cc[i].id,cc[i].v);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
AC代码

D. 花瓶

 动规好题

 其实并不显然……

 $50$ 分的代码相当好写

#include
#include
#include<string>
#define WR WinterRain
#define int long long
using namespace std;
const int WR=5010,INF=2147483647;
int n;
int sum[WR],dp[WR][WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
signed main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+read();
    for(int i=1;i<=n;i++) dp[i][1]=0;
    for(int i=2;i<=n;i++){
        for(int j=1;j){
            dp[i][j]=-INF;
            for(int k=0;k){
                dp[i][j]=max(dp[i][j],dp[j][k]+(sum[i]-sum[j])*(sum[j]-sum[k]));
            }
        }
    }
    int maxx=0;
    for(int i=1;i<=n;i++){
        maxx=max(maxx,dp[n][i]);
    }
    printf("%lld",maxx);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
50分代码

但是我们考虑怎么优化这个鬼东西

发现它可以用斜率优化，每次维护一个上凸包

维护右端点时：比较目前队首和当前元素做队首时的优劣

不妨设 $sum$ 数组维护前缀和，$que$ 数组模拟单调队列

$l$ 是队首，$r$ 是队尾

也就是比较 $\frac{dp[i][que[r]]-dp[i][que[r-1]]}{sum[que[r]]-sum[que[r-1]]}$ 和 $\frac{dp[i][id[j]]-dp[i][que[r-1]]}{sum[id[j]]-sum[que[r-1]]}$

维护左端点时同理，比较 $\frac{dp[i][que[l+1]]-dp[i][que[l]]}{sum[que[l+1]]-sum[que[l]]}$ 和 $sum[id[j]]-sum[i]$

注意要把斜率里的除化成乘不然会RE

#include
#include
#include<string>
#include
#define WR WinterRain
#define int long long
using namespace std;
const int WR=5010,INF=2147483647;
int n,a[WR];
int que[WR],l,r;
int id[WR];
int sum[WR],dp[WR][WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
bool cmp(int a,int b){
    return sum[a]<sum[b];
}
signed main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i],id[i]=i;
    sort(id,id+1+n,cmp);//因为下面遍历要从0开始所以排序也要从0开始
    memset(dp,-0x3f,sizeof(dp));
    for(int i=0;i<=n;i++) dp[i][0]=0;
    for(int i=1;i<=n;i++){
        l=1,r=0;
        for(int j=0;j<=n;j++){
            if(id[j]<i){
                while(l1]])*(sum[id[j]]-sum[que[r-1]])
                      <=(dp[i][id[j]]-dp[i][que[r-1]])*(sum[que[r]]-sum[que[r-1]])) r--;
                que[++r]=id[j];//维护右端点
            }
        }
        for(int j=n;j>=0;j--){
            if(id[j]>i){
                while(l1]]-sum[que[l]])
                      <=(dp[i][que[l+1]]-dp[i][que[l]])) l++;
                dp[id[j]][i]=max(dp[id[j]][i],dp[i][que[l]]+(sum[id[j]]-sum[i])*(sum[i]-sum[que[l]]));
                //维护左端点
            }
        }
    }
    int maxx=0;
    for(int i=0;i){
        maxx=max(maxx,dp[n][i]);
    }
    printf("%lld",maxx);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
AC代码

然后就费尽艰辛地改完了

今天考得太差了，明天加油罢

A-游记

相关

标签