牛客OI周赛15-普及组
嘀咕一下：
原本以为和前几次的的题目一样的难度，结果我就会写一题，线段树当时还没学，多组背包还不会，但是其实这个难度还是可以接受的
传送门
A-咪咪游戏
题目大意：
每次询问你一个字符串，判断是否由mq连接而成
难度：
看懂了题目要你做什么就很好做出来了，一道签到题
题目类型：模拟
思路：
1.由mq连接而成一定是一个偶数串
2.如果是偶数串，就用一个strng类的变量模拟连接的过程
复杂度：
(log n)
代码：
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int main(){
int q;
js;
cin>>q;
string s,ss;
while(q--){
s="";
cin>>ss;
int len = ss.size();
if(len&1){
cout<<"No"<<endl;
continue;
}
len>>=1;
for(int i = 0 ; i < len ;++i) s+="mq";
if(s==ss) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
B-三角形
题目大意：
在n组数中各取一个数相加得到一个和a[i]，求前m小的和a[i]相加的结果
难度：
刚开始如果想到了暴力枚举然后再观察怎么去优化还是可以做出来的，我当时只想暴力枚举。。这是不可能过的
题目类型：dp
思路：
仔细观察会发现n个宝箱和的全部可能并不大，所以可以用dp把所有情况枚举出来，取前m大即可。
多组背包，状态dp[i][k]，表示处理到（求和）第i个背包时，和为k的个数,dp[i][k]=0表示没有这个和数；
状态转移方程：dp[i][k]+=dp[i-1][k-a[i][j]]，最后的答案就是在dp[n][1~tot]中取前m个加起来，tot是n个宝箱最大的和
复杂度：
暴力枚举的话不会超时，但是存不下所有的方案，动态规划的复杂度：
枚举n个宝箱，取出m个宝物，最多10000个结果，所以总复杂度是 (10000*nm)
代码：
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int f[105][10005],a[105][105];
int n,m,tot=0;
int main() {
js;
cin>>n>>m;
for(int i=1;i<=n;++i) {
cin>>a[i][0];
int sum=0;
for(int j=1;j<=a[i][0];++j) {
cin>>a[i][j];
sum=sum<a[i][j]?a[i][j]:sum;
}
tot+=sum;
}
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 cnt=0,ans=0;
for(int i=1;i<=tot;++i) {
while(f[n][i]) {
ans+=i;
--f[n][i];
++cnt;
if(cnt==m) return cout<<ans<<endl,0;
}//如果直接ans+=i* f[n][i]，取的数可能超过m个
}
}C-区间加
题目大意：
牛妹有长度为n的一组数按顺序存储在数组里，她想把这些数都变成m，可以通过任选一段区间[ai~aj]，j>=i，将里面的数字全部加一，每个区间的i和j也就是起点和终点都不能一样，问有多少方案
思路：
题目的意思是区间的起点和终点都要不一样，很重要。
可以看成括号匹配来写，首先用a[i]表示Ai=m需要的操作次数，在这个基础上a[i]-=a[i-1]表示Ai=m需要的操作次数比A(i-1)=m多多少还是少多少，特别的，a[1]表示Ai=m需要的操作次数，a[n+1]表示An=m需要的操作次数的相反数，这样处理后就是括号匹配问题了。
如果a[i]=1表示Ai=m需要的操作次数比A(i-1)=m多1，我们就要在i这个位置放一个左括号，也就是now++；
如果a[i]=-1表示Ai=m需要的操作次数比A(i-1)=m少1，我们就要在i-1这个位置放一个右括号，对应的左括号有now种选择，而且加上一个右括号就会少一个左括号，所以答案乘以now--；
如果a[i]=0,表示Ai=A(i-1)，可能用左括号括起i-1或者i-1和i，然后再在固定的位置补上一个右括号或者固定的左右括号，有now种方案，也可以什么都不做，所以答案乘以(now+1)，特别的，当now==0时表示Ai和A(i-1)就是m，不需要任何操作。
注意：如果a[i]大于1或者小于-1表示a[i]=-1表示Ai=m需要的操作次数比A(i-1)=m多或者少大于1次，这种方案是不存在的，比如a[i]=2，我们只能在i放一个左括号，如果在i-1处也放一个显然Ai和A(i-1)不会相等，但是又不能在一个位置放多个括号，所以这个时候直接输出答案为0，其它的情况也都类似。
复杂度：
从头到尾判断是否要加括号，复杂度 (n)
题目类型：思维
代码：
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod = 998244355;
int a[2005],n,m;
int main() {
js;
cin>>n>>m;
for(int i=1;i<=n;++i) {
cin>>a[i]; //存入Ai
a[i]=m-a[i]; //a[i]表示Ai=m需要操作的次数
}
for(int i=n+1;i>=1;--i) a[i]-=a[i-1]; //a[i]=-1表示比i-1需要的操作次数少，也就是比i-1大，反之亦然，等于0就是相等
ll now=0,ans=1;
for(int i=1;i<=n+1;++i) {
if(a[i]<-1||a[i]>1) return cout<<"0"<<endl,0;
if(a[i]==-1) ans=ans*now-- % mod;
if(!a[i]) ans=ans*(now+1) % mod;
if(a[i]==1) ++now;
}
cout<<ans<<endl;
return 0;
}D-多元组
题目大意：
给一个序列a，问有多少个长度为m的递增子序列
前导知识：
ai是10^9比较大需要用到线段树的离散化将ai=10^9压缩到n=10^5
然后利用树状数组来得到区间的和
难度：
不会线段树和离散化不好写
题目类型：dp，离散化，树状数组
思路：
可以看成是求长度为m的lis(最长递增子序列)问题。
状态：dp[i][j],以a[i]结尾长度为j的lis
状态转移方程:dp[i][j]=
∑可以用树状数组维护。如果先枚举长度一个树状数组就可以了。
具体操作为：
状态：tree[len][a[i]],以a[i]结尾长度为len的lis,
状态转移方程：tree[len][a[i]]+=sum(len-1,a[i]-1),状态转移需要用add来维护，修改其它涉及a[i]的地方
复杂度：
O(mnlogn)
代码：
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod = 1e9+7;
ll tree[51][100001];
inline int lowbit(int x) {
return (x&-x); //得到x二进制第一个非0的1的幂
}
void add(int i,int x,ll v) {
while(x<=100000) {
tree[i][x]=(tree[i][x]+v)%mod;
x+=lowbit(x);
}
}//状态转移并维护含有a[i]的地方
ll sum(int i,int x) {
ll sum=0;
while(x) {
sum=(sum+tree[i][x])%mod;
x-=lowbit(x);
}
return sum;
}//结尾小于等于x的lis的数量
int a[100001], b[100001],n,m;
int main() {
js;
cin>>n>>m;
for(int i=1; i<=n; i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
int cnt=unique(b+1,b+1+n)-b-1; //得到b中不重复元素的个数，多余的元数被移到数组后面
for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+cnt,a[i])-b; //离散化
for(int i=1;i<=n;++i)
for(int len=1;len<=m;++len)
if(len==1) add(1,a[i],1);
else add(len,a[i],sum(len-1,a[i]-1));
cout<<sum(m,n)<<endl;
return 0;
}
自愧不如