开始暑期集训到现在两个礼拜了，每天都要做大量的习题，应接不暇，感觉这么下去如果不复习的话没什么效果。再加上昨天的组队赛确实很惨烈，今天白天有一天的时间，在此把前段时间的习题都整理一下思路，给代码加一加注释，同时总结一下之后需要注意的问题。
Codeforces Round #422 (Div. 2)
先从校赛结束的那天晚上说起吧，自己练了一场CF。
A题是一道水题，和旁边几个人聊着天，就把它A了，题目是求两个阶乘的GCD，实际上就是求两个阶乘中较小一个的值。数据范围也很小，打了个表，直接A了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> using namespace std; int a, b; int fac[15]; void init() { //初始化阶乘 fac[1] = 1; for (int i = 2; i < 15; i++) { fac[i] = i * fac[i - 1]; } } int main() { cin >> a >> b; init(); int ans = min(a, b); cout << fac[ans] << endl; return 0; } |
B题也是一道水题，给出两个字符串，要求尽可能少的对第一个字符串进行字符替换从而使他能够成为第二个字符串的一个子串。
题目数据范围很小，考虑暴力处理，但由于自己的处理方法不当，搜索的时候出现了溢出和漏判等情况，最后看了题目的数据才成功把它AC。
|
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 28 29 30 31 32 33 34 |
#include <cstring> #include <iostream> #include <string> using namespace std; int n, m; string s, t; int x; int y; int main() { cin >> n >> m cin >> s >> t; int min = 10000; for (int i = 0; i + n <= m; i++) { //这里在搜字串，所以要i+n<=m，自己做的时候一直用i<=m，以后要注意 int tmp = 0; for (int k = 0; k < n; k++) { // 判断有几个不同的字符 if (s[k] != t[i + k]) { tmp++; } } // cout << tmp << " "; if (tmp < min) { //若比最小值还小，就更新字串位置。 min = tmp; x = i; // cout << x << endl; } } cout << min << endl; //输出最小需要改变的字母 for (int i = 0; i < n; i++) { //输出哪一位需要被改变 if (s[i] != t[i + x]) { cout << i + 1 << " "; } } return 0; } |
C题是一道值得被记住的题，看了大神的代码，发现他们的思路真的太厉害了，一定要学习吸收。
题意是说有一个人要去旅游，一共要玩x天。旅游社里有很多种不同的旅游计划，每种计划都有出发时间和截止时间，这个人希望进行两次旅游，这两次旅游不能互相交叉，并且旅游时间之和需要正好等于x。这个人还希望花的钱尽可能的少，题目要求我们输出花的钱的最小值。
这道题一开始看感觉像dp，但又不知道该从何下手。贪心的话感觉会T，除非用二分，但是想了想也没有很好的二分方法。可以记录每一个价格所对应的计划，然后再去二分对应的价格，这样的话需要n*logn的复杂度，应该也能做。不过看了CF榜前几名的代码才感叹，这些人的思路确实比较开阔。
我先把注释之后的代码放到这里，因为直接说思路可能会比较懵逼。
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <algorithm> #include <climits> #include <cmath> #include <cstdio> #include <cstring> #include <deque> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <vector> //#pragma comment(linker, "/STACK:1024000000,1024000000") #define all(a) (a).begin(), (a).end() #define ll long long #define endl "\n" #define DE cout << "------" << endl #define mems(a, b) memset(a, b, sizeof a) #define pii pair<int, int> #define mp make_pair using namespace std; const int MOD = 1e9 + 7; const int INF = 2e9 + 100; const int N = 200022; int n, x; vector<pii> a[N]; vector<pii> b[N]; int c[N]; // c[i]用来存储进行某一段时长的旅程所需要的最低价格 int main() { ios::sync_with_stdio(false); while (cin >> n >> x) { int ans = INF; for (int i = 0; i < N; i++) { c[i] = INF; } for (int i = 0; i < n; i++) { //这里建两个vector分别保存以某一点左端点和以某一点为右端点的旅程计划信息 int l, r, cost; //下面我们就能了解到为什么这么设置。 cin >> l >> r >> cost; a[l].push_back(mp(r - l + 1, cost)); b[r].push_back(mp(r - l + 1, cost)); } for (int i = 0; i < N; i++) { for (pii t : a[i]) { //这个循环要在看完下边的循环之后再看。因为第一边循环不会过这个循环，同时不能交叉的定义要求不能有相等的情况，所以这个for循环放在上边 if (t.first >= x) { // 这个循环实际上是以i为左边界的 continue; } if (c[x - t.first] != INF) { ans = min(c[x - t.first] + t.second, ans); } } for (pii t : b[i]) { //首先初始化以i为右边界的花费,并把它们存储到c【i】中 c[t.first] = min(c[t.first], t.second) } } if (ans == INF) { cout << "-1" << endl; } else { cout << ans << endl; } } return 0; } |
其实这种方法也是很暴力的，它遍历了所有的日期边界，然后遍历这些边界左边的所有旅途和右边的所有旅途，有小的就记录下来，最终输出最小的结果。
CUGBACM16级2016年ICPC青岛赛区现场赛重现
这场比赛的A题是水题，我迟到两分钟，星哥已经A了，就很烦。
C题是概率题，我们找规律做的，要熟记住一些常用的常量啊。
B题是魔方题，要注意往左转其实可以等同于往右转三次，所以可以通用化处理。
D题目前待补。
学姐开的题库一
这场我只做了第一题，第一题是一道二分，题意是给出四排数字，让找出有多少种不同的方式从每排挑出一个数字最后的和为一个特定的值。
把前两排的sum全部储存，后两排sum也全部储存，然后遍历第一个对第二个sum进行二分即可得到结果。
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <algorithm> #include <climits> #include <cmath> #include <cstdio> #include <cstring> #include <deque> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <vector> #pragma comment(linker, "/STACK:1024000000,1024000000") #define all(a) (a).begin(), (a).end() #define ll long long #define endl "\n" #define DE cout << "------" << endl #define mems(a, b) memset(a, b, sizeof a) #define pii pair<int, int> #define mk make_pair using namespace std; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; int n; int t; int a[4005], b[4005], c[4005], d[4005]; // ll sum[160004], sum2[160003]; int sum[4005 * 4005]; int sum2[4005 * 4005]; int main() { ios::sync_with_stdio(false); cin >> t; while (t--) { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; } int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { sum[cnt] = a[i] + b[j]; sum2[cnt] = c[i] + d[j]; cnt++; } } // cout << cnt << endl; int ans = 0; sort(sum2, sum2 + cnt); for (int i = 0; i < cnt; i++) { // cout << ans << endl; ans += (upper_bound(sum2, sum2 + cnt, -sum[i]) - lower_bound(sum2, sum2 + cnt, -sum[i])); } cout << ans << endl; if (t) cout << endl; } return 0; } |
BC第1场
A题拓扑排序模板题，比较需要注意的一点是序号小的人要尽可能考前。
B题暴力求解，但是有一个问题，用结构体的时候初始化时间太长了，导致了TLE，把结构体换成单个的数组之后，就AC了，以后再用结构体一定是需要到某一个排序的时候再用，如果次序不变的话就不需要结构体了。此外，如果是两个元素的话，用pair效果更佳。
C题是一道网络流，这道题也提供了一种新的建图思路——奇偶建图。顾名思义，奇偶建图的精髓就是把奇数点和偶数点连一条边。其中的奇偶则通过横坐标和纵坐标确定。具体到这道题，C题的思路和建图至关重要，我们把相邻的两个点连一条边，然后把每两个相邻的深海或陆地变成超级源点和超级汇点，因为这些边是不能够转变为海岸线的边，然后跑一边网络流，用总边数减去网络流的结果即为所求。其中建立超级源点和超级汇点的具体过程百度上有很多，我就不多说了，这道题的收获主要是一种建边的思想以及看到不会的图论题就好好问问自己，是不是网络流？
D题不可做，BC通过率百分之零。
BC第二场
A题大意很简单，就是求一个队列中人数的最大值，用队列做果断T了，之后考虑用vector储存时间和人数，来人就用正数，人走就用负数。然后对字符串（时间）进行排序。搜一遍记录最大值，800ms，时间有些慢。隔壁有人用线段树来做，同样过了。代码如下：
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <algorithm> #include <climits> #include <cmath> #include <cstdio> #include <cstring> #include <deque> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <vector> //#pragma comment(linker, "/STACK:1024000000,1024000000") #define all(a) (a).begin(), (a).end() #define ll long long #define endl "\n" #define DE cout << "------" << endl #define mems(a, b) memset(a, b, sizeof a) #define psi pair<string, int> #define REP(i, n) for (int i = 0; i < (n); i++) #define mp make_pair using namespace std; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; int n; int t; int a[19000]; string st[19500]; string ed[19500]; vector<psi> q; // priority_queue <psi,vector<psi>,greater<psi> > q; int main() { ios::sync_with_stdio(false); cin >> t; while (t--) { cin >> n; q.clear(); for (int i = 0; i < n; i++) { cin >> a[i] >> st[i] >> ed[i]; q.push_back(mp(st[i], a[i])); q.push_back(mp(ed[i], -a[i])); } sort(q.begin(), q.end()); // sort(q,q+2*n); int max1 = 0; int sum = 0; for (int i = 0; i < 2 * n; i++) { // cout<<(q.top()).second<<endl; int peo = q[i].second; sum += peo; if (sum > max1) { max1 = sum; } } cout << max1 << endl; } return 0; } |
B题待补
C题我一眼望去就是一道简单的最短路，没想到自己看漏了一个条件——同一条直线上只要经过了的话就一定要停下来加油，很尴尬，最后还是顺利A了。需要建立一个特殊的结构体，很难写
题意是找一个只包括八个字母并且长度最小的不是给定字符串的子串的字符串，可能有点绕，不过只有八个字母，就要想到用八进制来表示，结果一直WA，感觉很奇怪，自己的八进制转入转出都没啥问题，莫名其妙少输出几个字母，暂时还不想在debug，不过这种把字符串压缩成八进制数字的思想很重要
2016ACM/ICPC亚洲区大连站-重现赛
这场做的比较多，收获也比较大，首先是A题，摔跤比赛，这道题之前做过一遍，其实就是一道bfs，重点在于题意有点坑。以后读题的时候还是要先静下心来好好读题。
B题赛后做的，学习了一个新的算法Shift_and，据说是一种很高效的字符串匹配算法。但在接下来的几场发现它在某些情况下竟然没有KMP快。本来想以后的字符串匹配算法都用这个，哎，还是老老实实用KMP吧。
明白了shift_and的原理之后，这道题很简单就解决了。
C题是一道裸的威佐夫博弈……..加大数，其中根号5的精度很高很高，郝进用一个大数二分模拟小数漂亮的解决了这道题，不在话下。
E题是一道树状数组的原理题。题意很令人费解，不过这道题和F题的解决方法其实有点像，都是计数，花式计数。他给了从1到n的n个整数，让我们回答几个询问，询问有两种，第一种是询问加入从L到R所有的数字需要花费的能量，第二种是问我们一共需要将x放入多少个set里。其实每放入一个新的数字，它的花费其实就是lowbit(i)。因此也就是求一个区间内lowbit的和以及一个数有几个父节点，第二种询问可以直接从当前节点往上寻找直到最大的值。第一种询问一开始根本没思路，后来贾大佬帮我讲明白其实是统计整个区间里每一种数字的个数最后加在一起。
F题其实本质上是一种贪心，最后需要逆元求取模除法。他要求把一条绳子分成几个不同的部分且各部分不相等并且他们的乘积要最大，其实就从2开始往上加，加到最后几个之后进行特殊处理。
G是一道树的分治，感觉有点难啊。郝进做了。
HIJ题均为水的不能再水的题，一道算概率算了一会之后就出了结果，一道算个三角形面积，一道三星两分钟a掉的题
BestCoder Round #3
A题是一道贪心，求一个最早能插入的地方。一开始我被之前皮皮讯的捕捉器困住了，一直在想办法找gap，最后发现反向一搜，问题就迎刃而解。林讯提出了一种想法，用两个vector，一个存储能用的一个存储不能用的，直接lower_bound，这也是一种不错的思路。
B题的思路我确实没想到，很巧妙，也有我做的题少的原因，题意是求使m为为中位数的子串有几个，这道题先进行状态压缩，将所有大于m的数变成1，所有小于m的数变成0，然后对m左边的数进行搜索，接着搜右边，对右边的每一个子串，搜索左边有没有对应的可以与他组成相加为0的子串，特别注意如果子串相对于m是单向的要特殊处理。
C题跟B题的思路很像，我也是赛后看的题解，他有一点组合数学的感觉在里边。是要求整个字符串里有几个偶数的子串，用一个状态压缩记录每一个字母的奇偶情况，两个相同状态的子串相减就是一个偶数字母子串，所以只需要统计出每个状态的数目然后对每一个求c(n,2)就好了。对于问号要特殊处理，这里不再详述。
D题待补。
通过总结这些题发现自己以后每个礼拜都要进行一次这样的总结。有的题做完之后竟然完全想不起该怎么做，算法的专题当然还要再练，但对自己过去的总结一定不能丢！