#include <iostream> #include <algorithm> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const int INF = 0x3f3f3f3f; const int MAX = 1e4 + 7; int n, k; int c[MAX], v[MAX]; double w[MAX]; //全局变量区 bool judge(double x) { for (int i = 1; ...

答案的单调性大多数情况下可以转化为一个函数，其单调性证明多种多样，如下： 移动石头的个数越多，答案越大（NOIP2015跳石头）。 前i天的条件一定比前 i + 1 天条件更容易（NOIP2012借教室）。 满足更少分配要求比满足更多的要求更容易（NOIP2010关押罪犯）。 满足更大最大值比满足更小最大值的要求更容易（NOIP2015运输计划）。 时间越长，越容易满足条件（NOIP2012疫情控制）。 可以解决的问题 求最大的最小值（NOIP2015跳石头）。 求最小的最大值（NOIP2010关押罪犯）。 求满足条件下的最小（大）值。 求最靠近一个值的值。 求最小的能满足条件的代价。

注意要多写 #include <bits/stdc++.h> using namespace std; string s; int zhuan(int l, int r){ int num = 0; for(int i = l; i <= r; i++){ num = num * 10 + s[i] - '0'; } return num; } int calu(int l, int r){ int cnt = 0; int pos1 = -1, pos2 = -1, pos3 = -1; for(i...

#include <bits/stdc++.h> using namespace std; int main() { int a,b,c,m; scanf("%d%d",&a,&b); if(a<b) swap(a, b); m=a*b; c=a%b; while(c!=0) { a=b; b=c; c=a%b; } printf("最大公约数是:\n%d\n",b); printf("最小公倍数是:\n%d\n",m/b); }...

当涉及位运算，或者有明确的是或否可以用0或1来表示的，可以考虑按位贪心的思路解决问题。 例： NC18979 毒瘤xor NC20860 兔子的区间密码 NC17857 起床困难综合症

该问题的难点在于序列并非连续，需要精确定位，才能够实现优化。 对于该题目的思路是往往对于每一个位置配备字符查找指针，指向字母第一次出现的位置（后序遍历实现），使得对应的查找问题变的简单，降低时间复杂度， 指针可以是类指针（序列串） using namespace std; string s; int last[40]; int nxt[1000010][40]; int n, pos, flag; int main(){ cin >> s; memset(last, -1, sizeof(last)); for(int i = s.length() - 1...

此类题型往往枚举量有限，剩下部分可以依靠有效的递推解决问题 //枚举优化，注意到只要确定了第一个空的状态，第二空的状态也是定的，以此类推，只要看最后一个空是否合理就行 #include <bits/stdc++.h> using namespace std; int arr[10005];//存输入的数据 int res[10005];//存方案 int n,cnt=0;//计数多少种方案 bool check()//通过arr最后一个数，检查扫雷的第一列是否合理 { if(arr[n] - res[n] - res[n-1] == 0) return true...

顺序贪心：顺序决定了策略的优劣，如果局部顺序最优能够保证整体上顺序最优，则通过冒泡排序的思想（实际上是快速排序sort），进行最终策略的选择。 NC16783 拼数 直接贪心：贪心策略容易得出同时容易证明，不需要其他的加工操作 NC16618 排座椅 处理贪心：需要通过一部分的枚举后进行贪心，此类问题往往直接贪心结果受多重因素影响，无法直接计算最优策略，需要通过枚举等手段先消除其中一个因素的影响。 NC200190 矩阵消除游戏 边界贪心：往往边界是决定最优策略的重要因素，形似动态规划的策略。 NC23036 华华听月月唱歌 说明：排序往往是解决贪心问题的第一步，也是最后一步

上述为引用洛谷题解 说明：高精度计算的板子应提前书写，贪心策略很重要 ">#include<algorithm>//用到sort #include<cstring>//用到memset using namespace std; const int MAXN = 1010, MAXM = 10010;//注意高精数组开到10000 struct Node{//一个人 int l, r; }a[MAXN]; int pro[MAXM], ans[MAXM], tmp[MAXM];//左手乘积，答案，临时数组 int read(){//快读 int x = 0,f = 1...

此类题型往往状态有限且可以通过特定形式表现出来，例如bite序列等，往往通过一定的状态压缩和酶具有有效序列的方式解决问题。 说明： scanf(" %c", &c);其中格式中含有空格，可以有效避免读入空格或者换行符等，使得c一定是字符形式 0x7f7f7f7f有时会很好用 3.位运算符及位运算要合理应用，注意不确定就加括号 #include <cstdio> using namespace std; int a[20], b[20], change[20]; char c; int calu(int x){ int cnt = 0; wh...

顾名思义，bitset是位bit的set集合，是可以当做容器使用的一种数据结构。 bitset提供了一些很实用的方法，能用来替代C语言的直接按位运算带来的不便。 #include <string> #include <bitset> int main() { std::bitset<5> bs1; //00000，无参默认0 std::bitset<5> bs2(4); //00100，整数转二进制，参数可为16进制 std::bitset<5> bs3("0011"); //00011，字符串转二进制，缺则补0，多则截...

枚举的要点： 确定需要枚举的变量 确定枚举的范围 优化手段 ：改变/减少枚举变量 缩小枚举范围 二分 ：二分查找、二分搜索非常有效，一般是复杂度从O(N)降到O(logN)，使用范围也很广 哈希：Hash，空间换时间 双指针：Leetcode上对应的分类是two pointer，直译过来就是双指针，大概的思想就是滑动窗口 前缀、后缀和：空间换时间 //枚举优化，注意到只要确定了第一个空的状态，第二空的状态也是定的，以此类推，只要看最后一个空是否合理就行 #include <bits/stdc++.h> using namespace std; int arr[10005];//存...

尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案，所以要先判断是否可以使用尺取法再进行计算。 使用尺取法时应清楚以下四点： 1、 什么情况下能使用尺取法? 2、何时推进区间的端点？ 3、如何推进区间的端点？ 4、何时结束区间的枚举？ 尺取法通常适用于...

两种思想 1.区间合并思想 using namespace std; int m, times; struct ty{ int x,y; }a[1005]; bool cmp(ty a, ty b){ if(a.x < b.x) return 1; return 0; } int main(){ scanf("%d%d", &m, &times); for(int i = 1; i <= times; i++){ scanf("%d%d", &a[i].x, &a[i].y); } ...