T1
用时：\(20\) min
期望得分：\(100\) pts
实际得分：\(100\) pts
直接二分，然后贪心 check 一下就行。
#include<bits/stdc++.h>
#define ll long long
#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
/*
一眼二分
让当前数尽量小，这样可以给后面更多的调整空间
*/
int a[MAX],n;
bool check(int lim){
int t=a[1]-lim;
for(int i=2;i<=n;i++){
int x=t+1;
if(x-a[i]>lim) return 0;
t=max(x,a[i]-lim);
}
return 1;
}
signed main(){
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) a[i]=read();
int l=0,r=2e9,ans=0;
while(l<=r){
int mid=(l+r)>>1;
// cout<<mid<<endl;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans;
return 0;
}
T2
考场用时：\(2.5\) h
期望得分：\(0\)
实际得分：\(0\)
这题构思+读题花了约 \(1\) h，然后连写带调一直写到考试结束，细节很多，自己码力也不是很行，没写出。
这题就是二分 \(ans\)，然后断环为链，贪心判断是否合法即可。
#include<bits/stdc++.h>
#define ll long long
#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
/*
二分ans，对于check，枚举最终选择的颜色段
对于每个颜色开一个vector，s[i]代表颜色为i的点的所有下标，枚举时只在对应vector内枚举
断环为链，线性的枚举这个长度为lim的区间，O(1)转移dis和
判断dis和是否<=k，满足则直接返回1
假设所有颜色个数都相等，复杂度 O(nlogn)
期望得分100pts
*/
int n,m,k,tong[MAX],cnt;
vector<int> s[MAX];
int del(int i,int l,int r,int mid){
int dell=(s[i][mid]-s[i][mid-1]-1)*(mid-l);
int delr=(s[i][mid]-s[i][mid-1]-1)*(r-mid+1);
return dell-delr;
}
bool check(int lim){
// cout<<lim<<endl;
for(int i=1;i<=cnt;i++){
// cout<<i<<endl;
int siz=s[i].size();
if(siz<2*lim) continue;
int mid=0,sum=0;
for(int j=0;j<lim;j++)
sum+=(s[i][j]-s[i][0]-j);
// cout<<sum<<endl;
while(del(i,0,lim-1,mid+1)<=0){
sum+=del(i,0,lim-1,mid+1);
mid++;
}
// cout<<mid<<" "<<sum<<endl;
if(sum<=k) return 1;
//中点单增
for(int l=1;l+lim-1<siz;l++){
int r=l+lim-1;
sum-=(s[i][mid]-s[i][l-1]-(mid-(l-1)));
sum+=(s[i][r]-s[i][mid]-(r-mid));
while(del(i,l,r,mid+1)<=0){
sum+=del(i,l,r,mid+1);
mid++;
}
// cout<<mid<<" "<<sum<<endl;
if(sum<=k) return 1;
}
}
return 0;
}
signed main(){
// freopen("10.in","r",stdin);
// freopen("magic.out","w",stdout);
n=read(),m=read(),k=read();
// if(n==10&&m==10&&k==1) return puts("3"),0;
for(int i=1;i<=n;i++){
int x=read();
if(!tong[x]) tong[x]=++cnt;
s[tong[x]].push_back(i);
}
for(int i=1;i<=cnt;i++)
for(int j=0,siz=s[i].size();j<siz;j++)
s[i].push_back(n+s[i][j]);
int l=1,r=n,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
// puts("---------------");
}
cout<<ans;
return 0;
}
T3
考场用时：\(10\) min
期望得分：\(0\)
实际得分：\(10\)
T2花了太长时间，导致这题暴力都没写，直接 \(T\) 组数据全部输出了 Satisfied，正好第一个包是全都有解，瞎猫碰上死耗子了属于是。
\(60\) 的暴力就是直接枚举所有的 \((2n-2m)!\) 种配对方案，然后 \(O(n^2)\) 的并查集或者二分图染色即可。
代码没写完。
标签：10,报告,int,mid,long,11.1,解题,check,define From： https://www.cnblogs.com/wapmhac/p/16849434.html