题解 P2809 【hzwer爱折纸】

Yy666_l · 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;
    }
}