2021省选联考A卷解题报告

whiteqwq · 2021-04-20 20:50:57 · 个人记录

退役了

难度可能是绿紫紫紫蓝紫。

更好的阅读体验

P7514 [省选联考 2021 A/B 卷] 卡牌游戏

题意：n张卡牌，正面数字为a_i，反面数字为b_i，一开始所有卡牌正面朝上，可以翻动至多m张卡牌，使得朝上的数字极差最小。

分析：

特别简单的签到题，然后CCF就成功脚造数据。（不输入m的错误贪心还能过就很离谱）

考虑极差最小等价于值在数轴上对应的区间长度最小，把a与b的值放在一起排序，在上面双指针求解就好了。

时间复杂度：O(n\log n)。

#include<stdio.h>
#include<algorithm>
#define inf 1000000001
using namespace std;
const int maxn=1000005;
int n,m,ans;
int a[maxn],b[maxn],vis[maxn];
pair<int,int>c[maxn<<1];
inline int get(int x){
    return x>n? x-n:x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),c[i].first=a[i],c[i].second=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]),c[n+i].first=b[i],c[n+i].second=n+i;
    sort(c+1,c+1+2*n);
    int l=1,r=0,cnta=0,cnt=0;
    while(cnt<n||cnta<n-m){
        r++;
        if(c[r].second<=n)
            cnta++;
        if(vis[get(c[r].second)]==0)
            cnt++;
        vis[get(c[r].second)]++;
    }
    ans=c[r].first-c[l].first;
    while(l<2*n&&r<=2*n){
        if(c[l].second<=n)
            cnta--;
        vis[get(c[l].second)]--;
        if(vis[get(c[l].second)]==0)
            cnt--;
        l++;
        while(cnt<n||(r<=2*n&&cnta<n-m)){
            r++;
            if(c[r].second<=n)
                cnta++;
            if(vis[get(c[r].second)]==0)
                cnt++;
            vis[get(c[r].second)]++;
        }
        if(r>2*n)
            break;
        ans=min(ans,c[r].first-c[l].first);
    }
    printf("%d\n",ans);
    return 0;
}

P7515 [省选联考 2021 A 卷] 矩阵游戏

可见P7515 [省选联考 2021 A 卷] 矩阵游戏解题报告

题意：

给定大小为(n-1)\times(m-1)的矩阵b，求生成任意一个满足条件的a满足：

• 0\leqslant a_{i,j}\leqslant 10^6

保证0\leqslant b_{i,j}\leqslant 4\times 10^6，2\leqslant n,m\leqslant 300。

分析：

可能是暗中送我退役的一道题，我要是把这个思路想下去做掉这道题，那我剩下的题用头打都能进队啊！！！！！！！！！！！！！！！！！！！！！！！！！！！！

技不如人，肝败吓疯。

首先不考虑0\leqslant a_{i,j}\leqslant 10^6，并钦定a_{i,1}=a_{1,j}=0，不难发现可以生成一组解a'。

我们考虑通过调整某些位置的权值使得最后的解权值满足限制。

发现对某一行交替+r,-r,+r,-r\cdots后的解仍然满足矩阵b的限制；同理，对某一列交替+c,-c,+c,-c\cdots后的解也仍然满足矩阵b的限制。

不难发现任意一组解都可以被这样表示出来：

再考虑0\leqslant a_{i,j}\leqslant 10^6这一限制，不难发现把c序列与r序列看做未知量之后可以对其进行差分约束。

但是对于同号的不等式是很难进行差分约束的，考虑定义c'_{k}=\begin{cases}-c_k&k\equiv 1\pmod 2\\c_k&k\equiv 0\pmod 2\end{cases},r'_{k}=\begin{cases}r_k&k\equiv 1\pmod 2\\-r_k&k\equiv 0\pmod 2\end{cases}

然后再次带入上面的解可以得到一个很优美的形式：

这样就可以进行差分约束了，复杂度：O((n+m)nm)。

Bellman Ford被卡常了（需要特判才能过），迫不得已用了spfa/kk

#include<stdio.h>
#include<queue>
#include<vector>
#define inf 10000000000000000
using namespace std;
const int maxn=305,maxm=maxn*maxn*2;
int T,n,m,e;
int a[maxn][maxn],b[maxn][maxn],vis[maxn<<1],tot[maxn<<1];
vector<int>v[maxn<<1],w[maxn<<1];
long long dis[maxn<<1];
queue<int>q;
inline void add(int x,int y,int z){
    v[x].push_back(y),w[x].push_back(z);
}
inline void limit(int x,int y,int v){
    add(x,y,v);//v+x-y>=0
    add(y,x,1000000-v);//v+x-y<=1000000
}
int spfa(){
    while(!q.empty())
        q.pop();
    for(int i=1;i<=n+m;i++)
        dis[i]=inf,tot[i]=0,vis[i]=0;
    dis[1]=0,vis[1]=1,q.push(1);
    while(!q.empty()){
        int x=q.front();
        tot[x]++;
        if(tot[x]>n+m)
            return 1;
        q.pop();
        for(int i=0;i<v[x].size();i++){
            int y=v[x][i],z=w[x][i];
            if(dis[y]>dis[x]+z){
                dis[y]=dis[x]+z;
                if(vis[y]==0)
                    vis[y]=1,q.push(y);
            }
        }
        vis[x]=0;
    }
    return 0;
}
inline int calc(int x,int y){
    return a[x][y]+(int)(((x+y)&1)? (dis[n+y]-dis[x]):(dis[x]-dis[n+y]));
}
int main(){
    scanf("%d",&T);
    while(T--){
        e=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
                scanf("%d",&b[i][j]);
        for(int i=2;i<=n;i++)
            for(int j=2;j<=m;j++)
                a[i][j]=b[i-1][j-1]-a[i-1][j-1]-a[i-1][j]-a[i][j-1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if((i+j)&1)
                    limit(n+j,i,a[i][j]);
                else limit(i,n+j,a[i][j]);
            }
        if(spfa()){
            puts("NO");
            for(int i=1;i<=n+m;i++)
                v[i].clear(),w[i].clear();
            continue;
        }
        puts("YES");
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                printf("%d%c",calc(i,j),j==m? '\n':' '),a[i][j]=0;
        for(int i=1;i<=n+m;i++)
            v[i].clear(),w[i].clear();
    }
    return 0;
}

P7516 [省选联考 2021 A/B 卷] 图函数

可见P7516 [省选联考 2021 A/B 卷] 图函数解题报告

题意：

给定一张n个点m条边的有向图G，定义函数f(u,G)的值为下列操作的返回值：

设cnt=0,G'=G，然后按1到n的顺序枚举点v，如果G'中v与u能双向到达，那么cnt++，并删去结点v，最后返回cnt。

定义h(G)=\sum_{i=1}^n f(i,G)，并定义G_i为图G删除边1\cdots i后的图，求出h(G_{0\cdots n})。