2017年浙江理工大学程序设计竞赛校赛 题解&源码(A.水, D. 简单贪心 ,E.数论,I 暴力)
2017年浙江理工大学程序设计竞赛校赛 题解&源码(A.水, D. 简单贪心 ,E.数论,I 暴力)
Problem A: 回文
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 1719 Solved: 528
Description
小王想知道一个字符串是否为ABA’型字符串。ABA’型字符串的定义：S=ABA’，A，B，A’都是原字符串的子串(不能是空串），A’的意思是A的反转串，B不一定要和A或A’不同。符合ABA’型的例如："aba”，"acbbca”，"abcefgcba”等。"Abcefgcba”是ABA’型，因为它能找到一组对应的A（"abc”)，B(”efg”)和A’("cba")满足定义。
Input
第一行给测试总数T(T <= 1000)，接下来有T组测试数据。
每组测试数据有一行字符串S(1 <= |S| <= 50000)，字符串保证只有小写或大写英文字母。
Output
每组测试数据输出一行，如果S是ABA’型字符串，输出"YES”，否则输出"NO"。
Sample Input
5
abA
gg
Codeforces
acmermca
myacmSample Output
NO
NO
NO
YES
YESHINT
题目链接:http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=0
分析：这题好水好水，只要当字符串的长度大于等于3，第一项和最后一项相等就输出YES，否则输出NO，字符串长度小于等于2，一定输出NO
下面给出AC代码：
1 #include <bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5 int T;
6 char s[50010];
7 while(scanf("%d",&T)!=EOF)
8 {
9 while(T--)
10 {
11 scanf("%s",s);
12 int len=strlen(s);
13 if(len==1||len==2)
14 printf("NO\n");
15 else
16 {
17 if(s[0]==s[len-1])
18 printf("YES\n");
19 else printf("NO\n");
20 }
21 }
22 }
23 return 0;
24 }Problem B: RPG的地图
Time Limit: 3 Sec Memory Limit: 128 MB Submit: 103 Solved: 4
Description
lyf有天晚上做梦，梦见自己去游戏公司实习了。那里正准备做一款RPG游戏，lyf在做游戏地图时遇到这样的一个问题：
游戏里有一个不规则的地图，可能是凹多边形，也可能是凸多边形，已经处理出了这个多边形轮廓的坐标，并且把这些坐标以逆时针的顺序给出。比如说下面这个图形：
那么我们会以（4,0），（3,3），（0,3），（-2,0），（0，-3），（3，-3）的顺序把坐标给出。
现在lyf要完成的任务是要完成m次询问，每次给出一对坐标（x, y）,要判断出（x, y）是否在给出的多边形内。
请帮lyf解决这个问题吧。
Input
有多组数据（组数<=10）。
每组数据输入形如：
n m
x1 y1
x2 y2
....
xn yn
askX1 askY1
askX2 askY2
...
askXm askYm
n（3 <= n <= 100000）表示多边形轮廓上的点个数，它们以逆时针的顺序给出, 给出的点保证能构成多边形。
m (1 <= m <= 200000) 表示询问次数， 询问（askXi, askYi）是否在多边形内，注意如果在多边形的边上，也认为在多边形内部。
-1000<=xi, yi, askXi, askYi<=1000, 它们都为整数。
Output
每组输出形如：
ans1
ans2
...
ansm
ansi：表示如果第i次询问的坐标在多边形内，输出“Yes”, 否则输出“No”。
Sample Input
6 3
4 0
3 3
0 3
-2 0
0 -3
3 -3
0 0
4 1
-1 2Sample Output
Yes
No
NoHINT
题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=1
分析：好吧，我没做出来！
Problem C: 国王的命令
Time Limit: 7 Sec Memory Limit: 128 MB Submit: 75 Solved: 10
Description
A国有n个城市，非常巧合的是这n个城市刚好构成了一棵树。A国的国王是位日理千机的贤君，为了能及时发布自己的命令，于是决定在每个城市都建造一个信号塔，信号塔能传播信息，城市i的信号塔的传播能力是val(i): 表示如果城市i和城市j的dist(i,j) <= val(i)，那么就能把信息从城市i传到城市j(注意能否把信息从城市j传到城市i, 则要满足dist(i,j) <=val(j))。国王所在的城市为1号城市，国王想尽可能快的让自己发布的命令在i号城市被执行，所以他希望把命令从1号城市传播到i号城市这个过程中的传播次数尽可能少，如图：
val(1)=1, val(2)=3, val(3)=1, val(4)=1, val(5)=1, val(6)=1, val(7)=1, val(8)=1;
所以从1号城市传播到8号城市的最少传播次数为2，有两种方法：
1->2->8,或者1->3->8，而其他方式都大于2.
dist(i, j) : 表示在树上，从节点i走到节点j所需要走过的最少的边数，如上图中，
dist(2, 8) = 3, dist(5, 6) = 2等等。
Input
多组测试数据。每组输入如下
第一行输入一个n表示树有n个点。(2 <= n <= 100000)
第二行输入n个数。第i个数表示i号城市val(i)(val(i) >= 1)
然后输入n-1行。每行两个数字u,v表示一条边。 1 <= u,v <= n
Output
每个测试组输出n-1个数：
ans2 ans3 ... ansn
ansi: 表示国王的命令从1号城市到i号城市所需的最少传播次数。
Sample Input
8
1 3 1 1 1 1 1 1
1 2
1 3
1 4
2 5
2 6
3 7
3 8Sample Output
1 1 1 2 2 2 2HINT
题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=2
Problem D: 买iphone
Time Limit: 3 Sec Memory Limit: 128 MB Submit: 1855 Solved: 348
Description
自从上次仓鼠中了1000万彩票后，彻底变成了土豪了，一群人愿意认他做干爹，仓鼠决定送他的干儿子每人一部iphone。仓鼠今天带了一群人去买iphone，每个人身上都背着一个大背包，只有3种背包，分别能装a，b，c个iphone，仓鼠希望每个人都能用iphone装满自己的背包。仓鼠有n个干儿子，也就是要买n部手机，仓鼠带了k个人去买手机，问是否存在一种情况能让每个买iphone的人的背包都装满
Input
输入包含多组测试数据，每组一行，包含5个整数n, k, a, b, c
(1 <= n, k , a, b, c <= 10000)
abc可以相同
Output
如果存在输出Yes，否则输出No
Sample Input
10 3 3 3 4
20 7 1 1 1
80 3 100 3 3
15 4 3 5 6Sample Output
Yes
No
No
YesHINT
样例一3个人分别带大小为 3 3 4的背包去买手机正好每个人都装满
样例二 很明显只有一种背包，全部都是1也无法买20部iphone
样例四 4个人分别带大小为 3 3 3 6的背包去买手机正好每个人都装满
题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=3
题解：暴力
没想到这个题纯暴力就能过了，当然了不是k^2级别的。一共有k个人去装手机，假设有x个人装a,y(y小于k-x)个人装b,剩下的人装c，只要判断出x*a+y*b+(k-x-y)*c==n的情况就可以了
下面给出AC代码：
1 #include <bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5 int n,k,a,b,c;
6 int flag;
7 while(scanf("%d%d%d%d%d",&n,&k,&a,&b,&c)!=EOF)
8 {
9 flag=0;
10 for(int i=0;i<=k;i++)
11 {
12 for(int j=0;j<=k-i;j++)
13 {
14 if(i*a+j*b+(k-i-j)*c==n)
15 {
16 flag=1;
17 break;
18 }
19 if(flag)
20 break;
21 }
22 }
23 if(flag)printf("Yes\n");
24 else printf("No\n");
25 }
26 return 0;
27 }Problem E: 同源数
Time Limit: 3 Sec Memory Limit: 128 MB Submit: 1344 Solved: 244
Description
如果x和y的质因子集合完全相同，那么我们就说他们是同源的。
比如说18 = 2 * 32，12 = 3 * 22；
Input
本题有多组数据（组数 <= 555555）。
每组数据输入形如：
x y
x, y为整数（1 <= x, y <= 1e18）
Output
输出形入：
ans
如果x, y为同源数，那么ans为”Yes”, 不然为”No”.
Sample Input
18 12
2 3Sample Output
Yes
NoHINT
题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=4
题解：数论，唯一分解定理，gcd(),
这个题是分析的时间最长的一个题了，最后想出解法后还因为没考虑到全面的情况，又花了很长的时间。首先读完题目的第一反应就是唯一分解定理，然后就卡壳了。突然想到了gcd(),就在纸上分析了一下，慢慢的才ac的。
同源数，也就是他们的质因子的元素是相同的（个数不一定相同）。假如a=2*3*3*5*7,b=2*2*3*5*5*7,他们两个是同源数，对a,b求gcd(a,b)=g;显然g分解后质因子一定包含他们共有的质因子，即2*3*5*7，然后a,b都除以他们的质因子，如果两个数是同源数的话，那么让a一直除以a和g的gcd(),a=a/gcd(a,g),直到a==1或gcd(g,a)为止，如果a==1的说说明了a的质因子只包含了和g相同的质因子，如果a!=1&&gcd(a,g)==1的话，说明a和g互素，也就是a中的质因子有和g中的质因子不同的元素。同理对b也这样处理。如果a==1&&b==1的话说明是同源数，否则不是。
特殊处理a==b和a==1||b==1的情况。
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 ll gcd(ll a,ll b)
5 {
6 return b==0?a:gcd(b,a%b);
7 }
8 int main()
9 {
10 ll a,b;
11 while(scanf("%lld%lld",&a,&b)!=EOF)
12 {
13 if(a==b)
14 printf("Yes\n");
15 else if(a!=1&&b==1)
16 printf("No\n");
17 else if(a==1&&b!=1)
18 printf("No\n");
19 else
20 {
21 ll t=gcd(a,b);
22 ll m=a/t;
23 ll n=b/t;
24 ll mm=1,nn=1;
25 while(1)
26 {
27 ll k=gcd(m,t);
28 m=m/k;
29 if(m==1)
30 break;
31 else if(k==1)
32 {
33 mm=0;
34 break;
35 }
36 }
37 while(1)
38 {
39 ll k=gcd(n,t);
40 n=n/k;
41 if(n==1)
42 break;
43 else if(k==1)
44 {
45 nn=0;
46 break;
47 }
48 }
49 if(mm&&nn)
50 printf("Yes\n");
51 else printf("No\n");
52 }
53 }
54 return 0;
55 }Problem F: 垃圾生成器
Time Limit: 2 Sec Memory Limit: 128 MB Submit: 89 Solved: 19
Description
仓鼠非常爱干净，但是又不想花时间打扫寝室。于是有一天，他心血来潮想算一下他的寝室能够生成垃圾的期望数量，问题如下：
我们把仓鼠的寝室抽象成一个1行n列的网格图，在这个网格图中会随机生成垃圾，每个垃圾占x个连续的网格，垃圾不能放到网格图外，也不能相互重叠，直到网格图中放不下任何垃圾为止。
比如说n = 3, x = 2，会生成如下两种情况：
请你帮仓鼠计算一下生成垃圾的期望数量。
Input
多组测试
每组数据输入形如：
n x
（1 <= n,x <= 100000）
Output
输出生成垃圾的期望个数，请保留到小数点后5位。
Sample Input
3 2
4 2Sample Output
1.00000
1.66667HINT
题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=5
Problem G: 最佳淘汰算法
Time Limit: 12 Sec Memory Limit: 128 MB Submit: 366 Solved: 53
Description
Lyf在做操作系统作业的时候，遇到了一题要他实现下Opt算法（全称页面置换最佳淘汰算法）。可是Lyf发现最近好忙啊，于是他想请他的学弟,学妹们帮他来完成。
作业里的内容是这样的：
提出最佳页面淘汰算法。是操作系统存储管理中的一种全局页面替换策略当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距现在最长时间后要访问的页面。它所产生的缺页数最少，然而，却需要预测程序的页面引用串，这是无法预知的，不可能对程序的运行过程做出精确的断言。但是我们在这里会告诉你一个已经存在的一个页面序列，请输出最终在内存中存在的页面即可。
Input
有多组数据（组数<=21）。
每组数据输入形如：
n m
a1 a2 a3 a4 .... an
其中n(n，m<=500000)表示已知页面序列的长度。
ai(0<=ai<=100000)表示页面类型，为整数。
m为在内存中保存的页面类型数量。
Output
输出形如：
b1 b2 b3 .... bk
具体要求请仔细阅读样例和Hint。
Sample Input
21 3
7 0 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
3 2
2 1 3
4 3
1 0 0 1Sample Output
7 0 1
3 1
1 0HINT
第一个样例：
访问页面7，当前内存中页面数为0，没有达到3页，放入7，当前内存中的页面为（7）
访问页面0，当前内存中页面数为1，没有达到3页，放入0，当前内存中的页面为（7,0）
访问页面0，已经在内存中存在，不做任何操作，当前内存中的页面为（7,0）。
访问页面1，当前内存中页面数为2，没有达到3页，放入1，当前内存中的页面为（7,0,1）。
访问页面2，内存中页数已经达到3页，开始淘汰页面。我们发现在内存中的7下次出现的位置为19, 0为6,1为15，所以7是最长时间后才要访问的，所以7被淘汰。
现在内存中的三个页面变为（2，0，1）。
访问页面0，我们发现0已经存在于我们的内存中，于是我们不做任何如理，继续访问下一个页面。以此类推。
注意如果在某次插入时，在内存中有多种页面在淘汰后不会再被访问，那么我们这次淘汰页面类型号最大的，请看第二个样例。
题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=6
Problem H: 玩具
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 795 Solved: 162
Description
商店有n个玩具，第i个玩具有价格a[i]和快乐值b[i]。有一天，小王来到商店想买一些玩具，商店老板告诉他，如果他买的所有玩具的位置是连续的，那么老板答应小王购买的所有玩具中某一个可以免费。小王接受老板的提议，他现在有零花钱k可以用来买玩具，那么他能获得的最大的快乐值是多少。
Input
第一行给测试总数T(T <= 100)，接下来有T组测试数据。
每组测试数据第一行有两个数字n(1 <= n <= 5000)和k(0 <= k <= 1000000000)。
第二行有n个数字，第i个数字表示第i个玩具的价格a[i](1 <= a[i] <= 1000000)。
第三行有n个数字，第i个数字表示第i个玩具的快乐值b[i](1 <= b[i] <= 1000000)。
Output
每组测试输出小王能获得的最大快乐值。
Sample Input
3
5 14
1 2 3 4 5
5 4 3 2 1
3 1
100 1000 10000
100 1000 10000
1 0
1000000
1000000Sample Output
15
10000
1000000HINT
题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=7
Problem I: 约素
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 1876 Solved: 489
Description
判断一个正整数n的约数个数是否为p，其中p是素数。
Input
第一行给测试总数T(T <= 10000)。
接下来有T行，每行有两个数字n(1 <= n <= 1000000000)和p(2 < p <= 1000000000)。
Output
每组测试数据输出一行，如果n的约数个数是p，输出“YES”，否则输出“NO”。
Sample Input
5
64 7
911 233
1080 13
1024 11
20170211 1913Sample Output
YES
NO
NO
YES
NOHINT
题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=8
题解：暴力求约数，常规技巧简化
约数，我都想问到底什么叫做约数。以前做的计算约数的个数的理解记得不是这样的来。这个题的约数就是让你暴力找一遍n%i==0时i的个数。而紫书上的约数的个数是表示质因子的个数相乘得来的。
当然这个也不能1-n暴力，因为对于n%x==0的话，也就得出了另一个约数：y=n/x,既然是约数，x,y都是小于n的，那么x从1开始一直到，n/x就可以了，此时当x增大的时候,n/x就在减小。知道x>=n/x.特别处理，当x==n/x的时候约数的个数+1，否则+2（x和n/x都是n的约数）
下面给出AC代码：
1 #include <bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5 int T;
6 int n,m;
7 while(scanf("%d",&T)!=EOF)
8 {
9 while(T--)
10 {
11 scanf("%d%d",&n,&m);
12 int sum=0;
13 for(int i=1;i<=n/i;i++)
14 {
15 if(n%i==0)
16 {
17 sum++;
18 if(i!=n/i)
19 sum++;
20 }
21 }
22 if(sum==m)
23 printf("YES\n");
24 else printf("NO\n");
25 }
26 }
27 return 0;
28 }