A. Skip
分析
设 (f[i]) 为上一次参加的比赛是第 (i) 场的最大愉悦值
则 (f[i]=max(f[i],f[j]-frac{(i-j)(i-j-1)}{2}+a[i]),j<i,a[j] leq a[i])
对于随机的数据，把枚举的范围卡到 (3000) 即可
容易发现，如果没有 (a[j] leq a[i]) 的限制，那么就是一个裸的斜率优化 (dp)
把 (f[i]-frac{i^2}{2}-frac{i}{2}) 看做 (y)，把 (i) 看做 (x)，把 (-i) 看做 (k)
横坐标和斜率都是单调的
加上后面的限制之后可以用 (CDQ) 分治人为地排出权值的单调性
具体地，在大区间内按照权值从小到大排序，在计算左区间对右区间的贡献时按照在原数组中的下标排序
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
const double eps=1e-8;
int a[maxn],n,id[maxn];
long long f[maxn];
bool cmp1(rg int aa,rg int bb){
if(a[aa]==a[bb]) return aa<bb;
return a[aa]<a[bb];
}
bool cmp2(rg int aa,rg int bb){
return aa<bb;
}
double getY(rg int id){
return 1.0*f[id]-0.5*id*id-0.5*id;
}
double getX(rg int id){
return 1.0*id;
}
double getxl(rg int i,rg int j){
if(std::abs(getX(j)-getX(i))<eps){
if(std::abs(getY(j)-getY(i))<eps) return 0;
else if(getY(j)>getY(i)) return 1e18;
else return -1e18;
}
return (getY(j)-getY(i))/(getX(j)-getX(i));
}
int q[maxn],head,tail;
void solve(rg int l,rg int r){
if(l==r) return;
rg int mids=(l+r)>>1;
solve(l,mids);
std::sort(id+l,id+mids+1,cmp2);
std::sort(id+mids+1,id+r+1,cmp2);
head=1,tail=0;
rg int now=l;
for(rg int i=mids+1;i<=r;i++){
while(id[now]<id[i] && now<=mids){
while(head<tail && getxl(q[tail],id[now])>=getxl(q[tail-1],q[tail])) tail--;
q[++tail]=id[now];
now++;
}
while(head<tail && getxl(q[head],q[head+1])>=-1.0*id[i]) head++;
if(head<=tail) f[id[i]]=std::max(f[id[i]],f[q[head]]-1LL*(id[i]-q[head]-1)*(id[i]-q[head])/2LL+a[id[i]]);
}
std::sort(id+l,id+r+1,cmp1);
solve(mids+1,r);
}
int main(){
n=read();
for(rg int i=1;i<=n;i++) a[i]=read(),id[i]=i;
memset(f,~0x3f,sizeof(f));
f[0]=0,a[0]=-0x3f3f3f3f;
std::sort(id,id+n+1,cmp1);
solve(0,n);
rg long long ans=-0x3f3f3f3f3f3f3f3f;
for(rg int i=0;i<=n;i++) ans=std::max(ans,f[i]-1LL*(n-i)*(n-i+1)/2LL);
printf("%lld
",ans);
return 0;
}
B. String
分析
考虑搜索，搜索时从小到大去加字符相当于按照字典序排序
搜索的时候记录一个字符出现次数的前缀和来判断是否合法
数据范围比较大，要记忆化
因为影响答案的只是上一个字符出现的次数和前面已经出现了 (1 sim k) 次的字符有多少种
把后面的部分哈希一下存到以前面部分为下标的 (map) 中即可
这样写 (k>8) 的也能直接搜过，不用特判
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<unordered_map>
#define rg register
typedef unsigned long long ull;
typedef long long ll;
const int maxn=1e6+5;
const ull bas=233333;
int k,tax[maxn],tot,vis[maxn],cnt;
char s[maxn];
ull ed;
ll n;
std::unordered_map<ull,ll> mp[30];
ll dfs(rg ull zt,rg int lat,rg ll rk){
if(mp[lat].find(zt)!=mp[lat].end() && rk>mp[lat][zt]) return mp[lat][zt];
if(zt==ed){
if(rk==1){
printf("%s
",s+1);
std::exit(0);
} else {
return mp[lat][zt]=1;
}
}
rg ll nans=0,tmp=0;
cnt++;
for(rg int i=0;i<26;i++){
if(i+'a'==s[cnt-1]) continue;
vis[i]++,tax[vis[i]]++;
rg ull nzt=0;
for(rg int j=1;j<=k;j++) nzt=nzt*bas+j*tax[j];
if(tax[vis[i]]<=k-vis[i]+1){
s[cnt]='a'+i;
tmp=dfs(nzt,vis[i],rk);
nans+=tmp,rk-=tmp;
}
tax[vis[i]]--,vis[i]--;
}
cnt--;
return mp[lat][zt]=nans;
}
int main(){
scanf("%d%lld",&k,&n);
for(rg int i=1;i<=k;i++) ed=ed*bas+i*(k-i+1);
dfs(0,0,n);
printf("-1
");
return 0;
}
C. Permutation
分析
令 (f[i][j]=f[i-1][j]+f[i][j-1]+j,f[1][x]=x+1,f[x][0]=1)
那么答案就是 (f[m][n-k-1])
发现可以用组合数的含义去优化
然后再用 (sumlimits_{i=a}^{b} C_i^y = C_{b+1}^{y+1} -C_a^{y+1}) 就可以做到线性
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5,mod=1e9+7;
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int delmod(rg int now1,rg int now2){
return now1-=now2,now1<0?now1+mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
int n,k,m,jc[maxn],jcc[maxn],ny[maxn];
int getC(rg int nn,rg int mm){
return mulmod(jc[nn],mulmod(jcc[mm],jcc[nn-mm]));
}
int ans=0;
int main(){
n=read(),k=read(),m=read();
n-=(k+1);
ny[1]=1;
for(rg int i=2;i<maxn;i++) ny[i]=mulmod(mod-mod/i,ny[mod%i]);
jc[0]=jcc[0]=1;
for(rg int i=1;i<maxn;i++) jc[i]=mulmod(jc[i-1],i),jcc[i]=mulmod(jcc[i-1],ny[i]);
if(m>=2) for(rg int j=0;j<=n;j++) ans=addmod(ans,mulmod(n-j,getC(m-1+j,j+1)));
for(rg int j=0;j<=n;j++) ans=addmod(ans,getC(m+j-1,m-1));
printf("%d
",ans);
return 0;
}