P3484

035966_L3 · 2024-12-04 20:43:17 · 题解

Gossip

模拟赛一道难过到我的题！——P2377 原题面

双倍经验：P2377。

这个双倍经验一看就是 UNowen 当年（2015）遇到的原题！

Algorithm

本题和 P2377 的不同点是：

• 不需要再检验整个图形是否内陷。也就是说，P2377 中题目描述中 k=3 的修改在本题中合法。（但本题依然不允许出现 P2377 中的 \texttt{\#}）
• 对于 \texttt{N} 询问，从单个三角形（\texttt{eee}）开始暴力拓展即可。

My Accepted Code (R192823783)

#include <bits/stdc++.h>
using namespace std;
char cv(int x)
{
    return '0'+(x+600000)%6;
}
string mod(string s,int k)
{
    int n=s.size()-1;
    char x=cv(s[k]+1),y=cv(s[k]-1);
    char xx,yy;
    if(k==1) xx=s[n];
    else xx=s[k-1];
    if(k==n) yy=s[1];
    else yy=s[k+1];
    if(abs(xx-x)==3&&abs(yy-y)==3)
    {
        s[k]=' ';
        if(k==1) s[n]=' ';
        else s[k-1]=' ';
        if(k==n) s[1]=' ';
        else s[k+1]=' ';
    }
    if(abs(xx-x)==3&&abs(yy-y)!=3)
    {
        s[k]=y;
        if(k==1) s[n]=' ';
        else s[k-1]=' ';
    }
    if(abs(xx-x)!=3&&abs(yy-y)==3)
    {
        s[k]=x;
        if(k==n) s[1]=' ';
        else s[k+1]=' ';
    }
    if(abs(xx-x)!=3&&abs(yy-y)!=3)
    {
        s[k]=y;
        string z=" ";
        z[0]=x;
        s.insert(k,z);
    }
    int p=s.size()-1;
    string res="";
    for(int i=0;i<=p;i++)
        if(s[i]!=' ') res+=s[i];
    return res;
}
bool check(string s)
{
    int cur=0;
    int n=s.size();
    s=' '+s;
    for(int i=1;i<=n;i++)
    {
        switch(s[i])
        {
            case '0': {cur++;break;}
            case '1': {cur+=1001;break;}
            case '2': {cur+=1000;break;}
            case '3': {cur--;break;}
            case '4': {cur-=1001;break;}
            case '5': {cur-=1000;break;}
        }
    }
    return (cur==0);
}
string diff(string s)
{
    int n=s.size();
    string res="";
    for(int i=1;i<=n-1;i++)
        switch(cv(s[i-1]-s[i]))
        {
            case '4': {res+='a';break;}
            case '5': {res+='b';break;}
            case '0': {res+='c';break;}
            case '1': {res+='d';break;}
            case '2': {res+='e';break;}
        }
    switch(cv(s[n-1]-s[0]))
    {
        case '4': {res+='a';break;}
        case '5': {res+='b';break;}
        case '0': {res+='c';break;}
        case '1': {res+='d';break;}
        case '2': {res+='e';break;}
    }
    return res;
}
string mins(string s)
{
    string res=s;
    int n=s.size();
    for(int i=1;i<=n;i++)
    {
        char c=s[0];
        s.erase(0,1);
        s+=c;
        if(s<res) res=s;
    }
    return res;
}
bool ok(string S)
{
    int n=S.size();
    S=' '+S;
    string s="0";
    int now=0;
    for(int i=2;i<=n;i++)
    {
        switch(S[i-1])
        {
            case 'a': {now+=2;break;}
            case 'b': {now++;break;}
            case 'c': {break;}
            case 'd': {now--;break;}
            case 'e': {now-=2;break;}
        }
        s+=cv(now);
    }
    return check(s);
}
int man(string S)
{
    int n=S.size();
    S=' '+S;
    string s=" 0";
    int now=0;
    for(int i=2;i<=n;i++)
    {
        switch(S[i-1])
        {
            case 'a': {now+=2;break;}
            case 'b': {now++;break;}
            case 'c': {break;}
            case 'd': {now--;break;}
            case 'e': {now-=2;break;}
        }
        s+=cv(now);
    }
    map<string,int> mp;
    priority_queue<string,vector<string>,greater<string> > pq;
    for(int i=1;i<=n;i++)
    {
        string rr=mod(s,i);
        if(!check(rr)) continue;
        string rr1=diff(rr);
        string rr2=rr1;
        reverse(rr2.begin(),rr2.end());
        string res1=mins(rr1);
        string res2=mins(rr2);
        string res=res1;
        if(res2<res1) res=res2;
        if(!mp.count(res1)&&!mp.count(res2)&&ok(res)) pq.push(res);
        mp[res1]=1;
        mp[res2]=1;
    }
    cout<<pq.size()<<endl;
    while(!pq.empty())
    {
        cout<<pq.top()<<' ';
        pq.pop();
    }
    cout<<endl;
    return 0;
}
priority_queue<string,vector<string>,greater<string> > pq,qp;
map<string,int> mp;
int mans1()
{
    string S=qp.top();
    qp.pop();
    int n=S.size();
    S=' '+S;
    string s=" 0";
    int now=0;
    for(int i=2;i<=n;i++)
    {
        switch(S[i-1])
        {
            case 'a': {now+=2;break;}
            case 'b': {now++;break;}
            case 'c': {break;}
            case 'd': {now--;break;}
            case 'e': {now-=2;break;}
        }
        s+=cv(now);
    }
    for(int i=1;i<=n;i++)
    {
        string rr=mod(s,i);
        if(!check(rr)) continue;
        string rr1=diff(rr);
        string rr2=rr1;
        reverse(rr2.begin(),rr2.end());
        string res1=mins(rr1);
        string res2=mins(rr2);
        string res=res1;
        if(res2<res1) res=res2;
        if(!mp.count(res1)&&!mp.count(res2)&&ok(res)) pq.push(res);
        mp[res1]=1;
        mp[res2]=1;
    }
    return 0;
}
int mans2()
{
    string S=pq.top();
    pq.pop();
    int n=S.size();
    S=' '+S;
    string s=" 0";
    int now=0;
    for(int i=2;i<=n;i++)
    {
        switch(S[i-1])
        {
            case 'a': {now+=2;break;}
            case 'b': {now++;break;}
            case 'c': {break;}
            case 'd': {now--;break;}
            case 'e': {now-=2;break;}
        }
        s+=cv(now);
    }
    for(int i=1;i<=n;i++)
    {
        string rr=mod(s,i);
        if(!check(rr)) continue;
        string rr1=diff(rr);
        string rr2=rr1;
        reverse(rr2.begin(),rr2.end());
        string res1=mins(rr1);
        string res2=mins(rr2);
        string res=res1;
        if(res2<res1) res=res2;
        if(!mp.count(res1)&&!mp.count(res2)&&ok(res)) qp.push(res);
        mp[res1]=1;
        mp[res2]=1;
    }
    return 0;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        string T,S;
        cin>>T>>S;
        if(T=="K") man(S);
        else
        {
            stringstream ss;
            ss<<S;
            int x;
            ss>>x;
            pq.push("eee");
            for(int i=1;i<=x-1;i++)
            {
                if(i%2) while(!pq.empty()) mans2();
                else while(!qp.empty()) mans1();
                mp.clear();
            }
            if(x%2)
            {
                cout<<pq.size()<<endl;
                while(!pq.empty())
                {
                    cout<<pq.top()<<' ';
                    pq.pop();
                }
                cout<<endl;
            }
            else
            {
                cout<<qp.size()<<endl;
                while(!qp.empty())
                {
                    cout<<qp.top()<<' ';
                    qp.pop();
                }
                cout<<endl;
            }
        }
    }
    return 0;
}