题目链接
D. 结果填空：马的管辖
E. 代码填空：LIS
链接
F. 程序设计：找质数
思路:因为时间复杂度的问题，O(n*n)的时间复杂度可能会超时，可以选择的筛选素数的方法有埃氏筛法O(n*logn)，欧拉筛法，这里选的是欧拉筛法O(n)。
直接遍历找两个素数相加等于n(因为要求字典树最小，所以不会超时)。
AC代码:
#include<iostream>//欧拉筛法用了最小质因数,减少了重复筛选的次数
#include<string.h>//相比于埃氏筛选
#include<algorithm>
#define in(x) scanf("%d",&x)
#define out(x) printf("%d",x)
using namespace std;
const int maxn=1e6+5;
int vis[maxn]={0},isp[maxn]={0},go[maxn]={0};
int len=0;//用来记数
void prime()
{
for(int i=2;i<=maxn;i++){
if(!vis[i]) isp[len++]=i,go[i]=i;//len用来记数
for(int j=0;j<len&&i*isp[j]<=maxn;j++){//因为i从2遍历到maxn,那么
vis[i*isp[j]]=1;//每个素数的(i~maxn)倍都会被遍历
if(i%isp[j]==0) break;//这样看来显然也会重复筛选很多
} //所以有了以上这一条
}
}
int main()
{
int t,n,s=1;
prime();
in(t);
while(t--){
in(n);
for(int i=1;i<=n;i++){
if(go[i]&&go[n-i]){
printf("%d %d\n",go[i],go[n-i]);
break;
}
}
}
}
H. 程序设计：轻重搭配
n 个同学去动物园参观，原本每人都需要买一张门票，但售票处推出了一个优惠活动，一个体重为 xxx 的人可以和体重至少为 2x2x2x 配对，这样两人只需买一张票。现在给出了 nnn 个人的体重，请你计算他们最少需要买几张门票？
输入格式
第一行一个整数 nnn，表示人数。
第二行 nnn 个整数，每个整数 aia_iai 表示每个人的体重。
输出格式
一个整数，表示最少需要购买的门票数目。
数据范围
样例解释
111 和 999 配对，777 和 333 配对，剩下 5,55,55,5 单独，一共买四张票。
样例输入复制
6
1 9 7 3 5 5
样例输出复制
4
思路:有多种思路，贪心，二分，我的思路是处理后遍历，时间复杂度是nlogn,思路在注释上
贪心思路:其实就是我的代码的改进，改成直接找后半元素大于等于前半元素大的个数，其实也一样了。
二分思路:没思路。。。
代码:
#include<iostream>
#include<string.h>
#include<algorithm>
#include<cstdio>
#define in(x) scanf("%d",&x)
#define out(x) printf("%d",x)
using namespace std;//我的思路是先排序，标记前半元素,使得前半数值翻倍,再排序
const int maxn=1e6+5;
int a[maxn]={0};//排序需要重新弄一下，因为前半元素翻倍后可能和后半元素相等
struct node//如果相等使得前半元素(翻倍后)排在前面，这样只需逆序遍历一下
{ //想想为什么？？
int a,b;
}pp[maxn];
bool cmp(node x,node y)//重新排序,使得如果有相同的标记为1的排在前面
{ //比如 6| 1 1 2 2 4 4
if(x.a!=y.a) return x.a<y.a;
else{
return x.b<y.b;
}
}
int main()
{
int n,sum=0,size,s=0;//刚开始没有初始化sum只对了四个样例，TAT
in(n);
for(int i=1;i<=n;i++){
in(a[i]);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
if(i<=n/2){
pp[i].a=2*a[i];
pp[i].b=1;
}
else{
pp[i].a=a[i];
pp[i].b=2;
}
}
sort(pp+1,pp+1+n,cmp);
for(int i=n;i>=1;i--){
if(pp[i].b==2) sum++;
else if(sum>0&&pp[i].b==1){
s++;
sum--;
}
}
out(n-s);
}
J. 程序设计：蒜厂年会
在蒜厂年会上有一个抽奖，在一个环形的桌子上，有 nnn 个纸团，每个纸团上写一个数字，表示你可以获得多少蒜币。但是这个游戏比较坑，里面竟然有负数，表示你要支付多少蒜币。因为这些数字都是可见的，所以大家都是不会出现的赔的情况。
游戏规则：每人只能抓一次，只能抓取一段连续的纸团，所有纸团上的数字和就是你可以获得的蒜币。
蒜头君作为蒜厂的一员在想，我怎么可以获得最多的蒜币呢？最多能获取多少蒜币呢？
因为年会是发奖，那么一定有大于 000 的纸团。
输入格式
第一行输入一个整数 nnn，表示有 nnn 个纸团。
第二行输入输入 nnn 个整数 aia_iai，表示每个纸团上面写的数字（这些纸团的输入顺序就是环形桌上纸团的摆放顺序）。
输出格式
输出一个整数，表示蒜头君最多能获取多少蒜币。
数据范围
样例输入复制
3
1 -2 1
样例输出复制
2
题目来源
2019 蓝桥杯省赛 B 组模拟赛（一）
思路:
有很多方法能写，比如优先级队列
这里提供一种较为简便的方法，有两种可能情况，
一种是1~n中出现了最大，直接用O(n)的方法当输入时找出最大值
还有就是跨越了尾部出现。为后者时，只需应总的和减去最小连续和，再与前一种情况比较大小即可。
代码:
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define in(x) scanf("%lld",&x)
#define out(x) printf("%lld",x)
using namespace std;
typedef long long int ll;
const ll inf=0x3f3f3f3f;
const int maxn=1e6+5;
ll a[maxn]={0};
int main()
{
ll sum=0,s=0,smin=inf,sg=0,smax=-inf;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
in(a[i]);
sum+=a[i];
if(sg>=0) sg+=a[i];//对当前元素有贡献
else sg=a[i];
if(s<=0) s+=a[i];//对当前元素有贡献
else s=a[i];
smin=min(smin,s);
smax=max(smax,sg);
}
smax=max(smax,sum-smin);
out(smax);
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
