Codeforces Beta Round #4 (Div. 2 Only) 【完整题解】

基德KID.1412

KIDx 的解题报告
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, y += b;//x为最小和，y为最大和，可能形成的和为[x, y]}for (i = n - 2; i >= 0; i--)a += a[i+1];//a = (a + 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, 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 == 0)puts ("OK");else{tp = m++;//tp获取s之前出现的次数，然后出现次数+1k = 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;s[j] = 0;printf ("%s\n", s);}m++;//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.w, &e.h);e.i = num++;//编号num独立，不受下面的if影响if (e.w <= w || e.h <= h)i--, n--;}if (n <= 0)//没有信件可以装下卡片{puts ("0");continue;}for (i = 0; i < n; i++)    //初始化dp.v = 1, dp.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.h > e[j].h && e.w > e[j].w && dp[j].v < dp.v + 1){dp[j].v = dp.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.next)printf (" %d", e.i);printf ("\n");}return 0;}