- 博客(192)
- 收藏
- 关注
RSS订阅原创 T114048 [RC-02] yltx数对 (打表）
这题如果全部打表的话，文件大小会有65kb，超了，所以只打出一半，前一半用程序算就可以了，并不会超时。如果算法优化的好，其实可以打的更少。#include <bits/stdc++.h>using namespace std;const int maxn=1e5+10;// const int N=1e4+10;const int N=5e3+10;int vis[ma...
2020-02-06 15:23:50
326
原创 P1030 求先序排列 （一个非常棒的写法）
理论正确就是真正的正确，误。。。就是找嘛，找到每一个对应字符，然后对应的左右子树的区间，然后就可以了。#include <bits/stdc++.h>using namespace std;char mid[100];char suff[100];void getpre(int ml,int mr,int sl,int sr) { // printf("%d ...
2019-12-25 14:49:27
157
原创 试题编号： 201803-4 试题名称： 棋局评估 (对抗搜索 博弈）
这题真的是一道很不错的题，首先我对题意的理解有点问题，我以为的最优策略是，用最优的策略取胜，但是题目的意思是用最优的策略取得最好的得分。到哪个人行棋，就暴搜哪个人的可选的每一步，然后比较下一个人行棋所得的结果，取最优。例如当alice行棋时，就让alice下一步棋的得分取bob最优行棋的分数，然后alice有不同的点可以下，就让alice下一步走法的最优解等于alice走完下一步之后，对应的b...
2019-12-23 20:30:21
235
原创 1022_Digital_Library (30分)
这里提供两种写法， 其实都是一样的，第一种比较快。#include <bits/stdc++.h>using namespace std;map<string,set<string> > mp[6];int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); ...
2019-12-21 20:58:10
97
原创 1018 Public Bike Management (30分) （迪杰斯特拉+dfs）
思路就是dijkstra找出最短路，dfs比较每一个最短路。dijkstra可以找出每个点的前一个点， 所以dfs搜索比较的时候怎么处理携带和带走的数量就是关键，考虑到这个携带和带走和路径顺序有关，所以可以用下面的写法，看代码就可以了。最开始的时候是想用一个偏动态规划的写法做，但是因为题目的显示，既要带去的车数量最少，又要求从一个点带走的车数量最少，所以如果过动规的话，对于一个点的多个最短路，...
2019-12-21 17:01:55
136
1
原创 PAT 1014 Waiting in Line (30分) 一个简单的思路
这题写了有一点时间，最开始想着优化一下时间，用优先队列去做，但是发现有锅，因为忽略了队的长度。然后思考过后，觉得用时间线来模拟最好做，先把窗口前的队列填满，这样保证了队列的长度是统一的，这样的话如果到某个时间，队首的人已经服务完了，这样这个队列的长度就减少一，这就变成了所有队列中长度最短的队列，所以直接向这个队列里面添加一个人就可以了。按照从小到大轮询窗口的话，这样正好符合题中的要求，就是队列...
2019-12-20 09:50:56
107
原创 1010 Radix (25分)
改了一天也没明白，第7个数据是怎么卡的#include <bits/stdc++.h>using namespace std;const int maxn=1005;typedef long long ll;ll tonum(char c){ if (c>='0'&&c<='9') { return c-'0'; } return c...
2019-12-17 18:26:28
70
原创 试题编号： 201809-4 试题名称： 再卖菜 记忆化搜索
这题一看就是搜索，然后我不会写，咯咯咯。看了题解发现好简单，这是一个递推式，令d[n] 为第n家第一天的菜价 a[n]为第n家第二天的菜价则 (d[n-1]+d[n]+d[n+1]) / 3 = a[n]d[n+1] = 3 * a[n] - d[n-1] - d[n] + k (k=0,k=1,k=2)递推一下就可以了，但是对于第n天，n-1天的菜价为x，第n天的菜价为y , ...
2019-12-12 17:23:26
150
原创 试题编号： 201903-3 试题名称： 损坏的RAID5
这题的数据未免也太水了，题目的意思好像默认是每块磁盘装载数据的长度是相等的。我写了判断每次取数据是否会超过每块磁盘存的数据的长度，然而并没有什么卵用。交上去20分，写了个数据测了下，如果要求的块太大的话，这样下面计算得出的对应磁盘号会太大，然后就会runtime error，所以求出最大块号，如果查询的块超过最大块号，就输出错误就可以了。#include <bits/stdc++.h>...
2019-12-11 16:37:21
164
原创 CCF 试题编号： 201909-4 试题名称： 推荐系统
这题是stl的综合应用，map要想快，直接上unordered_map，这样查询接近O(1)，是不是很嗨皮。思路其实还是很简单的，type+id做个Hash，由于set.insert的第一个返回值是指向该插入元素的迭代器，所以，对于每一个type+id我们都可以存下它对应的迭代器，这样删除不就很快了吗，省去查找。这题是我第一次用c++11的语法， 原谅我的low，嘻嘻，auto还挺好用。#i...
2019-12-08 17:46:56
243
原创 洛谷P3809 后缀数组模板
把题读清楚，题中的输入是包括数字、大写字母和小写字母的。初始化排名的时候可以把字符的ascii值作为排位，因为排名是可以并列的。但是最后的后缀排名是不可能并列的，因为每一个后缀的长度不一样。基数排序的时候，注意处理并列的情况。下面的代码是复旦大学的程序设计里面的代码，写的挺清晰的，想看的可以直接粘走。#include <bits/stdc++.h>using namespace...
2019-11-26 16:57:45
107
原创 UVa 400 Unix Is命令
简单题#include <bits/stdc++.h>using namespace std;const int maxn=110;string s[maxn];int main(){ // freopen("data.in","r",stdin); ios::sync_with_stdio(false); int N; while (cin>>N)...
2019-10-27 19:40:34
118
原创 Uva 136 丑数
n^2暴力就完事，但是上限要高，不然就算不到对应的1500，刘汝佳的写法更好。#include <bits/stdc++.h>using namespace std;const int maxn=10000;int cnt=4;long long a[maxn];map<long long , int> mp;int main(){ // clo...
2019-10-27 19:39:10
114
原创 The Preliminary Contest for ICPC Asia Xuzhou 2019 K. Center
这题对于能加入最多边缘点的center点，这个点就是最优的center ，对于center点，总共是n^2的，顶多也就1e6，所以直接双重循环就行了， 然后map<pair,set >映射一下,第二个用set是因为虽然同一个中心点，对应的边缘点不会出现两次，但是题目中允许一个点作为边缘点两次 ，所以去重的是自己和自己相同的点。最后输出以下答案就可以了。#include <bi...
2019-10-23 11:29:26
87
原创 The Preliminary Contest for ICPC Asia Xuzhou 2019 J Random Access Iterator （树形DP）
每次循环向下寻找孩子时，随机选取一个孩子，设dp[u]为从u出发，不能得出正确答案的概率，则从u出发，走一次的情况下不能得出正确答案的概率是 P = (dp[v1]+dp[v2]+dp[v3]+……dp[vk]) / cnt_son[u] ，则从u出发，要走cnt_son[u]次，那么dp[u]=P^cnt_con[u] 。dp的意义也可以改成能得出正确答案的概率，下面的式子稍微改改就行了。...
2019-10-12 11:18:36
108
原创 The Preliminary Contest for ICPC Asia Xuzhou 2019 G Colorful String（回文自动机+dfs）
这题建立一棵回文树，然后用dfs搜索答案，但是有一点需要注意，就是打vis的标记时，如果标记为1，那么在好几个节点都对同一个字符i打过标记，此时的搜索从字符i点回溯，回到它的父亲节点，搜索其它的字符，回溯的时候把vis[i]标记成0了，之前的vis[i]标记全被清空了，如果该父亲的其它字符节点下，有字符i的孩子，则此时统计就会出错。所以打vis标记的时候让vis++，而不是标记为0。#inclu...
2019-10-02 15:57:44
91
原创 The Preliminary Contest for ICPC Asia Xuzhou 2019 E XKC's basketball team（排序+二分）
这题其实就是瞎搞，稍微想一想改一改就能过。排序按值的大小排序，之后从后向前更新node节点的loc值，如果后一个节点的loc大于（不会等于）前#include <bits/stdc++.h>using namespace std;const int maxn=5e5+10; struct Node { long long val,loc;}node[maxn];lo...
2019-09-28 10:12:50
96
原创 The Preliminary Contest for ICPC Asia Xuzhou 2019 M. Longest subsequence（思维+序列自动机）
序列自动机跑s串假设k为s和t相同的长度，初始时相同长度为0取s串中大于t[i]的最左边的位置，用n-tmp+1+i-1更新答案，tmp是最左端的位置然后去t[i]相等的位置，走到下一位，如果下一位的位置不存在或者在tmp的右边，跳出循环即可。最后就是s串中找出了一个和t串相同的串，之后的长度只要不为0，也是可以用来更新答案的。#include <bits/stdc++.h>...
2019-09-24 20:25:56
125
原创 The Preliminary Contest for ICPC Asia Xuzhou 2019 B. so easy （unordered_map+并查集）
这题单用map过不了，太慢了，所以改用unordered_map，对于前面删除的点，把它的父亲改成，后面一位数的父亲，初始化的时候，map里是零，说明它的父亲就是它本身，最后输出答案的时候，输出每一位数的父亲就好了。#include <bits/stdc++.h>using namespace std;unordered_map<int,int>mp;int f...
2019-09-24 11:14:26
131
原创 HDU 1237 简单计算器（栈+stringstream）
提供几份代码，这题的输入可以用stringsteam处理，先处理乘除后处理加减，正常思路，但是后面统计加减法的时候，对栈的运用相当于加了几个括号就错了。正确的简单解法就是，加法，就让正数入栈，减法就让该数的相反数入栈，之后的操作也不会影响该数的正负，这样处理最简单。单栈#include <iostream>#include <sstream>#include &l...
2019-09-23 19:40:07
118
原创 National Contest for Private Universities (NCPU), 2019 C Boxes（双向链表）
题目中的要求如果x在y的左边，不需要移动，x在y的右边，2操作不需要移动。有一个问题是，如果x与y相邻，这时的swap操作变成了三个而不是四个，这点尤其需要注意，不然就会死循环。注意x是和y相邻，这时应该考虑x在y的左边还是在y的右边，因为修改指针的操作是有方向性的。#include <bits/stdc++.h>using namespace std;const int ma...
2019-09-23 11:09:04
442
原创 LeetCode 42接雨水 按行求解（差分+排序）
按行求解的思路比较清晰明了，但是这个方法的复杂度高达O(heightSize*sum(height[i]))，几乎高达O(N^2)。但是也并不是不可以解决，经观察我们可以发现，这个算法的缺点在于要遍历每一个柱体的每一个高度，所以解决的时就要从这个点着手。设之前已经存在的柱体的最高高度为bp，当前柱体的高度为h，则如果h<=bp,说明该高度和它以下的高度已经出现过，我们更新该高度的end位...
2019-09-19 17:15:42
218
原创 The Preliminary Contest for ICPC Asia Shanghai 2019 B Light bulbs （离散的差分）
复杂度分析，询问一千次，区间长1e6，O（1e9）超时。那么我们知道对于差分来说，没必要一个一个求，只需要知道区间长就可以了，所以我们定义结构体差分节点，一个头结点，一个尾节点。这样tail.loc-head.loc就是整个区间长，该区间的实际的大小就是 Add标记的大小，Add标记就是从头加到尾。排序2*m个差分节点，对于loc相同的节点，说明是同一个位置的差分，add合并就可以了，不需要...
2019-09-15 20:24:28
213
原创 The Preliminary Contest for ICPC Asia Shenyang 2019 C Dawn-K's water （完全背包）
完全背包为什么要取到M，可以取到2*M嘛，这题需要整取，对于不能整取的背包容量，dp[k]=INF，以及dp[j-water[i].weight]=INF时，dp[j]也不需要更新。如果不整取的话，后面无法得知背包是否装满了，只知道，背包容量为m时，所花的最小消耗是多少，但是此时背包可能没装满。#include <bits/stdc++.h>using namespace std;...
2019-09-14 18:29:48
253
原创 BZOJ 3262: 陌上花开 (cdq分治，三维偏序）
#include <iostream>#include <stdio.h>#include <algorithm>using namespace std; const int maxn=1e5+10;const int maxk=2e5+10; int n,k; struct Triple { int a,b,c,cnt,ans;}...
2019-09-11 23:22:05
116
原创 BZOJ-1563-郁闷的出纳员（权值线段树）
偏移量要考虑清楚。#include <bits/stdc++.h>using namespace std;const int N=4e5+10;const int BASE=1e5+1;const int RIGHT=3e5+5e4;int segtree[N<<2],lazy[N<<2];void pushdown(int rt){ i...
2019-09-11 23:19:48
82
原创 HDU-1702-ACboy needs your help again!(Stack)
队列和栈的判空都可以用empty#include <bits/stdc++.h>using namespace std;string oper,stru;int T,M,num;int main(){ cin>>T; while (T--) { cin>>M>>stru; if (str...
2019-09-04 14:05:53
92
原创 HDU1276-士兵队列训练问题 (Queue)
题很简单，STL中queue的基本使用。#include <bits/stdc++.h>using namespace std;int N,num;int main(){ scanf("%d",&N); while (N--) { scanf("%d",&num); if (num<=3) { ...
2019-09-04 13:51:41
151
原创 HDU1285-确定比赛名次（拓扑+优先队列）
对于拓扑排序，每次能入队的只有入度为0的点，所以用优先队列即可。以及，第一组数据日常卡OJ，这组数据跳了一个点，我的程序这个版本也过不了（其实写了另一个版的），稍微改改更正确。#include <bits/stdc++.h>using namespace std;const int maxn=510;vector<int> vec[maxn];int inde...
2019-09-03 22:17:34
124
原创 The Preliminary Contest for ICPC Asia Nanjing 2019 - D Robots（概率dp+拓扑排序）
这题概率dp + 拓扑排序可以写改天补解释#include <bits/stdc++.h>using namespace std;const int maxn=1e5+10;vector<int>vec[maxn];int indeg[maxn],seq[maxn];double d[maxn],f[maxn];int N,M,T,tot=0;void...
2019-09-02 20:09:29
146
原创 拓扑排序板子 hihocoder-1174
思路不断删入度为1的点及其出边。详解： https://blog.csdn.net/qq_38984851/article/details/82844186#include <bits/stdc++.h>using namespace std;const int maxn=1e5+10;vector<int> vec[maxn];int InDeg[maxn...
2019-09-02 20:03:32
132
原创 二叉树性质 n0=n2+1
假设树的节点个数为n，那么n=n0+n1+n2，并且边的个数等于n-1，那么 n-1=n22+n1则 n0+n1+n2-1=n22+n1，即n0=n2+1。
2019-08-26 16:34:28
2197
原创 洛谷 P3808 【模板】AC自动机（简单版） （AC自动机优化板子）
题中有一个坑点，就是模式串可以相同，并且全部计数。#include <bits/stdc++.h>using namespace std;const int maxn=1e6+10;const int N=maxn;char str[maxn];struct Dfa { int trie[N][26],cnt; int e[N]; int fail[N]; ch...
2019-08-22 12:07:53
104
原创 POJ 3987 Computer Virus on Planet Pandora (AC自动机优化）
题意问一个字符串中包含多少种模式串，该字符串的反向串包含也算。思路解析一下字符串，简单。建自动机的时候，做路径压缩，跑优化版的ac自动机，跑过的模式串不能二次计数。代码附赠一大波样例#include <iostream>#include <stdio.h>#include <queue>#include <string.h>...
2019-08-22 11:47:51
257
原创 POJ 1204 Word Puzzles（AC自动机）
这题的数据卡在，如下：5 5 3ABCDEFGHIJKLMNOPQRSTUVWXYPQRRSRSTpuzzle中间的行中可以包含要查询的多个单词。这个问题很好解决，SearchDfa的时候别return就行了，一直搜到字符串的结尾。但是这样做也有一个bug，如果数据是这样的：4 7 5ABCDEFGHIJKLMNOPQRSTUVWXYZAKRSTUSTUT...
2019-08-21 11:23:02
140
原创 2019牛客暑期多校训练营（第十场） Han Xin and His Troop （高精度+拓展中国剩余定理）
题意裸题思路题中的模数之间并不互质，所以应该用拓展中国剩余定理。但是交上去会炸，__int128过不了，所以用高精度的板子或者java大数都挺好过的。这里推荐java大数，因为高精度板子用起来没用java的方便。#include <bits/stdc++.h>using namespace std; constexpr int base = 1000000000;c...
2019-08-20 09:19:25
186
原创 POJ-2891 Strange Way to Express Integers（拓展中国剩余定理）
放一个写的不错的博客：https://www.cnblogs.com/zwfymqz/p/8425731.htmlPOJ好像不能用__int128。#include <iostream>#include <stdio.h>typedef long long ll;const int maxn=1e6+10;ll m[maxn],r[maxn];void e...
2019-08-19 14:44:48
115
原创 POJ-1087 A Plug for UNIX （网络流）
思路电器数1 ~ 100，附带100种接口，注意题目：You notice that some of the devices use plugs for which there is no receptacle.墙上接口1 ~ 100，还有1 ~ 100转接口，转接口有两个接口。假设所有的接口类型都不相同，接口就有400种。所以汇点值 >= 501。读入电器的时候，它的接口可能在墙上并...
2019-08-15 17:11:39
174
原创 POJ-3821-Dining (拆点网络流）
这题为什么不能用 左边放食物，中间放牛，后面放水？原因很简单，假设一头牛喜欢两个食物和两种水，如果从一个食物A，走到牛A，再走到水A。此时还可以有另一条路，从另一个食物B，走到该牛A，并走到该牛喜欢的另一个水B。这是错误的原因之一，其实也跟反边有关。所以对于牛，拆开，中间建立一条边，说明该牛已经使用过，这样也避免了从其它食物C走到牛A，此时我们希望它走反边，即牛A到食物A，再从食物A走向其...
2019-08-14 16:59:59
137
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人