ymx10086

分类

笔记(4) 题解(12)

/ 注册

全部文章（共16篇）

传送带（三分答案）

本次问题需要进行两次三分，同时需要有效划归三分的结点，代码参考上一个题解的，仅为自己学习所用 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); ...

C C++

2022-08-10

1 407

小咪买东西（01规划问题）

#include <iostream> #include <algorithm> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 ...

C C++

2022-08-10

0 388

二分答案（判断结果合理性）

答案的单调性大多数情况下可以转化为一个函数，其单调性证明多种多样，如下：移动石头的个数越多，答案越大（NOIP2015跳石头）。前i天的条件一定比前 i + 1 天条件更容易（NOIP2012借教室）。满足更少分配要求比满足更多的要求更容易（NOIP2010关押罪犯）。满足更大最大值比满足更...

C C++

2022-08-10

0 279

表达式计算4（递归分治重点题型）

注意要多写 #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++){ ...

C C++

2022-08-05

0 358

更相减损术（求最大公约数和最小公倍数）

#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=...

C C++

2022-08-05

0 561

按位贪心

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

C C++

2022-07-31

0 345

月月查华华的手机（指针优化）

该问题的难点在于序列并非连续，需要精确定位，才能够实现优化。对于该题目的思路是往往对于每一个位置配备字符查找指针，指向字母第一次出现的位置（后序遍历实现），使得对应的查找问题变的简单，降低时间复杂度，指针可以是类指针（序列串） using namespace std; string s; int...

C C++

2022-07-31

0 398

扫雷MINE（枚举+递推）

此类题型往往枚举量有限，剩下部分可以依靠有效的递推解决问题 //枚举优化，注意到只要确定了第一个空的状态，第二空的状态也是定的，以此类推，只要看最后一个空是否合理就行 #include <bits/stdc++.h> using namespace std; int arr[10005...

C C++

2022-07-31

0 417

一般贪心类型总结

顺序贪心：顺序决定了策略的优劣，如果局部顺序最优能够保证整体上顺序最优，则通过冒泡排序的思想（实际上是快速排序sort），进行最终策略的选择。 NC16783 拼数直接贪心：贪心策略容易得出同时容易证明，不需要其他的加工操作 NC16618 排座椅处理贪心：需要通过一部分的枚举后进行贪心...

C C++

2022-07-30

0 346

国王的游戏（贪心推公式）

上述为引用洛谷题解说明：高精度计算的板子应提前书写，贪心策略很重要 ">#include<algorithm>//用到sort #include<cstring>//用到memset using namespace std; const int MAXN = 1010, M...

C C++

2022-07-30

4 624