咪咪游戏
应该比较简单，就是%7D)
扫一遍即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int sum=0,ff=1; char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') ff=-1;
ch=getchar();
}
while(isdigit(ch))
sum=sum*10+(ch^48),ch=getchar();
return sum*ff;
}
const int N=1e5+5;
char ch[N];
signed main()
{
int Q=read();
for (;Q--;)
{
scanf("%s",ch+1);
int n=strlen(ch+1);
if(n&1)
{
printf("No\n");
goto rp;
}
for ( int i=1;i<=n;i+=2 )
if(ch[i]=='m'&&ch[i+1]=='q') continue;
else
{
printf("No\n");
goto rp;
}
printf("Yes\n");
rp:;
}
} 
三角形
把所有情况枚举出来，取前m大即可。
考虑
于是只要
统计答案就很简单了。
#include <bits/stdc++.h>
using namespace std;
const int N=105;
const int M=N*N;
int n,m,f[N][M],a[N][N],ret[M],ans,tot;
inline int read() {
int sum=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch))
sum=sum*10+(ch^48),ch=getchar();
return sum;
}
int main() {
n=read(),m=read();
for ( int i=1;i<=n;i++ ) {
a[i][0]=read();
int nm=0;
for ( int j=1;j<=a[i][0];j++ ) {
a[i][j]=read();
nm=max(nm,a[i][j]);
}
tot+=nm;
}
f[0][0]=1;
for ( int i=1;i<=n;i++ )
for ( int j=1;j<=a[i][0];j++ )
for ( int k=tot;k>=a[i][j];k-- )
if(f[i-1][k-a[i][j]])
f[i][k]+=f[i-1][k-a[i][j]];
int sum=0,res=0;
for ( int i=1;i<=tot;i++ ) {
while(f[n][i]) {
res+=i;
f[n][i]--;
sum++;
if(sum==m) return printf("%d\n",res),0;
}
}
return 0;
}
区间加
以左括号表示操作区间左端点，右括号表示操作区间右端点，那么一个位置不 能出现两个以及上的左括号或右括号。
故一个位置只有四种情况：
- 不放括号
- 放一个左括号
- 放一个右括号
- 放一个左括号放一个右括号
所以我们设f(i,j)表示前i个位置左括号比右括号多j个且使
对于第i个位置不放括号，有f[i][j]+=f[i−1][j]
第i个位置放左括号，有f[i][j]+=f[i−1][j−1]
第i个位置放右括号，有f[i][j]+=(j+1)⋅f[i−1][j+1]，其中乘上j+1是因为要给当前放的这个右括号匹配上左括号
第i个位置放左右括号，有f[i][j]+=(j+1)⋅f[i−1][j]，其中乘上j+1与上一种情况同理
注意对于1,2情况，a[i]位置相当于被加了j，故需要a[i]+j=h该步才可以转移过去。同样的，对于3,4情况，a[i]位置加了j+1，故需要a[i]+j+1=h，
最后f[n][0]即为答案
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int sum=0,ff=1; char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') ff=-1;
ch=getchar();
}
while(isdigit(ch))
sum=sum*10+(ch^48),ch=getchar();
return sum*ff;
}
const int mo=998244355;
const int N=4005;
int n,m,f[N][N],a[N],ans;
signed main()
{
n=read();
m=read();
for ( int i=1;i<=n;i++ ) a[i]=read();
if(a[1]==m-1||a[1]==m) f[1][0]=1;
if(a[1]==m-1) f[1][1]=1;
for ( int i=2;i<=n;i++ )
for ( int j=max(0ll,m-a[i]-1);j<=max(m-a[i],i);j++ )
{
if(a[i]+j==m)
{
f[i][j]=(f[i][j]+f[i-1][j]+mo)%mo;
if(j) f[i][j]+=f[i-1][j-1]%mo;
f[i][j]=(f[i][j]+mo)%mo;
}
if(a[i]+j==m-1)
{
f[i][j]+=(f[i-1][j+1]*(j+1))%mo;
f[i][j]=(f[i][j]+mo)%mo;
f[i][j]+=(f[i-1][j]*(j+1))%mo;
f[i][j]=(f[i][j]+mo)%mo;
}
}
printf("%lld\n",(f[n][0]+mo)%mo);
return 0;
} 
多元组
其实就是对于M=3的拓展。
对于M=3的情况，考虑树状数组。对于一个a[i]，它的贡献即为左边比他小的
右边比他大的。然后这些就可以用树状数组维护。
考虑到k有两个限制条件，k 具体来说，在外层循环i，建立一个树状数组，以a[k]为下标存储f[i-1][k]的值。当内层循环到j时，f[i][j]+=ask(a[j]-1)，然后在转移到下一个j之前add(a[j],f[i-1][j])。j从小到大循环保证了k
复杂度O(NMlogN)
对于M=3的情况，考虑树状数组。对于一个a[i]，它的贡献即为左边比他小的
考虑到k有两个限制条件，k 具体来说，在外层循环i，建立一个树状数组，以a[k]为下标存储f[i-1][k]的值。当内层循环到j时，f[i][j]+=ask(a[j]-1)，然后在转移到下一个j之前add(a[j],f[i-1][j])。j从小到大循环保证了k
复杂度O(NMlogN)
#include<bits/stdc++.h>
using namespace std;
#define N 100050
const int mod=1e9+7;
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*f;
}
int a[N],b[N],n,mx,bit[51][N],ans,k;
#define ck(x) (x>=mod?x-mod:x)
inline void Add(int p,int x,int d){
while(x<=mx){
bit[p][x]=ck(bit[p][x]+d);
x+=(x&(-x));
}
}
inline int Ask(int p,int x){
int ans=0;
while(x){
ans=ck(ans+bit[p][x]);
x-=(x&(-x));
}
return ans;
}
int main(){
n=read();k=read();
for(int i=1;i<=n;i++){
a[i]=b[i]=read();
}
sort(b+1,b+n+1);
mx=unique(b+1,b+n+1)-b-1;
for(register int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+mx+1,a[i])-b;
}
for(register int i=1;i<=n;i++){
Add(1,a[i],1);
for(int j=2;j<=k;j++){
int tmp=Ask(j-1,a[i]-1);
Add(j,a[i],tmp);
}
}
for(int i=1;i<=mx;i++){
ans=(ans+Ask(k,i)-Ask(k,i-1)+mod)%mod;
}
cout<<ans<<endl;
return 0;
} 
全部评论
(4) 回帖