目录
D. Almost Arithmetic Progression
A. Remove Duplicates
要求我们从右边开始保留数，我们可以考虑的就是用map来保存第一个出现的，然后倒着输出即可
void solve(){
cin>>n;
vector<int> a(n);
for(auto&v:a) cin>>v;
vector<int> ans;
map<int,int> mp;
for(int i=n-1;i>=0;i--){
if(mp.count(a[i])) continue;
ans.push_back(a[i]);
mp[a[i]]++;
}
cout<<ans.size()<<endl;
for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]<<' ';
cout<<endl;
return ;
}B. File Name
从字符中把三个以上的x删掉最多连续两个，明显的对于x我们使用双指针来维护即可
void solve(){
cin>>n;
string s; cin>>s;
s=' '+s;
int ans=0;
for(int i=1;i<=n;i++){
int j=i;
if(s[j]=='x'){
while(j<=n && s[j]=='x') j++;
j--;
ans+= max(0,j-i+1-2);
i=j;
}
}
cout<<ans<<endl;
return ;
}
C. Letters
最为经典的前缀和加二分处理，注意我们找到比现在大于等于的然后减去前面的就好了
void solve(){
cin>>n>>m;
vector<LL> a(n+5);
for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
while(m--){
LL x; cin>>x;
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
cout<<l<<' '<<x-a[l-1]<<endl;
}
return ;
}D. Almost Arithmetic Progression
题目考察的是等差数列的性质我们可以了解到等差数列固定了第一个数和公差整个也就固定了，也就是固定了第一个数和第二个数整个也就固定了，所以一共有3*3=9种操作次数，所以我们只要对1，2处理即可，考虑使用函数解决（重复的东西用函数美丽且好调试）
void solve(){
cin>>n;
vector<int> a(n+5),b(n+5);
int ans=2*n+5;
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
if(n==1||n==2) return cout<<0,void();
auto change = [&](){
int d=b[2]-b[1];
int res=0;
for(int i=3;i<=n;i++){
if(b[i]-b[i-1]==d) continue;
res++;
if(b[i]-b[i-1]==d+1) b[i]--;
else if(b[i]-b[i-1]==d-1) b[i]++;
else return 2*n+5;
}
return res;
};
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++){
for(int k=1;k<=n;k++) b[k]=a[k];
b[1]+=i,b[2]+=j;
ans=min(ans,abs(i)+abs(j)+change());
}
cout<<(ans >2*n ? -1 : ans)<<endl;
return ;
}E. Bus Video System
我们可以多样的思考问题，整个过程一定是以恶搞波形图，最后一定是整体上升的一个过程，那么最大的不能大过容量，最小的不能小于0，所以我们就此维护最大值和最小值然后处理出初始的时候的上下限即可
LL t,n,m;
void solve(){
cin>>n>>m;
LL Smax=0,Smin=m,now=0;
while(n--){
LL x; cin>>x;
now+=x;
Smax=max(Smax,now);
Smin=min(Smin,now);
}
LL top = m-Smax;
LL down = max(0ll - Smin,0ll);
cout<<max(top-down+1,0ll)<<endl;
return ;
}F. Mentors
题目告诉我们关系不会重复不妨这样考虑如果我们从小到大按照能力排序然后对于每一个关系维护前面比他小的有口角的人数，按照他的排序减去有口角的即可，对于相同的数我们在口角中去掉，然后再考虑答案的时候用map来维护前面每一个能力出现的数量再减去即可
struct code{
int x,id;
bool operator<(const code&t)const{
return x<t.x;
}
}e[N];
void solve(){
cin>>n>>m;
vector<int> w(n+1);
for(int i=1;i<=n;i++){
int x; cin>>x;
w[i]=x;
e[i]={x,i};
}
sort(e+1,e+1+n);
vector<int> ton(n+5);
map<int,int> same;
while(m--){
int a,b; cin>>a>>b;
if(w[a]==w[b]) continue;
if(w[a]>w[b]) swap(a,b);// 有能力的在后面
ton[b]++;
}
vector<int> ans(n+5);
for(int i=1;i<=n;i++){
auto [x,id]=e[i];
ans[id]=i-1-ton[id]-same[x];
same[x]++;
}
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
cout<<endl;
return ;
}G. Petya's Exams
简单贪心策略，我们肯定是谁先考试先处理谁他的前面一定是最多的可用空闲时间,然后从他的告诉考试时间考试处理，如果够了就退出，这是一个比较简单且明显的贪心策略，可以简单的证明是正确的
struct code{
int id,d,test,need;
bool operator<(const code&t)const{
return test<t.test;
}
}e[N];
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int d,test,need; cin>>d>>test>>need;
e[i]={i,d,test,need};
}
sort(e+1,e+1+m);
vector<int> day(n+5);
for(int i=1;i<=m;i++){
auto [id,d,test,need]=e[i];
day[test]=m+1;
for(int i=d;i<=test;i++){
if(day[i]) continue;
day[i]=id;
need--;
if(!need) break;
}
if(need) return cout<<-1,void();
}
for(int i=1;i<=n;i++) cout<<day[i]<<' ';
cout<<endl;
return ;
}
