题意：n个排成一排的怪物，每次可以进行两种操作
1.消除长度小于等于k的连续怪物序列
2.消除长度等于k的连续怪物序列并要求两边的怪物序列不为空
思路：根据题意打个表先
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long
const int N = 1e3 + 10;
int sg[N];
int main(){
IOS
int k;cin >> k;
sg[0] = 0;cout << 0 << endl;
for(int i = 1;i <= N - 10;i++){
bool vis[N] = {0};
if(i <= k)
vis[0] = 1;
for(int j = 1;j <= i - j - k;j++){
vis[sg[j] ^ sg[i - j - k]] = 1;
}
for(int j = 0;j <= N - 10;j++)
if(!vis[j]){
sg[i] = j;
break;
}
if(sg[i] == 0)
cout << i << endl;
}
}
可以得出当n为\(0\)或者\((n-k-1)\%(4k+2)=0\)时必败
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long
int main(){
IOS
int t;cin >> t;
while(t--){
int k,n;cin >> k >> n;
if(n == 0 || ((n - k - 1) % (4*k + 2) == 0))
cout << "Bob" << endl;
else
cout << "Alice" << endl;
}
}
题意：给出一个01序列（第一个一定为1），每次可以翻转\([l_i,r_i]\)内的字符(从0变1，从1变0)，问k次操作后最大能变到多少
思路：每次操作最多消除一个连续0串，因为第一个一定为1，因此如果有0串，那么也可能不消除0串（10变01，0串数量不变，k--）因此如果存在0并且k大于0串的数量那么就让它变成全1，如果k数量少于0串数量，那么就让前面的0串变为1
如果n为1，那么根据奇偶性得出答案
如果全为1，那么第一次一定会多一个0串，因此当k=1时一定有一个0串，否则一定能将其重新翻回全1，因此当k=1是就让最后一个为0即可
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long
int main(){
IOS
int t;cin >> t;
while(t--){
int n;ll k;cin >> n >> k;
string s;cin >> s;
int num0 = 0;
for(int i = 1;i < n;i++){
if(s[i] == '0' && s[i] != s[i - 1])
num0++;
}
if(num0 == 0 && k == 1){
for(int i = 1;i < n;i++)
cout << 1;
cout << 0 << endl;
}else if(n == 1){
if(k % 2)
cout << 0 << endl;
else
cout << 1 << endl;
}else if(num0 <= k){
for(int i = 1;i <= n;i++)
cout << 1;
cout << endl;
}else{
for(int i = 0;i < n;i++){
if(s[i] == '0' && s[i] != s[i - 1])
k--;
if(s[i] == '0' && k >= 0)
cout << 1;
else
cout << s[i];
}
cout << endl;
}
}
}
题意：n个堆，一开始第1堆有\(k,k-1,...,1\)，每次移动只能移动x到x+1的头上或者到空堆上，问将第1堆移动到第二堆k的最大值
思路：\(f(2)=1\)，要移动所有子到另一个格子，那么最下面的必须移动，也就是将上面的全移动后还剩下两个格子，如果剩下m个空格子，那么我最多转移\(f(m)+1\)个物品到新格子上，那么让它剩下两个的可以转移的物品数量就为\(\sum^{n-1}_{i=2} (f[i]+1)\)，那么还剩下一个转移的数字因此\(f[n+1]=(\sum^{n-1}_{i=2} (f[i]+1))+1\)，因此\(f[n]=2^{n-1}-1\)
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long
ll p = 998244353;
ll qpow (ll x,ll y){
ll ans = 1;
while(y){
if(y&1) ans = (ans * x) % p;
x = (x*x) % p;
y >>= 1;
}
return ans;
}
int main(){
IOS
int t;cin >> t;
while(t--){
int n;cin >> n;
cout << (qpow(2,n - 1) - 1 + p) % p << endl;
}
}
题意：找能组成特定图形边集的数量
思路：枚举特殊点对，用bitset优化连接点的交集数量
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long
const int N = 1e3 + 10, p = 1e9 + 7;
bitset<N> bs[N];
ll ny[N],jcny[N],jc[N];
ll fmx(ll a,ll b){
ll ans = 1;
while(b){
if(b&1) ans = (ans * a) % p;
a = (a*a) % p;
b >>= 1;
}
return ans;
}
void init(){
ny[0] = jc[0] = jcny[0] = 1;
for(int i = 1;i <= N - 10;i++){
ny[i] = fmx(i,p - 2);
jcny[i] = ny[i] * jcny[i - 1] % p;
jc[i] = jc[i - 1] * i % p;
}
}
ll C(ll n,ll m){
if(n < m) return 0;
return (((jc[n]*jcny[n-m]) % p) * jcny[m]) % p;
}
int main(){
IOS
init();
int t;cin >> t;
while(t--){
int n,m;cin >> n >> m;
for(int i = 1;i <= n;i++) bs[i].reset();
for(int i = 1;i <= m;i++){
int u,v;cin >> u >> v;
bs[u][v] = bs[v][u] = 1;
}
ll ans = 0;
for(int i = 1;i <= n;i++){
for(int j = i + 1;j <= n;j++){
bitset<N> tem = bs[i] & bs[j];
int n1 = bs[i].count(),n2 = bs[j].count(),n3 = tem.count();
if(bs[i][j]) n1--,n2--;
ans = (ans + C(n3,4) * (C(n2 - 4,2) + C(n1 - 4,2))) % p;
}
}
cout << ans << endl;
}
}
题意：取k个子字符串，并且子字符串内字符完全相同，问最大子字符串总长减k的值
思路：水
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long
const int N = 1e3 + 10, p = 1e9 + 7;
int main(){
IOS
int t;cin >> t;
while(t--){
string s;cin >> s;
int n = s.size();
int ans = 0;
for (int l = 0; l < n;) {
int r = l;
while (r + 1 < n && s[r + 1] == s[l]) {
r++;
}
if (r - l >= 1) {
ans += r - l;
}
l = r + 1;
}
cout << ans << endl;
}
}
题意：每m个至少选两个，让花费最小
思路：那么我们只要考虑前m个的状态即可，因此开\(dp[M][M]\)即可，第一个参数代表相对位置，第二个代表包括自己与前面不取的数量(该数量最大为m)，我们在转移的过程中保证两边的空和不大于m-1即可
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long
const int M = 2e3 + 10,N = 2e4 + 10;
const ll INF = 1e18;
ll dp[M][M],mi[M][M],pos[N],a[N];
int main(){
IOS
int t;cin >> t;
while(t--){
int n,m;cin >> n >> m;
memset(dp,0x3f,sizeof(dp));
memset(mi,0x3f,sizeof(mi));
for(int i = 1;i <= n;i++){
cin >> a[i];
pos[i] = i % m;
}
for(int i = 2;i <= m;i++){
for(int j = i - 1;j >= 1;j--){
dp[pos[i]][i - j] = a[i] + a[j];
mi[pos[i]][i - j] = min(dp[pos[i]][i - j],mi[pos[i]][i - j - 1]);
}
}
for(int i = m + 1;i <= n;i++){
for(int j = i - 1;j >= i - m + 1;j--){
dp[pos[i]][i - j] = a[i] + mi[pos[j]][m - (i - j)];
mi[pos[i]][i - j] = min(mi[pos[i]][i - j - 1],dp[pos[i]][i - j]);
}
}
ll ans = INF;
for(int i = n - m + 1;i <= n;i++){
ans = min(ans,mi[pos[i]][i - n + m - 1]);
}
cout << ans << endl;
}
}
题意：n个人，任意排列，先得前k个人最大值，之后一个一个比对其他人直到找到比最大值大的取，问取到最大值概率最大时k的最小值
思路：设n个人，取前k个人
假设最大值在m位置，那么m必须大于k，并且前m-1的最大值必须落在前面k个位置
因此概率为\(\frac{k}{n(m-1)}\)，结合m的取值因此概率为\(p=\sum_{i=k+1}^n \frac{k}{n(i-1)}\)
计算前缀和\(\frac{1}{i}\)就能在\(O(1)\)时间内算出特定\(p=f(n,k)\)的概率，取最大的p最小的k即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
double pre[N];
int main(){
for(int i = 1;i <= 1e4;i++)
pre[i] = pre[i - 1] + 1.0 / i;
int t;cin >> t;
while(t--){
int n;cin >> n;
pair<int,double> ans = {0,1.0 / n};
for(int k = 1;k < n;k++){
if(ans.second < (k * (pre[n - 1] - pre[k - 1])) / n)
ans = {k,(k * (pre[n - 1] - pre[k - 1])) / n};
}
cout << ans.first << endl;
}
}