模拟
按题中要求找规律，模拟操作，这种题可以巨难....
- 提前写好所有的流程
- 每个操作模块化（函数、结构体、类等）
枚举：DFS/BFS
- DFS:枚举所有可以到达目标状态的路径,对一个传入状态，遍历它的子状态，对每一个都进行判断，若合法，则递归搜索这一子状态，直到达成目标条件或者状态不合法，则回溯到父亲节点，搜索下一个子状态。求解某个方案数之类的问题。
bool judge(参数列表){
//参数不合法或越界时返回false 否则返回true
}
void dfs(传入状态){
if(达成目标条件){
输出信息或者修改信息；
return;
}
for(遍历传入状态的所有子状态){
if(judge(子状态)){
传入状态加标记；
dfs(子状态)；
传入状态取消标记//回溯
}
}
}
- BFS: 找到最快到达目标的一条路径，借助队列实现，队列不为空时，弹出队首元素A，判断A，状态A的子状态中未标记过的状态均入队，加标记。（先搜索这一层的状态是否有最终目标，若找到目标，进行相关操作，结束bfs函数。否则，接着搜索这一层所有状态的子状态， ...）求解到达某方案的最短步骤之类的问题
void judge(node){
if(非法条件为真 || 范围越界) return false;
return true;
}
void bfs(A){
queue<node> q;
q.push(A);
while(!q.empty()){
temp = q.front();
q.pop();
if(temp 达成目标条件){
输出信息；
}
for(/*遍历所有子状态*/){
if(judge(temp)){//子状态合法则入队
q.push(temp);
++vis[temp];//每个节点只访问一次
}
}
}
}
- 双向bfs，起点与终点同时开始搜索，每到一层先检查两边的状态是否相接（判断相接状态），有解时，状态数远小于bfs
二分，题目满足：最大，最小，二段性，单调性...
- 实数二分
while(r - l > res){
int mid = (r + l) / 2;
if(ans 在左区间) r = mid;//右区间相反
else l = mid;
}
Best Cow Fences:对一个数列，求一个平均值最大、长度不小于f的子段。前缀和 + 二分答案 范围0——2000 ，计算mid，a[i]减去mid后计算前缀和，看是否有一段长度 >= f 且 前缀和>= 0
// 左区间...目标区间...右区间
bool check(double mid){//判定当前值是否可取
for(int i=1;i<=n;i++) sum[i] = val[i]-mid+sum[i-1];
double mi = 1e10,ans = -1e10;
for(int i=f;i<=n;i++){//区间长度最短为f
mi = min(mi,sum[i-f]);//前缀和最小的左区间
ans = max(ans,sum[i]-mi);
if(ans >= 0) return true;
}
return false;
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
double l,r,mid;
cin >> n >> f;
for(int i=1;i<=n;i++) cin >> val[i];
l = 0;r = 2000;
while(r-l > 1e-5){
mid = (l+r)/2;
if(check(mid)) l = mid;
else r = mid;
}
cout << int(r*1000) << endl;
return 0;
}
- 整数二分（两种情况）
while(r > l){
int mid = (r + l) / 2;
if(ans 在左区间) r = mid;
else l = mid + 1;
}
while(r > l){
int mid = (r + l + 1) / 2;//防止死循环
if(ans 在右区间) l = mid;
else r = mid - 1;
}
前缀和：（一维）预处理一个数组，每个元素的值为：另一数组当前索引元素和之前所有元素和
-
计算区间和 -- O(1)
-
只能处理静态数组
-
二维：左上角元素和，计算区间和（容斥原理）
//一维
sum[i] = sum[ i - 1] + a[i];//索引从1开始，避免处理边界问题
i~j的区间和：ans = sum[j] - sum[i - 1]
//二维
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]//索引处理同上
a,b ~ c,d的区间和
ans = sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1]
一个数组中，存在一些特殊元素：数组中存在一些区间和 == a[i];求出数组中特殊元素个数。
- 1 <= n <= 8000,1 <= a[i] <= n
- n最大直到8000，所以O(n^2)以内的算法均可。
- 使用前缀和，直接计算所有的区间和，同时判断是否 <= n，若是，则记录下来(记录数组范围 <= n)
- 遍历数组，计算数组中有多少个元素被记录
int ans,t,v,n,a[8010],s[8010],book[8010];//需要处理的最大范围：[1,8000]
//数据量很小，暴力+前缀和 记录所有的长度大于2的子序列和 找符合条件的
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> t;
while(t--){
ans = s[0] = 0;
memset(book,0,sizeof(book));
cin >> n;
for(int i = 1; i <= n; i++){//索引从1开始，避免处理边界问题
cin >> a[i];
if(i > 1){
s[i] = s[i - 1] + a[i];
for(int j = 0; j < i - 1; j++){//r - l >= 2
v = s[i] - s[j];
if(v <= n && !book[v]) book[v] = 1;
}
}else s[i] = a[i];
}
for(int i = 1; i <= n; i++) if(book[a[i]]) ++ans;
cout << ans << endl;
}
return 0;
}
差分：是一种和前缀和相反的策略，数组中每一个元素记录原数组中与前一项的差值，对这个数组求前缀和即可恢复原数组
-
维护多次对若干区间加上某个数，最后若干次询问某一位的数...
-
每次对最左端的点a[1]先增加相应的值，对应修改a[l],a[r]更新区间和
codedforces 1343D Constant Palindrome Sum
输入由n个整数组成的数组a,和整数k，替换数组中de一些元素为[1,k]中的任一元素，使数组满足：
- a[i] <= k
- a[i] + a[n - i + 1] = x,即对称的元素和为定值( 2 <= x <= 2k)
- 求最小替换元素的个数
对于确定的x，每对元素的交换次数确定
- a + b = x
- x ∈[min(a,b) + 1,max(a,b) + k + 1)，半开半闭的区间方便合并，获得最小和，最大和,差分，此区间 + 1--起始位置 + 2，左边界(闭)-1，右边界(开) +1
- 其它
交换次数存在一个最大值，当x = k + 1，为 n / 2（所有元素值的区间[1,k]）；对每一对元素，计算交换次数为1的区间，使用差分思想通过cnt数组在区间外+2，区间内+1，对每一对元素的和特殊处理；在枚举完所有的元素对后，将差分数组cnt修改为前缀和即为相应x的替换次数，ans 初始化为n / 2,遍历cnt数组寻找最小替换次数。。。
const int kN = 2e5 + 10,kM = 4e5 + 5;
int t,n,k,l,r,ans,a[kN],cnt[kM];
//替换最少数量的元素，数组中对称元素和满足 a[i] + a[n - i + 1] = x;x为某个定值
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >>t;
while(t--){
memset(cnt,0,sizeof(cnt));
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n / 2; i++){
l = min(a[i],a[n - i + 1]) + 1;
r = max(a[i],a[n - i + 1]) + k + 1;//区间左闭右开，便于合并
cnt[1] += 2;//差分 边界[2,l) 需要两次
cnt[l]--;//[l,r] 一次
cnt[r]++;
cnt[a[i] + a[n - i + 1]]--;//0
cnt[a[i] + a[n - i + 1] + 1]++;
}
for(int i = 2; i <= 2 * k; i++) cnt[i] += cnt[i - 1];//计算各个x值的替换次数
ans = n / 2;
for(int i = 1; i <= 2 * k; i++) ans = min(ans,cnt[i]);
cout << ans << endl;
}
return 0;
}
贪心：尽量选择当前最优状态
- 排序后按最大值or最小值取（离线）
- 每次都取当前最大or最小的xxx，更新xxx（在线）
长为n的数组中，1~n每个数字只出现一次，在这个数组中，相邻元素差的绝对值的范围[2,4]。
- 贪心：
- n < 4，无解
- 从大到小输出小于等于n的所有奇数。
- 输出“4 2”
- 输出所有小于等于n的偶数
- method2：:先输出偶数，但是n == 4的时候需要特判，之后输出"5,1,3",其它奇数升序
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> t;
while(t--){
cin >> n;
if(n < 4) cout << "-1";
else{
s = n;
if(!(s & 1)) --s;//先奇数
while(s > 0){
cout << s << ' ';
s -= 2;
}
cout << "4 2";
s = 6;
while(s <= n){
cout << ' ' << s;
s += 2;
}
}
cout << endl;
}
return 0;
}
E1思路：
一个由小字字母组成的字符串，所有元素均被涂上了黑色 or 白色，相邻且异色的字符可交换，字符串中的字符是否可以升序排列，如果可以，给出染色方案：0 1表示两种颜色
思路：
异色字符才可以交换，同色字符相对顺序不会发生改变 -- 即同色字符不递减。
贪心：s是否可分为两个不递减的子串
- 使用c1,c2分别记录两个同色字符串的最大字符，遍历字符串，若s[i] >= c1,加入c1所在子串；若 s[i] >= c2,加入c2所在子串；若s[i] 小于 c1,c2则在同色子串中出现递减 --> "NO"
E2与E1相比，字符的染色种类更多。需要输出染色种类最少的方案。
思路：
- 最多26种染色，依然可以贪心,增加一个字符串数组存储当前各字符串的最大字符，对s[i],进行E1中相同的步骤，不同的是：标记当前s[i]是否可以加入现有的字符串中，若不可以则增加一个字符串（题目保证最多26种染色，有解。），增加一个ans数组，在选择过程中存储答案即可。
const int kN = 2e5 + 5;
int n,idx,ans[kN];
bool flag;
char c[27];
string s;
//26个字符，最多26种染色
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> s;
for(int i = 1;i <= 26; i++) c[i] = 'a';
idx = 1;
for(int i = 0; i < s.length(); i++){
flag = true;
for(int j = 1; j <= idx && flag; j++){
if(s[i] >= c[j]){
c[j] = s[i];
ans[i] = j;
flag = false;
}
}
if(flag){
c[++idx] = s[i];
ans[i] = idx;
}
}
cout << idx << endl ;
for(int i = 0; i < n; i++){
if(i) cout << ' ';
cout << ans[i];
}
return 0;
}