A 咪咪游戏
直接判断奇数位是否均为m,偶数位均为q即可。
/* * @Author: wxyww * @Date: 2020-04-03 19:18:25 * @Last Modified time: 2020-04-03 19:20:35 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 100010; ll read() { ll 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*10+c-'0'; c=getchar(); } return x*f; } char s[N]; void solve() { scanf("%s",s + 1); int n = strlen(s + 1); if(n & 1) { puts("No");return; } for(int i = 1;i <= n;i += 2) if(s[i] != 'm') { puts("No");return; } for(int i = 2;i <= n;i += 2) if(s[i] != 'q') { puts("No"); return; } puts("Yes"); } int main() { int Q = read(); while(Q--) { solve(); } return 0; }
B 三角形
用f[i][j]表示前i个箱子,宝物价值和为j的方案数。状态是的。转移的时候枚举当前箱子选的宝物,背包转移即可。复杂度为
总复杂度就是。
最后枚举宝物价值和,找到前K中方案即可。
/* * @Author: wxyww * @Date: 2020-04-03 19:29:25 * @Last Modified time: 2020-04-03 20:43:42 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 110; ll read() { ll 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*10+c-'0'; c=getchar(); } return x*f; } ll ans; int f[N][N * N]; int a[N][N],len[N]; int main() { int n = read(),K = read(); for(int i = 1;i <= n;++i) { len[i] = read(); for(int j = 1;j <= len[i];++j) a[i][j] = read(); } f[0][0] = 1; for(int i = 1;i <= n;++i) { for(int j = 1;j <= len[i];++j) { for(int k = a[i][j];k <= 10000;++k) { f[i][k] += f[i - 1][k - a[i][j]]; f[i][k] = min(f[i][k],K); } } } for(int i = 1;i <= 10000;++i) { int w = min(K,f[n][i]); K -= w; ans += w * i; } cout<<ans; return 0; }
C 区间加
一开始理解错题意了。题目要求“对于任意两次区间加的起始,结束位置各不相同。”而不是“两个区间的不能相同。”
我们用now记录下现在还没有匹配的区间左端点的个数,用表示第个点到还需要加多少。
这样如果比小1,我们就要在i - 1这个位置放一个右端点,对应的左端点有now种选择,所以答案乘以now。
如果比大1,我们就要在i这个位置放一个左端点,就让now++
如果a[i]与a[i-1]相等的话,我们可以在i-1处放一个右端点,再在i处放一个左端点,防止右端点的时候有now种方案,也可以什么都不做,所以就有(now+1)种方案,所以答案乘以(now+1)即可。
/* * @Author: wxyww * @Date: 2020-04-03 21:19:10 * @Last Modified time: 2020-04-04 07:58:55 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 2010,mod = 998244355; ll read() { ll 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*10+c-'0'; c=getchar(); } return x*f; } int a[N]; int main() { int n = read(),m = read(); for(int i = 1;i <= n;++i) a[i] = m - read(); for(int i = n + 1;i >= 1;--i) a[i] -= a[i - 1]; ll now = 0,ans = 1; for(int i = 1;i <= n + 1;++i) { if(abs(a[i]) > 1) { puts("0");return 0; } if(a[i] == -1) ans = ans * now-- % mod; if(a[i] == 0) ans = ans * (now + 1) % mod; if(a[i] == 1) ++now; } cout<<ans; return 0; }
D 多元组
用表示前个数字,选择了j个数字的方案数量。
如果暴力转移的话就是
先将一开始的数组离散化一下,然后开K个树状数组优化一下,转移的复杂度就变成了,总的复杂度就是。
/* * @Author: wxyww * @Date: 2020-04-03 21:07:29 * @Last Modified time: 2020-04-03 21:15:18 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 100010; const int mod = 1e9 + 7; ll read() { ll 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*10+c-'0'; c=getchar(); } return x*f; } int n,m,a[N],ls[N],f[N][52]; void update(int *tree,int pos,int c) { while(pos <= n) { tree[pos] += c; tree[pos] >= mod ? tree[pos] -= mod : 0; pos += pos & -pos; } } int query(int *tree,int pos) { int ret = 0; while(pos) { ret += tree[pos]; ret >= mod ? ret -= mod : 0; pos -= pos & -pos; } return ret; } int tree[52][N]; int main() { n = read(),m = read(); for(int i = 1;i <= n;++i) a[i] = ls[i] = read(); sort(ls + 1,ls + n + 1); for(int i = 1;i <= n;++i) a[i] = lower_bound(ls + 1,ls + n + 1,a[i]) - ls; ll ans = 0; for(int i = 1;i <= n;++i) { f[i][1] = 1; for(int j = 2;j <= m;++j) f[i][j] = query(tree[j - 1],a[i] - 1); for(int j = 1;j <= m;++j) update(tree[j],a[i],f[i][j]); ans += f[i][m]; ans >= mod ? ans -= mod : 0; } cout<<ans; return 0; }