自动搬运

查看原文

来自洛谷，原作者为

	Yy666_l **

搬运于2025-08-24 21:41:50，当前版本为作者最后更新于2019-09-15 20:52:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

居然没c++题解

其实这题暴力枚举再用一个什么东西判个重就行了

其实是想不到超过一半是一样的

stl的map和vector用一用简直美滋滋。（c++舒服呀）

还是贴代码吧

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
int n,m,x,L;
vector<int> a,b;
map<vector<int>,bool> ma;
bool ok;
vector<int> fz(int k,vector<int> V)//英语渣渣，只好首字母缩写，翻折
{
	vector<int> u;
	u.clear();
	u.push_back(0);
	int l=V.size()-1,e=0;
	int t=max(k,l-k);
	for(int i=t;i>=1;i--)
	{
		int z=0;
		if(k-i+1>0) z+=V[k-i+1];
		if(k+i<=l)	z+=V[k+i];
		e++;
		u.push_back(z);//把新序列放进一个vector
	}
	return u;//vector可以作为函数返回值； 
}
bool pd(vector<int> V)
{
	for(int i=1;i<=m;i++)
	if(V[i]!=b[i]) return 0;
	return 1;
}
void dfs(vector<int> V)
{
	if(ma.count(V)) return;
	ma[V]=1;  //map判重，类似hash，但有一个log 
	int l=V.size()-1;
	if(l==L) if(pd(V)) ok=1;
	if(l<L) return;
	for(int i=0;i<=l;i++)//枚举翻折的位置
	{
		dfs(fz(i,V));
		if(ok) return;
	}
}
int main()
{
	while(cin>>n)//cin卡了点，但数据小的时候是个好东西
	{
		a.clear();
		b.clear();
		a.push_back(0);
		b.push_back(0);
		ma.clear();
		for(int i=1;i<=n;i++)
		{
			cin>>x;
			a.push_back(x);
		} 
		cin>>m;
		for(int j=1;j<=m;j++)
		{
			cin>>x;
			b.push_back(x);
		}
		L=b.size()-1;
		ok=0;
		dfs(a);
		if(ok) cout<<"S"<<endl;
		else cout<<"N"<<endl;
	}
}