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

本文主要是介绍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;
}

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