```cpp #include <bits/stdc++.h> using namespace std; #define ll long long int main() { string s; if (!(cin >> s)) return 0; int ans = 0; int lzone = 0, mzone = 0, szone = 0; for (int i = 0; i < s.length(); i++) { if (s[i] == 'L') lzone++; else if (s[i] == 'M') mzone++; else szone++; } int lstart = 0, lend = lzone - 1; int mstart = lzone, mend = lzone + mzone - 1; int sstart = lzone + mzone, send = (int)s.length() - 1; int minl = 0, sinl = 0, linm = 0, sinm = 0, lins = 0, mins = 0; for (int i = lstart; i <= lend; i++) { if (s[i] == 'M') minl++; else if (s[i] == 'S') sinl++; } for (int i = mstart; i <= mend; i++) { if (s[i] == 'L') linm++; else if (s[i] == 'S') sinm++; } for (int i = sstart; i <= send; i++) { if (s[i] == 'M') mins++; else if (s[i] == 'L') lins++; } ans += min(lins, sinl) + min(linm, minl) + min(sinm, mins); // 每三本形成一个环的书需要两次交换 ans += (abs(lins - sinl) + abs(linm - minl) + abs(sinm - mins)) / 3 * 2; cout << ans; return 0; } ``` 本质上就是先按L,M,S分块，本来在对应块里的不用动，优先换互相占了对方位置的书，这样换一次就能使两本书到对应位置，剩下的书每三本成环，每个环要交换两次

emmmm既然要最后两个数组一样 那么他们的长度必须一样，而且只能有合并操作，那么合并一次长度减一，在第二个数组不进行合并的情况下，直接用两个数组长度相减就是答案。而且由题目可以得到，第二个数组不进行任何操作的情况也是正解 ``` #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef struct point{ int x; int y; }point; int main(){ int n,m; cin>>n>>m; int arr[n+10]; int brr[m+10]; for(int i=1;i<=n;i++) cin>>arr[i]; for(int j=1;j<=m;j++) cin>>brr[j]; cout<<abs(n-m)<<endl; return 0; } ```

include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); ``` int cnt=0; string t; getline(cin,t); int n= stoi(t); string s; getline(cin,s); for(int i=0;i<n;i++){ if(s[i]!=' '){ cnt++; } } cout<<cnt<<'\n'; return 0; ``` }

当看到“求方案总数”，“且当前决策只受上一个决策影响”的问题时，脑子里应该自动浮现这个框架： ``` long long dfs(int index, int last_state) { // 1. 边界：任务完成了，算作 1 种有效方案 if (index > total_steps) return 1; // 2. 累加器 long long res = 0; // 3. 遍历当前所有可能的选择 for (int choice : all_possible_choices) { // 4. 判断当前选择是否符合规则（依赖 last_state） if (is_legal(choice, last_state)) { // 5. 递归下去，把子问题的结果加起来 res += dfs(index + 1, choice); } } return res; } ``` ​这种 DFS 其实就是自顶向下的动态规划。 dfs(col, prev_row)实际上就是在计算dp[col][prev_row]。 如果你在 DFS 里加上一个数组memo[col][prev_row]来记录已经计算过的结果（记忆化搜索），它就和递推形式的 DP 完全等价了。 一句话口诀： 按序搜，传状态，过边界，返一，合分求总数。 对于本题，传入的参数为当前的列号和上一行的行号，因为皇后也和上一个皇后在同一行或上下两行，所以要有上一行来作为参数 在主循环中主要是根据initial[i]即是否已经放了皇后来判断方案数 ``` #include<bits/stdc++.h> using namespace std; int n; int initial[11]; // col:当前列数 // prev_row:上一列皇后所在的行号 long long dfs(int col, int prev_row) { // 递归边界：所有列都放好了 if(col>n) return 1; long long count=0; // 如果当前列已经有预设的皇后 if (initial[col]!=0) { int curr_row = initial[col]; // 如果是第一列，或者与上一列行数差不超过1 if (col==1||abs(curr_row-prev_row) <= 1) { count+=dfs(col+1,curr_row); } } // 如果当前列没有预设，需要尝试放置 else { if (col==1){ // 第一列可以放任何位置 for(int r=1;r<=n;r++){ count+=dfs(col+1,r); } } else { // 非第一列，只能放在上一列行号的[-1,0,1]范围内 for(int r=prev_row-1;r<=prev_row+1;r++){ if(r>=1&&r<=n) { //确保不越界 count+=dfs(col+1,r); } } } } return count; } int main() { while(cin>>n&&n!=0){ for(int i=1;i<=n;i++){ cin>>initial[i]; } cout<<dfs(1,0)<<endl; //从第一列开始搜,初始行可以设为任意值 } return 0; } ```

动态规划+前后缀预处理优化 dp[i][j] 为，匹配到t串的第i个字符，且当前在s串下标j的最小路程和，（转为滚动数组） ``` #include <bits/stdc++.h> using namespace std; const int INF = 1e9; int main() { ios::sync\_with\_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ios::sync\_with\_stdio(false); int n, m, l; string s, t; cin >> n >> m >> l; cin >> s >> t; vector<vector<int>> mp(26); for (int i = 0; i < n; ++i) { mp[s[i] - 'a'].push\_back(i); } // 初始化滚动数组 vector<int> prev\_dp(n, INF); int first\_char = t[0] - 'a'; for (int pos : mp[first\_char]) { prev\_dp[pos] = 0; } int ans = 1; // 至少能匹配第一个字符 for (int i = 1; i < m; ++i) { int curr\_c = t[i] - 'a'; int prev\_c = t[i-1] - 'a'; auto& prev\_pos = mp[prev\_c]; auto& curr\_pos = mp[curr\_c]; if (prev\_pos.empty() || curr\_pos.empty()) break; // 预处理前缀最小值和后缀最小值 int k\_prev = prev\_pos.size(); vector<int> prefix\_min(k\_prev, INF); vector<int> suffix\_min(k\_prev, INF); // 计算前缀最小值（dp[p] - p） int min\_val = INF; for (int k = 0; k < k\_prev; ++k) { int p = prev\_pos[k]; min\_val = min(min\_val, prev\_dp[p] - p); prefix\_min[k] = min\_val; } // 计算后缀最小值（dp[p] + p） min\_val = INF; for (int k = k\_prev - 1; k >= 0; --k) { int p = prev\_pos[k]; min\_val = min(min\_val, prev\_dp[p] + p); suffix\_min[k] = min\_val; } vector<int> curr\_dp(n, INF); bool found = false; for (int j : curr\_pos) { // 寻找最大的k <= j auto it = upper\_bound(prev\_pos.begin(), prev\_pos.end(), j); int idx = it - prev\_pos.begin() - 1; int left\_cost = INF; if (idx >= 0) { left\_cost = prefix\_min[idx] + j; } // 寻找最小的k >= j it = lower\_bound(prev\_pos.begin(), prev\_pos.end(), j); int idx2 = it - prev\_pos.begin(); int right\_cost = INF; if (idx2 < k\_prev) { right\_cost = suffix\_min[idx2] - j; } int best = min(left\_cost, right\_cost); if (best <= l) { curr\_dp[j] = best; found = true; } } if (found) { ans = i + 1; // 更新最大匹配长度 prev\_dp.swap(curr\_dp); } else { break; // 无法继续匹配，提前终止 } } cout << ans << '\\n'; return 0; } ```

```cpp #include <iostream> #include <vector> #include <set> #include <string> using namespace std; using ll = long long; // [y][x] constexpr int fx[8][2] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} }; int n = 0, k = 0; vector<vector<int>> tizu; vector<vector<int>> vis; set<string> res; string now; int sb[10][10][10][10]; void dfs(int i, int j, int next) { if (i == n - 1 && j == n - 1) { if ((int)now.size() == n * n - 1) { // res.insert(now); cout << now << '\n'; exit(0); } return; } next = (next + 1) % k; for (int d = 0; d < 8; ++d) { char c = '0' + d; int y = i + fx[d][0], x = j + fx[d][1]; if (y < 0 || y >= n || x < 0 || x >= n || vis[y][x] || tizu[y][x] != next) { continue; } // [i][j] -> [y][x] if (c == '1' && (sb[y+1][x][y][x-1] || sb[y][x-1][y+1][x])) continue; if (c == '3' && (sb[y-1][x][y][x-1] || sb[y][x-1][y-1][x])) continue; if (c == '5' && (sb[y-1][x][y][x+1] || sb[y][x+1][y-1][x])) continue; if (c == '7' && (sb[y+1][x][y][x+1] || sb[y][x+1][y+1][x])) continue; vis[y][x] = 1; sb[i][j][y][x] = 1; now += c; dfs(y, x, next); now.pop_back(); sb[i][j][y][x] = 0; vis[y][x] = 0; } } int main() { cin >> n >> k; tizu = vector<vector<int>>(n, vector<int>(n)); vis = vector<vector<int>>(n, vector<int>(n)); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> tizu[i][j]; vis[0][0] = 1; if (tizu[0][0] == 0) dfs(0, 0, 0); cout << "-1\n"; return 0; } ```

暴力做法 网站数据比较少竟然所有数据都过了每次都画最少的那张 ``` #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef struct point{ int m_min; int cnt; }point; int main(){ int n,m; cin>>n>>m; bool flage[n+10]={false}; int arr[n+10]={0}; point m_min={100000,0}; for(int i=1;i<=n;i++){ cin>>arr[i]; if(m_min.m_min>arr[i]){ m_min.m_min=arr[i]; m_min.cnt=i; } } int brr[n+10]={0}; for(int i=1;i<=n;i++) { cin>>brr[i]; } for(int i=1;i<=m;i++){ if(brr[m_min.cnt]>0) { arr[m_min.cnt]++; brr[m_min.cnt]--; m_min.m_min=100000; }else{ flage[i]=true; } for(int j=1;j<=n;j++){ if(m_min.m_min>arr[j]&&!flage[j]){ m_min.m_min=arr[j]; m_min.cnt=j; } } // cout<<m_min.m_min<<endl; // cout<<m_min.cnt<<endl; } cout<<m_min.m_min<<endl; return 0; } ```

```cpp #include<bits/stdc++.h> using namespace std; const int N = 200; int g[N][N]; int dp[N][N]; int main() { int n;cin >> n; memset(g,0,sizeof(g)); for(int i = 1;i<=n;i++){ for(int j = 1;j<=i;j++){ cin >> g[i][j]; } } memset(dp,0,sizeof(dp)); dp[1][1]=g[1][1]; for(int i = 2;i<=n;i++){ for(int j = 1;j<=i;j++){ dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+g[i][j]; } } int res=0; if(n%2==0)res=max(dp[n][n/2],dp[n][n/2+1]); else res=dp[n][n/2+1]; cout << res; return 0; } ```

``` #include<bits/stdc++.h> using namespace std; vector<int> v(1010, 0); int main() { string s; cin >> s; int len = s.size(); for(int i = 0; i < len; i++) { v[s[i]-'a']++; } int maxCount = 0; for(int i = 0; i < 1010; i++) { if(v[i] > maxCount) { maxCount = v[i]; } } for(int i = 0; i < 1010; i++) { if(v[i] == maxCount) { cout << (char)(i + 'a') << endl; cout << maxCount; break; } } } ```

``` #include <iostream> #include <string> using namespace std; int main() { string S; cin >> S; int count[26] = {0}; for (char c : S) { count[c - 'A']++; } int maxCount = 0; for (int i = 0; i < 26; i++) { if (count[i] > maxCount) { maxCount = count[i]; } } for (int i = 0; i < 26; i++) { if (count[i] == maxCount) { cout << (char)(i + 'A'); } } cout << endl; return 0; } ```