数据结构算法（数组操作实例）

A：给你一个整数n，输出一个长度为n的序列（1~n每个数都只出现一次），使得所有子数组的 或操作之和 大于子数组的长度。

子数组长度也就是1,2,3…n-1.所以我们直接让序列为1,2,3,4,5,6…n即可
这样子，选取的子数组 或操作之和 最小也会等于 子数组的最后一位。

#include <iostream> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; for(int i = 1; i <= n; i++) { cout << i << " "; } cout << endl; } return 0; } 

B：给你一个n*m的矩阵，每个矩阵规定了在(i,j)位置的下一步方向，问：最少修改多少个格子，使得所有的格子都可以到达右下角。

中间的格子，不管他是D还是R，都是向着右下前进。
只有最右边一列，必须向下；以及最底一行，必须向右。
所以，统计最右边一列向右的个数 + 最底一行向下的个数 即可。

#include <iostream> #include <algorithm> using namespace std; const int maxn = 150; char map[maxn][maxn]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--) { int n,m; cin >> n >> m; int ans = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> map[i][j]; if(i == n && j == m) break; if(i == n) { if(map[i][j] == 'D') ans++; } if(j == m) { if(map[i][j] == 'R') ans++; } } } cout << ans << endl; } return 0; } 

C：给你一个整数n，构造长度为n的序列（1~n每个数只出现一次）,规定两个点之间连线的条件，问：有多少个序列可以形成环

总结可以成环的条件： 存在三个数字a,b,c
其中 a在左，b在中间，c在右。（不一定相邻）。只要b < a 同时 b < c 就可以成环。

相反：不成欢的条件就是1,2,3,4,5…n按从大到小的顺序插入序列，插入位置总是序列的两个边界。
比如： n = 4
插入1： 两种情况 1 _ _ _ 与 _ _ _ 1
再插入2：是2*2种： 1 2 _ _ 与 1 _ _ 2,以及：2_ _ 1, _ _ 2 1
这样可以保证每个数的一侧都是小于他的数，就破坏了成环的条件

所有的序列是n的阶乘
所有不满足的情况是2的n-1次方（因为最后一位只有一个空位了，没得选择）
快速幂取模即可
n的阶乘 - 2的n-1次方

#include <iostream> #include <algorithm> using namespace std; const int mod = 1e9 + 7; long long quickPower(long long x, long long y)//快速幂加取模  { long long result = 1; // 定义答案  while (y > 0) // 当指数大于 0 时进行幂运算 { if (y & 1) // y 和 1 做与运算,相当于对 2 求模 { result = (result * x) % mod;// 如果 y 为奇数,则结果只乘一个 x } x = x * x % mod; // x 乘二次方,下次使用 y = y >> 1; // y 右移一位,相当于除以 2 } return result % mod; // 返回结果  } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; long long ans = 1; for(int i = 2; i <= n; i++) { ans *= i; ans %= mod; } long long t = quickPower(2,n-1); if(ans < t) { ans += mod; ans -= t; } else ans -= t; cout << ans % mod << endl; return 0; } 

本文地址：https://blog.csdn.net/weixin_43934344/article/details/107903350