Y1模拟一 补题报告
T1：拆分成绩题面
题目描述
小可参加了两场考试，由于老师比较粗心，把两场考试的成绩写的很近，小可不知道两场考试分别考了多少分。所以小可需要把这个写成一块的成绩拆分开来。
当然，两科的成绩都是正整数，且不应该含有前导零。小可知道自己第一科的成绩一定是比第二科成绩低的。请帮助小可拆分成绩。
比如：老师给出的成绩是100101，小可两科的成绩分别是 100、101 。
输入描述
第一行：输入一个正整数t，表示多组输入组数。
接下来t行：每行输入一个正整数x，表示老师给出的成绩。
输出描述
对于每个输入的成绩，输出按照要求拆分的两科成绩。
其中：如果有多个符合要求的，输出第一课成绩最低的情况。
如果没有合法情况，输出-1 。
输入样例
520002001391125200200200100012
输出样例
2000 20013 91125-1200 10001 2
数据描述
思路
模拟，找每个非零的点分割，按要求判断，找第一个符合条件的点，输出
代码
#include<iostream>
using namespace std;
long long t;
string s;
int main(){cin>>t;while(t--){cin>>s;bool flag = 0;if(s.size()==2) {if(s[0]-'0'<s[1]-'0'){cout<<s[0]<<" "<<s[1]<<"\n";continue;}else {cout<<"-1\n";continue;}}for(int i=1;i<s.size()-1;i++){long long s1=0,s2=0;if(s[i]=='0') continue;for(int j=0;j<i;j++){s1=10*s1+(s[j]-'0');}for(int j=i;j<s.size();j++){s2=s2*10+(s[j]-'0');}cout<<s1<<" "<<s2;if(s1<s2){cout<<s1<<" "<<s2<<"\n";flag =1;break;}}if(!flag) cout<<"-1\n";}return 0;
} T2：奇偶交替
题面
时间限制：1秒 内存限制：128M
题目描述
对于一个长度为n的序列，小可想找到一个非空的连续的子序列，这个子序列满足如下条件：
1.子序列中的相邻的数字，奇偶性不能相同。
2.这个子序列的和最大。
请帮助小可找出这个子序列，输出子序列的和。
输入描述
第一行：输入一个正整数t，表示多组输入的数据组数。
对于每组数据：
第一行：输入一个正整数n，表示序列包含的数字个数。
第二行：输入n个整数，表示这个序列aiai
输出描述
输出题目描述中所述的答案。
输入样例
751 2 3 4 549 9 8 86-1 4 -1 0 5 -44-1 2 4 -31-10003101 -99 10120-10 5 -8 10 6 -10 7 9 -2 -6 7 2 -4 6 -1 7 -6 -7 4 1
输出样例
151784-100010110
思路
类似最长上升子序列，加入一个奇偶判断和累加即可
代码
#include<iostream>
#include<cstring>
using namespace std;
long long dp[200005],t,n,a[200005],maxx=-0x3f3f3f3f,sum=0;
int main(){cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sum=a[1];maxx=a[1];for(int i=2;i<=n;i++) {maxx=max(maxx,sum);if((a[i-1]&1)==(a[i]&1)||sum<0) sum=a[i];else sum+=a[i];maxx=max(maxx,sum);}cout<<maxx<<"\n";}return 0;
} T3：构造三角形
题面
时间限制：1秒 内存限制：128M
题目描述
小可很喜欢三角形，所以当他有三条木棒的时候，他就会尝试一下，这三条木棒能不能构成三角形，他知道任意两条木棒的和大于第三条，那么就可以构成三角形。
现在小可有n条木棒，编号从1到n，第 i 条木棒的长度为 2ai2ai 。
小可想从这n条木棒中，选出3条来，并且这3条可以构成三角形。小可想知道一共有多少种选择方式。
注意：选择木棒的顺序不影响答案，也就是说：选择第1 2 3条木棒，和选择第2 1 3条木棒是同一种方案。
输入描述
第一行：输入一个正整数t，表示多组输入的数据组数。
对于每组数据：
第一行：输入一个正整数 n ，表示木棒数量。
第二行：输入n个非负整数aiai，表示木棒的长度 2ai2ai 。
输出描述
对于每组数据，输出对应的方案数。
输入样例
371 1 1 1 1 1 143 2 1 331 2 3
输出样例
3520
思路
用桶统计每种长度小棒的个数，若b[i]>=3，累加C b[i] 3 ，若b[i]>=2,累加(C b[i] 2)*sum
sum是 b[1]+b[2]+...+b[i]
代码
#include<iostream>
#include<cstring>
using namespace std;
long long t;
int b[300005];
long long a[300005],n,sum,cnt;
int main(){cin>>t;while(t--){cin>>n;cnt=0;sum=0;memset(b,0,sizeof b);for(int i=1;i<=n;i++){cin>>a[i];b[a[i]]++;}for(int i=0;i<=n;i++){if(b[i]>=3){cnt+=b[i]*(b[i]-1)*(b[i]-2)/6;}if(b[i]>=2){cnt+=sum*(b[i]*(b[i]-1)/2);}sum+=b[i];}cout<<cnt<<"\n";}return 0;
}