注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4665 Unshuffle  

2013-08-12 12:22:58|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4665
两个相同的串以任意的方式交叉在一起,组成一个新的串,但仍保持原来的顺序,比如两个ABCD可以组成ABCABDCD。现在给出这么一个合成的串,然后找出原来的两个相同串,一个串的所有元素用0表示,另一个用1表示。
题解:比赛的时候看到串有2000长,于是就放弃了搜索的思想,结果后来才发现这题数据比较水,直接dfs就能解决,于是乎打了个dfs,稍微剪枝了下就A了,竟然只跑了15MS。

/*
* pro.cpp
*
* Created on: 2013-08-12
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=2010;
const int M=32010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const double eps=1e-7;
const double PI=acos(-1.0);

int flag,f[N],res[N];

void dfs(int tar,int tmp,int n,int tot)
{
if(flag)
return ;
if(tot == n/2)
{
for(int i=0;i<n;i++)
printf("%d",res[i]);
printf("\n");
flag=1;
return ;
}
if(res[tar]==1)
{
dfs(tar+1,max(tmp,tar+2),n,tot);
return ;
}
for(int i=tmp;i<n;i++)
if(f[i] == f[tar] && res[i] == 0)
{
res[i]=1;
dfs(tar+1,i+1,n,tot+1);
res[i]=0;
}
}

void solve(int n)
{
for(int i=0;i<n;i++)
{
scanf("%d",&f[i]);
res[i]=0;
}
flag=0;
dfs(0,1,n,0);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int n,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
solve(n);
}
return 0;
}



 
  评论这张
 
阅读(82)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017