字符统计：给出一个只包含空格和小写字母的字符串，问出现次数最多的字符（多个字符按照字典序输出）
签到题。
#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;
}