当看到“求方案总数”，“且当前决策只受上一个决策影响”的问题时，脑子里应该自动浮现这个框架： ``` 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; } ```

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; ``` }

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<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; } ```

动态规划+前后缀预处理优化 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; } ```

并查集 n个传送阵可能会构成多个环，利用并查集把n个传送阵构造成若干个环，并让每个根节点记录对应环的长度。 最后遍历每个传送阵，判断当前传送阵和前后邻近的传送阵是否连通，不连通则说明可以使用魔法，将两个环的长度加起来；连通则说明在同一个环里。结果取最大值 ``` #include <iostream> using namespace std; const int N = 1e6+2; int n; int fa[N]; void init() { for(int i = 1;i<=n;i++) fa[i] = i; } int root(int x) { return fa[x] = (x == fa[x]? x : root(fa[x])); } void add(int x ,int y) { if(root(x) != root(y)) { fa[root(x)] = root(y); } } int main() { cin>>n; int next[n+1]; int num[n+2] = {0}; bool v[n+1] = {0}; init(); for(int i = 1;i<=n;i++) { cin>>next[i]; } for(int i = 1;i<=n;i++) { if(v[i]) continue; v[i] = true; int now = i; int cnt = 1; while(next[now] != i) { add(now, next[now]); v[next[now]] = true; now = next[now]; cnt++; } num[root(i)] = cnt; } int ans = 0; for(int i = 1;i<=n;i++) { if(root(i)!= root(i-1)) ans = max(ans, num[root(i)] + num[root(i-1)]); if(root(i) != root(i+1)) ans = max(ans, num[root(i)] + num[root(i+1)]); } cout<<ans; return 0; } ```

0技巧，纯暴力 ``` #include<bits/stdc++.h> using namespace std; bool func(int x) { long long num = 8100178706957568; while(num) { if(num % x < 10) { num /= x; } else { return false; } } return true; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//取消同步流,让C++代码更快 for(int i = 11;i <= 36;i++) { if(func(i)) { cout<<i<<endl; break; } } return 0; } ```

纯暴力兄弟们，九层循环，排除各个字母相等的情况。直接暴力~ ``` package com.xzy.dashoj.day03; public class xzy_05_凑算式 { public static void main(String[] args) { int count = 0; for (int a = 1; a <= 9; a++) { for (int b = 1; b <= 9; b++) { for (int c = 1; c <= 9; c++) { for (int d = 1; d <= 9; d++) { for (int e = 1; e <= 9; e++) { for (int f = 1; f <= 9; f++) { for (int g = 1; g <= 9; g++) { for (int h = 1; h <= 9; h++) { for (int i = 1; i <= 9; i++) { if (a != b && a != c && a != d && a != e && a != f && a != g && a != h && a != i && b != c && b != d && b != e && b != f && b != g && b != h && b != i && c != d && c != e && c != f && c != g && c != h && c != i && d != e && d != f && d != g && d != h && d != i && e != f && e != g && e != h && e != i && f != g && f != h && f != i && g != h && g != i && h != i) { int shang = d * 100 + e * 10 + f; int xia = g * 100 + h * 10 + i; if (a * c * xia + b * xia + shang * c == 10 * c * xia) { count++; } } } } } } } } } } } System.out.println(count); } } ```

``` #include <bits/stdc++.h> #define int long long using namespace std; typedef pair<int,int> pii; int s=8100178706957568; int check(int x) { int ss=s; while(ss) { if(ss%x>=10) return 0; ss/=x; } return 1; } void solve() { for(int i=11;i<=36;i++) { if(check(i)) { cout<<i; } } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; t=1; // cin>>t; while(t--) { solve(); } return 0; } ```