嗯嗯，参加了之后才知道这种地方不是我等渣渣能去的地方 _(:3」∠)_ 虽然在 hihoCoder 上只要小数据能通过就可以进初赛，但是小数据排名的第一名三项全 AC，罚时只有两个多小时 _(:3」∠)_（虽然由于大数据没过而排名后延了，但现在的第一名还是两个多小时 orz），而且在讨论里他们说到什么“模拟退火”，完全听不懂 _(:3」∠)_ 果然我等只做了两题而且大数据全部 TLE 的渣渣只有当炮灰的命……
咳咳，炮灰归炮灰，还是来看看题目吧，嗯，解题什么的还是挺好玩的……
顺便，没有 JavaScript 差评
题目1 : 2月29日
时间限制:2000ms
单点时限:1000ms
内存限制:256MB描述
给定两个日期，计算这两个日期之间有多少个2月29日（包括起始日期）。
只有闰年有2月29日，满足以下一个条件的年份为闰年：
1. 年份能被4整除但不能被100整除
2. 年份能被400整除
输入
第一行为一个整数T，表示数据组数。
之后每组数据包含两行。每一行格式为”month day, year”，表示一个日期。month为{“January”, “February”, “March”, “April”, “May”, “June”, “July”, “August”, “September”, “October”, “November” , “December”}中的一个字符串。day与year为两个数字。
数据保证给定的日期合法且第一个日期早于或等于第二个日期。
输出
对于每组数据输出一行，形如”Case #X: Y”。X为数据组数，从1开始，Y为答案。
数据范围
1 ≤ T ≤ 550
小数据
2000 ≤ year ≤ 3000大数据
2000 ≤ year ≤ 2×10^9样例输入
4
January 12, 2012
March 19, 2012
August 12, 2899
August 12, 2901
August 12, 2000
August 12, 2005
February 29, 2004
February 29, 2012样例输出
Case #1: 1
Case #2: 0
Case #3: 1
Case #4: 3此题小数据最终通过率为 89%，大数据通过率为 48% (2827/5870)
嗯，直觉上感觉要用到动态多维数组什么的，Google 了一下大概了解了怎么用，各种填坑后花了两小时完成了这玩意 orz
不过比赛结束前同学说代码有些逻辑有些问题，可以试试改一下语句顺序减少运算，所以刚刚把代码改好后发现已经不能提交运行了 orz 所以也不知道这个方法能不能过……
另外这里可以用一个足够大的静态数组，这样可以不用动态分配内存，不过哪一个比较好就不清楚了 orz 并不熟悉 C 语言
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <stdio.h> #include <stdlib.h> #include <string.h> int getMonth(char *month) { char *list[12] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" , "December"}; //printf("%s\n", month); if (0 == strcmp(month, list[0])) return 1; else if (0 == strcmp(month, list[1])) return 2; else if (0 == strcmp(month, list[2])) return 3; else if (0 == strcmp(month, list[3])) return 4; else if (0 == strcmp(month, list[4])) return 5; else if (0 == strcmp(month, list[5])) return 6; else if (0 == strcmp(month, list[6])) return 7; else if (0 == strcmp(month, list[7])) return 8; else if (0 == strcmp(month, list[8])) return 9; else if (0 == strcmp(month, list[9])) return 10; else if (0 == strcmp(month, list[10])) return 11; else if (0 == strcmp(month, list[11])) return 12; else return 0; } int main(void) { /*char m[9]; int n; scanf("%s", &m); printf("%s\n", m); n = getMonth(m); printf("%d\n", n); */ int count, i, j, y, r, ***items; char m[9]; scanf("%d", &count); items = (int***)malloc(count * sizeof(int**)); for(i = 0; i < count; i++) { items[i]=(int**)malloc(2 * sizeof(int*)); for(j = 0; j < 2; j++) { items[i][j]=(int*)malloc(3 * sizeof(int)); scanf("%s %d, %d", &m, &items[i][j][1], &items[i][j][2]); items[i][j][0] = getMonth(m); } } for(i = 0; i < count; i++) { r = 0; for (y = items[i][0][2]; y < items[i][1][2]; y++) { if (y % 4 == 0 && y % 100 != 0 || y % 400 == 0) { ++r; } } if (items[items[i][0][2]][0][0] >= 3) --r; if (items[items[i][1][2]][1][0] > 2 || (items[items[i][1][2]][1][0] == 2 && items[items[i][1][2]][1][1] == 29)) ++r; printf("Case #%d: %d\n", i + 1, r); } // 此处释放内存似乎并不彻底，三维数组的内存好像没有释放 for(i = 0; i < count; i++) { free(items[i]); } free(items); //system("pause"); return 0; } |
附历次提交代码：
题目2 : 回文字符序列
时间限制:2000ms
单点时限:1000ms
内存限制:256MB描述
给定字符串，求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。例如字符串aba中，回文子序列为”a”, “a”, “aa”, “b”, “aba”，共5个。内容相同位置不同的子序列算不同的子序列。
输入
第一行一个整数T，表示数据组数。之后是T组数据，每组数据为一行字符串。
输出
对于每组数据输出一行，格式为”Case #X: Y”，X代表数据编号（从1开始），Y为答案。答案对100007取模。
数据范围
1 ≤ T ≤ 30
小数据
字符串长度 ≤ 25大数据
字符串长度 ≤ 1000样例输入
5
aba
abcbaddabcba
12111112351121
ccccccc
fdadfa样例输出
Case #1: 5
Case #2: 277
Case #3: 1333
Case #4: 127
Case #5: 17此题小数据最终通过率为 90%，大数据通过率为 25% (684/2719)
这一题咱并没有看懂题目，所以看菊苣怎么解释了 _(:3」∠)_
题目3 : 基站选址
时间限制:2000ms
单点时限:1000ms
内存限制:256MB描述
需要在一个N × M的网格中建立一个通讯基站，通讯基站仅必须建立在格点上。
网格中有A个用户，每个用户的通讯代价是用户到基站欧几里得距离的平方。
网格中还有B个通讯公司，维护基站的代价是基站到最近的一个通讯公司的路程（路程定义为曼哈顿距离）。
在网格中建立基站的总代价是用户通讯代价的总和加上维护基站的代价，最小总代价。
输入
第一行为一个整数T，表示数据组数。
每组数据第一行为四个整数：N, M, A, B。
接下来的A+B行每行两个整数x, y，代表一个坐标，前A行表示各用户的坐标，后B行表示各通讯公司的坐标。
输出
对于每组数据输出一行”Case #X: Y”，X代表数据编号（从1开始），Y代表所求最小代价。
数据范围
1 ≤ T ≤ 20
1 ≤ x ≤ N
1 ≤ y ≤ M
1 ≤ B ≤ 100小数据
1 ≤ N, M ≤ 100
1 ≤ A ≤ 100大数据
1 ≤ N, M ≤ 107
1 ≤ A ≤ 1000样例输入
2
3 3 4 1
1 2
2 1
2 3
3 2
2 2
4 4 4 2
1 2
2 4
3 1
4 3
1 4
1 3样例输出
Case #1: 4
Case #2: 13此题小数据最终通过率为 91%，大数据通过率为 17% (330/1925)
嗯，这题还是能看懂的，计算起来也不算麻烦，只是在写代码时有一段地方由于脑残改错变量导致后面的代码跑错了 orz 这就是那堆 RE 的原因……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <stdio.h> #include <stdlib.h> #include <math.h> int main(void) { long int count, settings[4], ****items, i, j, k, l, m, n, x, y; scanf("%d", &count); items = (long int****)malloc(count * sizeof(long int***)); for (i = 0; i < count; i++) { items[i] = (long int***)malloc(2 * sizeof(long int**)); scanf("%d %d %d %d", &settings[0], &settings[1], &settings[2], &settings[3]); //printf("%d %d %d %d", settings[0], settings[1], settings[2], settings[3]); items[i][0] = (long int**)malloc(settings[2] * sizeof(long int*)); items[i][1] = (long int**)malloc(settings[3] * sizeof(long int*)); for (j = 0; j < settings[2]; j++) { items[i][0][j] = (long int*)malloc(2 * sizeof(long int)); scanf("%d %d", &items[i][0][j][0], &items[i][0][j][1]); //printf("%d %d\n", items[i][0][j][0], items[i][0][j][1]); } for (j = 0; j < settings[3]; j++) { items[i][1][j] = (long int*)malloc(2 * sizeof(long int)); scanf("%d %d", &items[i][1][j][0], &items[i][1][j][1]); //printf("%d %d\n", items[i][1][j][0], items[i][1][j][1]); } } for (i = 0; i < count; i++) { n = -1; for (j = 1; j <= settings[0]; j++) { for (k = 1; k <= settings[1]; k++) { m = 0; y = -1; for (l = 0; l < settings[2]; l++){ m += (items[i][0][l][0] - j ) * (items[i][0][l][0] - j) + (items[i][0][l][1] - k) * (items[i][0][l][1] - k); //printf("%d %d 1 %d %d %d\n", j, k, l, m, n); } for (l = 0; l < settings[3]; l++){ x = abs(items[i][1][l][0] - j) + abs(items[i][1][l][1] - k); if ((x < y) || (y == -1)) y = x; //printf("%d %d 1 %d %d %d\n", j, k, l, m, n); } m += y; //printf("------\n"); if ((m < n) || (n == -1)) n = m; } } printf("Case #%d: %d\n", i + 1, n); } // 同样没有完全释放内存，不知道为什么，似乎如果用完全释放内存的代码（注释部分）会编译错误，不知道是不是写错了 for(i = 0; i < count; i++) { /*for(j = 0; j < settings[2]; j++) { free(items[i][0][j][0]); free(items[i][0][j][1]); free(items[i][0][j]); }*/ /*for(j = 0; j < settings[3]; j++) { free(items[i][1][j][0]); free(items[i][1][j][1]); free(items[i][1][j]); }*/ /*for(j = 0; j < 4; j++) { free(settings[j]); }*/ free(items[i][0]); free(items[i][1]); free(items[i]); } free(items); //system("pause"); return 0; } |
最后还是历次提交代码：
- 334793, RE|TLE
- 334951, RE|TLE
- 335122, RE|TLE
- 335456, RE|TLE
- 335511, RE|TLE
- 339325, WA|TLE
- 340030, WA|TLE
- 340511, CE|CE
- 340532, AC|TLE
- 340558, AC|TLE
其他
嗯，感觉怎么说呢，嗯，编写代码可能是件挺痛苦的事——当然确实挺有趣，在没有太多压迫的情况下——不过最终通过的时候还是很高兴的，嗯，简单来说就是如释重负吧？
另外还去看了另一个 Code Hunt 的试题，题目还算简单，就是执行一段代码，右边给出预期结果和输出结果，然后改代码实现结果一致。但语言只有 C# 和 Java，所以刚开始并没有做。后来尝试做了一下，据说 C 与 C# 的语法挺类似（谁说的给我站出来！），所以用了 C#。不过 Sector 00 做到一半就卡在 for 循环给数组赋值上了，网上各种找解决方案都没通过。最后尝试用 Java，结果代码几乎没有变动居然就给通过了 _(:3」∠)_ 接下来用蹩脚的 Java （其实是 JavaScript）通过了 Sector 00 _(:3」∠)_ 接下来的题目懒得做了……
嗯，以上 _(:3」∠)_
终于更新了啊 第一时间来围观
反正我是不懂啦
仰望菊苣
突然发现第一题可以直接对两个输入的年份除以四、除以一百、除以四百然后再进行计算 _(:3」∠)_ 脑残了，不需要 for 循环
能去这种比赛什么的还是很厉害的嘛
@Kirito 只是资格赛而已，不是过初赛，而且初赛由于班级春游冲突所以估计要杯具 _(:3」∠)_
第一题用java不是太简单。。。
写惯 Swift 之后再也写不来 C 了_(:з」∠)_字符串的处理太麻烦了
@lovee 其实用了 JavaScript 来用 C 也觉得 C 太麻烦了 _(:3」∠)_
@864907600cc @864907600cc 毕竟是底层一些的语言
cc炸屍了(╯‵□′)╯︵┻━┻。。。我也炸一下ノ( ◕‿‿◕ )ノ
这是牛人的工作
厉害呀！
第一题用C和数组貌似挺好解
杀进你们学校ACM队木有？看你这么感兴趣的样子，训练一下子，前途大大的有！
@七夕之雪
看你这几题，还是偏向野路子呢。。编程之美资格赛题目还是简单的，初赛就要努把力啦，我记得去年初赛在hihoCoder501名，也是囧。想练习一些算法相关的东西，可以看刘汝佳出的几本书呢，很不错。
@七夕之雪 嗯，其实并不算是对算法很感兴趣，当时 c 也没学多少，就当玩玩而已，只是比较喜欢那种解决问题的乐趣而已
@864907600cc 这样啊..我说好好的一个美少女，怎么就步入歧途了呢，哈哈。享受到愉快就好，过的好快啊。。
竟然更新了！ _(:3」∠)_ 虽然现在才看到。 嘛， 开心就好啦！
好久不见
COOL~