A
诈骗题，看起来有点高大上，其实只要将\(k\)减\(1\)即可。
B
此时序列中的递增子序列是不需要移动的，所以此时本题就满足一个贪心，设不在这个递增子序列中的数的个数是\(x\),则答案为\(\lfloor \frac{x}{k} \rfloor\)
C
这破比赛怎么这么喜欢排列。
此时这个排列满足三个性质。
- 每个数字出现不能超过两次。
- 数字\(1\)不能出现超过一次。
- 数字\(n\)必须出现。
此时考虑原数组中出现过两次的数，每次出现这个数，构造的两个排列中必定有且仅有其中一个这一位于数组中这一位相等，此时另一个排列只需填入任意一个小于这个数且没出现过的数即可。这里可以\(\text{lowerbound}\)来维护。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f;
const int N=2e5+10;
inline int read(){
int f=1,w=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
w=(w<<1)+(w<<3)+(c^48);
c=getchar();
}
return f*w;
}
struct node{
int fir,sec;
}c[N];
int maxn=0;
int t[N];
int a[N];
int T;
int n;
int p[N],q[N];
signed main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++){
t[i]=0;
c[i].fir=c[i].sec=0;
}
for(int i=1;i<=n;i++){
a[i]=read();
t[a[i]]++;
p[i]=inf;
q[i]=inf;
if(c[a[i]].fir) c[a[i]].sec=i;
else c[a[i]].fir=i;
}
bool fl=1;
for(int i=1;i<=n;i++){
if(t[i]>2) fl=0;
}
if(fl==0){
printf("NO\n");
continue;
}
fl=1;
for(int i=1;i<=n;i++){
if(t[i]>1) fl=0;
}
if(fl){
printf("YES\n");
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
printf("\n");
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
printf("\n");
}else{
bool pd=0;
vector <int> v;
for(int i=1;i<=n;i++){
if(t[i]==0) v.push_back(i);
}
for(int i=1;i<=n;i++){
if(t[a[i]]==2){
p[i]=a[i];
q[c[a[i]].sec]=a[i];
int little=upper_bound(v.begin(),v.end(),a[i])-v.begin()-1;
if(little<0){
pd=1;
break;
}
p[c[a[i]].sec]=v[little];
q[i]=v[little];
t[a[i]]=inf;
v.erase(v.begin()+little,v.begin()+little+1);
}
}
if(v.size()>0||pd==1){
printf("NO\n");
}else{
printf("YES\n");
for(int i=1;i<=n;i++){
if(p[i]==inf) printf("%d ",a[i]);
else printf("%d ",p[i]);
}
printf("\n");
for(int i=1;i<=n;i++){
if(q[i]==inf) printf("%d ",a[i]);
else printf("%d ",q[i]);
}
printf("\n");
}
}
}
return 0;
}
D
这道题xj来的时候似乎讲过，考虑构造一张图，将要交换的两个数建边，使\(i ->P_i\)，则会形成若干个环，所以最小步数即为\(n-\)环数，这时若有两个相邻的数在一个环上，则可以少做一步操作，最小步数减一，否则加一。
E
神仙组合题，对\(f(p)\)进行分类讨论。
- \(f(p)=0\):一种，此时数组有序。
- \(f(p)=1\)
- \(f(p)=2\)
- \(f(p)=3\)
所以\(ans_0=1,ans_1=2 \times (2n)!-n!,ans_2=2 \times C_{2n}^{n}\times n! \times (2n)!- \sum \limits_{i=0}^{n}{C_{n}^{n-i}C_{n}^{i}C_{2n-i}^{n} \times (n!)^3},ans3=(3n)!-ans0-ans1-ans2\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
inline int read(){
int f=1,w=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
w=(w<<1)+(w<<3)+(c^48);
c=getchar();
}
return f*w;
}
int jc[N*3],ny[N*3];
int n,mod;
int ans0,ans1,ans2,ans3;
int quickpow(int x,int p){
int ans=1;
while(p){
if(p&1){
ans=x*ans%mod;
}
p>>=1;
x=x*x%mod;
}
return ans;
}
int C(int a,int b){
if(a<=b) return 1;
return jc[a]*ny[b]%mod*ny[a-b]%mod;
}
signed main(){
n=read();mod=read();
jc[0]=1;
ny[0]=1;
for(int i=1;i<=3*n;i++){
jc[i]=i*jc[i-1]%mod;
}
for(int i=1;i<=3*n;i++){
ny[i]=quickpow(jc[i],mod-2);
}
ans0=1;
ans1=(2ll*jc[2*n]-jc[n]-ans0+mod)%mod;
ans2=2ll*C(2*n,n)%mod*jc[n]%mod*jc[2*n]%mod;
int res=0;
for(int i=0;i<=n;i++){
res=(C(n,n-i)%mod*C(n,i)%mod*C(2*n-i,n)%mod*jc[n]%mod*jc[n]%mod*jc[n]%mod)%mod;
ans2=(ans2-res+mod)%mod;
}
ans2=(ans2-ans1-ans0+mod)%mod;
ans3=(jc[3*n]-ans1-ans2-ans0+mod)%mod;
int now=0;
now=(ans1+ans2*2+ans3*3)%mod;
//cout<<ans1<<" "<<ans2<<" "<<ans3<<" "<<endl;
cout<<now<<endl;
return 0;
}
F
首先这题有一个显然的\(O(n^2)\)dp,\(f_i=\min{(f_i,f_j+\min \limits_{k=j}^{i}{a_k})\times (i-j)^2}\)
但显然这个dp无法通过，我们考虑优化，这里有一个引理：
若从\(i\)跳到\(j\)，中间经过\(k\),则当选\(a_k=\min \limits_{k=i}^{j}{a_k}\)时最优。
这个其实很好猜到，因为经过最小值肯定比不经过最小值更优。
有这个引理，再结合这道题的数据量，我们可以考虑进行根号分治。对于每一次转移，必定有\((i-j)^2 \times \min \limits_{k=i}^{j}{a_k} \le (i-j) \times n\)。
考虑移项，\(\min \limits_{k=i}^{j}{a_k} \le \frac{n}{i-j}\)。
到这里进行分类讨论。
- 若\((i-j) \le \sqrt{n}\)：
这样的话需要处理的次数较少，直接暴力枚举即可，时间复杂度\(O(n \sqrt{n})\)
- 若$(i-j) > \sqrt{n} $:
根据引理，每次转移时\(i,j\)中其中一个必定是这段区间的最小值，如果最小值在\(j\)，那就对于每一个\(i\)，枚举最小值\(x\)；如果最小值在\(i\)，那就对于每一个\(j\)枚举最小值\(x\)，转移到\(j\)的下一个等于\(x\)的位置。用单调栈维护，时间复杂度\(O(n \sqrt{n})\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+10;
const int inf=1e18;
inline int read(){
int f=1,w=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
w=(w<<1)+(w<<3)+(c^48);
c=getchar();
}
return f*w;
}
int f[N];
int n;
int a[N];
int id[N];
int s[N];
int tot;
int x;
signed main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
f[i]=inf;
}
s[++tot]=1;
f[1]=0;
int limit=sqrt(n);
for(int i=2;i<=n;i++){
x=a[i];
for(int j=i-1;j>=1&&j>=i-limit;j--){
x=min(x,a[j]);
f[i]=min(f[i],f[j]+(i-j)*(i-j)*x);
}
while(tot&&a[s[tot]]>a[i]) tot--;
s[++tot]=i;
for(int j=1;j<=limit+1&&j<tot;j++){
f[i]=min(f[i],f[s[j]]+(i-s[j])*(i-s[j])*a[s[j]]);
}
if(a[i]<limit){
for(int j=i-1;j>=1;j--){
if(a[i]>=a[j]) break;
f[i]=min(f[i],f[j]+(i-j)*(i-j)*a[i]);
}
}
}
for(int i=1;i<=n;i++){
printf("%lld ",f[i]);
}
return 0;
}