- 浏览: 308735 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
KIDx 的解题报告
http://codeforces.com/contest/4
以下省略头文件
A题
非一般的水
B题
题意:输入n和sum,再输入n个闭区间,每个区间找一个数,使得这些数的和等于sum,能找出输出"YES"并输出这些数【多种答案只要输出其中一种】,否则输出"NO"
简单构造一下解即可
C题
题意:输入一个用户名进行注册,如果该用户名之前木有被注册过,输出"OK",如果注册过在后面加个编号i,i从1开始,还存在,那么i++,直到可以注册为止,输出这个可以注册的用户名
注意一下这组数据:
用map暴力搞搞即可
D题
题意:输入n【信封个数】,w,h【卡片宽高】
是否存在x个信封组成的一叠信封使得x最大【这叠信封要严格有序,而且最小的信封必须要装得下卡片】
若存在,输出x以及这些信封【有序:从小到大】
若不存在,输出0,占一行
单调最长递增/减子序列模型,典型的dp水题
http://codeforces.com/contest/4
以下省略头文件
A题
非一般的水
int main() { int x; while (~scanf ("%d", &x)) { if ((x & 1) || x == 2) puts ("NO"); else puts ("YES"); } return 0; }
B题
题意:输入n和sum,再输入n个闭区间,每个区间找一个数,使得这些数的和等于sum,能找出输出"YES"并输出这些数【多种答案只要输出其中一种】,否则输出"NO"
简单构造一下解即可
int main() { int n, sum, i, a[35], b[35], x, y; while (~scanf ("%d%d", &n, &sum)) { x = y = 0; memset (a, 0, sizeof(a)); for (i = 0; i < n; i++) { scanf ("%d%d", a+i, b+i); x += a[i], y += b[i]; //x为最小和,y为最大和,可能形成的和为[x, y] } for (i = n - 2; i >= 0; i--) a[i] += a[i+1]; //a[i] = (a[i] + a[i+1] + … + a[n-1]) if (sum >= x && sum <= y) { puts ("YES"); for (i = 0; i < n; i++) { if (i > 0) printf (" "); int tp = min (b[i], sum-a[i+1]); sum -= tp; printf ("%d", tp); } printf ("\n"); } else puts ("NO"); } return 0; }
C题
题意:输入一个用户名进行注册,如果该用户名之前木有被注册过,输出"OK",如果注册过在后面加个编号i,i从1开始,还存在,那么i++,直到可以注册为止,输出这个可以注册的用户名
注意一下这组数据:
用map暴力搞搞即可
map<string, int> m; char ch[100005], s[100005+M]; //必须开够哦 int main() { int n, k, i, j, tp; while (~scanf ("%d", &n)) { m.clear(); while (n--) { scanf ("%s", s); if (m[s] == 0) puts ("OK"); else { tp = m[s]++; //tp获取s之前出现的次数,然后出现次数+1 k = 0; while (tp) { ch[k++] = tp % 10 + '0'; tp /= 10; } ch[k] = 0; //tp转为字符串加到s的后面 j = strlen (s); for (i = k - 1; i >= 0; i--) s[j++] = ch[i]; s[j] = 0; printf ("%s\n", s); } m[s]++; //s的出现次数+1 } } return 0; }
D题
题意:输入n【信封个数】,w,h【卡片宽高】
是否存在x个信封组成的一叠信封使得x最大【这叠信封要严格有序,而且最小的信封必须要装得下卡片】
若存在,输出x以及这些信封【有序:从小到大】
若不存在,输出0,占一行
单调最长递增/减子序列模型,典型的dp水题
struct Dp{ int v; int next; //记录路径 }dp[M]; struct envelope{ int w, h, i; }e[M]; bool cmp (envelope a, envelope b) { if (a.w == b.w) return a.h > b.h; return a.w > b.w; } int main() { int n, w, h, i, j, maxs, v, num; while (~scanf ("%d%d%d", &n, &w, &h)) { num = 1; for (i = 0; i < n; i++) { scanf ("%d%d", &e[i].w, &e[i].h); e[i].i = num++; //编号num独立,不受下面的if影响 if (e[i].w <= w || e[i].h <= h) i--, n--; } if (n <= 0) //没有信件可以装下卡片 { puts ("0"); continue; } for (i = 0; i < n; i++) //初始化 dp[i].v = 1, dp[i].next = -1; maxs = 1; sort (e, e+n, cmp); v = 0; for (i = 0; i < n; i++) //单调最长递减子序列模型,逆向方便记录路径 { for (j = i + 1; j < n; j++) { if (e[i].h > e[j].h && e[i].w > e[j].w && dp[j].v < dp[i].v + 1) { dp[j].v = dp[i].v + 1; dp[j].next = i; if (maxs < dp[j].v) maxs = dp[j].v, v = j; } } } printf ("%d\n", maxs); printf ("%d", e[v].i); for (i = dp[v].next; i != -1; i = dp[i].next) printf (" %d", e[i].i); printf ("\n"); } return 0; }
发表评论
-
《挑战编程》第11章-动态规划
2013-02-02 12:46 1468UVa 题号: 10131 Is Bigger Smart ... -
UVA 10201 Adventures in Moving - Part IV
2013-02-01 17:40 1660// [解题方法] // dp[i][j]表示到达第 ... -
UVA 10271 Chopsticks
2013-02-01 11:47 2199// [解题方法] // 将筷子按长度从大到小排序 ... -
UVA 10261 Ferry Loading
2013-01-31 16:34 3094// [题意] // n辆车按顺序安排在一个渡口的左 ... -
UVA 10003 Cutting Sticks
2013-01-31 15:35 1914// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 116 Unidirectional TSP
2013-01-30 09:53 1652// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 10154 Weights and Measures
2013-01-30 09:40 1959// 乌龟塔问题:每个乌龟有力量和重量,求最多能堆多少乌 ... -
UVA 10069 Distinct Subsequences
2013-01-29 16:23 1422// [解题方法] // dp[i][j]表示Z串的 ... -
UVA 10131 Is Bigger Smarter?
2013-01-29 16:01 1812// [解题方法] // 对大象增加编号属性i,以免 ... -
hdu 4170 Supply Mission
2012-09-22 10:03 1206KIDx的解题报告 ... -
UVA 10202 + HDU 1270 小希的数表
2012-09-15 20:01 2696KIDx的解题报告 题目链接:http://ac ... -
HDU 1979 Fill the blanks
2012-08-20 12:40 1077KIDx的解题报告 题目链接:http://ac ... -
【拓扑+DP】HDU 4109 Instrction Arrangement
2012-03-25 23:34 1376KIDx的解题报告 题目链接:http://acm ... -
【DP最大公共子序列】HDU 1159/1080/1503
2012-03-11 18:04 3116KIDx的解题报告 第一题(比较简单,不详细解): ... -
【最大不连续子序列和】HDU 2845 Beans
2012-03-08 22:09 3565KIDx的解题报告 题目链接:http://acm.h ... -
【数学】HDU 1719 Friend
2012-03-02 16:44 1163KIDx的解题报告 好久没写博客了,来题数学提提神 ... -
【BKDR_hash】HDU 2648 Shopping
2011-12-10 19:35 1780KIDx 的解题报告 题目链接:http://acm. ... -
Codeforces Beta Round #97 (Div. 2) 【完整题解】
2011-12-10 14:23 1500KIDx 的解题报告 题目链接:http://codeforc ... -
Codeforces Beta Round #96 (Div. 2)【完整题解】
2011-12-06 17:03 1444KIDx 的解题报告 题目链接:http://codeforc ... -
2011 ACM/ICPC 北京赛区现场赛 B题(hdu 4082)
2011-11-12 14:15 2065KIDx 的解题报告 题目链接:http://acm.hdu. ...
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
题解:6nlogn,先sort三个数组a,b,c, 六次枚举二分查找,再每次min找最小值,例如:先固定数组a,再在数组b,c中利用lower_bound找到第一个大于等于a[i]的数, #pragma GCC optimize(2) #include #define ll long long...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
传送门 A. EhAb AnD gCd 直接输出1,n-1即可 #include #include #include #include #include #include #include #include #include #include #define pb push_back #define lb lower_bound ...con
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
-2,4,5,5,6,8 要输出的序列应该是每次从前面选一个,然后从后面选一个 -2,8,4,6,5,5 然后把该序列倒着输出即可 代码: #include #include #include #include #include #include #include #include #...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...