字符统计：给出一个只包含空格和小写字母的字符串，问出现次数最多的字符（多个字符按照字典序输出）

签到题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum[250];
char ans[250];

signed main()
{
	//freopen("T1.in","r",stdin);
	//freopen("T1.out","w",stdout);
	string x;getline(cin,x);
	int len=x.size();
	for(int i=0;i<len;i++) sum[x[i]]++;
	int mx=0,cnt=0;
	for(int i='a';i<='z';i++){
		if(sum[i]>mx){
			mx=sum[i];
			cnt=0;ans[++cnt]=i;
		}
		else if(sum[i]==mx) ans[++cnt]=i;
	}
	for(int i=1;i<=cnt;i++) cout<<ans[i];
	return 0;
}

填数游戏：给出 \(n\) 个空，每个空有一个权值，再给出 \(m\) 个数（\(m\ge n\)），选出 \(n\) 个数填在空里，每填一个数对答案的贡献为这个数乘以这个空的权值，问答案的最大值。

一眼贪心，对于 \(a\) 中小于等于 \(0\) 的和 \(b\) 小的配，对于 \(a\) 中大于 \(0\) 的和 \(b\) 大的配。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int N=1e5+5;
int a[N],b[N];

signed main()
{
	//freopen("T2.in","r",stdin);
	//freopen("T2.out","w",stdout);
	scanf("%lld%lld ",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++) scanf("%lld",&b[i]);
	sort(a+1,a+n+1);sort(b+1,b+m+1);
	int pos=0,ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]<=0) ans+=a[i]*b[i],pos=i;
	}
	for(int i=n,j=m;i>pos;i--,j--) ans+=a[i]*b[j];
	printf("%lld",ans);
	return 0;
}

夹道之樱：一个 \(n\) 个点的带权无向连通图的起点为 \(1\)，终点为 \(n\)，找出一条路径，满足经过的边的最大值减最小值最小，问这个差值为多少。

枚举边权，判断连通，并查集即可。

真服了，暴力我没有想出来。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
const int N=2e3+5,M=4e3+5;
const int inf=0x3f3f3f3f;
struct Edge{
	int u,v,w;
}a[M];
struct DSU{
	int fa[N];
	void init(){
		for(int i=1;i<=n;i++) fa[i]=i;
		return ;
	}
	int find(int x){
		if(fa[x]==x) return x;
		return fa[x]=find(fa[x]);
	}
	void merge(int x,int y){
		int fx=find(x),fy=find(y);
		if(fx==fy) return ;
		fa[fx]=fy;
	}
}pav;

signed main()
{
	//freopen("T3.in","r",stdin);
	//freopen("T3.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&a[i].u,&a[i].v,&a[i].w);
	sort(a+1,a+m+1,[](Edge x,Edge y){return x.w<y.w;});
	int ans=inf;
	for(int i=1;i<=m;i++){
		pav.init();
		for(int j=i;j>=1;j--){
			pav.merge(a[j].u,a[j].v);
			if(pav.find(1)==pav.find(n)){
				ans=min(ans,a[i].w-a[j].w);
				break;
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

终焉之理：给出一个正整数序列以及数 \(k\)，每一轮从第一项开始，排序 \([1\sim k]\ [2\sim k+1]\ ……\)，问需要几轮才可以让原序列变得有序。

这个操作可以看作一个数是把左边比它大的数移到右边，但是移动的区间有限制，每一次最多移动左边的 \(k-1\) 个数，而这个数左边大于它的数肯定都是紧贴着它着，所以需要 \(\lceil \frac{num}{k-1} \rceil\) 轮才可以移到指定位置（\(num\) 表示左边有多少个数比它大）。

这不就是逆序对嘛，可以直接树状数组。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
const int N=1e5+5;
struct BIT{
	int tree[N];
	void init(){
		for(int i=1;i<N;i++) tree[i]=0;
		return ;
	}
	int lowbit(int x){
		return x&-x;
	}
	void add(int key,int x){
		while(key<=N){
			tree[key]+=x;
			key+=lowbit(key);
		}
		return ;
	}
	int ask(int key){
		int ans=0;
		while(key>0){
			ans+=tree[key];
			key-=lowbit(key);
		}
		return ans;
	}
}T;

signed main()
{
	int t;scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&n,&k);
		int mx=0;T.init();
		for(int i=1;i<=n;i++){
			int x;scanf("%lld",&x);
			T.add(x,1);
			mx=max(mx,i-T.ask(x));
		}
		int ans=ceil(num*1.0/(k-1));
		printf("%lld\n",ans);
	}
	return 0;
}

有一个更简便的方法，由于左边大于自己的数是紧贴自己的，所以原序列的位置减去最后移到的位置就是左边有多少个数比它大。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
const int N=1e5+5;
struct Num{
	int val,id;
}a[N];

bool cmp(Num x,Num y){
	return x.val<y.val;
}
signed main()
{
	int T;scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&n,&k);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i].val);
			a[i].id=i;
		}
		stable_sort(a+1,a+n+1,cmp);
		int mx=0;
		for(int i=1;i<=n;i++) mx=max(mx,a[i].id-i);
		int ans=ceil(mx*1.0/(k-1));
		printf("%lld\n",ans);
	}
	return 0;
}