0%

这篇post会持续更新(如果有的话)。

2020-6-6补充:已经坑啦,因为现在绝大多数代码都是在Linux下面写了,以后有空写个Linux的配置吧。

CodeRunner

用来直接运行代码的插件,需要自己安装好MinGW的编译器环境。
运行的环境不支持UTF-8,所以要改配置在终端中运行,配上chcp 65001。

GDB调试

直接配置调试是不行的,必须新建一个Task。
tasks.json配置如下:

1
2
3
4
5
6
7
8
9
10
11
{
"version": "2.0.0",
"tasks": [
{
"label": "test",
"type": "shell",
"command": "g++",
"args": ["-g", "${file}", "-o", "${workspaceRoot}/lab3.exe"]
}
]
}
然后launch.json配置如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
{
"version": "0.2.0",
"configurations": [

{
"name": "(gdb) Launch",
"type": "cppdbg",
"request": "launch",
"program": "${workspaceFolder}/xxx.exe",
"args": [],
"stopAtEntry": false,
"cwd": "${workspaceFolder}",
"environment": [],
"externalConsole": true,
"preLaunchTask": "test",
"MIMode": "gdb",
"miDebuggerPath": "D:\\Program Files\\mingw-w64\\x86_64-8.1.0-posix-seh-rt_v6-rev0\\mingw64\\bin\\gdb.exe",
"setupCommands": [
{
"description": "Enable pretty-printing for gdb",
"text": "-enable-pretty-printing",
"ignoreFailures": true
}
]
}
]
}

阅读全文 »

这一章讲ACM中的数学。值得纪念的是6~9章我一共做了uva上的100题。本章我的代码见Github

2020-06-06补:为什么叫(上)呢?当然是因为我坑了!

10.1节例题10-1 uva11582

10.1节例题10-4 uva10791

10.1节例题10-5 uva12716

注意要预处理求出\(3\times 10^7\)以内的所有答案然后再查询,否则会超时。

●10.2节例题10-6 uva1635

注意不能预处理求出\(10^5\)以内的所有素数再进行因子分解,应该每次把m的质因数分解求出来,然后只对着这些质因数做分解就行了,不然会超时。
因为某个之前遇到过的神奇问题RE了无数回。。

10.2节例题10-7 uva10820

10.2节例题10-8 uva1262

阅读全文 »

这一章是DP。本章我的代码见Github

9.2节例题9-2 uva437

试了一下std::tuple,感觉比较麻烦。

9.2节例题9-3 uva1347

9.4节例题9-6 uva11400

9.4节例题9-8 uva1625

本来想同时存储选i,j个元素的最优结果和对应各字母的最后一个位置进行状态转移,但发现这样没有最优子结构(比如,如果目前的字母各不相同,你并不知道哪种顺序是最优的,但这可能影响后面的选择)。看了书上的解法,发现书上精妙地把复杂地状态简单化了:我只需要考虑那些还没选完的字母个数,而这是只取决于当前状态而与将来无关的。

9.4节例题9-9 uva10003

四边形不等式优化不太好理解。

●9.4节例题9-11 uva1331

阅读全文 »

这一章的内容感觉比较杂,以具体的技巧为主。本章我的代码见Github

8.5节例题8-1 uva120

8.5节例题8-3 uva1152

强烈推荐std::sort,std::lower_bound和std::upper_bound。

8.5节例题8-4 uva11134

起初的做法是将数组先按r[i]再按l[i]排序,判断第i个位置是否在l[i]..r[i]中。但这个做法是错误的(如考虑[1,3],[1,3],[2,2]),正确做法是对每个位置i遍历一遍,找到未标记的包含此位置的r[j]最小的j并标记。

★8.5节例题8-6 uva1606

开始的时候因为纠结极角排序是按照直线排还是按照射线排浪费了不少时间,最终决定按照斜率从小到大排序,位于竖直线上的点作为最大,开始时把右侧(包括y轴正半轴)设为left(开始的时候这么写的……后来懒得改正了),另一半设为right,直线逆时针转动,遇到同一直线上的若干点时,位于右侧的由left转right,位于左侧的由right转left。似乎数据中不会出现点重合的情况,也不会有N=1的情况?
标程用atan2排序用叉乘精确判断同一直线,将颜色为1的点坐标取反从而忽略颜色,以及扫描的时候采用了类似尺取的方法,代码非常简洁。

★8.5节例题8-8 uva1471

阅读全文 »

本章我的代码见github

7.4节例题7-5 uva129

7.4节例题7-7 uva1354

标程很值得学习,用位运算处理子集,用vector<pair<double,double>>存储某个子集对应的所有可能的L,R值,并且预处理计算sum。注意如果s=1那么答案就是0,我因为算ans时把0作为初始值,最后判断如果ans=0就输出-1而WA1次。

7.6节例题7-12 uva1343

不要被lrj骗了,BFS+判重是要TLE的!原因在于转移代价很高,而且如果选定的目标数字不对的话BFS会遍历相当多的状态还没用。正确的做法只能是IDA*,估价函数为8-目标位置中出现最多数字的次数(因为每次操作最多把1个目标数字加入目标位置中)。

7.6节例题7-14 uva1602

标程也很值得学习,用set<pair<int,int>>以散点的形式存储网格,在套上一个set以查重。大量使用STL和foreach能使代码变简洁。 值得注意的是编程时发现的一个小地方:如果f(T&)的实参是const T&类型的,C++编译器会隐式类型转换,创造一个从调用的实参拷贝过来的临时变量作为真正的实参。

习题7-4 uva818

IDS要打开的圆环,判断剩下的圆环是否都形成链以及是否满足开环数+1>=链数。连通集形成链的条件是要么d0=1要么d2=2且d(>=3)=0(这里dn表示度数为n的点的个数)。
写的时候问题颇多。写BFS,莫名其妙地RE2次(推测是队列开的不够大),写IDS先是忘了判重TLE1次,然后是漏了d0=1(即单个圆环)的条件WA1次。

阅读全文 »

紫书就是刘汝佳的《算法竞赛入门经典(第二版)》。前5章被我跳了(写模拟WA到怀疑人生),这是做第6章题目的经历和心得。
本章我的代码见github

6.1节例题6-1 uva210

lock失败的这个指令在加入block列表的同时应当保留而不是跳过这个指令,这里WA2次。

6.2节例题6-5 uva12657

对于交换两个相邻位置的盒子时应该单独处理,这里TLE6次,但这个单独处理没什么根据,怀疑是标程针对测试数据的特殊策略。

6.3节例题6-7 uva122

这题可以不按照书上建树的方法做。先判断有没有路径重复的,再判断非空路径去掉最后一位后是否存在对应节点,从而排除不完全的情况。然后以长度为第一关键字,字典序为第二关键字排序,按序输出即可。
起初我是先排序,然后枚举查找判断是否完全的,但莫名其妙地WA7次。后来改成用set<string>来判重、找父节点,就AC了。

6.4节例题6-14 uva816

BFS队列大小开的是400结果开小了RE1次,后来改成100000。

6.4节例题6-16 uva10129

阅读全文 »

以后这里就是我的个人博客了,可能会用来记录写过的ACM题或是记录一些学习计算机时遇到的经历。
感谢Github pages提供傻瓜式的建站方法,感谢NexT提供的美观、便捷的网站模板。

阅读全文 »