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

纯暴力兄弟们，九层循环，排除各个字母相等的情况。直接暴力~ ``` 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> using namespace std; #define int unsigned long long const int N=1e6+10,M=1e18; int a[N]; signed main() { int n,f=1; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); if(!a[1]) { cout<<0; return 0; } for(int i=n;i>=1;i--) { if(f>(int)(M/a[i])) { f=0; break; } f=f*a[i]; } if(!f)cout<<-1<<'\n'; else cout<<f<<'\n'; } ```

填空题：手搓蓝桥杯省一 填空题么，写个程序是不是小题大做了，我们可以先按照这个写几个出来 【1 2 6 7 15 16 28】 【3 5 8 14 17 27】 【4 9 13 18 26】 【10 12 19 25】 【11 20 24】 【21 23】 【22】 我们可以发现一个规律，针对坐标为（i，i）的数字即（1，1），（2，2）……这些数字的增加方式很有意思，我们拆分出来即：1，5，13，25，41……，每次增加的都是4的倍数，第一次增加是4的1倍……，所以我们只需要手算一下变化20次的（20，20）即可知道答案，用时2min，（这不比编写一个程序简单？）

贪心+模拟,我们将数组分为左右两堆,那么答案就是左边那堆的最大的n个数之和减去后面那堆最小的n个数之和,由题目意思易得,左边那堆和右边那堆数都至少有n个数字,于是我们可以先把前n个数放入左边,后2n个数放入右边,然后再把右边不需要的数放入容器cc中,然后我们从n+1开始遍历对于每一个数,如果他在cc中出现了,那么就将这个数从cc中删除,如果他替换左边的最小值会使答案更优则将他替换,如果该数没有在cc出现,那么他一定在bb中出现了,则将该数从bb中删除,后选取cc中最小的数放入bb...... ``` #include<bits/stdc++.h> using namespace std; #define int long long const int N=1e6+10; int a[N]; multiset<int>aa,bb,cc; signed main() { int n,ans=-1e18,sum=0; cin>>n; for(int i=1;i<=3*n;i++) { cin>>a[i]; if(i<=n)aa.insert(a[i]); else bb.insert(-a[i]); } while(bb.size()>n) { auto xx=*bb.begin(); cc.insert(-xx); bb.erase(bb.begin()); } for(auto xx:aa)sum+=xx; for(auto xx:bb)sum+=xx; ans=max(ans,sum); for(int i=n+1;i<=2*n;i++) { int x=a[i]; auto j=cc.lower_bound(x); if(j!=cc.end()&&*j==x) { cc.erase(j); auto xx=*aa.begin(); if(x>xx) { aa.erase(aa.begin()); aa.insert(x); sum=sum-xx+x; } } else { auto jj=bb.lower_bound(-x); bb.erase(jj); sum+=x; auto xx=*cc.begin(); cc.erase(cc.begin()); sum-=xx; auto yy=*aa.begin(); if(x>yy) { sum=sum-yy+x; aa.erase(aa.begin()); aa.insert(x); } } ans=max(ans,sum); } cout<<ans; } ```

``` #include<bits/stdc++.h> using namespace std; #define int long long const int N=1e6+10; int a[N]; signed main() { int n,k,q; cin>>n>>k>>q; for(int i=1;i<=n;i++)a[i]=k-q; while(q--) { int x; cin>>x; a[x]++; } for(int i=1;i<=n;i++) { if(a[i]>0)cout<<"Yes"<<'\n'; else cout<<"No"<<'\n'; } } ``` 先让大家都扣q分如果你回答正确了那么你就多扣了分,給它加回去即可

``` #include<bits/stdc++.h> using u32 = unsigned; using i64 = long long; using u64 = unsigned long long; using i128 = __int128; void solve() { int n; std::cin >> n; std::vector<i64> a(n); for (auto &i: a) { std::cin >> i; } std::sort(a.begin(), a.end()); i128 ans = 1; for (auto i: a) { ans *= i; if (ans > 1000000000000000000) { std::cout << "-1\n"; return; } } std::cout << (i64) ans << "\n"; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr), std::cout.tie(nullptr); int T = 1; // std::cin >> T; while (T--) { solve(); } 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; } ```