test Week1

Week 1 test 总结

180min 3/5 前三道基础题120min

1题是基础的找最大值的题目

2题直接求关系式　&　求模的化简

3题一道栈的模拟题，一开始想的太复杂了，遍历一遍找到两个相邻且相同的字符就把它去掉，不断循环知道没有为止

其实仔细一想这个做法的最坏情况是回文串的情况那么就是一个o(n^2)的一个算法，数据规模是20000，果断TLE。。

那么就应该用o(n)的算法了，简单的栈模拟啊，想半天没看出来？？ 平时有点眼高手低了。。。

4.5题 难题，由于就剩50min左右时间已经比较难有作为了，4题没看 5题求最长回文子序列，刚好最近在usaco上有相关的练习

就写了个o(n^2)的枚举中心点，果断超时。。（下次在写之前要评估可用的复杂度才行！！要不然做无用功）

目标:

心态稳住，70min第三题没出时略慌张啊，乱了些，以后usaco上要限时间多练才行。

基础题要稳、快，压缩前三题的时间，从第3题上面可以看出依旧是见题太少，多做点基础题吧，usaco做起来，基础题做快了、

稳了后面才好办一点。

后篇：

5题要用到O(n)求最长回文子串的manacher算法 : 用类似dp的方法省去了重复的判断，由于N的串就会有2×N-1个对称中心， 那么首先对串进行修改

在两个字符之间加入#，串头加入@字符防止越界。

void changeformana() {int tmplen = tmp.length();s = "@";s += "#";for (int i = 0; i < tmplen; i++) {s += tmp[i];s += "#";}
}

接下来是算法的核心代码段：有一个p[2*N]的数组表示组合串中以i为中心的最长向右延伸距离 ； mx记录回文串中到达最右侧的距离，id是该距离的中心点；

 if(mx > i) p[i] = min(p[2*id -i], mx-i) 这个核心判断 基于这么一个事实：当mx大于i时， p[i] 会确定一个最小值就是i关于id点的对称点的最长延伸距离和mx-i的长度之间的小者

void manacher() {maxpalinlen = 0;id = 0; mx = 0;int len = s.length();for (int i = 0; i < len; i++) {if (mx > i) p[i] = min(p[2 * id - i], mx - i);else p[i] = 1;for (; s[i - p[i]] == s[i + p[i]]; p[i]++) if (p[i] + i > mx) {id = i;mx = p[i] + i;}if (maxpalinlen < p[i]) maxpalinlen = p[i];}maxpalinlen -= 1;
}

另附相关练习poj3974

#include 
#include 
#include 
#include 
using namespace std;const int maxn = 2000010;
string tmp;
string s;
int p[maxn];
int len, mx, id, maxpalinlen;void manacher() {for (int i = 0; i < len; i++) {if (mx > i) p[i] = min(p[2 * id - i], mx - i);else p[i] = 1;for (; s[i - p[i]] == s[i + p[i]]; p[i]++) if (p[i] + i > mx) {id = i;mx = p[i] + i;}if (maxpalinlen < p[i]) maxpalinlen = p[i];}maxpalinlen -= 1;
}int main() {int cases = 1;while (cin >> tmp) {if (tmp == "END") break;len = 0; mx = 0; id = 0; maxpalinlen = 0;memset(p, 0, sizeof(p));int tmplen = tmp.length();s = "@"; s += "#";for (int i = 0; i < tmplen; i++) {s += tmp[i];s += "#";}len = s.length();manacher();printf("Case %d: %d\n", cases++, maxpalinlen);}
}

后后篇：但是binary palindrome 这道题的瓶颈不在于回文子串的查找，而是将1到N的二进制数组合起来，给定一个二进制数N要将1到N组合至少是O(n^2) 的复杂度，那么也就是说常规方法：　先合成串，再用最快的manacher在1^6的数据规模， 1s的时间内也稳稳的超时。。。那么也就是说要用非常规的方法通过给定的N直接得出答案——打表找规律

一开始的规律不明显，到后面就可以看见是2的次方关系。

#include 
#include 
#include 
using namespace std;const int maxn = 1000005;
char s[maxn];
int len;int btoten() {int tmp = 0;for (int i = 0; s[i] != 0 ; i++) {tmp = tmp * 2 + (s[i] - '0');}return tmp;
}int main() {scanf("%s", s);len = strlen(s);if (len < 6) {int number = btoten();if (number == 1) cout << 1 << endl;else if (number == 2) cout << 2 << endl;else if (number <= 6) cout << 5 << endl;else if (number <= 10) cout << 7 << endl;else if (number <= 14) cout << 9 << endl;else if (number <= 18) cout << 10 << endl;else if (number <= 22) cout << 11 << endl;else cout << 13 << endl;}else {bool isok = 0;for (int i = 1; i < len-3; ++i) {if (s[i] == '1') {isok = 1;break;}}if (isok || (s[len-1] == '1' && s[len-2] == '1' && s[len-3] == '1')) {cout << (len-5) * 3 + 13 << endl;}else  {cout << (len-6) * 3 + 13 << endl;}}
}

D篇， 是类似线性规划的一道题，由题目得以下关系式：

1.a2*x + b2*y == a2*(n-x) + b2*(m-y)

2.0<=x<=n

3.0<=y<=m

根据以上式子，可以得到a1*x+ b1*y的最大值出现在1的方程与2，3方程和xy轴的四个交点上。逐一判断即可。代码写丑了一次莫名WA。。重新整理一遍才过。

#include 
#include 
using namespace std;double a1, b1, a2, b2, n, m;
double ans;
double x, y;
double y1, x1, y2, x2;int main()
{cin >> a1 >> b1 >> a2 >> b2 >> n >> m;double q = (a2*n + b2*m)/2;y1 = q/b2;x1 = (q-b2*m)/a2;y2 = (q-a2*n)/b2;x2 = q/a2;if (y1 <= m && y1 >= 0) {if (ans < y1*b1) {ans = y1*b1;x = 0; y = y1;}}if (x1 <= n && x1 >= 0) {if (ans < x1*a1 + m*b1) {ans = x1*a1 + m*b1;x = x1; y = m;}}if (y2 <= m && y2 >= 0) {if (ans < n*a1 + y2*b1) {ans = n*a1 + y2*b1;x = n; y = y2;}}if (x2 <= n && x2 >= 0) {if (ans < x2*a1) {ans = x2*a1;x = x2; y = 0;}}cout << fixed << setprecision(8) << x << ' ' << y << endl;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！