6月21日训练 (东北林业大学)（个人题解）

前言：

这次训练是大一大二一起参加的训练，总体来说难度是有的，我和队友在比赛时间内就写出了四道题，之后陆陆续续又补了了三道题，还有一道题看了学长题解后感觉有点超出我的能力范围了，就留给以后的自己吧。话不多说，上正文。

正文：

Problem:A 幸运数字：

#include <bits/stdc++.h>
using namespace std;
int sum,ans;
int main()
{
    int n,t;cin>>n;
    for(int i=1;i<=n;i++){
            sum=0;t=i;
    while(1){
        sum+=t%10;
        if(t/10==0&&t%10==0)
            break;
        t=t/10;
    }
    if(i%sum==1) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

简单的签到题，直接枚举判断就行了。

Problem:B 子数组和：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010;
LL a[N];
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	bool flag = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			LL res = a[j] - a[i - 1];
			if (res == k) {
				flag = 1;
				cout << i << " " << j;
				return 0;
			}
		}
	}
	cout << -1;
}

先做前缀和，在循环枚举即可。

Problem:C 搭积木（待补）：

学长说这题需具备树状数组、线段树等任一种支持单点修改+区间查询的数据结构，以及二位偏序的相关知识。

也可以看看见我的队友写的记忆化搜索东北林业大学6.21训练补题-CSDN博客。

Problem:D 最大子序列：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[10005];int dp1[10005],dp2[10005];
vector<int> low;
int main(){
	int n;
	while(cin>>n){
	int ans=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp1[1]=1;
	low.clear();
	low.push_back(a[1]);
	for(int i=2;i<=n;i++){
		if(a[i]>low.back())low.push_back(a[i]);
		else {
			*lower_bound(low.begin(),low.end(),a[i])=a[i];
		}
		dp1[i]=lower_bound(low.begin(),low.end(),a[i])-low.begin()+1;
		//cout<<dp1[i]<<endl;
	}
	//
	dp2[n]=1;
	low.clear();
	low.push_back(a[n]);
	for(int i=n-1;i;i--){
		if(a[i]>low.back())low.push_back(a[i]);
		else {
			*lower_bound(low.begin(),low.end(),a[i])=a[i];
		}
		dp2[i]=lower_bound(low.begin(),low.end(),a[i])-low.begin()+1;
		//cout<<dp2[i]<<endl;
	}
	for(int i=1;i<=n;i++){
		if(dp1[i]>1&&dp2[i]>1){
			ans=max(ans,2*min(dp1[i],dp2[i])-1);
		}
		else ans=max(1,ans);
		//if(dp1[i]<=dp2[i+1])ans=max(ans,2*dp1[i]);
		//if(dp1[i]>=dp2[i+1])ans=max(ans,2*dp2[i+1]);
	}
	//cout<<n<<" "<<ans<<endl;
	cout<<ans<<endl;}
	return 0;
}

解释这道题之前我要先吐槽一下出题人的语文水平，整个题干写的雨里雾里的，什么是前n+1个数和后n+1个数1 2 3 4 5 5 4 3 2 1这算不算一个长度为10的序列，这些题干和样例都没表示清楚。

这题有点像我之前写的合唱队形：算法基础精选题单动态规划（dp）（递推+线性dp）（个人题解）-CSDN博客

这题与那题区别在于递增递减序列长度要一样且不为0（都不为0），如果只有一个数那长度为1。

所以我们依旧是求两次最长上升子序列，这里直接两层循环会超时，所以第二层循环我们用二进制来优化掉。

Problem:E 阿华找阿璐：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+500;
int prime[N],b[N];
int cnt=0,maxl=1e6+499;
int init(){
    memset(b,1,sizeof(b));
    b[0]=b[1]=0;
    for(int i=2;i<=maxl;i++){
        if(b[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=maxl;j++){
            b[prime[j]*i]=0;
            if(i%prime[j]==0) break;
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    init();
    int t,m,f=0;cin>>t;
    while(t--){
        cin>>m;
        for(int i=1;i<10005;i++){
            if(prime[prime[i]]>=m)
            {
                cout<<prime[prime[i]]<<endl;f=1;break;
            }
        }
        //if(f==0) cout<<"No"<<endl;
    }
    return 0;
}

先初始化素数数组，prime[i]表示第i个素数，prime[prime[i]]就表示两次去素数后该值的初始值，之后再枚举找到第一个大于 m 的数即可。

Problem:F 阿祥和阿华：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	int t;
	cin>>t;
	while(t--){
		ll ans=1;
		ll n;
		cin>>n;
		for(int i=2;i*i<=n;i++){
			int cnt=0;
			if(n%i==0){
				while(n%i==0){
					cnt++;
					n/=i;
				}
				ans*=(cnt*2+1);
			}
		}
		if(n>1)ans*=3;
		cout<<(ans+1)/2<<endl;
	}
}

这题用到了约数定理，原式可以变化为 n^2 = (n - x) * ( n - y)

即：求n^2的约数组合数，n^2的质因数与n的质因数相同，个数为n的两倍，所以我们先求n的质因数，原本求组合数的公式是循环乘（x+1），x，那么n^2的组合数就是循环乘（x*2+1）最后在乘个（1*2+1），因为大于sqrt（n）的质因数有且仅有一个（除1以外），所以最后有if(n>1)ans*=3;

最后因为（2，3）与（3，2）算同一组，所以答案要取取一半，又因为可能会出现（x,x）这一组不需除2的情况，所以我们最后要(ans+1)/2。

Problem:G 数字游戏：

#include<bits/stdc++.h>
using namespace std;
int a[3005];
int book[10005];
int main(){
	int n;
	while(cin>>n){
		memset(book,0,sizeof(book));
		int k;
		cin>>k;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				book[a[i]+a[j]]++;
				//cout<<a[i]+a[j]<<endl;
			}
		}
		int t=k;
		for(int i=10000;i>=0;i--){
			while(k>0&&book[i]>0){
				if(t==k)cout<<i;
				else cout<<" "<<i;
				k--;book[i]--;
			}
		}
		cout<<endl;
	}
	return 0;
}

用sort排序会超时，但这题数字范围不是很大，我们可以用桶排做，注意和的总数不一定大于m（因为这个卡了超级久）。

Problem:H 剪花布条：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	while(n--){
		string a,b;
		cin>>a>>b;
		int l=a.size()-b.size();
		if(l<0)l=0;
		int r=0,ans,res=0,cnt=0;
		for(int i=l;i<a.size();i++){
			ans=0;int x=i;
			for(int j=0;j<b.size()&&x<a.size();j++,x++){
				//cout<<a[x]<<b[j]<<endl;
				if(a[x]==b[j])ans++;
				else break;
				//cout<<ans<<endl;
			}
			//cout<<x<<" "<<ans<<endl;
			if(x==a.size())res=max(res,ans);
		}
		cout<<res<<endl;
	}
	return 0;
}

一开始看这数据范围我还以为暴力做不了，但测评数据估计不是很大，暴力也卡过去了。做法就是从头到尾两个循环遍历，太暴力了以至于我比赛时都不敢写。