A. Planets
题意：给你一个序列 aaa，你可以分别进行如下操作任意次：
- 花费 \(1\) 的代价删除 \(a_i\)
- 花费 \(c\) 的代价删除 \(\forall a_i=x\)，\(x\) 自定。
求删除整个序列的最小代价。多测。
解法：没啥好说的，暴力
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=2200,mod=998244353;
int a[WR],cnt[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
signed main(){
int T=read();
while(T--){
int n=read(),c=read();
int ans=0;
for(int i=1;i<=n;i++) a[i]=read(),cnt[a[i]]++;
for(int i=1;i<WR;i++){
if(cnt[i]>=c) ans+=c,cnt[i]=0;
else ans+=cnt[i],cnt[i]=0;
}
printf("%lld\n",ans);
}
return 0;
}
B. Meeting on the Line
题意：给定一个长为 \(n\) 的序列 \(a\) 和 \(t\)，请你求出一个 \(x_0\)，使得 \(\max\limits_{i=1}^{n}\{t_i+|a_i-x_0|\}\) 最小化，输出 \(x_0\)
解法：注意到这个 \(t\) 完全可以合并进距离，假如说 \(x_0\) 在 \(a_i\) 右侧，则可以将 \(a_i\) 再左移 \(t\) 格
在左边同理
那我们就人工给 \(a_i\) 加/减 \(t_i\) ，然后求一个坐标最大一个坐标最小加起来除以 \(2\) 即可
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=2200000,mod=998244353,INF=9e18;
int a[WR],c[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
signed main(){
int T=read();
while(T--){
int n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) c[i]=read();
int maxx=0,minn=INF;
for(int i=1;i<=n;i++){
maxx=max(maxx,a[i]+c[i]);
minn=min(minn,a[i]-c[i]);
}
printf("%.8lf\n",(double)(maxx+minn)/2.0);
}
return 0;
}
C. Minimum Notation
题意：给定一个仅包含 \(0\) 到 \(9\) 这几个数字的字符串，你可以执行以下操作任意次：
选择字符串中的一个数字 \(d\)，将 \(d\) 删除后，向字符串任意位置插入一个数字 \(\min(d+1,9)\)
求能够得到的字典序最小的字符串。
解法：又是意识流写出来的
不难发现我们肯定要保留目前序列里最小的数字，并且把它们尽量往前放
如果有其它的数在最小数的前面我们统一把它们扔到后面去，这样肯定更优
因此记录一个最小值，再记录一个最小值的后缀和，枚举每一位判断
具体来说，维护一个 \(cnt\) 数组，如果当前值 \(x\) 是最小值，\(cnt[x]+1\)
否则 \(cnt[\min(x+1,9)]+1\)
当最小值后缀和为 \(0\) 的时候更新最小值即可
（代码里好像还有没啥用的前缀和？）
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=220000,mod=998244353,INF=9e18;
int a[WR],pre[WR][10],suf[WR][10];
int cnt[WR];
char str[WR];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
signed main(){
int T=read();
while(T--){
scanf("%s",str+1);
int n=strlen(str+1);
for(int i=0;i<=9;i++) cnt[i]=0;
for(int i=1;i<=n;i++) a[i]=str[i]-'0';
for(int i=0;i<=n+1;i++){
for(int j=0;j<=9;j++){
pre[i][j]=suf[i][j]=0;
}
}
for(int i=1;i<=n;i++){
pre[i][a[i]]++;
for(int j=0;j<=9;j++){
pre[i][j]+=pre[i-1][j];
}
}
for(int i=n;i>=1;i--){
suf[i][a[i]]++;
for(int j=0;j<=9;j++){
suf[i][j]+=suf[i+1][j];
}
}
// for(int i=1;i<=n;i++){
// for(int j=0;j<=9;j++){
// printf("i=%lld num=%lld pre=%lld suf=%lld\n",i,j,pre[i][j],suf[i][j]);
// }
// }
int pos=0;
for(int i=1;i<=n;i++){
while(!suf[i][pos]) pos++;
if(a[i]!=pos) cnt[min(a[i]+1,9ll)]++;
else cnt[a[i]]++;
}
for(int i=0;i<=9;i++){
for(int j=1;j<=cnt[i];j++) printf("%lld",i);
}
printf("\n");
}
return 0;
}
D. Prefixes and Suffixes
题意：有两个字符串 \(s~,~t\) ，每次可以交换长度为 \(k\) 的 \(s\) 的前缀和 \(t\) 的后缀，可以操作任意次，判断操作是否可能使得 \(s=t\)。
解法：手玩样例会发现无论如何变换， \(s_i\) 和 \(t_{n-i+1}\) 的相对位置是不变的
然后又发现对于这样的一对字符，可以将其移动到任意位置
小证一下：假设要从 \(s_p\) 移动到 \(s_q\) 那么可以先交换 \(p\) 再交换 \(q\)
考虑用这个搞搞事情
注意到一对字符若不同则必定出现偶数次，如果相同则只能在 \(n\) 为奇数时有单独一个出现奇数次
维护一个 \(cnt\) 数组记录每对数的出现次数即可
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=220000,mod=998244353,INF=9e18;
char a[WR],b[WR];
int cnt[30][30];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
signed main(){
int T=read();
while(T--){
memset(cnt,0,sizeof(cnt));
int n=read();
scanf("%s%s",a+1,b+1);
for(int i=1;i<=n;i++){
int vala=a[i]-'a'+1,valb=b[n-i+1]-'a'+1;
if(vala>valb) swap(vala,valb);
cnt[vala][valb]++;
}
int tot=0,flag=true;
for(int i=1;i<=26;i++){
tot+=(cnt[i][i]%2);
for(int j=i+1;j<=26;j++){
// printf("%lld %lld %lld\n",i,j,cnt[i][j]);
if(cnt[i][j]&1){
flag=false;break;
}
}
if(!flag) break;
}
if(!flag||tot>(n&1)) printf("No\n");
else printf("Yes\n");
}
return 0;
}
E. Maximums and Minimums
题意：给定一个长度为 \(n\) 数组 \(a\)，求有多少个区间 \([l, r]\)，满足区间最大值是最小值的倍数
点击查看代码
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=998244353,INF=9e18;
vector<int>d[WR];
int cnt[WR];
int minn[WR>>1][19],lg[WR];
stack<int>stk;
int read(){
int vec=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
vec=(vec<<3)+(vec<<1)+ch-'0';
ch=getchar();
}
return vec*w;
}
void sieve(int n=WR-1){
for(int i=1;i<=n;i++){
cnt[i]=-1;
for(int j=i*2;j<=n;j+=i){
d[j].emplace_back(i);
}
}
}
void STable(int n){
lg[0]=-1;
for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int j=1;j<=lg[n];j++){
for(int i=1;i<=n-(1<<j)+1;i++){
minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r){
int tmp=lg[r-l+1];
return min(minn[l][tmp],minn[r-(1<<tmp)+1][tmp]);
}
int n;
int a[WR],pre[WR],suf[WR],st[WR],ed[WR];
vector<int>vec[WR];
void solve(){
n=read();
for(int i=1;i<=n;i++) a[i]=minn[i][0]=read(),vec[a[i]].emplace_back(i);
STable(n);
while(!stk.empty()) stk.pop();
for(int i=1;i<=n;i++){
while(!stk.empty()&&a[stk.top()]>=a[i]) stk.pop();
if(!stk.empty()) pre[i]=stk.top();
else pre[i]=0;
stk.push(i);
}
while(!stk.empty()) stk.pop();
for(int i=n;i>=1;i--){
while(!stk.empty()&&a[stk.top()]>=a[i]) stk.pop();
if(!stk.empty()) suf[i]=stk.top();
else suf[i]=n+1;
stk.push(i);
}
while(!stk.empty()) stk.pop();
for(int i=1;i<=n;i++){
while(!stk.empty()&&a[stk.top()]<a[i]) stk.pop();
if(!stk.empty()) st[i]=stk.top();
else st[i]=0;
stk.push(i);
}
while(!stk.empty()) stk.pop();
for(int i=n;i>=1;i--){
while(!stk.empty()&&a[stk.top()]<=a[i]) stk.pop();
if(!stk.empty()) ed[i]=stk.top();
else ed[i]=n+1;
stk.push(i);
}
// for(int i=1;i<=n;i++) printf("%lld %lld\n",pre[i],suf[i]);
int ans=0;
for(int i=1;i<=n;i++){
int l=st[i]+1,r=ed[i]-1;
ans+=(min(r+1,suf[i])-i)*(i-max(l-1,pre[i]));
// printf("ans:%lld\n",ans);
for(int j=0;j<d[a[i]].size();j++){
int x=d[a[i]][j];
if(cnt[x]>=0&&cnt[x]<(int)vec[x].size()-1&&l<=vec[x][cnt[x]]&&vec[x][cnt[x]+1]<=r){
int pl=vec[x][cnt[x]],pr=vec[x][cnt[x]+1];
if(query(pl+1,i)>x&&query(i,pr-1)>x){
ans+=(pl-max(l-1,pre[pl]))*(min(r+1,suf[pr])-i);
ans+=(i-max(l-1,pre[pl]))*(min(r+1,suf[pr])-pr);
ans-=(pl-max(l-1,pre[pl]))*(min(r+1,suf[pr])-pr);
}else if(query(pl+1,i)>x){
ans+=(pl-max(l-1,pre[pl]))*(min(r+1,suf[pl])-i);
}else if(query(i,pr-1)>x){
ans+=(min(r+1,suf[pr])-pr)*(i-max(l-1,pre[pr]));
}
}else if(cnt[x]>=0&&l<=vec[x][cnt[x]]){
int p=vec[x][cnt[x]];
if(query(p+1,i)>x){
ans+=(min(r+1,suf[p])-i)*(p-max(l-1,pre[p]));
}
}else if(cnt[x]<(int)vec[x].size()-1&&vec[x][cnt[x]+1]<=r){
int p=vec[x][cnt[x]+1];
if(query(i,p-1)>x){
ans+=(min(r+1,suf[p])-p)*(i-max(l-1,pre[p]));
}
}
}
// printf("ans:%lld\n",ans);
cnt[a[i]]++;
}
printf("%lld\n",ans);
for(int i=1;i<=n;i++) cnt[a[i]]=-1,vec[a[i]].clear();
}
signed main(){
sieve();
int T=read();
while(T--) solve();
return 0;
}