codeforces 202B Brand New Easy Problem

题目的意思就是说给定不超过四个词的句子,将这几个次进行全排列,然后在去下面给出的例子中进行匹配,如果某个全排列匹配成功的话,就求出其逆序数,找到符合情况的逆序数最小的情况,如果有多的选择,则选择编号最小的情况,并按照给定的格式进行输出。

题目中说到就是子串中的单词不会重复,但是匹配串会有单词重复,如果说去每个匹配串中找到相应的单词,并求出所有可能的逆序的话,这样的任务量会很大。不如就是把子串所有的全排列全部匹配一遍,这样的话会省去很多判断的过程,对于编码和时间都会有很大的改善。

那么这道题的主要思路就是用到next_permutation()函数将子串进行全排列,然后把每种情况的逆序数求出来,然后和匹配串一一匹配,然后再重中找到最终的解。

#include #include #include #include using namespace std; struct node { char s[21][25]; int k; } v[10]; int main() { int n,m,k,f[4]; scanf("%d",&n); char a[4][20]; for(int i=0; if[i]) sum++; if(sum>ans) continue; for(i=0; i=n) break; } if(ii)) p=i,ans=sum; } while(next_permutation(f,f+n)); if(p==20) printf("Brand new problem!\n"); else { printf("%d\n[:",p+1); int t=n*(n-1)/2+1-ans; for(int i=0; i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:hdu2435最大流最小割
下一篇:PAT: 1054. The Dominant Color (20)
相关文章
图文推荐
codeforces 202B Brand New Easy Problem
ZOJ 3640 Help Me
codeforces 202B Brand New Easy Problem
CF 518C(Anya and
codeforces 202B Brand New Easy Problem
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-08 人气:8
本文关键词:
分享到:

相关文章

  • codeforces-379C. New Year Ratings Change 2012-11-15

    codeforces-379C. New Year Ratings Change 原理=北大OJ1088滑雪,叫记忆DP吧,就是深搜的感觉,只是边走边做记号,用函数的回溯。。。。 数据太大?开不了那么大的数组?用数据离散化,容器map。 就是,走过的地方,就留标记,标记后面有多少步已经走过了,下次再走到这个地方,就直接跳过标记不再走,可以节省时间。 5621923 Jan 5, 2014 4:15:28 PM 20114045007 379C - New Year Ratings Change

  • HDU 2601 An easy problem 因式分解 2015-02-27

    点击打开链接 An easy problem Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5726 Accepted Submission(s): 1394 Problem Description When Teddy was a child , he was always thinking about some simple math

  • CodeForces 379 D. New Year Letter 2013-05-14

    枚举开头结尾的字母,枚举ac的个数,总AC个数就是两个Fibonacci数列的和。。。。。 D. New Year Letter time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Many countries have such a New Year or Christmas tradition as writing a lett

  • hdu2435最大流最小割 2014-06-14

    2435 There is a war 题意: 给你一个有向图,其中可以有一条边是无敌的,这条边可以是图中的边,也可以是自己任意加上去的图中没有的边,这条无敌的边不可以摧毁,让1和n无法连通的最大摧毁费用,就是1到n的最小割中的最大的那个,这个题卡了好几天,一开始是各种方法各种wa,后来无意中发现自己犯了个sb错误,结果改正后以前的各种方法各种ac,比赛要是碰到这样的事估计就跪了... 思路: 首先能确定的就是题目要求咱们就最小割(最大流 = 最小割),但关键是有那么一条无坚不摧的nb道路,所以

  • zoj3791(An Easy Game) DP 2012-02-04

    题意:给出两个01字符串s1,s2.每次改变s1上m个位置的字符。问k步之后使得s1变为s2的方法有多少种。 解法:DP,关键是状态的设计。考虑还是唯一性和可传递性。dp[i][j]表示第i步后有j个不同到目标的走法数。记忆化搜索dp[0][dif](dif表示初始时不同字符的个数)。转移时候枚举选择情况即可。 代码: /****************************************************** * author:xiefubao ***************

  • zoj 3761 Easy billiards(建图+贪心+dfs) 2012-05-04

    题目链接:zoj 3761 Easy billiards 题目大意:在一个平面上,有若干个球,给出球的坐标,每次可以将一个球朝另一个球打过去(只有上下左右),碰到下一个球之后原先的球停下来,然后被撞的球朝这个方向移动,直到有一个球再也撞不到下一个球后,这个球飞出。问说最少平面上剩几个球,并且给出打球的方案。 解题思路:对于每个球,最多有4个边,上下左右,将它与每个方向上最近的那个球相连,方法也很简单,先按照x排序,x相同按照y排序,然后遍历,如果相邻的两个之间x相同,即可相连;y同理。 然后对于

  • ZOJ 2833-Friendship(并查集+优化) 2012-07-21

    Friendship Time Limit: 3 Seconds Memory Limit: 32768 KB A friend is like a flower, a rose to be exact, Or maybe like a brand new gate that never comes unlatched. A friend is like an owl, both beautiful and wise. Or perhaps a friend is like a ghost, w

  • Upgrading to BackTrack 5 R2 2013-08-03

    The long awaited release of the BackTrack 5 R2 kernel has arrived, and it’s now available in our repositories. With a spanking brand new 3.2.6 kernel, a huge array of new and updated tools and security fixes, BT5 R2 will provide a more stable and com

  • 算法导论实践中的教训 2014-07-24

    1 昨天因为关键字,折腾一天,为何定义的结构体总是说没有这个定义,原来问题出现在没有用关键字typedef,这个关键字通俗点说就是别名的意思,可用用定义的别名来定义其他的变量或函数,当需要改变这个别名类型的时候,只要修改typedef定义就可以做到一改全改的目的,不用一个个去改变类型了。 2 今天因为在函数内部申请的内存,回到原函数是,申请的内存已经被释放了,百思不得其解,终于看到C++的伟大之处,使用引用&操作符,可以解决这个问题,Mark一下。 二叉查找树代码 #include us

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.058 (s). 10 q(s)