- 博客(103)
- 收藏
- 关注
RSS订阅原创 WXG一面凉经
是我不配WXG，真的太恐怖了时长：60min自我介绍（5min）：主要说竞赛经历，简单了解C++、OS和计网的部分基本知识。问答题：了解C++11、C++17和C++20之间的差别吗？了解C++的STL库吗？简单介绍几个？你说 vectorvectorvector 底层是一个数组，请你从操作系统的角度分析系统是怎样为 vectorvectorvector 分配内存的？分配的内存种类是什么？为什么是这样？进程为什么比线程开销大？既然你提到了创建和回收内存，请你回答一下系统是怎么分配的？解释一
2021-02-26 14:17:51
2288
4
原创 面试刷题记录
已知前序和中序遍历，还原二叉树：/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<int> ..
2021-01-31 21:56:28
231
原创 洛谷P2754 [CTSC1999]家园 / 星际转移问题【网络流/按时间拆点/前后】
题目链接：P2754 [CTSC1999]家园 / 星际转移问题分析：这道题我wa了太多次所以我PTSD了所以我什么都不想说了#include<bits/stdc++.h>#define pb push_backusing namespace std;typedef long long ll;const int maxn=1e5+7;const int mod=1e...
2020-03-28 17:47:10
279
原创 洛谷P1402 酒店之王【网络流/点的限制/拆点】
题目链接：P1402 酒店之王分析：对客人拆点加上限为1的限制；#include<bits/stdc++.h>#define pb push_backusing namespace std;typedef long long ll;const int maxn=1200;const int mod=1e9+7;const int inf=0x3f3f3f3f;s...
2020-03-28 13:58:40
216
原创 POJ3281 Dining【网络流/点的限制/拆点】
题目链接：POJ3281 Dining题意：f个食物和d个饮料，分别有自己的编号，n个奶牛吃到自己想要的食物和饮料才会开心，求最多多少奶牛开心；分析：对奶牛而言有1的上限，对奶牛拆点建边，流量为1（注意点的编号）；#include<cstdio>#include<cstdlib>#include<iostream>#include<cm...
2020-03-28 13:34:25
121
原创 洛谷P4551 最长异或路径【Trie树异或路径】
题目链接：P4551 最长异或路径题意：n个点的一棵树，两点间的距离是路径上所有边权的异或和；分析：由树的性质可以想到：dis[u][v]=dis[root][u]^dis[root][v]，那么就dfs一棵树出来，更新dis[root][i]；每个点dis的二进制01串建一棵trie，然后从高向低，贪心选取高位异或为1的；#include<bits/stdc++.h>...
2020-03-24 21:49:14
265
原创 洛谷P2580 于是他错误的点名开始了【trie板子】
题目链接：洛谷P2580 于是他错误的点名开始了最近在重新学字符串体系，打算从头开始好好学习；这里先贴一个trie的板子；#include<bits/stdc++.h>#define pb push_backusing namespace std;typedef long long ll;const int maxn=5e5+7;const int mod=1e...
2020-03-24 19:24:52
158
原创 Educational Codeforces Round 83 (Rated for Div. 2)
比赛链接：Educational Codeforces Round 83 (Rated for Div. 2)A. Two Regular Polygons分析：判断是否倍数；#include<bits/stdc++.h>#define pb push_backusing namespace std;typedef long long ll;const int m...
2020-03-10 00:45:43
162
原创 Codeforces Round #626 (Div. 2, based on Moscow Open Olympiad in Informatics)
比赛链接：Codeforces Round #626 (Div. 2, based on Moscow Open Olympiad in Informatics)A. Even Subset Sum Problem题意：找一个子集sum为偶数；分析：xjb写#include<bits/stdc++.h>#define pb push_backusing names...
2020-03-09 11:56:59
150
原创 Codeforces Round #625 (Div. 2, based on Technocup 2020 Final Round)
比赛链接： Codeforces Round #625 (Div. 2, based on Technocup 2020 Final Round)C. Remove Adjacent题意：给你一个字符串，相邻有前一位的可以删除，问最多删多少个；分析：越大的影响越小，从大到小删除，每次暴力；#include<bits/stdc++.h>using namespace ...
2020-03-07 19:30:09
140
原创 HDU1598 find the most comfortable road【最小生成树】
题目链接：HDU1598 find the most comfortable road题意：询问xy所有路径上mx-mn的最小值；分析：枚举每一条边作为最小生成树的最小边，直到xy连通时更新答案，用当前-最小边更新，有可能会出现将无用边算入答案的情况，但后面会把答案改小，所以不影响；#include<bits/stdc++.h>#define pb push_back...
2020-03-06 23:57:16
156
原创 CodeCraft-20 (Div. 2)
比赛链接：CodeCraft-20 (Div. 2)A. Grade Allocation题意：啊懒得说了分析：啊懒得分析了#include<bits/stdc++.h>#define pb push_backusing namespace std;typedef long long ll;const int maxn=2e5+7;const int mod...
2020-03-05 21:09:03
185
原创 HDU2121 Ice_cream’s world II【最小树形图】
题目链接：HDU2121 Ice_cream’s world II题意：n个点m条边做最小树形图，如果存在输出权值和根，不存在输出impossible；分析：加一个超级点和每个点都有边，如果存在那么超级点连向的点一定是根，并且有且只有一个；如果有多个，那么原图必定不存在最小树形图，因为多借用了至少一条虚边（因为加了一个点，一条虚边是必须要的），那么我们就把虚边的权值定为所有边权值和+1（s...
2020-02-27 22:54:55
135
原创 HDU4009 Transfer water【最小树形图算法详解】
最小树形图最小树形图实际上可以理解为有向图的最小生成树，它满足这样的要求：1、不存在环；2、除根结点的入度为0，其他点的入度都为1；3、满足1和2的条件的所有子图中权值和最小；朱刘算法的基本思想每次找最小入边集，如果有环或不连通，环缩点重新建图再继续重复；0、初始化：每个点入边最小权值初始化为极大值；1、找最小入边集：就是找到每一个点所有入边里权值最小的那个，并记录...
2020-02-27 21:52:34
213
原创 Codeforces Round #621 (Div. 1 + Div. 2)
E. Cow and Treats分析：想一想就知道每一边的牛爱吃的草都不一样枚举每一个元素作为左边到达的最远距离，再看右边能不能有一个吃一样草的，然后再看其他味道的草，a只能放在左边，b只能放在右边，c两边都可以，然后判断更新答案；#include<bits/stdc++.h>#define pb push_backusing namespace std;type...
2020-02-24 00:08:18
256
原创 Codeforces Round #576 (Div. 1)
比赛链接：Codeforces Round #576 (Div. 1)A. MP3题意：n个声音要压缩在Ibyte中，压缩规则是：所需空间，其中K为不同声音的个数，你可以选择一个声音的上下边界并将边界外的删掉，问你最少删掉多少个声音可以压缩在Ibyte中。（注意：1byte=8bits）分析：可以通过I求的k的最大值，离散化后做一个前缀和，扫一遍；（小心爆long long）#i...
2020-02-20 14:23:01
199
原创 Codeforces Round #549 (Div.1)
比赛链接：Codeforces Round #549 (Div.1)A. The Beatles题意：n*k个点围成一圈，1、k+1、2k+1……这些位置有快餐店，一个人以s为起点，l为间隔建立了许多stop，他将只能到达stop，他只记得s到最近的快餐店距离为a，到达下一个stop之后到最近的快餐店距离为b，求stop个数的最大最小值；分析：很显然可以得到l==tt*k+abs(a-...
2020-02-11 16:26:56
111
原创 Codeforces Round #618 (Div.1)
比赛链接：Codeforces Round #618 (Div.1)A. Anu Has a Function题意：给出n个数的排列，使得题给表达式的值最大；分析：将所有数转成二进制，一旦某个位置有多个数都为1，那么该位置在最终答案一定为0，因此，答案取决于只有一个数在某个位置为1的情况，贪心的令这个位置尽可能高，把它定为第一个（因为第一个不会减掉这个位置的1），如果不存在这样的位置，...
2020-02-10 21:42:51
217
原创 HDU1179 Ollivanders: Makers of Fine Wands since 382 BC.【二分图匹配/匈牙利算法】
题目链接：Ollivanders: Makers of Fine Wands since 382 BC.#include<bits/stdc++.h>#define pb push_backusing namespace std;const int maxn=111;vector<int> g[maxn<<2];bool vis[maxn];i...
2020-01-22 23:45:08
188
原创 HDU1384 Intervals【差分约束】
题目链接：HDU1384 Intervals题意：区间[a,b]至少有c个，问至少多少个能满足n个区间；分析：差分约束建边求最长路；#include<bits/stdc++.h>using namespace std;const int maxn=50007;const int INF=0x3f3f3f3f;int dis[maxn],head[maxn];bo...
2020-01-22 23:07:08
104
原创 Educational Codeforces Round 77 (Rated for Div. 2)
只会写没水平的题A.尽量平均分最少#include<bits/stdc++.h>using namespace std;const int maxn=1e5+5;typedef long long ll;int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++) { ...
2019-11-28 00:39:53
124
原创 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest
A.Berstagram题意：起始数列是1，2，3，……，n，给你m个操作x，表示将数字x和前一个位置的数交换，如果已经在第一个则不做操作，求每个数能到达的位置的最大和最小值；分析：扫一遍模拟，更新左右极限；#include<bits/stdc++.h>using namespace std;const int maxn=1e5+7;int a[maxn],pos[...
2019-11-07 17:16:36
764
原创 2019CCPC哈尔滨 Gym102394
比赛链接：Gym102394E. Exchanging Gifts题意：有n个操作，每个操作决定Si，op==1表示后面Si为当前给出的序列，op==2表示Si是Sx+Sy，由此得到最后的Sn，Sn随意交换得到H，问H与Sn最多有多少个不同；分析：假设我们已经得到Sn，长度为len，出现次数最多的数是x，出现次数为num，如果num*2>len，ans=2*(len-num)，否...
2019-11-03 16:36:49
595
1
原创 CF1245 F.Daniel and Spring Cleaning【数位DP】
题目链接：CF1245 F.Daniel and Spring Cleaning题意：给你一个区间，问区间内有多少对数满足a^b==a+b；（[a,b]和[b,a]是两个答案）分析：由题意知道是求a&b==0的对数，既然是位运算就可以转化成二进制下的数位DP，1e9不到30位；#include<bits/stdc++.h>using namespace std;...
2019-11-02 19:38:18
166
原创 Codeforces Round #597 (Div.2)
A.判断是否互质；#include<bits/stdc++.h>using namespace std;int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int main(){ int t;scanf("%d",&t); while(t--) { int a,b;scanf("%d...
2019-11-02 19:33:31
103
原创 HDU5961 Sitting in Line【状压DP】
题目链接：HDU5961 Sitting in Line题意：给你n个数和他们的位置，如果位置为-1表示这个数可以取任意位置，选择一种放置方式，使得相邻两数乘积之和最大；分析：N<=16，考虑状压DP；dp[i][j]表示取状态i中为1的数放在前面且这一位放j时的答案；当dp[i][j]成立时，可以从它向后更新dp[i|(1<<k)][k]，要注意更新时需要判断这一位的位...
2019-10-31 11:22:17
98
原创 HDU1045 Fire Net【DFS】
题目链接：HDU1045 Fire Net【DFS】题意：一个至多4*4的棋盘，棋盘上有一些墙壁，可以阻挡子弹，炮台可以向四个方向发射子弹，问在保证他们不能互相攻击的情况下至多可以放置多少炮台；分析：搜就对了；#include<bits/stdc++.h>using namespace std;char mp[5][5];int n,ans;bool check(...
2019-10-30 17:23:23
128
原创 HDU3290 The magic apple tree【DFS】
题目链接：HDU3290 The magic apple tree题意：给你一个树，起始叶子结点的值为他的编号本身，开始更新后，如果一个非叶子结点有K个子节点有值，那么他的值更新为这些值中第(k+1)/2小，求根节点的最后值；分析：从根节点向下DFS，到叶子结点之后向上回溯，裸题；#include<bits/stdc++.h>#define pb push_backu...
2019-10-29 20:30:44
129
原创 Codeforces Round #596 (Div.2)
A.注意判断一下9和1；#include<bits/stdc++.h>using namespace std;int main(){ int a,b;scanf("%d%d",&a,&b); if(a==9 && b==1) printf("9 10\n"); else if(b-a>=2 || a>b) printf("-...
2019-10-28 17:34:53
85
原创 HDU1011 Starship Troopers【树形DP】
题目链接：HDU1011 Starship Troopers题意：n个房间，m个士兵，给出每个房间的bug数和价值，每个士兵可以消灭20个bug，对于每个房间，只有当前的bug被全部消灭才能进入与它相连的房间，如果当前房间没有bug也要留一个士兵，求最多可以获得的总价值；分析：dp[i][j]表示房间i有j个士兵的价值；#include<bits/stdc++.h>#d...
2019-10-17 16:20:28
138
原创 HDU1520 Anniversary party【树形DP】
题目链接：HDU1520 Anniversary party题意：给你一棵树，每个点都有价值，父子不可同时选择，问选择的点的最大价值和；分析：找到根，然后向下DFS树形DP，由子节点更新父节点，dp[i][1]表示选择i，dp[i][0]表示不选择i，然后向上回溯更新父节点；#include<bits/stdc++.h>#define pb push_backusin...
2019-10-17 14:12:22
95
原创 HDU2196 Computer【树形DP】
题目链接：HDU2196 Computer【树形DP】题意：给你一个树，求出所有节点在树中能到达的点的最远距离；分析：dp[i][0],表示顶点为i的子树的，距顶点i的最长距离；dp[i][1],表示Tree(i的父节点)-Tree(i)的最长距离+i跟i的父节点距离；dp[i][0]通过dfs1可以很快求出；dp[i][1]可以通过父节点转移来，要维护一个最长mx1和经过的子节点v1，次...
2019-10-16 21:43:02
93
原创 HDU3709 Balanced Number【数位DP】
题目链接：HDU3709 Balanced Number题意：问区间[l,r]内平衡数的个数，平衡数是指选某一位作支点，左右两边每一位数值*力矩的和相等；分析：dp[len][pos][sum]表示长度为len的数，当支点为pos时，力矩为sum的数的个数；转移是由长度为len-1的数+第len位转移而来，所以dp[len][pos][sum]+=dp[len-1][pos][sum+i*...
2019-10-16 11:41:33
94
原创 数电实验真有趣
可以参考的管脚配置https://wenku.baidu.com/view/a94fc49cbe1e650e53ea992f.html实验一 五输入表决器设计程序设计module first(a,b,c,d,e,f); input a,b,c,d,e; output f; wire a,b,c,d,e,f; assign f=(a&b&c)|(a&...
2019-10-15 11:32:04
777
原创 CF1238 E.Keyboard Purchase【状压/子集划分DP】
题目链接：CF1238 E.Keyboard Purchase题意：给你一个由前m个字母组成的长度为n(1e5)的字符串，要求你决定一个前m(20)个字母的排列，每个字母的价值是它在排列中的位置，原字符串的代价是相邻两个字母的价值差，问字符串的最小代价是多少；分析：首先可以预处理出相邻字母组合的出现次数；考虑状态压缩，第i位为1表示第i个字母已经定过了排列的位置，为0表示他的位置没有决定，...
2019-10-14 21:30:28
173
原创 HDU3555 Bomb【数位DP】
题目链接：HDU3555 Bomb题意：问1～n中含有49的个数；分析：首先用init()找到n位数有多少含有49的数；dp[i[[j]用于存储符合条件的数的个数 i代表目前处理的数长度为i；这里dp[i][j]处理的数可包含前导零；dp[i][0]代表长度为i的数中不含49数的数量；dp[i][1]代表长度为i的数中不含49但是最高位为9的数的数量；dp[i][2]代表长...
2019-10-14 21:03:46
95
原创 HDU4745 Two Rabbits【区间DP】
题目链接：HDU4745 Two Rabbits题意：有一段环形字符串，两个人相对而行，要使得他们走过的字母序列相同的最长长度是多少；实际上就是求字符串中最长的回文子序列的长度，最终答案是取长度为n的区间里最长的长度 和 长度为n-1的区间里最长的长度+1 的最大值；+1是因为n-1的区间剩下的那个可以被同时当作起点，注意是环形字符串；分析：根据差分，dp[l][r]=max(dp[l][...
2019-10-14 19:42:24
144
原创 HDU4632 Palindrome subsequence【区间DP】
题目链接：HDU4632 Palindrome subsequence题意：找出字符串里回文子序列的个数；分析：由差分可知dp[l][r]=(dp[l][r-1]+dp[l+1][r]-dp[l+1][r-1]+mod)%mod当s[l]=s[r]时，dp[l][r]=(dp[l][r]+dp[l+1][r-1]+1)%mod，[l,r]可由[l+1,r-1]转移来，并且构成一个新的回...
2019-10-14 19:33:14
127
原创 HDU3506 Monkey Party【区间DP】
题目链接：HDU3506 Monkey Party题意：类似于环形合并石子，合并两堆石头的代价是两堆石子的数量和，问将所有石子合并的最小代价；分析：dp[i][j]表示区间[i,j]的最小代价，p[i][j]表示区间[i,j]的石子个数，加入了四边形不等式优化，s[i][j]表示区间[i,j]的最佳断点；【四边形不等式优化】当a<b<=c<d时，如果满足f...
2019-10-14 19:22:16
133
原创 Petrozavodsk Winter-2018. Jagiellonian U Contest E.Guessing Game【三进制状压DP】
题意：和UVA1252一样，n个长为k的01串，问最优策略下最多猜几次就可以知道是哪个串；分析：UVA那个题k是11，刚好可以暴搜，但是这个题是13，就要想想状压DP，但这个每一位有三种状态，已定为1，已定为2，未定，所以就是三进制下的状压DP，就可以先预处理出所有状态三进制下每一位的值和3^i(p[i])；读入过程中处理记下出现的状态，记下个数为1，然后扫所有状态，比如状态i的第j位是2，表...
2019-10-11 18:19:43
160
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人