Problem A: 回文
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 1719 Solved: 528
Description
Input
Output
Sample Input
5
abA
gg
Codeforces
acmermca
myacm
Sample Output
NO
NO
NO
YES
YES
HINT
题目链接:http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=0
分析:这题好水好水,只要当字符串的长度大于等于3,第一项和最后一项相等就输出YES,否则输出NO,字符串长度小于等于2,一定输出NO
下面给出AC代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
char s[];
while(scanf("%d",&T)!=EOF)
{
while(T--)
{
scanf("%s",s);
int len=strlen(s);
if(len==||len==)
printf("NO\n");
else
{
if(s[]==s[len-])
printf("YES\n");
else printf("NO\n");
}
}
}
return ;
}
Problem B: RPG的地图
Time Limit: 3 Sec Memory Limit: 128 MB Submit: 103 Solved: 4
Description
Input
Output
Sample Input
6 3
4 0
3 3
0 3
-2 0
0 -3
3 -3
0 0
4 1
-1 2
Sample Output
Yes
No
No
HINT
题目链接: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号城市这个过程中的传播次数尽可能少,如图:
Input
Output
Sample Input
8
1 3 1 1 1 1 1 1
1 2
1 3
1 4
2 5
2 6
3 7
3 8
Sample Output
1 1 1 2 2 2 2
HINT
Problem D: 买iphone
Time Limit: 3 Sec Memory Limit: 128 MB Submit: 1855 Solved: 348
Description
Input
Output
Sample Input
10 3 3 3 4
20 7 1 1 1
80 3 100 3 3
15 4 3 5 6
Sample Output
Yes
No
No
Yes
HINT
没想到这个题纯暴力就能过了,当然了不是k^2级别的。一共有k个人去装手机,假设有x个人装a,y(y小于k-x)个人装b,剩下的人装c,只要判断出x*a+y*b+(k-x-y)*c==n的情况就可以了
下面给出AC代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k,a,b,c;
int flag;
while(scanf("%d%d%d%d%d",&n,&k,&a,&b,&c)!=EOF)
{
flag=;
for(int i=;i<=k;i++)
{
for(int j=;j<=k-i;j++)
{
if(i*a+j*b+(k-i-j)*c==n)
{
flag=;
break;
}
if(flag)
break;
}
}
if(flag)printf("Yes\n");
else printf("No\n");
}
return ;
}
Problem E: 同源数
Time Limit: 3 Sec Memory Limit: 128 MB Submit: 1344 Solved: 244
Description
Input
Output
Sample Input
18 12
2 3
Sample Output
Yes
No
HINT
题目链接:http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?cid=3648&pid=4
这个题是分析的时间最长的一个题了,最后想出解法后还因为没考虑到全面的情况,又花了很长的时间。首先读完题目的第一反应就是唯一分解定理,然后就卡壳了。突然想到了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的情况。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
return b==?a:gcd(b,a%b);
}
int main()
{
ll a,b;
while(scanf("%lld%lld",&a,&b)!=EOF)
{
if(a==b)
printf("Yes\n");
else if(a!=&&b==)
printf("No\n");
else if(a==&&b!=)
printf("No\n");
else
{
ll t=gcd(a,b);
ll m=a/t;
ll n=b/t;
ll mm=,nn=;
while()
{
ll k=gcd(m,t);
m=m/k;
if(m==)
break;
else if(k==)
{
mm=;
break;
}
}
while()
{
ll k=gcd(n,t);
n=n/k;
if(n==)
break;
else if(k==)
{
nn=;
break;
}
}
if(mm&&nn)
printf("Yes\n");
else printf("No\n");
}
}
return ;
}
Problem F: 垃圾生成器
Time Limit: 2 Sec Memory Limit: 128 MB Submit: 89 Solved: 19
Description
Input
Output
Sample Input
3 2
4 2
Sample Output
1.00000
1.66667
HINT
题目链接: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
提出最佳页面淘汰算法。是操作系统存储管理中的一种全局页面替换策略当要调入一页而必须淘汰旧页时,应该淘汰以后不再访问的页,或距现在最长时间后要访问的页面。它所产生的缺页数最少,然而,却需要预测程序的页面引用串,这是无法预知的,不可能对程序的运行过程做出精确的断言。但是我们在这里会告诉你一个已经存在的一个页面序列,请输出最终在内存中存在的页面即可。
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 1
Sample Output
7 0 1
3 1
1 0
HINT
第一个样例:
访问页面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
Input
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
1000000
Sample Output
15
10000
1000000
HINT
Problem I: 约素
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 1876 Solved: 489
Description
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 1913
Sample Output
YES
NO
NO
YES
NO
HINT
题解:暴力求约数,常规技巧简化
约数,我都想问到底什么叫做约数。以前做的计算约数的个数的理解记得不是这样的来。这个题的约数就是让你暴力找一遍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代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
int n,m;
while(scanf("%d",&T)!=EOF)
{
while(T--)
{
scanf("%d%d",&n,&m);
int sum=;
for(int i=;i<=n/i;i++)
{
if(n%i==)
{
sum++;
if(i!=n/i)
sum++;
}
}
if(sum==m)
printf("YES\n");
else printf("NO\n");
}
}
return ;
}