少女祈禱中...
Loading...
图片加载过慢?试试 从源站加载资源 X

ccloli

编程之美 2015 资格赛相关

嗯嗯,参加了之后才知道这种地方不是我等渣渣能去的地方 _(: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 语言

附历次提交代码:

题目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 的原因……

最后还是历次提交代码:

其他

嗯,感觉怎么说呢,嗯,编写代码可能是件挺痛苦的事——当然确实挺有趣,在没有太多压迫的情况下——不过最终通过的时候还是很高兴的,嗯,简单来说就是如释重负吧?

另外还去看了另一个 Code Hunt 的试题,题目还算简单,就是执行一段代码,右边给出预期结果和输出结果,然后改代码实现结果一致。但语言只有 C# 和 Java,所以刚开始并没有做。后来尝试做了一下,据说 C 与 C# 的语法挺类似(谁说的给我站出来!),所以用了 C#。不过 Sector 00 做到一半就卡在 for 循环给数组赋值上了,网上各种找解决方案都没通过。最后尝试用 Java,结果代码几乎没有变动居然就给通过了 _(:3」∠)_ 接下来用蹩脚的 Java (其实是 JavaScript)通过了 Sector 00 _(:3」∠)_ 接下来的题目懒得做了……

嗯,以上 _(:3」∠)_

  1. 雪见仙尊说道:

    终于更新了啊 第一时间来围观

    反正我是不懂啦

    Google Chrome 39.0.2171.99 Google Chrome 39.0.2171.99 Windows 7 x64 Edition Windows 7 x64 Edition
  2. 文科说道:

    仰望菊苣

    Unknown Unknown Unknown Unknown
  3. 864907600cc说道:

    突然发现第一题可以直接对两个输入的年份除以四、除以一百、除以四百然后再进行计算 _(:3」∠)_ 脑残了,不需要 for 循环

    Google Chrome 42.0.2311.90 Google Chrome 42.0.2311.90 Windows 8.1 x64 Edition Windows 8.1 x64 Edition
  4. Kirito说道:

    能去这种比赛什么的还是很厉害的嘛

    Google Chrome 41.0.2272.104 Google Chrome 41.0.2272.104 Mac OS X  10.10.3 Mac OS X 10.10.3
    1. 864907600cc说道:

      @Kirito 只是资格赛而已,不是过初赛,而且初赛由于班级春游冲突所以估计要杯具 _(:3」∠)_

      Google Chrome 42.0.2311.90 Google Chrome 42.0.2311.90 Windows 8.1 x64 Edition Windows 8.1 x64 Edition
  5. 天羽巧可说道:

    第一题用java不是太简单。。。

    Google Chrome 41.0.2272.89 Google Chrome 41.0.2272.89 Windows 7 x64 Edition Windows 7 x64 Edition
  6. lovee说道:

    写惯 Swift 之后再也写不来 C 了_(:з」∠)_字符串的处理太麻烦了

    Safari 8.0.5 Safari 8.0.5 Mac OS X  10.10.3 Mac OS X 10.10.3
    1. 864907600cc说道:

      @lovee 其实用了 JavaScript 来用 C 也觉得 C 太麻烦了 _(:3」∠)_

      Google Chrome 42.0.2311.135 Google Chrome 42.0.2311.135 Windows 8.1 x64 Edition Windows 8.1 x64 Edition
      1. @864907600cc @864907600cc 毕竟是底层一些的语言

        Firefox 39.0 Firefox 39.0 Ubuntu x64 Ubuntu x64
  7. p0i说道:

    cc炸屍了(╯‵□′)╯︵┻━┻。。。我也炸一下ノ( ◕‿‿◕ )ノ

    Google Chrome 42.0.2311.90 Google Chrome 42.0.2311.90 Windows 7 x64 Edition Windows 7 x64 Edition
  8. 木耳网说道:

    这是牛人的工作

    Firefox 37.0 Firefox 37.0 Windows 7 Windows 7
  9. Flippy说道:

    厉害呀!

    Firefox 35.0 Firefox 35.0 Windows 7 x64 Edition Windows 7 x64 Edition
  10. 千与琥珀说道:

    第一题用C和数组貌似挺好解

    Google Chrome 42.0.2311.135 Google Chrome 42.0.2311.135 Windows 7 Windows 7
  11. 七夕之雪说道:

    杀进你们学校ACM队木有?看你这么感兴趣的样子,训练一下子,前途大大的有!

    Google Chrome 43.0.2357.124 Google Chrome 43.0.2357.124 Mac OS X  10.10.3 Mac OS X 10.10.3
    1. 七夕之雪说道:

      @七夕之雪
      看你这几题,还是偏向野路子呢。。编程之美资格赛题目还是简单的,初赛就要努把力啦,我记得去年初赛在hihoCoder501名,也是囧。想练习一些算法相关的东西,可以看刘汝佳出的几本书呢,很不错。

      Google Chrome 43.0.2357.124 Google Chrome 43.0.2357.124 Mac OS X  10.10.3 Mac OS X 10.10.3
      1. 864907600cc说道:

        @七夕之雪 嗯,其实并不算是对算法很感兴趣,当时 c 也没学多少,就当玩玩而已,只是比较喜欢那种解决问题的乐趣而已

        Google Chrome 43.0.2357.78 Google Chrome 43.0.2357.78 Android 5.0.1 Android 5.0.1
        1. 七夕之雪说道:

          @864907600cc 这样啊..我说好好的一个美少女,怎么就步入歧途了呢,哈哈。享受到愉快就好,过的好快啊。。

          Google Chrome 43.0.2357.124 Google Chrome 43.0.2357.124 Mac OS X  10.10.3 Mac OS X 10.10.3
  12. Taobeier说道:

    竟然更新了! _(:3」∠)_ 虽然现在才看到。 嘛, 开心就好啦!

    Google Chrome 41.0.2272.118 Google Chrome 41.0.2272.118 GNU/Linux x64 GNU/Linux x64
  13. txh说道:

    好久不见

    Firefox 39.0 Firefox 39.0 Windows 7 x64 Edition Windows 7 x64 Edition
  14. LEO说道:

    COOL~

    Firefox 50.0 Firefox 50.0 Windows 10 x64 Edition Windows 10 x64 Edition

天羽巧可进行回复 取消回复