自动搬运

查看原文

来自洛谷，原作者为

	int_R 我在衡水上高三没空想你

搬运于2025-08-24 22:20:32，当前版本为作者最后更新于2023-09-26 21:07:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可能更好的阅读体验

水题。

发现根据限制 $M_{i,j}=M_{j,i}$ 可以知道除了主对角线上的点，其他的点都是成对出现的。也就是说如果有一条要求的 $a_i$ 为奇数，那么至少有一个 $c_i$ 在主对角线上。

记 $S=\sum\limits_{i=1}^{k} (a_i\equiv 1\pmod 2)$，即有 $S$ 个要求中 $a_i$ 为奇数。主对角线上只有 $n$ 个点，所以若 $S>n$ 则无解。

如果 $S=n$ 很好处理，但如果 $S<n$，说明主对角线上还需要放别的数，而且要一次性放入两个。

我们按字典序从小到大枚举字符，只处理 $(i,j)|i\leq j$ ，也就是主对角线及上方的点。

对于主对角线特别考虑，维护一个栈，从栈顶到栈底从小到大。里面放入现在剩余未填个数为奇数的字符，每次比较栈顶字符 $a$ 和当前的枚举字符 $b$，设栈的大小为 $cnt$，当前位置为 $(i,i)$：

如果 $b<a$ 则说明将 $b$ 填在此处比将 $a$ 填在此处更优，但同时需要保证 $(i-1)+(cnt+2)\leq n$，因为主对角线上已经填过 $i-1$ 个数，如果将 $b$ 填在这里，就说明在第 $i\sim n$ 行的主对角线上要填 $cnt+2$ 个数。所以如果这个值大于 $n$ 就会不合法。

对于其他点直接顺次放，一种字符一定是连续的，每一行用 vector 维护连续的字符段。总共 $n$ 行只会有 $n+|\Sigma|$ 个连续字符段，其中 $|\Sigma|$ 表示字符集大小。

输出答案时直接遍历，一行最多只会有 $|\Sigma|$ 连续的字符段，并且均摊 $O(1)$。

总时间复杂度为 $O(np)$。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=3e4+10;
int n,k,t[26],q[30],cnt,p,pos[60],h[MAXN];
struct node{int l,r,num;};
vector < node > v[MAXN];
inline char ANS(int x,int y)
{
    if(x>y) return ANS(y,x);
    if(x==y) return h[x]+65;
    for(node z:v[x]) if(z.l<=y&&z.r>=y) return z.num+65;
    return 0;
}
int main()
{
#ifdef ONLINE_JUDGE
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>n>>k;
    for(register int i=1;i<=k;++i){char c;int a;cin>>c>>a;t[c-65]=a;}
    //逆序，这样从栈顶到栈底从小到大；t[i]/=2 因为只考虑主对角线及上方
    for(register int i=25;i>=0;--i){if(t[i]&1) q[++cnt]=i;t[i]/=2;}
    if(cnt>n){cout<<"IMPOSSIBLE\n";return 0;}
    cin>>p;for(register int i=1;i<=p;++i) cin>>pos[i];
    //cur 是枚举元素
    for(register int i=1,cur=0;i<=n;++i)
    {
        while(!t[cur]) ++cur;
        //这里还要在栈顶加入 cur，因为这一行只填了一个，它变成了还剩奇数个未填
        if((cur<q[cnt]||!cnt)&&i+cnt+1<=n) h[i]=cur,t[cur]-=1,q[++cnt]=cur;
        else h[i]=q[cnt--];
        for(int l=i+1,r;l<=n;l=r+1)
        {
            while(!t[cur]) ++cur;
            r=min(n,l+t[cur]-1);
            v[i].push_back({l,r,cur});
            t[cur]-=(r-l+1);
        }
        for(register int j=1;j<=p;++j) cout<<ANS(i,pos[j]);
        cout<<'\n';
    }
    return 0;
}