华中农业大学第十三届程序设计竞赛个人题解（待补）

前言：

注意本篇博客的题解目前并不完整，未来会慢慢补齐的。

进入实验室后接触算法比赛的机会更多了，我接触的题也不再是简单的c语言题了，开始遇到更多我没接触过的算法和难题了，死磕这些难题对现在的我不但花时间而且成效甚微，我想不如也把这些题发在博客上，写过的题附上我的代码；那些没写过的题也先发在这，等到我有能力时在来补这些题，相当于是我的待补题单。

正文：

比赛题目网址：华中农业大学第十三届程序设计竞赛（同步赛）_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

已完成：

A：scx 的散文诗句：

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
	int t;
	cin>>t;
	while(t--){
		memset(a,0,sizeof(a));
		long long n,ans=0,x=0,y=0,z=0,j=0,k=0;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]<0)x++;
			else if(a[i]>0) y++;
			else z++;
		}
		sort(a+1,a+n+1);
	//	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
		for(int i=1;i<=x;i+=2){
			if(a[i]<0&&a[i+1]<0)ans+=a[i]*a[i+1];
			else j=a[i];
		}
		for(int i=1;i<=y;i+=2){
			if(a[n-i+1]>0&&a[n-i]>0)ans+=a[n-i+1]*a[n-i];
			else k=a[n-i+1];
		}
	//	cout<<ans<<j<<k<<endl;
		if(z==0)ans+=j*k;
		cout<<ans<<endl;
	}
	return 0;
}

把输入的数字排序并计算正数负数和0的数量分别有几个，再根据情况来决定组合方式，算出最大值。

C：猫猫大队：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,cat=0;
	cin>>n;
	while(n--){
		int m;cin>>m;
		if(m==1){
			cat++;
		}
	}
	if(cat%2==0)cout<<"zzy"<<endl;
		else cout<<"miao"<<endl;
	return 0;
}

签到题。

G：怯战蜥蜴：

#include<bits/stdc++.h>
using namespace std;
long long a[200005],pre[200005];
int main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pre[i]=pre[i-1]+a[i];
	}
	for(int i=1;i<=q;i++){
		int x;cin>>x;
		int l=0,r=n,mid=(l+r)/2;
		while(l<r){
			if(pre[mid]<=x){
				l=mid;
			}
			else r=mid-1;
			mid=(l+r+1)/2;
		}
		cout<<r<<endl;
	}
	return 0;
}

求前缀和然后用二分来找答案。

I：fumo 星：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x[1005],y[1005];
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
typedef struct line{
	ll A;
	ll B;
	ll C;
	bool operator < (const line b)const{
		if(A==b.A&&B==b.B&&C==b.C)return false;
		else return A==b.A?(B==b.B?C<b.C:B<b.B):A<b.A;
	}
}fumo;
typedef struct node{
	ll x;
	ll y;
}node;
node nod[1005];
set<line> s;
int main(){
	int n;
	cin>>n;
	if(n==1){
		cout<<"0"<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++){
		cin>>nod[i].x>>nod[i].y;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(nod[i].x==nod[j].x&&nod[i].y==nod[j].y){
				cout<<"inf"<<endl;
				return 0;
			}
			ll a=nod[i].y-nod[j].y;
			ll b=nod[j].x-nod[i].x;
			ll c=nod[i].x*nod[j].y-nod[j].x*nod[i].y;
			ll g=gcd(gcd(a,b),c);
			a/=g,b/=g,c/=g;
			if(c<0){
				a=-a;b=-b;c=-c;
			}
			s.insert({a,b,c});
		}
	}
	cout<<s.size()<<endl;
	return 0;
}

我本来是想用点斜式来表示各个直线的（一个斜率和一个截距就能表示一个直线），但不知为何只能过70%用例，最后再参考了其他大佬的写法后决定用标准式（Ax+By+C=0），暴力找全部直线后将他们放进set中，最后输出set的大小。

J：上春山：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
typedef struct mount{
	ll a;
	ll h;
}mount;
mount m[N];
ll prefixa[N],prefixh[N];
bool cmp( mount x, mount y){
	return x.h<y.h;
}
int main(){
	ll n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m[i].h;	
	}
	for(int i=1;i<=n;i++){
		cin>>m[i].a;
	}
	sort(m+1,m+n+1,cmp);
	for(int i=1;i<=n;i++){
		prefixh[i]=prefixh[i-1]+m[i].h;
		prefixa[i]=prefixa[i-1]+m[i].a;
	}
	for(int i=1;i<=n;i++){
		ll k=m[i].h-1,cnt=0;
		cnt+=prefixa[n]-prefixa[i-1];
		cnt-=(prefixh[n]-prefixh[i-1]-k*(n-i+1));
		ans=max(cnt,ans);
	//	cout<<cnt<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

根据贡献法我们能简单知道山的顺序并不影响结果，我们为了方便处理数据可以将他们排序。然后再根据贪心知k一定是取到某个h[i]-1得到最大结果，我们就可以枚举k来找最大值。

L：南湖少年团：

#include<bits/stdc++.h>
using namespace std;
char a[1010],b[10];
int main(){
	int n,m,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m-n+1;i++){
		int flag=1;
		for(int j=1;j<=n;j++){
			if(a[j+i-1]!=b[j]){
				flag=0;
			}
		}
		if(flag)ans++;
	}
	cout<<ans<<endl;
	return 0;
}

暴力即可。