CF
Problem - 474D - Codeforces(dp好题)
白花只能以k的倍数存在
\(f_i=f_{i-1}+f_{i-k}\)
注意可能是负数形式，所以最后
(s[r] - s[l - 1]+mod) % mod
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 1e9+7;
const int N=1e5+10;
LL f[N],s[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t,k;cin >> t >> k;f[0] = s[0] = 1;for (int i = 1; i <= 100000;i++){if(i>=k)f[i] = (f[i - 1] + f[i - k]) % mod;elsef[i] = f[i - 1] % mod;s[i] = (s[i - 1] + f[i]) % mod;}while(t--){int l, r;cin >> l >> r;cout << (s[r] - s[l - 1]+mod) % mod << endl;//可能是负数，要加再取模}
}
Problem - 814C - Codeforces（双指针）
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2000;
int sum[N][30];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;string s;cin >> s;s = " " + s;//注意for (int i = 1; i <= n;i++){for (int j = 0; j < 26;j++){sum[i][j] = sum[i - 1][j];}sum[i][s[i] - 'a']++;}int q;cin >> q;while(q--){int x;char c;cin >> x >> c;int l = 1, r = 1, ans = 0;for (int r = 1; r <= n;r++){while(r-l+1-(sum[r][c-'a']-sum[l-1][c-'a'])>x)//注意l++;ans = max(ans, r - l + 1);}cout << ans << endl;}
}
Problem - 1553D - Codeforces
贪心，匹配
It is guaranteed that the total number of characters in the strings over all test cases does not exceed 2⋅105.
可以注意到题目有写要求，所以时间复杂度为\(O(∑∣s∣)\)，不会超
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=2e5+10;void solve()
{string s, t;cin >> s >> t;int n = s.size();int m = t.size();int i = n - 1;bool flag = 1;for (int j = m - 1; j >= 0;j--){while(i>=0&&s[i]!=t[j])i -= 2;if(i<0){flag = 0;break;}i -= 1;}cout << (flag ? "YES\n" : "NO\n");
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
搜索
P1331 海战 - 洛谷
不一样的方法，直接枚举找左上角
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=1010;
char g[N][N];
bool check(int x,int y){int cnt = 0;if(g[x][y]=='#')cnt++;if(g[x][y+1]=='#')cnt++;if(g[x+1][y]=='#')cnt++;if(g[x+1][y+1]=='#')cnt++;return cnt == 3;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;for (int i = 1; i <= n;i++){for (int j = 1; j <= m;j++){cin >> g[i][j];}}for (int i = 1; i <= n;i++){for (int j = 1; j <= m;j++){if(check(i,j)){cout << "Bad placement.\n";return 0;}}}int ans = 0;for (int i = 1; i <= n;i++){for (int j = 1; j <= m;j++){if(g[i][j]=='#'&&g[i-1][j]!='#'&&g[i][j-1]!='#'){ans++;}}}cout << "There are " << ans << " ships.\n";
}
P1596 [USACO10OCT] Lake Counting S - 洛谷
常见dfs套路
注意分清n和m！！！
第一种写法，找满足的
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define double long double
#define endl '\n'
const LL mod = 998244353;
const int N=105;
char a[N][N];
int n,m;void dfs(int x,int y){a[x][y] = '.';for (int i = -1; i <= 1;i++){for (int j = -1; j <= 1;j++){int xx = x + i;int yy = y + j;if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]=='W')dfs(xx, yy);}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m;for (int i = 1; i <= n;i++){for (int j = 1; j <= m;j++){cin >> a[i][j];}}int ans = 0;for (int i = 1; i <= n;i++){for (int j = 1; j <= m;j++){if(a[i][j]=='W'){dfs(i, j);ans++;}}}cout << ans << endl;
}
第二种dfs写法，去掉不满足的
void dfs(int x,int y){
if(x<=0||x>n||y<=0||y>m||a[x][y]=='.')
return;
a[x][y] = '.';
for (int i = 0; i < 8;i++){
dfs(x + dx[i], y + dy[i]);
}
}