A. Avalon

题目大意：给出一个简单的多边形，判断它是否是镜面对称。

解题思路

本题是一道简单题，主要考核参赛选手的简单计算几何能力。

1、我们的基本解题思路是枚举两点，作其对称轴，然后判断该图形是否以其作为对称轴。

2、枚举两点只存在两种情况：⑴对称轴位于某相邻两点之间；⑵对称轴穿过其中一点。

3、枚举到对称轴之后以对称轴向两侧依次扩展判断各对点是否关于对称轴对称。

4、算法时间复杂度为O(n^2)。

 

B. ElGamal Decryption

题目大意

ElGamal公钥加密算法流程如下

用户A生成一个素数p,p的原根g和随机数x，计算h=gx。公布p,g,h为公钥。

用户B生成随机数y，计算a=gy,s=hy,b=m*s,m为需要加密的信息，(a，b)为密文

问：已知公钥和密文(a,b)的情况下，求原始信息m

解题思路

因为a=gy，使用离散对数可以得到y。然后计算s=hy ， 则m=b/s(mod p)

y=log_mod(g,a,p);

s=pow_mod(h,y,p);

m=divi(b,s,p);

即可求出m

离散对数使用哈希表

高幂取模使用二分

除法使用扩展欧几里德求逆元

时间主要消耗在离散对数，复杂度 O(p1/2)

 

C. The Least Palindromic Number

题目大意

定义：回文数是从前往后和从后往前得到的数是相同的。

给你一个正整数N，你需要找到比N大的回文数P，而且这个回文数是其中最小的那一个。

解题思路

本题是一道简单题，主要考核参赛选手控制程序的能力。

这个题有个简单的想法就是暴力枚举，但显然会超时。

因为回文数沿中点镜像对称。所以其后半部分基本是固定的，就是前半部分的镜像。

解题思路很简单，就是镜像比较前后部分，如果前面部分比后面大，后面部分就是前面部分的镜像；如果前面部分比后面小，将中位数加1后，同样后面部分就是前面部分的镜像。

注意中位数是9的情况，有进位。

最特殊的是N的每一位都是9，P的位长比N大1。而且具有10…01的形式。

 

D. GCD depth

题目大意

定义：GCD-depth(x,y)表示如下：

int GCD_depth( int x , int y ) {

if ( y == 0 ) return 0;

else return GCD_depth( y , x%y ) + 1 ;

}

 

现在题目给出x,要求求出在区间[y0,y1]之间的数y满足GCD-depth(x,y)=d条件的个数

解题思路

本题是一道简单题，主要考核参赛选手转化问题的基础能力。

虽然我们的y值得范围是10^9，但是我们由题目中给出的公式及x的范围可得出，在经过最多两次函数调用之后，y都相应的变小到可以暴力统计的范围了。

GCD-depth(x,y) =     y < x ,直接暴力统计

                     y = x ,特殊判断，结果为1

y > x ,调用GCD-depth两次之后，可以直接转化为y < x的情况，相当于d -= 2

1、求出所有0~(x-1)与x的GCD-depth值，并统计0~(x-1)的所有GCD-depth值出现的次数

2、对于y<x进行暴力统计，对于y>x看成三部分组成：0~（x-1）、若干个调用两次函数后转化为0~(x-1)的区间、y%x得到的尾部（暴力统计）

3、注意地方为：x = 0,特判，x == y时单独处理。

 

E. DIY Necklace

题目大意

给你一串包含n（0<n<=500000）个珠子的项链。每个珠子有自己的颜色，可能相同，可能不同。把珠子拆下来，按照原来的顺序从左往右摆成一行现在你从左往右一次挑选大于0个珠子DIY自己的相链，求有多少种DIY方法，两种方法称为不同当且仅当他们长度不一样或者对应某个珠子颜色不一样

解题思路

本题是一道动态规划题。假设我们先考虑所有珠子颜色都不一样，那么答案肯定为：2^n - 1;

那么相同的颜色的珠子的影响在哪里？如果按照所有珠子颜色不同来考虑所有问题，我们显然会重复计算了许多。我们假设“空集”为一种方法，f[i]表示为以珠子i，结尾的DIY方法的种数。所有珠子颜色不一样的话：

f[i] = f[0] + f[1] + ... + f[n-1]

对于颜色不同的话，假设珠子i颜色为c，颜色c在i之前出现的位置为j，那么在式子：

f[i] = f[0] + f[1] + ... + f[n-1] 中我们多算了f[0] + f[1] + ... + f[j-1]。

所以对于此时的f[i] = f[j] + ... +f[i-1]，最后 ans = sigma(f[i] , 1 <= i <= n)

 

F. Distinct Number

题目大意

该题让我们计算最小的t,使得 [12/n],[22/n],…,[t2/n] 中恰好有m个不同的整数，为此我们先需要计算对不同的n, t， [12/n],[22/n],…,[t2/n]中有多少个不同的整数，计次数为f(n,t)，这里[x]为取下整运算

例子(n=5,t=6)

 [12/5] [22/5] [32/5] [42/5] [52/5] [62/5]

0    0    1     3    5     7

f(5,6) = 5

 

解题思路

F(n,t)的计算依赖与下面这个性质

当 r<=(n+1)/2时, r2/n-(r-1)2/n<=1，有：[12/n],[22/n],…,[r2/n]跑遍[1/n]到[r2/n]间所有整数

当 r>=(n+1)/2时,r2/n-(r-1)2/n>=1，有：[r2/n],[(r+1)2/n]…各不相同

这样就不难得到f(n,t)的表达式

求得f(n, t)后可以用二分法查找求得最后的结果

 G. Election

 题目大意

本题为模拟题，关键是题意的理解，给定N个候选人，有M个人对其进行投票，已知每个投票人的优先选择顺序，要求每轮淘汰掉一个得票数最少的候选人。若几个人得票数相同，则淘汰编号较大的。最后剩下的编号即为结果。

如样例1：

3 4

10 1 4 2 3

15 3 2 1 4

12 4 3 2 1

（1）第一轮的得票情况为：

编号：1   2    3    4

得票：10  0    15   12     2号被淘汰，剩下进入第二轮

注意，每人在投票时都选择优先级高的候选人，除非这个人已经被淘汰了，才考虑第二个、第三个…

（2）第二轮

编号：1   3   4

得票：10  15   12     1号被淘汰

（3）第三轮

编号：3    4

得票：15  22        3号淘汰

剩下4号就是结果。

 

H. Largest Submatrix

思路：枚举+DP

只可以转为a、b、c三种字母，所以直接枚举，枚举可以转为a的矩阵、b的矩阵、c的矩阵，然后得到每个矩阵的最大矩阵值，再取其中的最大值~~

|返回 |   | 转到页头|