12月16日第二次上（zi）机（bi）考试良心题解

前言

嗯……呃……嘶……算了不知说什么，祝大家身体健康。

Problem A 筛素数

这题这么水，相信大家都AK了

题意：求[1,n]内的素数。N多大你猜你猜你猜猜想不到吧~反正绝对不是107!

好了，既然是第二次考质数，那我就简单讲讲欧拉筛的原理吧。
欧拉筛是一种线性筛法，复杂度是O（n）的,原理是每个数只会被筛一次。
而且保证了每个数只会被最小的因子筛到，如12=2∗3∗3，由2去筛它，105=3∗5∗7，由3去筛它。

欧拉筛枫版：

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,j,k) for (int i=j;i<=k;i++)
#define N 1000005
using namespace std;
int n,vis[N],dt[N],t;
void pre(int x){
	fo(i,2,x){
		if (!vis[i]) dt[++t]=i;
		fo(j,1,t) if (dt[j]*i>x) break;else{
			vis[i*dt[j]]=1;
			if (i%dt[j]==0) break;  //决定性的break
		}
	}	
}
int main(){
		//freopen(\"xx.in\",\"r\",stdin);
		scanf(\"%d\",&n);
		pre(n);
		fo(i,1,t) printf(\"%d\\n\",dt[i]);
		return 0;
}

朴素素数判断冰版

#include<cstdio> 

const int maxn = 1e4 + 5;

int main() {

	int nprime[maxn] = { 1, 1 }, i, j, n;

	for (i = 2; i < maxn; ++i) {

		if (!nprime[i]) { // nprime[i] == 0, 表示是素数

			for (j = i * i; j < maxn; j += i) nprime[j] = 1;
		}
	}
	scanf(\"%d\", &n);
	for (i = 2; i <= n; ++i) {

		if (nprime[i]) continue;
		printf(\"%d\\n\", i);
	}
	return 0;
}

Problem B 水仙花数

这题这么水，相信大家都AK了

题意：给定一个三位数，判断是否为水仙花数，水仙花数定义：当且仅当各个位数的立方和等于本身的数。

暴力分解个位十位百位的立方求和判断。
有的同学喜欢用pow()函数也可以，不过需要注意pow()函数的参数和返回值都是double哦！

枫版

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,j,k) for (int i=j;i<=k;i++)
using namespace std;
int n;
int pan(int x){
		int a,b,c;
		a=x/100;
		b=x/10%10;
		c=x%10;
		if (a*a*a+b*b*b+c*c*c==x) return 1;
		return 0;
}
int main(){
		//freopen(\"xx.in\",\"r\",stdin);
		scanf(\"%d\",&n);
		int x;
		fo(i,1,n){
			scanf(\"%d\",&x);
			if (pan(x)) printf(\"YES\\n\");else printf(\"NO\\n\");
		}
		return 0;
}

冰版

#include<cstdio> 

int conv(int num) {

	int k, sum = 0;
	while (num > 0) { // 逐位分离

		k = num % 10;
		sum += k * k * k;
		num /= 10;
	}
	return sum;
}

int main() {

	int t, num;

	scanf(\"%d\", &t);
	while (t--) {

		scanf(\"%d\", &num);
		printf(\"%s\\n\", conv(num) == num ? \"YES\" : \"NO\");
		// cout << (conv(num) == num ? \"YES\" : \"NO\") << endl;
	}
	return 0;
}

problem C 回文字符串

这题这么水，相信大家都AK了

题意：求字符串的最大回文子串，长度相同的位置靠左优先。

暴力解:
需要分两种情况：
1、中心点在字符本身（言下之意长度是奇数）
2、中心点在字符之间（言下之意长度是偶数）
或者dalaoiceup的添加’#\'字符法也可行！
然后从中心点往左右延伸就行了，复杂度O(Tn2)

但是由于出题人太过于良心，暴力不仅能过竟然还是0ms！一时语塞.jpg
为啥过不了，自己可以构造一个长度10000全是一样字符的字符串，跑跑就知道了。

正解：Manacher马拉车算法，复杂度O(Tn)
首先，要做个预处理，在字符串头加’$’,字符之间加’#’，避免了讨论。
如\"aabb\"可以变成\"$#a#b#b#a#\",而在开头加美元的目的，是为了让\"偶数\"和\"奇数\"型回文串的信息一致化。
简单地来说，就是利用了一个对称点（k），复制了当前点(i)关于点(k)的对称点(j)的信息。
我们不妨设
p[i]:以i为中心位置的最大回文子串半径
ms:当前最大的延伸点，即max(p[k]+k)
id:最大延伸回文串的中心点
如下图所示，画的丑别在意 ，蓝色线表示虚拟的回文串，所以就有下面的递推式。
但是这样还不够，如果正好p[i]取了ms−i的值，则需要继续左右延伸，并更新答案，ms等。
if (ms>i) p[i]=min(p[2∗id−i],ms−i);else p[i]=1;

Manacher枫版

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#define fo(i,j,k) for (int i=j;i<=k;i++)
#define N 100005
using namespace std;
int p[N],n;
string s;
void solve(string s){
		string x=\"$#\";
		int ans=0,len=0,ms=0,id=0;
		for (int i=0;i<s.size();i++) x=x+s[i]+\"#\";
		for (int i=0;i<x.size();i++){
			if (ms>i) p[i]=min(p[2*id-i],ms-i);else p[i]=1;
			while (x[i+p[i]]==x[i-p[i]]) p[i]++;
			if (ms<i+p[i]){
				ms=i+p[i];
				id=i;
			}
			if (len<p[i]){
					len=p[i];
					ans=i;
			}
		}
		cout<<s.substr((ans-len)/2,len-1)<<endl;
}
int main(){
	//freopen(\"xx.in\",\"r\",stdin);
	cin>>n;
	for (int i=1;i<=n;i++){
			cin>>s;
			solve(s);
	}
	return 0;
}

奇丑的暴力char枫版

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,j,k) for (int i=j;i<=k;i++)
#define N 100005
using namespace std;
int n,st,ans;
char c[N];
void up(int x,int y){                    //用来更新答案的
		if ((x>ans)||((x==ans)&&(y<st))){
				st=y;
				ans=x;
		}
}
int main(){
	//	freopen(\"xx.in\",\"r\",stdin);
		scanf(\"%d\",&n);
		int x,l,k;
		fo(i,1,n){
				ans=0;st=0;
				scanf(\"%s\",c+1);
				l=strlen(c+1);
				

					

						
继续阅读与本文标签相同的文章
						

														无标签