P6411 [COCI2008-2009#3] MATRICA 题解

· · 题解

可能更好的阅读体验

水题。

发现根据限制 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;
}