princess专题

HDU Ignatius and the Princess IV

题目传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1029 看来写这类题目必须要创新的思路,纯粹的写循环很容易被大数据爆掉。下面是一份超时代码,目前还没有发现原因,没有死循环,目测是数据量大的原因? #include<stdio.h>#include<string.h>#include<algorithm>//#define LOCAL

uva 10635 - Prince and Princess(LCS)

题目连接:10635 - Prince and Princess 题目大意:给出n, m, k,求两个长度分别为m + 1 和 k + 1且由1~n * n组成的序列的最长公共子序列长的。 解题思路:按一般的o(n^2)的算法超时了,所以上网查了下LCS装换成LIS的算法o(nlogn)。算法仅仅是将其中的一个序列重新标号1~m,然后按最长公共子序列的方法去做。 #in

杭电OJ 1027:Ignatius and the Princess II

题目的大意就是求一串数字的全排列的第m小的排列,比如1,2,3是3个数的最小的全排列,1,3,2是次小的全排列。这个题目可以用STL的一个函数next_permutation,这个函数是用来生成一个全排列的下一个全排列,当然也可以自己写生成排列算法,生成一个全排列的下一个全排列的算法如下: (1)从数组最后一个开始往前找,假设后一个记为p,前一个记为pre,直到找到一个满足A[pre]<A[p]

hdu 1028Ignatius and the Princess III(整数划分)

很水的一道题,DP可以, 母函数也可以…… 母函数代码: #include<iostream>#include<cstring>using namespace std;int main(){int n, num1[124], num2[124];//对小于100的整数进行划分int i, j, k;while( cin>>n ){for(i=0;

Ignatius and the Princess II【HDOJ1027】

题目链接 #include<cstdio>#include<algorithm>using namespace std;int main(){int n,m;int arr[1010];while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++){arr[i]=i;}int cnt=0;do{cnt++;if(cnt==m){for(int i

upc国庆集训第八天 Princess Principal(思维+栈)

问题 H: Princess Principal 时间限制: 2 Sec  内存限制: 1024 MB 提交: 183  解决: 37 [提交] [状态] [讨论版] [命题人:admin] 题目描述 阿尔比恩王国(the Albion Kingdom)潜伏着一群代号“白鸽队(Team White Pigeon)”的间谍。在没有任务的时候,她们会进行各种各样的训练,比如快速判断一个文档有没有

(2016弱小联盟十一专场10.3) Help the Princess! BFS

题目连接: https://acm.bnu.edu.cn/v3/statments/jag2016.pdf 分析: 直接判断‘%’到‘@’和最近的‘$’的距离,如果 ‘%’到‘@’小于%’到最近的‘$’的距离则输出YES否则输出NO AC代码: #include <iostream>#include <cstdio>#include <cstring>#include <algor

ACM DP Ignatius and the Princess IV

题目: "OK, you are not too bad, em... But you can never pass the next test." feng5166 says.  "I will tell you an odd number N, and then N integers. There will be a special integer among them, you ha

@Wannafly summer camp Day2 H:Princess Principal (栈模拟)

阿尔比恩王国(the Albion Kingdom)潜伏着一群代号“白鸽队(Team White Pigeon)”的间谍。在没有任务的时候,她们会进行各种各样的训练,比如快速判断一个文档有没有语法错误,这有助于她们鉴别写文档的人受教育程度。 这次用于训练的是一个含有n个括号的文档。括号一共有mm种,每种括号都有左括号和右括号两种形式。我们定义用如下的方式定义一个合法的文档: 1.一个空的字符串是一

HDU——1028 Ignatius and the Princess III(母函数)

Problem Description “Well, it seems the first problem is too easy. I will let you know how foolish you are later.” feng5166 says. “The second problem is, given an positive integer N, we define an eq

Hug the princess(思维,位运算)

Hug the princess Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit  Status There is a sequence with nn elements. Assuming they are a1,a2,⋯,ana1,a2,⋯,an

Hug the princess(思维,位运算)

Hug the princess Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit  Status There is a sequence with nn elements. Assuming they are a1,a2,⋯,ana1,a2,⋯,an

UESTC--1041--Hug the princess(位运算)

 Hug the princess Time Limit: 1000MS Memory Limit: 65535KB 64bit IO Format: %lld & %llu Submit Status Description There is a sequence with  n elements. Assuming they are  a1,a2,⋯,a

UESTC--1041--Hug the princess(位运算)

 Hug the princess Time Limit: 1000MS Memory Limit: 65535KB 64bit IO Format: %lld & %llu Submit Status Description There is a sequence with  n elements. Assuming they are  a1,a2,⋯,a

The 13th UESTC Programming Contest Preliminary——Hug the princess

题意:根据公式进行计算。 解题思路:首先,自己可以通过举几个例子来验证,异或运算与与运算之和刚好等价于或运算,或者可以这样想,异或是(1,0)、(0,1),与是(1,1),合起来刚好是或。然后题目就是求两倍的或运算了。然后,每一个ai都与aj或运算(i<j),每次ai与aj或的时候,aj二进制位上是1的数位在或运算后总还是1,所以前面有多个ai与aj或,最后结果里就有多少个aj的和;然后考虑aj

The 13th UESTC Programming Contest Preliminary——Hug the princess

题意:根据公式进行计算。 解题思路:首先,自己可以通过举几个例子来验证,异或运算与与运算之和刚好等价于或运算,或者可以这样想,异或是(1,0)、(0,1),与是(1,1),合起来刚好是或。然后题目就是求两倍的或运算了。然后,每一个ai都与aj或运算(i<j),每次ai与aj或的时候,aj二进制位上是1的数位在或运算后总还是1,所以前面有多个ai与aj或,最后结果里就有多少个aj的和;然后考虑aj

HDU 1027:Ignatius and the Princess II ← next_permutation()

【题目来源】http://acm.hdu.edu.cn/showproblem.php?pid=1027【题目描述】 Now our hero finds the door to the BEelzebub feng5166. He opens the door and finds feng5166 is about to kill our pretty Princess. But now the

例题27 UVa10635 Prince and Princess(DP:LIS的nlogn算法)

题意: 看白书 要点: 这题本来应该是LCS,但因为时间的要求,可以转化为LIS,而且还得用nlogn的算法,基本思路就是用b数组来存储当前b的值在a数组中对应的位置。LIS的nlogn算法的思路就是,每次用g来存储,并每次在其中进行二分查找,注意这里每次更新是不会改变LIS的性质的,最后g的结果不是所需的LIS,这里要注意一下。 #include<iostream>#include

HDU1028 Ignatius and the Princess III(整数拆分:母函数||DP)

题意: 给出一个值n,问有几种不同的拆分方法。 要点: 可以用母函数或DP来做,这里说一下母函数,基本思路是:写成(1+x^2+x^3+x^4……x^n)*(1+x^2+x^4+……)*(1+x^3+x^6+……)……这样,然后利用循环从每个括号开始算起,用c1存储前一次算出的所有指数对应的系数,c2暂存算上当前括号的对应系数,最后c1[n]就是答案。 母函数: 18281776201

[kuangbin带你飞]专题十二 基础DP1 -B - Ignatius and the Princess IV

“OK, you are not too bad, em… But you can never pass the next test.” feng5166 says. “I will tell you an odd number N, and then N integers. There will be a special integer among them, you have to tel

2534: The Hero Rescued The Princess

2534: The Hero Rescued The Princess ResultTIME LimitMEMORY LimitRun TimesAC TimesJUDGE3s65536K30892Standard 美丽的公主被关在古老的施了咒语的城堡中,你作为当今世上最勇敢的英雄,决定救出这位美丽的公主。 如果你成功了,最后公主就会嫁给你。当然故事有点俗套,至少如果你把她救出了,我会免费送