发现这个比赛忘写题解了，来补题解辣qwq
A.牛牛的三角形
总所周知，三条边可以拼出三角形的充要条件是：最小的两条边长度之和大于第三条边。
看数据范围，n<=100,于是直接一个n^3枚举再判断就行辣！
代码：
#include<bits/stdc++.h>
using namespace std;
int a[101];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);//sort后就不需要管谁大谁小了
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
for(int k=j+1;k<=n;++k){
if(a[i]+a[j]>a[k]){
cout<<a[i]<<" "<<a[j]<<" "<<a[k];
return 0;
}
}
}
}
puts("No solution");
return 0;
} B. 牛牛的鱼缸
嗯，平面几何。。。嗯。。。。
首先，我们先脑补一下，我们将l缩短一下，那么，就会使得我们的面积边为一个直角梯形。
于是，我们要分两种情况：
1.所求图形为直角梯形
2.所求图形为三角形
那么，两个情况的划分依据是什么呢？
显然，就是AD和l的大小关系了！（这里我们假设AD这条边是正好使得所求图形为三角形时，三角形的除h的那条直角边以外的另一条直角边（emmmm，觉得绕的话，就看图，这么想，我们AD是固定的，每次只是在改变l的长短罢了））
画个图发现，明显有:
那么，就有
所以，我们有
那么，我们的划分依据就是l是否大于等于了
若是，明显的，我们现在就是在求一个直角边分别为的三角形面积，相乘除2即可
若不是，我们就是求一个直角梯形的面积，画下图，我们可以直接利用相似三角形/正切求解：
上底=
下底=h
高=l
那么，带入公式（上底+下底）*高/2即可
此题解完。
(哎，我是真的不擅长几何问题啊qwq)
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
double h,l,H,L;
scanf("%lf%lf%lf%lf",&h,&l,&H,&L);
double sita=atan2(H,L);
double P=(h*L)/(H);
if(P<=l){
printf("%.8lf",P*h/2.0);
return 0;
}else{
double Q=(H*(P-l))/L;
printf("%.8lf",(Q+h)*l/2);
}
return 0;
} C.牛牛的揠苗助长
一道明显的二分题。
为啥满足二分性呢？
我们这么想，如果，我们X天后可以使得所有水稻等高，那么，X天以后的每天，我们就可以抑制当天生长的水稻，使它不长，那么所有水稻依旧等高。
所以，这是满足二分性的。
那么，假设，我们二分出来一个天数mid，那么，我们先算出mid天后，我们不进行任何操作，每个水稻的高度。
那么，现在问题就变成了，你可以使用至多x次操作，使得任意一个水稻高度+1 or -1，问你是否可以使得所有水稻等高。
那么，这个问题就与经典的集合问题等价了：
就是有n个人，每个人都在数轴上的一个位置，问你要使得所有人在同一个地方集合，并且所有人走的距离之和最小的距离是多少？
仔细想想，集合问题的走一步，不就正好和本题的改变水稻高度一样么？坐标-1，就相当于水稻高度-1，坐标+1，就相当于水稻高度+1，最后在同一个位置集合，就等价于坐标一样，也即是水稻高度一样。
那么，我们就利用集合问题的结论：在所有人的坐标的中位数的位置集合走的距离和最小。
于是，我们先将当前所有水稻的高度排个序，再计算出需要多少次操作就行了。最后在和mid比较下大小即可~
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+1;
int a[N],b[N];int n;
inline bool check(int x){
for(int i=1;i<=n;++i){
b[i]=a[i]+(x/n);
}
for(int i=x%n;i;--i){
++b[i];
}
//到中位数距离最近
sort(b+1,b+n+1);
int mid=(1+n)/2,res=0;
for(int i=1;i<=n;++i){
res+=abs(b[mid]-b[i]);
}
return res<=x;
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
int l=1,r=1e16,ans=1e16;
while(l<=r){//由于可以减少高度，故满足二分性
int mid=(l+r)>>1;
if(check(mid)){
ans=mid,r=mid-1;
}else{
l=mid+1;
}
}
printf("%lld",ans);
return 0;
} D.01限定串
一道有点麻烦但是明显而简单的dp题。
因为我们知道了待定串中，0和1的个数，那么，如果我们确定了前i个字符中0的个数，那么，前i个字符中1的个数和i后面的0和1的个数也就同时确定了，那么，我们就可以通过比较个数是否相等来计算贡献了~
(由于贡献有负，所以算最大值的时候需初始化为极小值而不是0)
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+1;
int dp[N][N];//最大
int pd[N][N];//最小
int sum[N];
int main(){
memset(dp,~0x3f3f,sizeof(dp));
memset(pd,0x3f3f,sizeof(pd));
dp[0][0]=0;pd[0][0]=0;
int n,cnt0,cnt1,valp,vals;
scanf("%d%d%d%d%d",&n,&cnt0,&cnt1,&valp,&vals);
string x,y;
cin>>x>>y;
for(int i=1;i<=n;++i){
sum[i]=(sum[i-1]+(x[i-1]=='0'));
}
for(int i=1;i<=n;++i){
for(int j=0;j<=min(cnt0,i);++j){
int val=0;
if(sum[i]==j){
val+=valp;
}
if(j&&y[i-1]!='1'){//put 0
int po=0;
if(cnt0-j+1==sum[n]-sum[i-1]){
po+=vals;
}
pd[i][j]=min(pd[i][j],pd[i-1][j-1]+val+po);
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+val+po);
}
if(y[i-1]!='0'){
int po=0;
if(cnt0-j==sum[n]-sum[i-1]){
po+=vals;
}
pd[i][j]=min(pd[i][j],pd[i-1][j]+val+po);
dp[i][j]=max(dp[i][j],dp[i-1][j]+val+po);
}
}
}
cout<<pd[n][cnt0]<<" "<<dp[n][cnt0];
return 0;
} E.牛牛的斐波那契字符串
最后一点时间码的，码了一百多行的分类讨论+矩阵快速幂，然后挂了qwq，这里就先提供个思路吧（要是有误欢迎指出）
我们注意到如果A，B的长度都大于等于S串的话，那么题目将变成寥寥的几个情况：
1.S在一整个A串中
2.S在一整个B串中
3.S在A和A衔接处
4.S在A和B衔接处
5.S在B和A衔接处
6.S在B和B衔接处
然后分别计算出贡献后，再统计最终串有多少个A,B,AA,AB,BA,BB（可以直接矩阵快速幂实现）再乘贡献即可（注意，有些情况其实并不可能）
但是，我们并不能保证A，B的长度大于等于S啊，怎么办呢？
我们可以先预做几次操作，直到A，B的长度大于等于S为止！（当然，如果中途等于n了，直接计算输出答案即可~）
然后再把n减小相应的操作次数就行辣！
此题完。
因为代码出锅了，懒得debug，所以就没有代码辣！qwq
F. 牛牛的树行棋
这该死的博弈论竟然如此的香
明显的博弈论。
我们可以转化为取石子游戏，每个点到它最终到达的叶子的距离就是它的石子数量，每次取x个石子，就等价于将这个点的棋子向最终所在的叶子移动x步。
但是，因为我们一个点可以到达的叶子其实有多个，所以，一个点到底有多少“石子”，其实是不定的。
这个怎么办呢？
对于这个，我们可以直接使用sg函数解决。
但是sg函数怎么求呢？
直接利用定义就好啦！
首先，叶子节点的sg值肯定就是0
那么对于其他的节点i，
但是，如果我们真的这么求的话，每次计算一个点的sg值是可能会被卡成O(n)的
那么，我怎么办呢？
很简单，我们观察发现，如果其中有一个点j的sg值为x，那么根据定义，肯定也存在相应的0...x-1(因为j在i的子树中，那么在j子树中的点也一定在i的子树中)，所以，i的后继节点的sg值肯定也包含了0-x
那么，我们只需要找到最大的一个sg[j]，那么0-sg[j]肯定都存在i的后继状态中，而同时由于sg[j]是最大的那个，那么sg[j]+1又肯定不在，所以，sg[i]=sg[j]+1,于是，我们再同时维护一下每个点的子树中最大的那么sg值就好啦！（其实算i儿子当中最大的sg值就行了。。。）
那么，再跟据结论，如果所有棋子的sg值的异或和为0，那么先手必败，输出NO，否则输出YES就好了
现在，最主要的问题是，如何计算第一步的方案数。
我们知道，要先手胜利的话，肯定是将通过取棋子将当前的棋子的sg异或和变为0，那么，我们枚举我们第一步操作的点，那么，我们就是需要将当前的点的sg值变为其他的点的sg值的异或和，那么，我们直接统计这个点的子树中有多少个sg值等于其他点的异或和即可，我们移到哪些点就行了。
要维护这个的话，我们直接乱搞个树上启发式合并树上差分就行了
感谢Lskkkno1大佬提供的思路，菜鸡看懂了qwq
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
#define int long long
struct node{
int v,nex;
}t[N<<1];
int las[N],len;
int sg[N],sum;
int cnt[N],ans;
inline void add(int u,int v){
t[++len]=(node){v,las[u]},las[u]=len;
}
inline void dfs(int now,int fa){
sg[now]=0;
for(int i=las[now];i;i=t[i].nex){
int v=t[i].v;
if(fa!=v){
dfs(v,now);
sg[now]=max(sg[now],sg[v]+1);
}
}
sum^=sg[now];
}
inline void dfs2(int now,int fa){
int tot=cnt[(sum^sg[now])];
++cnt[sg[now]];
for(int i=las[now];i;i=t[i].nex){
int v=t[i].v;
if(v!=fa){
dfs2(v,now);
}
}
tot-=cnt[(sum^sg[now])];
ans-=tot;
}
signed main(){
int n;
scanf("%lld",&n);
for(int i=1;i<n;++i){
int u,v;
scanf("%lld%lld",&u,&v);
add(u,v),add(v,u);
}
//把到叶子的距离看做石头个数的话，就是一个nim取石子游戏
dfs(1,1);
if(!sum){
puts("NO");
}else{
puts("YES");
dfs2(1,1);
printf("%lld",ans);
}
return 0;
} 
京公网安备 11010502036488号