本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-29 21:14:45

T316849 人数

考察最值、排序等。可以用最值，也可以用sort、桶排序等。

T311007 优秀的码字

本题考察枚举及其优化。

枚举：枚举第$i,j$个字符串$(i<j)$再判断其不同子串的个数。时间复杂度$O(n^2m)$

如何优化？

1. 当出现小于$k$的距离，立即退出。

2. 数学优化。在 $60%$数据基础上另有 $40%$ 的数据 $N>2^m $ 根据鸽笼原理，那么必然有两个相同的字符。一定不符合要求。

参考代码：

#include <bits\/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn=222;
string ss[maxn];

int main()
{
	int N,M,K;scanf("%d%d%d",&N,&M,&K);
	if(N>(1LL<<M))return puts("No"),0;
	for(int i=1;i<=N;++i) cin>>ss[i];
	sort(ss+1,ss+1+N);\/\/排序可以找出更近的符号。
	for(int i=1;i<=N;++i)
	{
		int dis=0,j=i+1;
		for(int k=0;k<M;++k)if(ss[i][k]!=ss[j][k]) ++dis;
		if(dis<K) return puts("No"),0;
	}
	
	for(int i=1;i<=N;++i)
  		for(int j=i+2;j<=N;++j)
	{
		int dis=0;
		for(int k=0;k<M;++k)if(ss[i][k]!=ss[j][k]) ++dis;
		if(dis<K) return puts("No"),0;
	}
	return puts("Yes"),0;
}

T3 挑战赛

考察内容：排序+贪心。 什么情况下一个人能拍到榜首呢？

自己先拿到最高分，让后其余的选手得分尽量低。

其他选手怎样得分尽量低呢？

$a_i$低的人本轮得到高分，高的人得到低分，那么有更多的人可以排名更高。

因为题目中讨论的是机会，可以从最有力一个选手的角度出发安排战局。

参考代码：

#include<bits\/stdc++.h> 
using namespace std;
const int N=3e5+114; 
int a[N];
bool cmp(int x,int y){
    return x>y;
}
int main(){
	int n,maxx=0,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	} 
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){\/\/高分的人本次得到小分。
        maxx=max(maxx,a[i]+i);
    }
    for(int i=1;i<=n;i++){
    	if(a[i]+n>=maxx) sum++;
	}
    cout<<sum;
    return 0;
}

方法二 zrul 二分如果一个排名x能拿第一，排名比x高的一定能na第一

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define N 300005
#define INF 2147483647
using namespace std;
int n,a[N],b[N];
inl int read(){
   reg int f=1,x=0;
   reg char ch=getchar();
   while(ch<'0'||ch>'9'){
       if(ch=='-') f=-1;
       ch=getchar();
   }
   while(ch>='0'&&ch<='9'){
       x=(x<<1)+(x<<3)+(ch^48);
       ch=getchar();
   }
   return f*x;
}
inl void write(int x){
   if(x<0) x=-x;
   if(x>=10) write(x\/10);
   putchar(x%10^48);
}
bool check(int x){
	int tot=n-1;
	for(int i=1;i<=n;i++,tot--)
		if(b[i]!=a[x]&&(b[i]+tot>a[x]+n||b[i]+tot==a[x]+n&&i<x)) return false;
	return true;
}
int lower(){
	int l=1,r=n,mid=0,ans=0;
	while(l<=r){
		mid=l+r>>1;
		if(check(mid)){
			ans=mid;
			l=mid+1;
		}else r=mid-1;
	}
	return ans;
}
signed main(){
   n=read();
   for(int i=1;i<=n;++i) a[i]=read();
   memcpy(b,a,sizeof(a));
   sort(a+1,a+n+1,greater<int>());
   sort(b+1,b+n+1);
  	write(lower());
   return 0;
}

T316918 爬楼梯

本题考察了递推和高精度加法。

设$f[i]$为达到第$i$层楼梯的方案数。 则$f[i]=f[i-1]+f[i-2]+f[i-3],i>3$

初始条件为$f[1]=1,f[2]=2,f[3]=4$,数据范围较大，需要用高精度加法。

参考代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n,f[5010][5010],len;
void add(int k) { \/\/高精加法
	for(int i=1; i<=len; i++)\/\/两数相加
		f[k][i]=f[k-1][i]+f[k-2][i]+f[k-3][i];
	for(int i=1; i<=len; i++) { \/\/进位
		f[k][i+1]+=f[k][i]\/10;
		f[k][i]%=10;
	}
	if(f[k][len+1]>0)len++;
}
int main() {

	cin>>n;
	len=1;
	f[1][1]=1;\/\/预处理
	f[2][1]=2;\/\/预处理
	f[3][1]=4;
	for(int i=4; i<=n; i++)\/\/开始计算
		add(i);
	
	for(int j=len; j>=1; j--)\/\/输出
		cout<<f[n][j];
	cout<<endl;
	return 0;
}

T316902 分糖果

本题的要求最大值最小，二分答案的标志性名次。那么分析本题具有单调性吗？

根据题意，小朋友们得到的糖果数越平均越好。蛀牙值越大，每个小朋友分的糖果数越多，分的份数就越少。否则越多。

我们二分蛀牙值，如果分完后糖果有剩余，就还要增大；如果不够分的，就要缩小。

参考代码：

#include <iostream>  
using namespace std;
long long n,m,l=1,r,ans;
long long a[300010];
bool check(long long x){ \/\/x 是当前的蛀牙值
	long long sum=0;
	for(int i=1;i<=m;i++) sum+=(a[i]+x-1)\/x;
	return sum<=n;
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){cin>>a[i];r+=a[i];} \/\/mid 的极限是总共的球数 
	while(l<r){	\/\/二分模板 
		long long mid=(l+r)\/2+1;
		if(check(mid)){r=mid-1;ans=mid;}
		else l=mid;
	}
	cout<<ans;
	return 0; 
}

T310718 花园

本题考察了结构体和集合的容斥。

要处理重合的部分

我们给定了矩形的对角线的两个端点，但没有说明大小，要统一为左上角和右下角，然后，找到交集部分。

如何找到交集部分？共有四个横坐标，四个纵坐标，找到中间的两个。

参考代码：

#include <iostream>
#include <iomanip>
#include<stdio.h> 
using namespace std;
typedef long long ll;
struct node{\/\/左上角 和右下角 
	ll xa,ya,xb,yb;
}jx1,jx2,jx3;
int n;

node le_ri(){
	node t;
	cin>>t.xa>>t.ya>>t.xb>>t.yb;
	if(t.xa>t.xb)swap(t.xa,t.xb);
	if(t.ya>t.yb)swap(t.ya,t.yb);
	return t;
}
ll s(node t){
	return (t.xb-t.xa)*(t.yb-t.ya);
}
int main()
{
    
	cin>>n;
    jx1=le_ri();
    if(n==1){
    	cout<<s(jx1)<<endl;
    	return 0;
	}
	jx2=le_ri();
	if(jx1.xa>=jx2.xb||jx1.xb<=jx2.xa||jx1.ya>=jx2.yb||jx1.yb<=jx2.ya) {\/\/2在1的左侧，右侧，下侧，上侧 
		cout<<s(jx1)+s(jx2)<<endl;
		return 0;
	}
	\/\/相交的情况
	 jx3.xa=max(jx1.xa,jx2.xa);
	 jx3.xb=min(jx1.xb,jx2.xb);
	 jx3.ya=max(jx1.ya,jx2.ya);
	 jx3.yb=min(jx1.yb,jx2.yb);
	 cout<<s(jx1)+s(jx2)-s(jx3)<<endl;
       
}