首页 > 代码库 > AHU 周末练习 题解
AHU 周末练习 题解
=。= 这次比赛乱搞题比较多。。做的时候也比较烦躁。。感觉效率不是很高。
A： 水题，直接记录每个数字的位置然后输出就好了。
B: 题目看半天才明白，其实就是考一个三进制转化，很水。。
typedef long long LL;const int maxn = 1024;int numa[maxn], numc[maxn], numb[maxn];int to3(LL num, int *str) { int len = 0; while(num) { str[len++] = num % 3; num /= 3; } return len;} int main() { int a, b, c; cin >> a >> c; int lena = to3(a, numa); int lenc = to3(c, numc); int lenb = max(lena, lenc); for(int i = 0; i < lenb; i++) { numb[i] = (numc[i] - numa[i]) % 3 + 3; numb[i] %= 3; } int ans = 0; for(int i = lenb - 1; i >= 0; i--) ans = ans * 3 + numb[i]; cout << ans << endl; return 0;}C: 注意特判一下全部元素都是1的情况，这时候只能交换到2，其他情况都是把最大的数换成1
#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <set>#include <bitset>#include <queue>#include <stack>#include <string>#include <iostream>#include <cmath>#include <climits>using namespace std;const int maxn = 1e5 + 10;int num[maxn];int main() { int n; cin >> n; bool flag = false; for(int i = 1; i <= n; i++) { cin >> num[i]; if(num[i] != 1) flag = true; } if(!flag) { for(int i = 1; i < n; i++) cout << "1 "; cout << 2 << endl; return 0; } num[0] = 1; sort(num, num + n + 1); for(int i = 0; i < n; i++) cout << num[i] << " "; cout << endl; return 0;}D: 题意是，给你八个点，问你能不能选出4个点使其构成正方形，剩下4个构成长方形。
先枚举所有点的全排列，然后只要无脑判断前4个点和后四个点就好了。
判断矩形只要判断相邻的边都垂直，正方形只要在这基础上保证四条边都相等就好。
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#include <cmath>using namespace std;struct Point { double x, y; Point(double x, double y) :x(x), y(y) {} Point() {};};Point operator - (Point a, Point b) { return Point(a.x - b.x, a.y - b.y);}double dist(Point a) { return sqrt(a.x*a.x + a.y*a.y);}double ag(Point a, Point b) { return fabs(a.x*b.x + a.y*b.y);}const double eps = 1e-7;Point p[10];int id[10];bool equ(double a, double b) { if (fabs(a - b) < eps) return true; return false;}bool isSquare(Point a1, Point a2, Point a3, Point a4) { Point p1 = a1 - a2, p2 = a2 - a3, p3 = a3 - a4, p4 = a4 - a1; double app = ag(p1, p2) + ag(p2, p3) + ag(p3, p4) + ag(p4, p1); if (fabs(app) > eps) return false; if (equ(dist(p1), dist(p2)) && equ(dist(p1), dist(p3)) && equ(dist(p1), dist(p4))) return true; return false;}bool isR(Point a1, Point a2, Point a3, Point a4) { Point p1 = a1 - a2, p2 = a2 - a3, p3 = a3 - a4, p4 = a4 - a1; double app = ag(p1, p2) + ag(p2, p3) + ag(p3, p4) + ag(p4, p1); if (fabs(app) > eps) return false; return true;}int main() { for (int i = 1; i <= 8; i++) { scanf("%lf%lf", &p[i].x, &p[i].y); id[i] = i; } do { bool r1 = isSquare(p[id[1]], p[id[2]], p[id[3]], p[id[4]]); bool r2 = isR(p[id[5]], p[id[6]], p[id[7]], p[id[8]]); if (r1 && r2) { puts("YES"); printf("%d %d %d %d\n", id[1], id[2], id[3], id[4]); printf("%d %d %d %d\n", id[5], id[6], id[7], id[8]); return 0; } } while (next_permutation(id + 1, id + 1 + 8)); puts("NO"); return 0;}E: 题意是：给你一个01？序列，有两个人先后从序列中取数字，直到只剩两个数字的时候。先手的人想让剩下的数字尽可能小，后手的人想让数字尽可能的大。问？取01任意情况的时候，最后剩下的两位数的所有可能性。
考虑没有问号的情况，设cnt0为0的数量，cnt1为1的数量。
有如果cnt0 > cnt1 必为 00
cnt1 > cnt0 + 1 必为11
cnt1 == cnt0 或者 cnt1 == cnt0 + 1 的时候可能10也可能01，最后的值由序列的最后一个元素的决定。
那么加上问号之后 有cnt2表示问号的数量
如果可能达到cnt0+cntw>cnt1 00是有可能出现的
如果可能达到cnt1 + cntw > cnt0 + 1 11是有可能出现的
然后如果可能出现一种情况使得加上问号之后有cnt1==cnt0或者cnt1==cnt0+1，并且序列的最后一位不是问号，那么10或者01中的一个是可能出现的。
如果序列最后一个数是问号，那么分别讨论这个问号是0和1的情况，并且重新判断加上cnt2-1个问号之后，cnt1==cnt0,cnt1==cnt0+1是否可能达到。
#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <set>#include <bitset>#include <queue>#include <stack>#include <string>#include <iostream>#include <cmath>#include <climits>using namespace std;const int maxn = 2e5 + 10;char buf[maxn];void gao(char *str) { int len = strlen(str); int cnt0 = 0, cnt1 = 0, cntw = 0; for(int i = 0; i < len; i++) { if(str[i] == ‘0‘) cnt0++; if(str[i] == ‘1‘) cnt1++; if(str[i] == ‘?‘) cntw++; } if(cnt0 + cntw > cnt1) puts("00"); if(cnt0 + cntw + 1 >= cnt1 && cnt1 + cntw >= cnt0) { if(str[len - 1] == ‘?‘) { //假设最后一位填1 if(cnt0 + cntw >= cnt1 + 1 && cnt1 + cntw >= cnt0) puts("01"); //假设最后一位填0 if(cnt0 + cntw + 1 >= cnt1 && cnt1 + cntw - 1 >= cnt0 + 1) puts("10"); } else if(str[len - 1] == ‘1‘) puts("01"); else puts("10"); } if(cnt1 + cntw > cnt0 + 1) puts("11");}int main() { while(scanf("%s", buf) != EOF) { gao(buf); } return 0;}F 题意是战场上有n个横向或者纵向的沟壑，每a秒会有激光扫射战场b秒，人的移动速度是1，问你能否从起点到达终点。。保证b大于任意一个沟壑长度。
先预处理出来所有沟壑之间的距离，然后bfs一遍就好了，因为只要距离小于a，时间肯定是a。
bfs可以用优先队列加速一下~
#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <set>#include <bitset>#include <queue>#include <stack>#include <string>#include <iostream>#include <cmath>#include <climits>using namespace std;const int maxn = 1e3 + 10;const double eps = 1e-9;int a, b, n;double sx, sy, ex, ey;double dist[maxn][maxn];double posx1[maxn], posx2[maxn], posy1[maxn], posy2[maxn];bool vis[maxn];bool equ(double a, double b) { return fabs(a - b) < eps;}struct Point { double x, y; Point (double x = 0, double y = 0): x(x), y(y) {} bool operator == (const Point &p) const { return equ(p.x, x) && equ(p.y, y); }};typedef Point Vector;double sq(double x) { return x * x;}Point operator - (Point a, Point b) { return Point(a.x - b.x, a.y - b.y);} double getdist(Vector v) { return sqrt(v.x * v.x + v.y * v.y);}double dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y;}double Cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x;}double getdist(Point p, Point a, Point b) { if(a == b) return getdist(p - a); Vector v1 = b - a, v2 = p - a, v3 = p - b; if(dot(v1, v2) < 0) return getdist(v2); else if(dot(v1, v3) > 0) return getdist(v3); else return fabs(Cross(v1, v2)) / getdist(v1);}double getdist(int i, int j) { //判断两条线段的距离 double x1 = posx1[i], x2 = posx2[i], y1 = posy1[i], y2 = posy2[i]; double x3 = posx1[j], x4 = posx2[j], y3 = posy1[j], y4 = posy2[j]; Point p1(x1, y1), p2(x2, y2), p3(x3, y3), p4(x4, y4); double ret = min(getdist(p1, p3, p4), getdist(p2, p3, p4)); ret = min(ret, min(getdist(p3, p1, p2), getdist(p4, p1, p2))); return ret;}struct Node { int id; double cost; Node(int id = 0, double cost = 0): id(id), cost(cost) {} bool operator < (const Node &x) const { return cost > x.cost; }};int main() { scanf("%d%d", &a, &b); scanf("%lf%lf%lf%lf", &sx, &sy, &ex, &ey); scanf("%d", &n); posx1[0] = posx2[0] = sx; posy1[0] = posy2[0] = sy; posx1[n + 1] = posx2[n + 1] = ex; posy1[n + 1] = posy2[n + 1] = ey; for(int i = 1; i <= n; i++) { scanf("%lf%lf%lf%lf", &posx1[i], &posy1[i], &posx2[i], &posy2[i]); } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { dist[i][j] = getdist(i, j); } } //BFS double pse = getdist(Point(sx, sy) - Point(ex, ey)); double ans = pse <= a ? pse : 1e12; priority_queue<Node> q; for(int i = 1; i <= n; i++) { double ret = getdist(0, i); if(ret <= a) { q.push(Node(i, a + b)); } } while(!q.empty()) { Node tt = q.top(); q.pop(); int now = tt.id; double nowcost = tt.cost; //printf("%d %.3f\n", now, nowcost); if(getdist(now, n + 1) <= a) { ans = min(ans, nowcost + getdist(now, n + 1)); } for(int i = 1; i <= n; i++) if(dist[now][i] <= a + eps && !vis[i]) { q.push(Node(i, nowcost + a + b)); vis[i] = true; } } if(ans > 1e10) puts("-1"); else printf("%.10f\n", ans); return 0;}
G:水题，直接搞。
H: 题意是，给你一个序列，现在最多可以进行k次操作，每次操作可以让序列中任意一个元素取反，问你最大可能的长度为len的子序列和的绝对值是多少。
考虑使用简单的滑窗模型，维护一个长度为len的子序列，每次只要增删一个值并且统计处理就可以了。
现在需要的就是这样一个数据结构，
可以快速增加和删除元素，可以快速的求前k大的和。
其实用两个multiset就可以处理这样的问题。。或者用两个map模拟 multiset
也可以用树状数组套主席树。。不过没必要吧。。
具体看代码吧。。
至于处理绝对值，只要把所有数字取反再算一遍就好了。
#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <set>#include <bitset>#include <queue>#include <stack>#include <string>#include <iostream>#include <cmath>#include <climits>using namespace std;typedef long long LL;const int maxn = 1e5 + 10;multiset<int> st1, st;int n, len, k, a[maxn];LL sum = 0;void insert(int num) { if (k == 0) { sum -= num; return; } if (st.size() == k) { int pnum = *st.begin(); if (pnum < num) { st.erase(st.begin()); sum = sum - 2 * pnum + num; st.insert(num); st1.insert(pnum); } else { st1.insert(num); sum -= num; } } else { sum += num; st.insert(num); }}void erase(int num) { if (k == 0) { sum += num; return; } multiset<int>::iterator it = st.find(num); if (it != st.end()) { st.erase(it); sum -= num; if (st1.size() != 0) { it = st1.end(); it--; insert((*it)); sum += *it; st1.erase(it); } } else { it = st1.find(num); if(it != st1.end()) st1.erase(it); sum += num; }}LL gao() { LL ans = 0; st.clear(); st1.clear(); sum = 0; for (int i = 1; i <= len; i++) { if (a[i] >= 0) sum += a[i]; else insert(-a[i]); } ans = sum; for (int i = len + 1, j = 1; i <= n; i++, j++) { if (a[j] < 0) erase(-a[j]); else sum -= a[j]; if (a[i] < 0) insert(-a[i]); else sum += a[i]; ans = max(ans, sum); } return ans;}int main() { scanf("%d%d", &n, &len); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d", &k); LL ans = gao(); for (int i = 1; i <= n; i++) a[i] = -a[i]; ans = max(ans, gao()); cout << ans << endl; return 0;}
I：伤心的一题。。。。可以直接暴力搞，复杂度不是很高，因为毕竟约数就不超过sqrt(n)个。我还花很久撸了一个KMP。。
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int maxn = 1000005;int f[maxn];inline void getfail(char *str) { int m = strlen(str); f[0] = f[1] = 0; for(int i = 2;i <= m;i++) { int j = f[i - 1]; while(j && str[i - 1] != str[j]) j = f[j]; if(str[i - 1] == str[j]) f[i] = j + 1; else f[i] = 0; }}int gao(char *str) { int n; n = strlen(str); getfail(str); if(f[n] > 0 && n % (n - f[n]) == 0) { return (n - f[n]); } else return n;}char str1[maxn], str2[maxn];int main() { int n,kase = 0; while(scanf("%s%s",str1, str2) != EOF) { int p1 = gao(str1), p2 = gao(str2); int len1 = strlen(str1), len2 = strlen(str2); if(strncmp(str1, str2, max(p1, p2)) == 0) { if(p1 == p2) { int ans = 0; for(int i = p1; i <= min(len1, len2); i += p1) { if(len1 % i == 0 && len2 % i == 0) { ans++; } } printf("%d\n", ans); } else puts("1"); } else { puts("0"); } } return 0;}J: DP水题，题目很长。。
#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <set>#include <bitset>#include <queue>#include <stack>#include <string>#include <iostream>#include <cmath>#include <climits>using namespace std;struct Board { int a, b; Board(int a = 0, int b = 0) : a(a), b(b) {} bool operator == (const Board &x) const { return a == x.a && b == x.b; } bool operator < (const Board &x) const { if(x.a == a) return x.b < b; return x.a < a; }};const int mod = 1e9 + 7;vector<Board> vec;int f[4000][300][2], n, l;int main() { scanf("%d%d", &n, &l); for(int i = 1; i <= n; i++) { int a, b; scanf("%d%d", &a, &b); if(a > b) swap(a, b); vec.push_back(Board(a, b)); } sort(vec.begin(), vec.end()); //vec.erase(unique(vec.begin(), vec.end()), vec.end()); int cnt_board = vec.size(); for(int i = 1; i <= l; i++) { for(int j = 0; j < cnt_board; j++) { if(i == vec[j].b) { f[i][j][0] = (f[i][j][0] + 1) % mod; } if(i == vec[j].a && vec[j].a != vec[j].b) { f[i][j][1] = (f[i][j][1] + 1) % mod; } else for(int k = 0; k < cnt_board; k++) if(j != k) { if(i - vec[j].b > 0) { if(vec[j].b == vec[k].a) f[i][j][0] = (f[i - vec[j].b][k][0] + f[i][j][0]) % mod; if(vec[j].b == vec[k].b) f[i][j][0] = (f[i - vec[j].b][k][1] + f[i][j][0]) % mod; } if(i - vec[j].a > 0 && vec[j].a != vec[j].b) { if(vec[j].a == vec[k].a) f[i][j][1] = (f[i - vec[j].a][k][0] + f[i][j][1]) % mod; if(vec[j].a == vec[k].b) f[i][j][1] = (f[i - vec[j].a][k][1] + f[i][j][1]) % mod; } } //printf("for length:%d, (%d,%d) ans is %d %d\n", i, vec[j].a, vec[j].b, f[i][j][0], f[i][j][1]); } } int ans = 0; for(int i = 0; i < cnt_board; i++) { ans = (ans + f[l][i][0]) % mod; ans = (ans + f[l][i][1]) % mod; } printf("%d\n", ans); return 0;}K: 原本拉这题想考DP的，没想到直接找规律就可以过。。。
L:水题，注意相加之后不要溢出了。。
AHU 周末练习 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。