比赛开始前为了消磨时间写了会php，结果忘了时间，想起比赛的时候已经开始10分钟了……
A题 Paper Work
题目大意：给你一个数组，你可以将数组分段，要求在保证每段内的负数不超过2个条件下，总段数最少。
输出段数以及每段包含的个数。
题解：根据贪心，我们可以把尽量多的数放入一个段中，直到这个段内的负数个数多于个。
View Code
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <set> #include <vector> #include <queue> #include <stack> #include <cmath> #include <map> using namespace std; #define INF 0x73737373 #define EPS 1e-8 #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 int a[105]; vector <int> ret; int main() { int n; scanf("%d", &n); int tmp = 0, num = 0; for(int i = 0; i < n; i++) { scanf("%d", &a[i]); tmp++; if(a[i] < 0) num++; if(num == 3) { num = 1; ret.push_back(tmp - 1); tmp = 1; } } if(tmp != 0) ret.push_back(tmp); printf("%d\n", ret.size()); for(int i = 0; i < ret.size(); i++) printf("%d ",ret[i]); puts(""); return 0; }
B题 Restoring IPv6
题目大意：有一个IPv6地址按照某种规则压缩，现在要求你把它还原回来。
压缩规则如下：
1.如果一个区块的值有前导0，则可以移除任意多个前导0，但必须保证该区块至少有一位数。
2.如果有两个以上的连续区块的值为0，我们可以把它压缩为::，但一个IPv6地址只能包含一个::
题解：根据题意，先把每个区块的位数用0补充直四位，再在::的地方用0000填充缺少的区块，直到整串的区块数为8即可。
代码写丑了。
View Code
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <set> #include <vector> #include <queue> #include <stack> #include <cmath> #include <map> using namespace std; #define INF 0x73737373 #define EPS 1e-8 #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 vector <string> ip; vector <string> ret; int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) { string ipAddress; cin >> ipAddress; string temp; ip.clear(); ret.clear(); bool zero = true; for(int j = 0; j < ipAddress.size(); j++) { if(ipAddress[j] != ':') temp += ipAddress[j]; else { if(zero && temp == "") { ip.push_back(temp); zero = false; } else if(temp != "") { ip.push_back(temp); } temp.clear(); } } if(temp != "")ip.push_back(temp); temp.clear(); zero = true; for(int j = 0; j < ip.size(); j++) { if(ip[j].size() != 0) { for(int k = 0; k < 4 - ip[j].size(); k++) temp += "0"; temp += ip[j]; ret.push_back(temp); temp.clear(); } else if(zero) { zero = false; for(int k = 0; k < 8 - ip.size() + 1; k++) { temp = "0000"; ret.push_back(temp); temp.clear(); } } } cout << ret[0]; for(int i = 1; i < 8; i++) cout << ":" + ret[i]; cout << endl; } return 0; }
C题 Movie Critics
题目大意：有一段数，从左至右遍历，如果当前的数和上一次的数值不同，则压力++。
现在你可以将某一个数值的所有数从这段数中取出，要求最后的压力最小，输出要取出的数的数值，如果有多个合法的数值，输出数值小的那个。
题解：很显然，一个数值相同的连续的段跟该数值的一个数是等价的，所以我们可以先把这段数处理一下，将数值相同的段缩成一个数。
接下来，如果这个数的左边的值和右边的值相同，那我们移除掉这个数就可以减少2个压力点，比如1 3 1，移除掉3可以减少2个压力点。
如果这个数的左边的值和右边的值不同，那我们移除掉这个数就可以减少1个压力点。比如1 2 3，移除掉2可以减少1个压力点。
所以O(n)遍历一遍，统计忽略每一个数值能减少多少压力点，选出能减少压力点最多的那个即可。
View Code
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <set> #include <vector> #include <queue> #include <stack> #include <cmath> #include <map> using namespace std; #define INF 0x73737373 #define EPS 1e-8 #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 vector<int> f; map<int ,int> hash; int main() { int n, k; scanf("%d%d", &n, &k); for(int i = 0; i < n; i++) { int a; scanf("%d", &a); if(f.size() == 0 || f[f.size() - 1] != a) f.push_back(a); } for(int i = 0; i < f.size(); i ++) { int left = i - 1; left = (left < 0)? -1:f[left]; int right = i + 1; right = (right >= f.size())? -1:f[right]; if(left != right)hash[f[i]] += 1; else hash[f[i]] += 2; } map <int, int> ::iterator it; int ret = -1, num = 0; for(it = hash.begin(); it != hash.end(); it++) { if(num <= it->second) { if(num == it->second) { ret = min(ret, it->first); } else ret = it->first; num = it->second; } } printf("%d\n", ret); return 0; }
D题 Building Bridge
题目大意：平面上有一条河，河的左岸的x轴坐标为a，河的右岸的x轴坐标为b。
河的左岸有n个点可以用于修桥，每个点的y坐标为yi，村子到达任意一点的距离都为其欧拉距离
河的右岸有m个点可以用于修桥，每个点的y坐标为yi‘，村子到达某点的距离为li
你可以选择左岸的某个点和右岸的某个点修一座桥。
现在从河左岸的村子，点(0, 0)出发，经过桥到达右岸的村庄，要求距离最短，输出应该选左岸的点的序号和右岸的点的序号。
题解：我们把左岸的点设为Ai(a, yi),右岸的点设为Bi(b, yi')，可以想到，对于任何一个Ai都存在一个Bi使得以Ai为起点到达村子的距离最短。
那么我们将Ai作为横轴，将左岸村子到达右岸村子的距离作为纵轴作图，可以看出这是一个凸性函数，那么我们可以通过三分法求出最小值，并记录下对应的Ai、Bi输出
View Code
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <set> #include <vector> #include <queue> #include <stack> #include <cmath> #include <map> using namespace std; #define INF 0x73737373 #define EPS 1e-6 #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 int l[105000]; typedef struct { int r, len, id; }RIGHT_POINT; RIGHT_POINT r[105000]; int n, m, a, b; double cal(double y) { double OA = hypot(a, y); double ret = 1e20; for(int i = 1; i <= m; i++) ret = min(ret, OA + hypot(b - a, r[i].r - y) + r[i].len); return ret; } int get_point(double val) { int index = 1; for(int i = 1; i <= n; i++) { if(fabs(val - l[index]) > fabs(val - l[i])) index = i; } return index; } int main() { int left_point; double max_ret = 1e20; scanf("%d%d%d%d", &n, &m, &a, &b); for(int i = 1; i <= n; i++) scanf("%d", &l[i]); for(int i = 1; i <= m; i++) { scanf("%d", &r[i].r); r[i].id = i; } for(int i = 1; i <= m; i++) scanf("%d", &r[i].len); int low = 1, high = n; while(low <= high) { int mid = (low + high) >> 1; int midmid = (mid + high) >> 1; double mid_ret = cal(l[mid]); double midmid_ret = cal(l[midmid]); if(mid_ret + EPS < max_ret) { max_ret = mid_ret; left_point = mid; } if(midmid_ret + EPS < max_ret) { max_ret = midmid_ret; left_point = midmid; } if(mid_ret <= midmid_ret) high = midmid - 1; else low = mid + 1; } double ret = 1e20; int right_point = -1; for(int i = 1; i <= m; i++) if(ret - EPS > hypot(b - a, r[i].r - l[left_point]) + r[i].len) { ret = hypot(b - a, r[i].r - l[left_point]) + r[i].len; right_point = i; } printf("%d %d\n", left_point, right_point); return 0; }