题 3 分值 13

一天蒜头君在想,[l,r][l,r] 之间有多少个数字是 dd 的倍数呢?

但是区间 [l,r][l,r] 是 dd 的倍数的数字太多,于是聪明的蒜头君便找到了你。

当 l = 1032l=1032,r = 12302135942453r=12302135942453,d = 234d=234,dd 的倍数有多少个呢?

程序 设计题F
一天蒜头君猜想,是不是所有的偶数(除了 22),都可以用两个质数相加得到呢?于是聪明的蒜头君就找你来验证了。

输入格式
第一行输入一个整数 tt 表示测试组数。

接下来 tt 行,每行一个整数 nn。

输出格式
输出两个整数,因为答案可能有多个,所有要求输出的这两个整数是所有答案中字典序最小的。

数据范围
对于 30%30% 的数据 1 \le t \le 10^31≤t≤10
3

对于 60%60% 的数据 1 \le t \le 10^51≤t≤10
5

对于 100%100% 的数据 1 \le t \le 10^6, 4 \le n \le 10^61≤t≤10
6
,4≤n≤10
6
,nn 为偶数。

样例输入复制
3
4
8
20
样例输出复制
2 2
3 5
3 17

解题报告:这道题我想的复杂了,其实只需要线性筛,然后枚举最小的质数,用st数组来判断它和n-它是不是都是质数。

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const	int N=1000010;
bool st[N];
int cnt;
int prime[N];
void get_primes()
{
   
    for(int i=2;i<=N;i++)
    {
   
        if(!st[i])
        {
   
            prime[cnt++]=i;
        }
        for(int j=0;prime[j]<=N/i;j++)
        {
   
            st[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}
int main()
{
   
    int t;
    get_primes();
   scanf("%d",&t);
    while(t--)
    {
   
        int n;
        scanf("%d",&n);
		for(int i=0;i<cnt;i++)
		{
   
			if(!st[prime[i]]&&!st[n-prime[i]])
			{
   
				printf("%d %d\n",prime[i],n-prime[i]);
				break;
			}
		}
    }
    
    
}

最后一题
程序设计:蒜厂年会
在蒜厂年会上有一个抽奖,在一个环形的桌子上,有 n 个纸团,每个纸团上写一个数字,表示你可以获得多少蒜币。但是这个游戏比较坑,里面竟然有负数,表示你要支付多少蒜币。因为这些数字都是可见的,所以大家都是不会出现的赔的情况。
游戏规则:每人只能抓一次,只能抓取一段连续的纸团,所有纸团上的数字和就是你可以获得的蒜币。
蒜头君作为蒜厂的一员在想,我怎么可以获得最多的蒜币呢?最多能获取多少蒜币呢?
因为年会是发奖,那么一定有大于 0 的纸团。
输入格式
第一行输入一个整数 n,表示有 n 个纸团。
第二行输入输入 n 个整数 aia_ia
i

,表示每个纸团上面写的数字(这些纸团的输入顺序就是环形桌上纸团的摆放顺序)。
输出格式
输出一个整数,表示蒜头君最多能获取多少蒜币。

这道题其实就是连续子序列最大和的改编版,改编就改编在他是一个环,看了大佬的题解后我才明白,其实无非就两种情况,一种就是在环上,另外一种就是在正常的连续序列上,两个情况取一个max就行了,至于算在环上的最大值,可以用sum-最小连续序列和来算。

#include<iostream>
#include<cstring>
using namespace std;
const	int N=100010;
typedef long long ll;
ll dp[N];
ll a[N];
ll sum;
int main()
{
   
    int n;
	scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
   scanf("%lld",&a[i]);
    sum+=a[i];
    }
     ll res=0;
    for(int i=1;i<=n;i++)
    {
   
        dp[i]=max(a[i],dp[i-1]+a[i]);
        res=max(res,dp[i]);
    }
    memset(dp,0,sizeof dp);
    ll minres=1e9+10;
    for(int i=1;i<=n;i++)
    {
   
        dp[i]=min(dp[i-1]+a[i],a[i]);
        minres=min(minres,dp[i]);
    }
    printf("%lld\n",max(res,sum-minres));
}

H. 程序设计:轻重搭配
蒜头君在做图像处理的项目时,遇到了一个问题。他需要摘取出图片中,某个黑色线框内的图片,现在请你来帮助他完成这一步,把黑色线框外的区域全部变为黑色,即只保留黑色线框内的颜色。
大致意思就是把除了正常矩形里的颜色都涂0。我一开始没想到原来题解这么简单,就是从边上非0的点开始dfs,与他连通的必定不在矩形内。

#include<iostream>
#include<algorithm>
using namespace std;
const	int N=500010;
bool st[N];
int w[N];
int main()
{
   
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%d",&w[i]);
    int cnt=0;
    sort(w,w+n);
    int pos=n-1;
    for(int i=n/2-1;pos>=0&&i>=0;i--)
    {
    
        if(w[pos]>=2*w[i]) 
        {
   
		st[pos]=true;
        st[i]=true;
        cnt++;
        pos--;
        }
    }
    for(int i=0;i<n;i++)
    {
   
        if(!st[i])
            cnt++;
    }
   printf("%d\n",cnt);
    return 0;
}

G. 程序设计:后缀字符串
题意大致就是给你n个字符串,求个字符串以他为后缀的字符串的数量(自身当然也算),唯一ac的题。。用map把每个string的后缀都处理一下就行啦。

#include<iostream>
#include<map>
using namespace std;
const	int N=100010;
string s[N];
map<string,int>mp;
int main()
{
   
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
   
        cin>>s[i];
        for(int j=0;j<s[i].size();j++)
        {
   
            string t=s[i].substr(j,s[i].size()-j);
            mp[t]++;
        }
    }
    for(int i=1;i<=n;i++)
    {
   
        int res=0;

            string t=s[i].substr(0,s[i].size());
            res+=mp[t];
        cout<<res<<endl;
    }
    return 0;
}

程序填空题
LIS 是最长上升子序列。什么是最长上升子序列? 就是给你一个序列,请你在其中求出一段最长严格上升的部分,它不一定要连续。

就像这样:22, 33, 44, 77 和 22, 33, 44, 66 就是序列 22 55 33 44 11 77 66 的两个上升子序列,最长的长度是 44。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int f[N], a[N];
int n;
int find(int l, int r, int x) {
   
	while (l < r) {
   
		int mid = (l + r) / 2;
		if (f[mid] < x) {
   
			l = mid + 1;
		} else {
   
			r = mid;
		}
	}
	return l;
}
int lis() {
   
	int len = 0;
	for (int i = 0; i < n; i++) {
   
		sort(f,f+len); int k=find(0,len,a[i]);
		f[k] = a[i];
		if (k == len) {
   
			len++;
		}
	}
	return len;
}
int main() {
   
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
   
		scanf("%d", a + i);
	}
	printf("%d\n", lis());
	return 0;
}

程序设计:轻重搭配
n 个同学去动物园参观,原本每人都需要买一张门票,但售票处推出了一个优惠活动,一个体重为 xx 的人可以和体重至少为 2x2x 配对,这样两人只需买一张票。现在给出了 nn 个人的体重,请你计算他们最少需要买几张门票?

解题报告:千万别和我一样,把pos从最大的开始减,容易爆0,看了题解还是从n/2开始吧,因为最多只能匹配n/2对。

#include<iostream>
#include<algorithm>
using namespace std;
const	int N=500010;
bool st[N];
int w[N];
int main()
{
   
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%d",&w[i]);
    int cnt=0;
    sort(w,w+n);
    int pos=n-1;
    for(int i=n/2-1;pos>=0&&i>=0;i--)
    {
    
        if(w[pos]>=2*w[i]) 
        {
   
		st[pos]=true;
        st[i]=true;
        cnt++;
        pos--;
        }
    }
    for(int i=0;i<n;i++)
    {
   
        if(!st[i])
            cnt++;
    }
   printf("%d\n",cnt);
    return 0;
}