记录从2021.11.29开始的除 Acwing 例题以外有意思的题目记录

基础算法

位运算

1. AcWing 998. 起床困难综合症 （利用了位运算时，位与位之间运算相互独立特性）
2. Codeforces1620C BA-String （进制转换）

排序算法

1. UVA11462 Age Sort (卡PE的大水题)

2. P1068 [NOIP2009 普及组] 分数线划定（普及组水题，注意录取线边界）

3. UVA11292 Dragon of Loowater（简单双指针、贪心）

4. UVA10041 Vito's Family（利用两边之和等于第三遍的条件，简单贪心）

5. UVA120 煎饼 Stacks of Flapjacks （选择排序思想）

6. POJ1804 Brainman （裸逆序对、归并排序、注意行间换行次数）

前缀和｜差分

1. Codeforces1359D div2 Yet Another Yet Another Task （最大子段和模型）
2. 2021冬季集训队选拔1 D （对异或和做前缀，统计子区间异或和为0的数目）
3. Codeforces1615B GlobalRound18 And It's Non-Zero （枚举个二进制各位，记录前缀和来计数）
4. 牛客数据结构课程1前缀和F （前缀置换）
5. 洛谷P2671 2015NOIP 普及组T3 （简单前缀和推导）
6. 牛客数据结构课程1前缀和H （区间依次规律修改可通过多次差分将操作优化到O(1)，用前缀和还原即可）

双指针

1. Codeforces489B （简单sort+双指针）

2. Codeforces1490C div3 Sum of Cubes （预处理+双指针贪心/map)

二分

1. AcWing.4080 第k个数 （巧妙二分）
2. OpenJudge4134 查找最接近的元素 （lower_bound重载）
3. SP297 AGGRCOW - Aggressive cows （经典二分答案）
4. UVA1152 和为0的4个值 4 Values whose Sum is 0 （卡PE）
5. POJ1064 Cable master （POJ评测有问题，一道简单二分）
6. CodeForces1613C div2 （一道纯送二分答案，div2纯送）
7. CodeForces1324C div3 （经典简单贪心+二分，调不好边界就把字符串或者数组下标从1开始）
8. Codeforces1359C div2 （数学+二分，值得多回顾）
9. Codeforces1619D div3 New Year's Problem （二分答案，check函数判断比较特殊）
10. [Codeforces689C div2 Mike and Chocolate Thieves](https://codeforces.com/problemset/problem/6 89/C) （数学+二分，主要是答案具有单调性， 考虑把题面翻译转换一下就好做了）
11. 2021冬季集训队选拔2 I题 （比较综合的一道题目，思维难度不高，二分+check函数内维护差分数组）
12. Codeforces1622C div2 Set or Decrease （一道很好的贪心+二分题目）

倍增

1. 洛谷P1613 跑路 （图论最短路+DP倍增预处理）

思维构造

1. Codeforces1433D div3 Districts Connection（构造相邻两点不同的图，以一个出现一次点为起点构造）
2. Codeforces1490F div3 Equalize the Array （求删去最小次数使数组各数出现0次或者C次，可以反面求能出现C次的最多元素数cnt，再取n - cnt为答案）
3. Codeforces1608B div1+div2 Build the Permutation （构造题，极大极小点问题）
4. Codeforces1591B div2 Array Eversion （简单思维，读完题多思考，思路大致清晰再写代码）
5. Codeforces1619E div3 MEX and Increments （利用MEX的性质）
6. Codeforces1151B div2 Dima and a Bad XOR （每行选个数字一起异或不为0的选择，先选第一列，异或为0再在各行找不同与第一列的数字，一个非常不错的构造方法）
7. 2021冬季集训队选拔2 J题 （一道非常nice的树形构造题）
8. Acwing第32周周赛 T2构造矩阵 （先构造出一个简单的方案，再向答案要求演变）
9. atcoder ABC238_D （位运算构造，运用集合的思想巧妙构造）

数学

公约数

1. Codeforces1618C div3 Paint the Array （简单思维、最大公约数）
2. Codeforces1617B div2 GCD Problem （两相邻自然数gcd为1，哥德巴赫猜想，任何一个大于2的偶数都可以表示为两个素数之和，任何一个大于5的奇数是3个素数的和）

质数

1. AcWing4086 最大公约数 （分解质因数，注意范围在 \(sqrt(n)\) 内枚举， 大于 \(sqrt(n)\)​ 质数单独判断)
2. 2021冬季集训队选拔1 H （质因数分解+阶乘分解+思维）

递推

1. UVA1646 Edge Case (不太好想的递推)
2. Codeforces1391C div2 Cyclic Permutations （自己用的递推解的，std考虑反向解答案，把最大的数先放然后依次在左右两边放最小的数就是没有环的情况）
3. Codeforces735C div2 Tennis Champion （思维转换，递推求解）
4. Codeforces1635D div2 Infinite Set （二进制、dp、数学、斐波那契）

同余

1. Codeforces1305C div1+div2 Kuroni and Impossible Calculation （求 \(n\) 个数的差值乘积对 \(m\) 取模，由于 \(m\) 的范围只有1000，在 \(m\) 大于1000的时候一定有两个数模 \(m\) 同余，最后乘积为0，就做出来了。。）

组合计数

1. UVA1510 Neon Sign （计数方法值得复习）
2. UVA530 Binomial Showdown （纯组合数板子题）
3. UVA369 Combinations (大水题)
4. POJ1942 Paths on a Grid (组合数上面的 \(b\) 要取小的数)
5. Codefroces1359E div2 Modular Stability （依次模很多数，当且仅当所有模数是最小模数的倍数才可以交换顺序最后结果不变，最后套用一下组合数的板子）

隔板法

1. Codeforces1288C div2 Two Array （把两个非严格单调数组连起来，就可以隔板法了）
2. UVA10910 Marks Contribution (隔板法)

数论分块

1. ABC230 E （1e14的分块板子题）

数据结构

单调队列、单调栈

1. 洛谷P1419 寻找段落 普及+/提高 （二分 + 最大子段和模型确定最短序列长度，滑动窗口确定最长序列长度）

并查集

1. AcWing4084 号码牌 （并查集处理连通块，也可以用bfs做）
2. 2021冬季集训队选拔F （与上题相同）
3. Codeforces1311B div3 WeirdSort （我的做法是并查集维护可交换区间、也可以双指针排序可交换段、也可以暴力n方做、也有\(O(n)\)巧解 主要利用了递增不可交换的性质

线段树

1. kuangbin专题 就一勾子 （性质不好推，尝试暴力算复杂度，有点剪枝的意思）

搜索

枚举

1. UVA11059 最大乘积 Maximum Product
2. Codeforces948A Protect Sheep （水题，但是要注意读清楚输入）
3. UVA10976 分数拆分 Fractions Again?! （推公式化简后枚举，注意除0的RE）
4. AcWing 95. 费解的开关 （二进制枚举第一行，然后再按行枚举）

DFS 深搜

1. UVA725 除法 Division （简单深搜枚举，毒瘤PE）
2. Openjudge2749 分解因数 (暂时不知道怎么总结，多复习吧)
3. Acwing第31场周赛B 01串 （一道数位暴搜好题）
4. ABC240E Ranges on Tree （向下搜索）

动态规划

线性DP

1. 2021冬季集训队选拔E （由向下取整，根据奇偶性dp）
2. Codeforces479E div2 Riding in a Lift （前缀和优化决策）
3. UVA10118 免费糖果 Free Candies （一道不错的记忆化搜索）
4. ABC240C Jumping Takahashi （简单暴力dp）

背包问题

二维费用背包问题

1. AcWing.4081 选数

树形DP

1. 牛客小白月赛45 E筑巢 （带点权，求联通快最大权值和）

数位DP

1. ABC242E （愿称之为字符串数位DP，比较简单，有一点点细节还算容易考虑）

图论

抽象建图，连通性

1. atcoder ABC238_E

DFS 深度优先搜索

BFS 宽度优先搜索

1. Codeforces1613E div2 Crazy Robot （bfs扩展）

Dijkstra

1. 洛谷P1339 [USACO09OCT]Heat Wave G （裸dijkstra，换个起点和终点）
2. POJ1847 Tram （简单套用dijkstra， 根据题意改变边权）
3. P2865 [USACO06NOV]Roadblocks G （Dijkstra求次短路， 不能用朴素dijkstra，无法处理一条边走多次的情况，使用堆优化dijkstra，并取消st数组的标记！）
4. POJ2502 Subway （无思维难度，输入有点麻烦，注意建图，一条地铁线上只能相邻走，标记只能标记相邻地铁）
5. 洛谷P1948 [USACO08JAN]Telephone Lines S （加双端队列bfs，二分答案）
6. 2021冬季集训队选拔 A （跑两次dijkstra，得到各点到起点和终点距离，判断加边能不能符合题意）

Floyd

1. UVA247 电话圈 Calling Circles （比较简单，用map哈希映射一下字符串编号，floyd判断连通即可）
2. UVA10048 噪音恐惧症 Audiophobia （Floyd，状态转移方程修改，求经过的路径上最大值的最小值）
3. UVA1001 奶酪里的老鼠 Say Cheese （三维空间建图，按照距离公式eng建就行，然后处理一下诡异的输出）
4. POJ1225 Stockbroker Grapevine （套floyd板子，找点到各点最短路最大值）

最小生成树

Kruskal

1. UVA534 Frogger （读题细节）
2. UVA11747 Heavy Cycle Edges （Kruskal判断图中最大环的长度）
3. P4047 [JSOI2010]部落划分 （Kruskal按照边的个数贪心性质的灵活应用）

二分图

1. Acwing第32周周赛 T3树的增边 (询问二分图中能添加的最大边数，图是一颗树)

贪心

贪心以模型大概分类

1. Codeforces1622B Berland Music （一道比较普通的贪心、思维很基础）

区间类

不知道啥反正是区间数轴上贪心

1.Codeforces1591C Minimize Distance （从原点往两边送货，每次货物定量，有往返求最小距离，从远点开始送，最后一次送取最远的没有返程，注意memset的时间）

区间选点

1. ABC230 D （acwing基础课区间选点简单扩展）

队列（堆）优化贪心

1. 2021冬季集训队选拔2 F题 （想起来还是比较顺，大根堆优化贪心过程）
2. 2022寒假集训队个人训练D （队列优化贪心）

greedy + math

1. Codeforces1617C div2 Paprika and Permutation （贪心+数学）
2. 2021冬季集训队选拔1 C （这个题有点搞，多复习复习吧）
3. Codeforces1278B div2 A and B （贪心+数学）

经验题

利用好数据范围，数论可能从模数做手脚

1. 727 A （用不好do while就别用)
2. Codeforces1490B div3 Balanced Remainders (学会取模造循环，标答贪心)
3. Codefroces1618E div3 E Singers' Tour （推公式题，细节在判整除，不仅%==0，还要被除数>0，商肯定不能为负数，切记！）
4. Codeforces1619A Square String? （英语学好点，读题不要引起歧义）
5. Codeforces1043D Mysterious Crime （思维+双指针枚举，主要是第一次卡cin，着实蛋疼）

简单题合集

Codeforces

Offical round

div1

div1 +div2

1. 1608 A （简单思维+数学）

div2

1. 736 B （贪心+枚举）
2. 445 A （简单模拟，注意代码的简洁度 (i + j) & 1 实现相邻位置棋子不同）

Educational round

div1

div2

1. 118 A （数字字符串混合处理)
2. 118 B （简单思维题）
3. 115 A （简单思维题）
4. 1020 B （简单模拟）
5. 1490 A （简单贪心+模拟）
6. 1591 A （简单模拟）
7. 1617 A （字符串处理）
8. #120 1622 A （细节颇多）

div3

1. 1618 D （简单贪心）
2. 1618 B （简单模拟）
3. 1618 A （简单思维、反推）
4. 1619 C （有点烦的模拟）

Others

1. 1057 A （special problem)
2. 500 A (简单模拟)
3. 910 A （简单贪心）

Atcoder

ABC

1. ABC230 A （简单模拟，不要把输出格式写错了）

2. ABC230 B （字符串子串判定）

3. ABC230 C （待补）

AcWing周赛

第28周

1. A 子序列 （暴力枚举）

Leetcode周赛