实际上如果你觉得你切了两道题但是没拍的话那就真的会保龄。所以我挂了200。警钟长鸣。
ARC125C
使字典序最小的话，他给了 \(k\) 个我们需要扔掉最后一个不看，要不然可能不优。例子我不会举。
首先去掉最后一个之后显然我们最优的就是让他给的做第一个，然后怎么小怎么来。构造的话考虑每次在他给的数后面放一个目前没有放过的最小的数，最后把所有没放过的倒序放一下。
考场上脑抽了把没放过的放开头了然后光荣保龄。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,k,cnt,pos,a[200010];
bool v[200010];
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1,j=1;i<k;i++){
printf("%d ",a[i]);
v[a[i]]=true;
while(v[j])j++;
if(j<a[i]){
printf("%d ",j);v[j]=true;
while(v[j])j++;
}
}
for(int i=n;i>=1;i--)if(!v[i])printf("%d ",i);
return 0;
}
ARC125D
如果你一个数前面出现了一个相同的数，那么以前面那个数结尾的应该全都不合法。于是考虑设 \(dp[i]\) 为第 \(i\) 个数结尾的答案，那么我们存一个 \(pos[i]\) 表示 \(i\) 的上一次出现的位置，转移就变成了：
- 如果没有出现过那么就是之前的所有答案+1
- 如果出现过则自己加上 \(pos[i]\) 到 \(i-1\) 的所有答案，顺便把 \(pos[i]\) 位置的清空（因为如果你 \(pos[i]\) 能结尾，那 \(i\) 也是一样的）。不能加之前的，因为之前的被 \(pos[i]\) 统计过了。
容易发现这是个单点修改区间查询，树状数组维护。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=998244353;
int n,ans,a[200010],c[200010],pos[200010];
int lowbit(int x){
return x&-x;
}
void update(int x,int val){
while(x<=n){
c[x]=(c[x]+val)%mod;x+=lowbit(x);
}
}
int query(int x){
int sum=0;
while(x){
sum=(sum+c[x])%mod;x-=lowbit(x);
}
return sum;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(pos[a[i]]){
int x=(query(pos[a[i]])-query(pos[a[i]]-1)+mod)%mod;
update(i,(query(i-1)-query(pos[a[i]]-1)+mod)%mod);
update(pos[a[i]],mod-x);
}
else update(i,query(i-1)+1);
pos[a[i]]=i;
}
printf("%d",query(n));
}
ARC126C
考场上写了个整除分块，本机跑挺快结果T飞了。
我们现在显然能手推出这样一个式子：（设 \(d\) 为公约数）
这个显然可以整除分块做是不是（
正解考虑开个桶整个前缀和维护 \(a\) ，于是我们找 \(d\) 的时候从大到小找，枚举倍数就行了。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
int n,ans,maxx,k,cnt[300010];
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++){
int x;scanf("%lld",&x);
k+=x;maxx=max(maxx,x);
cnt[x]++;
}
for(int i=maxx-1;i>0;i--)cnt[i]+=cnt[i+1];
if(k/n>maxx){
printf("%lld",k/n);return 0;
}
for(int i=maxx;i>=1;i--){
int ret=0;
for(int j=1;j<=maxx;j+=i)ret+=cnt[j];
if(k/i>=ret){
printf("%lld",i);return 0;
}
}
return 0;
}
ARC126D
这个我bdfs结果没什么详细的解释。也可能是我不会bdfs
看见这个 \(k\) 考虑状压。我们设 \(dp[i][j]\) 为扫描到 \(i\) ，找到的 \(1-k\) 的数的集合为 \(j\) 的答案，那么我们有两种转移：
- 扫到一个数，如果没在集合里，那么加进来。这时我们需要的步数是集合和这个数组成的逆序对数，也就是 \(j\) 中比 \(a\) 大的个数，也就是 \(j\) 中高于第 \(a\) 位的为 \(1\) 的位的个数。
- 把这个集合整个向右平移一位/把所有没放进来的数集体向左平移一位，取个最小值。
代码经过卡常。
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int n,k,dp[1<<16],cnt[1<<16],t[1<<16];
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
int main(){
n=read();k=read();
for(register int j=1;j<(1<<k);++j)cnt[j]=cnt[j>>1]+(j&1),t[j]=min(cnt[j],k-cnt[j]);
for(register int j=1;j<(1<<k);++j)dp[j]=0x3f3f3f3f;
for(register int i=1;i<=n;++i){
int a=read()-1;
for(register int j=(1<<k)-1;j>=0;--j){
if(dp[j]!=0x3f3f3f3f){
if(!(j&(1<<a)))dp[j|(1<<a)]=min(dp[j|(1<<a)],dp[j]+cnt[j>>a]);
dp[j]+=t[j];
}
}
}
printf("%d",dp[(1<<k)-1]);
}