15011418730 LV 7 @ 2025-8-24 21:37:01

自动搬运

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 21:37:01，当前版本为作者最后更新于2024-09-08 16:44:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Gossip

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

双倍经验：P3484。

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

Algorithm

很明显，对于两个全等的图形 $G_1$ 和 $G_2$ ，它们的向量序列只有两种情况：

它们向量序列的「标准表示」相同。
把 $G_2$ 的向量序列翻转（即 $\{\bm L_1,\bm L_2,\ldots,\bm L_n\}$ 变为 $\{-\bm L_n,-\bm L_{n-1},\ldots,-\bm L_1\}$ ）后，它们向量序列的「标准表示」相同。

此外，我们可以钦定 $\bm L_1$ 的方向水平向右。

接下来，根据题意模拟即可：

根据字符串 $S$ 反推出 $\{\bm L_n\}$ （即反推出 $\langle\bm L_1,\bm L_i\rangle$ ）；
枚举 $k=1,2,\ldots,n$ 进行修改；
对于每个修改方案，枚举 $l=1,2,\ldots,n$ 并比较，得到修改后的向量序列的「标准表示」（即这个修改方案的「修改结果」）；
结合上面的结论，使用 set/map 对等价的修改方案去重；
使用 sort/priority_queue/set/map/... 对「修改结果」排序后输出即可。

该算法的时间复杂度为 $O(T|S|^3)$ ，空间复杂度为 $O(|S|^2)$ ，可以通过此题。

My Accepted Code (R176331039)

#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)
{
    stack<pair<char,int> > st;
    st.push(make_pair('#',0));
    map<int,bool> mp;
    mp[0]=true;
    int cur=0;
    int n=s.size();
    s=' '+s;
    for(int i=1;i<=n-1;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;}
        }
        if(mp.count(cur)) return false;
        else
        {
            st.push(make_pair(s[i],cur));
            mp[cur]=true;
        }
    }
    return true;
}
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;
}
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)) pq.push(res);
        mp[res1]=1;
        mp[res2]=1;
    }
    cout<<pq.size()<<endl;
    while(!pq.empty())
    {
        cout<<pq.top()<<' ';
        pq.pop();
    }
    cout<<endl;
    cout<<endl;
    return 0;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        string S;
        cin>>S;
        man(S);
    }
    return 0;
}

Standard Code by the writer (R224712)

//DeathQuake
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;


const	int	d[6][2]={ {0,-2},{-1,-1},{-1,1},{0,2},{1,1},{1,-1} };
int	a[99],b[99],c[99],e[99],f[9999][99],p[99][2];
char	st[99];
int	TEST;


bool	cmp(int a[],int b[])
{
	int	Len=min(a[0],b[0]),k;
	for (k=1;k<=Len;++k)
	if (a[k]<b[k]) return 0; else if (a[k]>b[k]) return 1;
	if (a[0]>b[0]) return 1; else return 0;
}

bool	check(int a[])
{
	p[0][0]=p[0][1]=0;
	for (int i=1,dire=3;i<=a[0];++i)
	{
		dire=(dire+a[i]+3)%6;
		p[i][0]=p[i-1][0]+d[dire][0];
		p[i][1]=p[i-1][1]+d[dire][1];
	}
	if (p[a[0]][0] || p[a[0]][1]) return 0;
	for (int i=1;i<a[0];++i)
	for (int j=0;j<i;++j)
	if (p[i][0]==p[j][0] && p[i][1]==p[j][1]) return 0;
	return 1;
}

int	Min_Representation(int a[])
{
	int	i=1,j=2,k=0,Len=a[0];
	for (;k<Len;)
	if (a[(i+k-1)%Len+1]==a[(j+k-1)%Len+1]) ++k; else
	{
		if (a[(i+k-1)%Len+1]>a[(j+k-1)%Len+1]) i+=k+1; else j+=k+1;
		if (i==j) ++j;
		k=0;
	}
	return ((i-1)%Len<(j-1)%Len?(i-1)%Len+1:(j-1)%Len+1);
}

void	Represent(int a[])
{
	int	Loca=Min_Representation(a);
	for (int i=1;i<=a[0];++i) c[i]=a[(Loca+i-2)%a[0]+1];
	for (int i=1;i<=a[0];++i) a[i]=c[i];
}

void	AddAns(int a[])
{
	for (int i=1;i<=a[0];++i) e[a[0]+1-i]=a[i]; e[0]=a[0];
	Represent(a);
	Represent(e);
	if (cmp(a,e))
	{
		a[0]=e[0];
		for (int i=1;i<=a[0];++i) a[i]=e[i];
	}
	
	for (int i=1;i<=f[0][0];++i)
	{
		if (f[i][0]!=a[0]) continue;
		bool	flag=1;
		for (int j=1;j<=a[0] && flag;++j) if (f[i][j]!=a[j]) flag=0;
		if (flag) return;
	}
	++f[0][0];
	for (int i=0;i<=a[0];++i) f[f[0][0]][i]=a[i];
}

void	Work(int a[])
{
	int	Len=a[0];
	for (int i=1;i<=Len;++i) if (a[i]>1 && a[i%Len+1]>1)
	{
		b[0]=Len+1;
		for (int j=1;j<i;++j) b[j]=a[j];
		b[i]=a[(i+Len-1)%Len+1]-1; b[i%(Len+1)+1]=5; b[(i+1)%(Len+1)+1]=a[i%Len+1]-1;
		for (int j=i+2;j<=Len;++j) b[j%(Len+1)+1]=a[j];
		if (!check(b)) continue;
		AddAns(b);
	}
	for (int i=1;i<=Len;++i) if (a[i]>1 && a[i%Len+1]==1 && a[(i+1)%Len+1]>1)
	{
		b[0]=Len-1;
		for (int j=1;j<i;++j) b[(j-1)%(Len-1)+1]=a[j];
		b[(i-1)%(Len-1)+1]=a[i]-1; b[i%(Len-1)+1]=a[(i+1)%Len+1]-1;
		for (int j=i+3;j<=Len;++j) b[(j+Len-3)%(Len-1)+1]=a[j];
		if (!check(b)) continue;
		AddAns(b);
	}
}

void	Sort()
{
	for (int i=1;i<=f[0][0];++i)
	for (int j=i+1;j<=f[0][0];++j)
	{
		if (!cmp(f[i],f[j])) continue;
		int	Len=max(f[i][0],f[j][0]),Tmp;
		for (int k=0;k<=Len;++k) swap(f[i][k],f[j][k]);
	}
}

void	Print()
{
	printf("%d\n",f[0][0]);
	for (int i=1;i<=f[0][0];++i)
	{
		for (int j=1;j<=f[i][0];++j) printf("%c",f[i][j]+96);
		if (i==f[0][0]) puts(""); else printf(" ");
	}
	if (TEST) puts("");
}

int	main()
{
	for (scanf("%d",&TEST);TEST--;)
	{
		scanf("%s",st+1);
		a[0]=strlen(st+1);
		for (int i=1;i<=a[0];++i) a[i]=st[i]-96;
		f[0][0]=0;
		Work(a);
		Sort();
		Print();
	}
	
	return 0;
}

ID

1385

时间

1000ms

内存

125MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

Gossip

Algorithm

My Accepted Code (R176331039)

Standard Code by the writer (R224712)

三角形图

信息

1 条题解

自动搬运

以下是正文

Gossip

Algorithm

My Accepted Code (R176331039)

Standard Code by the writer (R224712)

三角形图

信息

还没有账户？

登录