T1
有N个单词，每个单词长c个字，韵律为k，你要用这些单词作诗，每个诗句长度必须为len
诗的某些句子必须是相同的韵脚
这样的句子组不超过26个
很显然的是，我们只要做一次背包DP推出每种韵脚，长度为len的句子有几个
然后快速幂统计一下答案就好了
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
long long tot=0,fs=1;
char ch;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),fs=-1;
while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
return tot*fs;
}
int n,m,k;
int s[5009],c[5009];
int tot[29];
int f[5009][5009],g[5009];
long long ksm(long long x,long long k)
{
long long fin=1;
while(k)
{
if(k&1) fin=(fin*x)%1000000007;
k>>=1;
x=(x*x)%1000000007;
}
return fin;
}
int main ()
{
n=read(),m=read(),k=read();
for(long long i=1;i<=n;i++)
{
s[i]=read(),c[i]=read();
}
for(long long i=1;i<=m;i++)
{
char c;
cin>>c;
tot[c-'A'+1]++;
}
f[0][0]=1;
g[0]=1;
for(long long i=0;i<k;i++)
{
if(!g[i]) continue;
for(long long j=1;j<=n;j++)
{
if(i+s[j]<=k)
{
f[i+s[j]][c[j]]+=g[i];
f[i+s[j]][c[j]]%=1000000007;
g[i+s[j]]+=g[i];
g[i+s[j]]%=1000000007;
}
}
}
long long ans=1;
for(long long i=1;i<=26;i++)
{
if(tot[i]==0) continue;
long long cnt=0;
for(long long j=1;j<=n;j++)
{
cnt+=ksm(f[k][j],tot[i]);
cnt%=1000000007;
}
ans*=cnt;
ans%=1000000007;
}
printf("%lld",ans);
return 0;
}
T2
给定一个序列，数字1——n，你要将其排序，你每次可以将序列开头的一个数字移动到任意位置，输出最短的操作序列（向后移的距离）
显然后缀有序的部分不用移，把前面的往后插即可，用树状数组维护后缀要插在哪个位置（你想打平衡树也行）
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int tot=0,fs=1;
char ch;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),fs=-1;
while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
return tot*fs;
}
int n;
int a[100009];
int tre[100009];
inline int lowbit(int x)
{
return x&(-x);
}
int find(int x)
{
int fin=0;
while(x)
{
fin+=tre[x];
x-=lowbit(x);
}
return fin;
}
void insert(int x)
{
for(int i=x;i<=100000;i+=lowbit(i))
{
tre[i]++;
}
}
int main ()
{
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
}
a[n+1]=n+1;
for(;n>=1;n--)
{
if(a[n]<a[n+1]) insert(a[n]);
else break;
}
cout<<n<<endl;
for(int i=1;i<=n;i++)
{
printf("%d ",n-i+find(a[i]));
insert(a[i]);
}
return 0;
}
T3
给定一个无向图，每头奶牛都延最短路前往原点
现在你可以加一条额外边，此边需要链接原点，问最大的减少的权值和是多少，奶牛只会在路过这条路时向前走
显然，这样的路径构成的是一棵树，那么加边只会影响子树的点，统计即可
#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
long long tot=0,fs=1;
char ch;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),fs=-1;
while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
return tot*fs;
}
long long n,m;
long long c[100009];
long long T,bh;
long long head[100009],nt[200009],to[200009],w[200009];
long long u,v,t;
long long dist[100009],siz[100009],ans;
bool tf[100009];
struct gzw
{
long long id,v;
bool operator<(gzw x)const{return v>x.v;}
};
priority_queue<gzw>q;
vector<long long>g[100009];
void add(long long u,long long v,long long t)
{
bh++;
nt[bh]=head[u];
head[u]=bh;
to[bh]=v;
w[bh]=t;
}
bool f[100009];
void dfs(long long x)
{
siz[x]=c[x];
f[x]=1;
for(vector<long long>::iterator it=g[x].begin();it!=g[x].end();it++)
{
if(!f[*it])dfs(*it),siz[x]+=siz[*it];
}
ans=max(ans,siz[x]*(dist[x]-T));
}
int main ()
{
cin>>n>>m>>T;
for(long long i=1;i<=n;i++) scanf("%lld",c+i);
while(m--)
{
scanf("%lld%lld%lld",&u,&v,&t);
add(u,v,t);
add(v,u,t);
}
q.push({1,0});
while(!q.empty())
{
gzw x=q.top();
q.pop();
if(tf[x.id]) continue;
tf[x.id]=1;
dist[x.id]=x.v;
for(long long j=head[x.id];j;j=nt[j])q.push({to[j],x.v+w[j]});
}
memset(tf,0,sizeof(tf));
for(long long i=1;i<=n;i++)
{
for(long long j=head[i];j;j=nt[j])
{
if(dist[to[j]]==dist[i]+w[j]&&!tf[to[j]])
{
tf[to[j]]=true;
g[i].push_back(to[j]),g[to[j]].push_back(i);
}
}
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
T4
给定一个01序列，将其划分为任意块，每块的长度不得超过k，问0比1多的块最少有多少
基础的dp方程：
dp[i]=min(dp[i],dp[i−j]+(pre[i]−pre[i−j]<=0));
pre为前缀和，显然，这具有单调性，只要dp[i-j]-pre[i-j]最小即可
用优先队列优化即可
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int tot=0,fs=1;
char ch;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),fs=-1;
while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
return tot*fs;
}
int n,k,pre[300001],dp[300001];
string s;
struct gzw
{
int x,y;
bool operator<(const gzw &t) const
{
if(x==t.x) return pre[y]>pre[t.y];
else return x>t.x;
}
}p;
priority_queue<gzw>q;
int main ()
{
//freopen("sb.in","r",stdin);
cin>>n>>k;
cin>>s;
for(int i=n;i>=1;i--)
{
s[i]=s[i-1];
}
for(int i=1;i<=n;i++)
{
pre[i]=s[i]=='H'?pre[i-1]+1:pre[i-1]-1;
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
p.x=0;
p.y=0;
q.push(p);
for(int i=1;i<=n;i++)
{
while(q.top().y<i-k) q.pop();
dp[i]=(pre[i]-pre[q.top().y])<=0?q.top().x+1:q.top().x;
p.x=dp[i];
p.y=i;
q.push(p);
}
cout<<dp[n];
return 0;
}
###T5
不会
###T6
给定一个未确定序列，已知在长度一定的滑动窗口的最小值，数字在1——1e9+7 问方案有多少种
假设最小值都是相同的，那么设f[i]为序列长度为i时，方案数
若窗口值为v，则设1e9+7-v为x，即可选的数
则 f[i]=(x+1)f[i-1]-x^k*f[i-k-1]
代码如下
int solve(int v,int len){
int x=1000000000-v,xk=pow(x,k);
f[0]=f[1]=1;
for(int i=2;i<=len+1;++i){
f[i]=1ll*(x+1)*f[i-1]%mod;
if(i-k-1>=0)f[i]=(f[i]-1ll*xk*f[i-k-1]%mod+mod)%mod;
}
return f[len+1];
}
那么解决了前面的问题，后面的也很好办
设s(v,len)表示现在假设有len个数，取值从v到10^9
，而且每连续k个数至少有一个是vv问题的答案，可以在O(len)时间内球解
可以将一段相等的c合并起来,问题就解决了
#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
long long tot=0,fs=1;
char ch;
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') ch=getchar(),fs=-1;
while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
return tot*fs;
}
const long long LIM=1000000000,mod=1000000007;
int f[200009],a[200009],n,k;
int ksm(int a,int b)
{
int s=1;
for(;b;a=1ll*a*a%mod,b>>=1)
if(b&1) s=1ll*s*a%mod;
return s;
}
int solve(int len,int v)
{
f[0]=1;
f[1]=1;
int pw=ksm(LIM-v,k);
for(int i=2;i<=len+1;i++)
{
f[i]=1ll*(LIM-v+1)*(f[i-1])%mod;
if(i-k-1>=0) f[i]=((f[i]-1ll*pw*f[i-k-1]%mod)%mod+mod)%mod;
}
return f[len+1];
}
int main ()
{
cin>>n>>k;
for(int i=1;i<=n-k+1;i++) cin>>a[i];
int ans=1;
for(int i=1,j=1;i<=n-k+1;i=j+1)
{
for(j=i;a[i]==a[j]&&j<=n-k+1;j++) ;
j--;
int len=j-i+k;
if(i>1&&a[i-1]>a[i]) len-=k;
if(j<n-k+1&&a[j+1]>a[j]) len-=k;
if(len>0) ans=1ll*ans*solve(len,a[i])%mod;
}
cout<<ans;
return 0;
}
