2016 苏州大学程序设计校赛题解 #1

作者: shad0w_walker(admin) 分类: 算法 发布时间: 2016-11-21 23:09 ė 6 5条评论

题目链接:2016苏州大学ACM-ICPC集训队招新第一场-试题卷

备用链接

分数查询入口:点击此处

人来的出乎意料的少,但还是感谢诸位的到来,这场题目还是比较水的,一些难题都被审题人删了。

作为审题人我已经尽量做到让题面能够被人类看懂了,毕竟代表了101阅读理解最低水平。

另外对非计科院的同学说声抱歉,因为考虑到计科院所以程序题全是你们没学过的python,反而会C的优势没了。

再说一遍,请想入队参加比赛的同学找机会学习C语言。

 

选择

BCCCBD

题5:模拟了一个数据结构——栈。

题6:因为可以攻击所在的行列,那么显然每一行只能放一个,选择放5个的行可以有\(C_{7}^{5}\)种,再选择列,可以有\(C_{8}^{5}\)种。

现在可以得到一个5*5的棋盘,所以就是\(A_{5}^{5}\)了,总的来说答案是\(C_{7}^{5}*A_{8}^{5}\)或者\(C_{8}^{5}*A_{7}^{5}=141120\)。

题7:只要不选D消极比赛即可。

 

填空

1、e、φ+1或1/φ或\(\frac{\sqrt{5}+1}{2}\)、\(\ln 2\)

有一位同学写了\(\lim_{x\rightarrow\infty }\sum_{i=1}^{n}\frac{(-1)^{i+1}}{i}\)?

2、86

抱歉题目好像说了一大堆废话,因为本来这题后面还有比较难的一小问被审题人去掉了。

3、35

基本组合数学

4、42

递推一下。先+1s到13然后不断+10s

5、168、480

出题人原意是:两个伤害分别为a和b,那么设x和y为答案

a^2=(x+y)^2=x^2+y^2+2*xy;

b=x*y/gcd(a,b);

x*y=gcd(a,b)*b;

d=x-y=sqrt(a^2-4b);

x=a+d/2;

y=a-x;

6、2和3和5

从1开始将一个正方形不断分割为小正方形,可以构造出所有解。

 

程序

1、9377

出题人很伤心,生气地把代码丢在我脸上,他说你们这个题都做不出来期中考一定不能及格哼。

2、y x%y x%y y

3、233 在递增数组a中找到最后一个不大于p的数。说到二分查找也对

499 在单峰数组a中找到最大值。说到三分或者找最大值等也对

 

阅读

1、2

哦?出题人英语水平一定很高

2、13

任何一种字母取两个序列中会出现两个相同的数,一定不是上升序列,所以每种字母取一个,从小到大一次赋值,所以答案就是出现的字母种类数。

 

简答

1、随便写出一种即可,例如2、3、4、6、9、12

首先我们可以构造三个数使得它们的最小公倍数等于它们相加之和:

1 2 3

再仔细观察一下可以发现扩大倍数是不影响的:

2 4 6

3 6 9

我们就可以利用{1,2,3}这一组特殊的数据构造出奇数个的所有情况:

1 2 3 12 18

假设要求构造\(n\)(\(n\)为奇数)个,那么我们记前\(n-2\)个数的数字之和为\(x\),可以得到第\(n-1\)个数字为\(2x\),第\(n\)个数字为\(3x\)。这样子大概奇数个的就全解决了。

那么\(n\)为偶数时呢?很简单的,只要构造\(n=4\)的一组数据,那就仍然可以递推了:

1 2 6 9

1 4 5 10

 

扩展到\(n=6\)时,分别可以得到:

1 2 6 9 36 54

1 4 5 10 40 60

……

 

当然这样的可以构造很多很多的。另外也可以证明:构造不出来两个正整数使得它们相加之和等于它们的最小公倍数,有兴趣的可以想一下。

 

2、

(解答一)将所有数排序,取前面一半放在a2,a4,a6… 位置,后一半放在a1,a3,a5… 位置。复杂度:O(n * logn)。

(解答二)从头开始相邻数两两比较,不满足条件就交换两数,可以证明一定可行。复杂度:O(n),满分解答。

 

3、找出任意一种方案还是挺简单的,毕竟对每个位置最多只要操作一次,多一次等于撤销一次操作。

(解答一)把每个格子设为一个变量,手解模域为2的高斯消元(加分)

(解答二)观察

(解答三)写程序暴力

 

 

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/542.html

0

5条评论

  1. ramay7 2016年11月22日 11:37 回复

    GKP老师劲啊!!!

    1. shad0w_walker(admin)
      shad0w_walker(admin) 2016年11月23日 00:20 回复

      101最大的腿,你憋说话

  2. stjean 2016年11月23日 13:46 回复

    GKP老师劲啊!!

    1. shad0w_walker(admin)
      shad0w_walker(admin) 2016年11月23日 13:48 回复

      你有毒啊骚猪!

  3. hollowstory 2016年11月23日 15:51 回复

    GKP老师真劲!!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部