前面的碎碎念：
每次练习赛都能让我清楚认识到自己有多么菜，有多少知识缺乏，菜不成声.jpg。
题解部分：
A-牛牛的三角形
众所周知，能形成三角形要求任意两边之和大于第三边。我们对数组从小到大排序一下，排序后，a[i+2]+a[i]>a[i+1]和a[i+1]+a[i+2]>a[i]是一定满足的，所以满足a[i]+a[i+1]>a[i+2]的三条边一定能形成三角形。故我们遍历一遍数组，判断是否有满足此要求的三条边即可。
时间复杂度：O(nlog(n))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,n,a[105];
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(i=1;i+2<=n;i++)if(a[i]+a[i+1]>a[i+2])break;
if(i+2<=n)printf("%d %d %d\n",a[i],a[i+1],a[i+2]);
else printf("No solution\n");
return 0;
}B-牛牛的鱼缸
初中数学题，分情况讨论即可，下面结合图进行分析，图画的很丑请见谅QAQ。
情况1：
情况1下，l较长，h较短，那么其面积就是一个三角形的面积。两直线平行，内错角相等，又有=H/L。那么在大三角形斜边上小三角形的直角边就等于h
L/H。之后再底乘高除二，即可得到三角形面积。
情况2：
情况2下，l较短，h较长，那么面积由三角形和矩形两部分组成。同样的内错角相等，根据可以求出三角形在h上的直角边长x，那么三角形面积就是x
l/2，而矩形面积就是(h-x)
l,把两者加起来即可。
时间复杂度：O(1)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int main()
{
double x,h,l,H,L,ans;
scanf("%lf%lf%lf%lf",&h,&l,&H,&L);
x=H/L*l;
if(x<h)ans=x*l/2+(h-x)*l;
else ans=h*h*L/H/2;
printf("%.8lf\n",ans);
return 0;
}C-牛牛的揠苗助长
只要天数越长，那么把所有水稻变成同一个高度的可能性就越大，为什么呢？假设至少在第ans天，能够让所有的水稻都长到同一个高度，那么对于第ans+1天，他只要让那天长高一单位的水稻再缩短一单位，仍然可以保持所有水稻同一高度，同理第ans+2，ans+3，...，ans+n天都可以保持所有水稻同一高度，因此说我们可以二分答案。
接下来是判断部分，对于每次二分的天数day，我们先让所有水稻高度加上day/n，再让下标小于等于day%n的水稻再加一，那么我们就得到了第day天，不施展魔法所有水稻的高度。接下来我们利用中位数定理，求出把所有水稻变成同一高度所需要的最小操作次数。若该最小操作次数小于等于day表示合法，否则非法。
时间复杂度：O(nlog(n)
log(n
max(ai)))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],b[100005];
bool judge(long long day)
{
long long i,j,s=0;
for(i=1;i<=n;i++)b[i]=a[i]+day/n;
for(i=1;i<=day%n;i++)b[i]++;
sort(b+1,b+1+n),j=b[(n+1)/2];
for(i=1;i<=n;i++)s+=abs(b[i]-j);
if(s<=day)return 1;
return 0;
}
int main()
{
long long i,l,r,mid,ans;
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
for(l=1,r=1e14;l<=r;)
{
mid=(l+r)>>1;
if(judge(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld\n",ans);
return 0;
}D-牛牛的01限定串
设状态DP1[i][j]为串T到第i位，有j个‘0’字符(‘1’字符的个数自然就是i-j)，串T的最大分数，DP2[i][j]为串T到第i位，有j个‘0’字符，串T的最小分数，那么最终的答案就是DP2[n][cnt0]和DP1[n][cnt0]。
我们先进行预处理，分别把DP1和DP2数组初始化为极小值和极大值，接下来求出字符串S中字符'0'的前缀和和后缀和，方便之后判断是否前缀后缀匹配进行加减分数操作。最后从前往后遍历T数组，按填‘0’和填‘1’两种情况分别递推求DP1和DP2即可，具体细节可见代码。
时间复杂度：O(n^2)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int DP1[1005][1005],DP2[1005][1005],pre[1005]={0},suf[1005]={0};
int main()
{
int i,j,k,n,zero,one,s1,s2;
char R[1005],T[1005];
scanf("%d%d%d%d%d%s%s",&n,&zero,&one,&s1,&s2,R+1,T+1);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)DP1[i][j]=-1e9,DP2[i][j]=1e9;
for(i=1;i<=n;i++)pre[i]=pre[i-1]+(R[i]=='0'?1:0);
for(i=n;i>=1;i--)suf[i]=suf[i+1]+(R[i]=='0'?1:0);
DP1[0][0]=DP2[0][0]=0;
for(i=1;i<=n;i++)
{
for(j=0;j<=n;j++)
{
if(DP1[i-1][j]==-1e9)continue;
if(T[i]!='1'&&j+1<=zero)
{
k=0;
if(pre[i]==j+1)k+=s1;
if(suf[i]==zero-j)k+=s2;
DP1[i][j+1]=max(DP1[i-1][j]+k,DP1[i][j+1]);
DP2[i][j+1]=min(DP2[i-1][j]+k,DP2[i][j+1]);
}
if(T[i]!='0'&&i-j<=one)
{
k=0;
if(pre[i]==j)k+=s1;
if(suf[i]==zero-j)k+=s2;
DP1[i][j]=max(DP1[i-1][j]+k,DP1[i][j]);
DP2[i][j]=min(DP2[i-1][j]+k,DP2[i][j]);
}
}
}
printf("%d %d\n",DP2[n][zero],DP1[n][zero]);
return 0;
}E-牛牛的斐波那契字符串
大概知道怎么做了，但是有点难写，懒...
F-牛牛的树行棋
此题其实就是一个树上的nim博弈，每个节点的sg值为其到叶子节点的最远距离，我们直接DFS一次即可求出。那么设ans=sg[1]^sg[2]^...^sg[n]，若ans为0，表示先手为负，输出NO，若ans为正，我们接下来的工作就是寻找sg[u]^sg[v]=ans的点对(u,v)数，其中v是以u为根节点的子树的子节点。设这个数量为s，我们再DFS一次，假如当前结点为x，k=ans^sg[x]，设V[k]为根节点到该节点路径上结点SG值为k的数量，那么s+=V[k]就行了。至于维护V数组，因为递归DFS遍历本质相当于出入栈操作，每次x结点入栈时V[sg[x]]++,出栈时V[sg[x]]--即可。
时间复杂度：O(n)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int s=0,ans=0,SG[500005]={0},V[1100005]={0};
vector<int>R[500005];
void DFS1(int x,int fa)
{
int i,j;
for(i=0;i<R[x].size();i++)
{
j=R[x][i];
if(j==fa)continue;
DFS1(j,x),SG[x]=max(SG[x],SG[j]+1);
}
ans^=SG[x];
}
void DFS2(int x,int fa)
{
int i,j,k;
V[SG[x]]++,k=ans^SG[x],s+=V[k];
for(i=0;i<R[x].size();i++)
{
j=R[x][i];
if(j!=fa)DFS2(j,x);
}
V[SG[x]]--;
}
int main()
{
int i,j,n;
scanf("%d",&n),n--;
while(n--)scanf("%d%d",&i,&j),R[i].push_back(j),R[j].push_back(i);
DFS1(1,0);
if(ans)DFS2(1,0),printf("YES\n%d\n",s);
else printf("NO\n");
return 0;
}完结撒花，若有疏漏之处，还望大佬们轻喷~
京公网安备 11010502036488号