首页 > 代码库 > 2016"百度之星" - 初赛（Astar Round2A）
2016"百度之星" - 初赛（Astar Round2A）
All X[HDU5690]
找循环节，注意可能是混循环。
#include <stdio.h>#include <string.h>bool f[10005];int a[10005], l, r;int main() { int n, x, k, c, t; long long m; scanf("%d", &n); for (int q = 0; q < n; q++) { scanf("%d%lld%d%d", &x, &m, &k, &c); memset(f, false, sizeof(f)); l = r = 0; a[r++] = x % k; f[a[0]] = true; for (int i = 0;; i++) { t = (a[r - 1] * 10 + x) % k; if (f[t]) { for (int j = 0; j < r; j++) { if (a[j] == t) { l = j; break; } } break; } f[t] = true; a[r++] = t; } m -= l; printf("Case #%d:\n%s\n", q + 1, c == a[m % (r - l) == 0 ? r - 1 : l + (int)(m % (r - l)) - 1] ? "Yes" : "No"); } return 0;}Sitting in Line[HDU5691]
状态压缩，状态i表示整数的选取状态，其二进制形式的10分别表示对应的数字是否选取。dp[i][j]表示在状态i下最后放置的数字是第j个数字能得到的最大值。
#include<bitset>#include<map>#include<vector>#include<cstdio>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<stack>#include<queue>#include<set>#define inf 0x3f3f3f3f#define mem(a,x) memset(a,x,sizeof(a))#define F first#define S secondusing namespace std;typedef long long ll;typedef pair<int, int> pii;inline int in() { int res = 0; char c; int f = 1; while ((c = getchar()) < ‘0‘ || c > ‘9‘)if (c == ‘-‘) { f = -1; } while (c >= ‘0‘ && c <= ‘9‘) { res = res * 10 + c - ‘0‘, c = getchar(); } return res * f;}const int N = 100010, MOD = 1e9 + 7;int a[16];int dp[1 << 16][16], must[16];int one[1 << 16];int main() { for (int i = 0; i < 1 << 16; i++) { for (int j = i; j; j >>= 1) { one[i] += j & 1; } } int T = in(), ca = 1; while (T--) { int n = in(); mem(must, -1); int x, y; for (int i = 0; i < n; i++) { scanf("%d%d", &x, &y); a[i] = x; if (y != -1) { must[y] = i; //y位置必须是ai值 } } int all = 1 << n; for (int i = 0; i < all; i++) { for (int j = 0; j < n; j++) { dp[i][j] = -inf; } } //0没法转移, 特殊处理 if (must[0] == -1) { for (int i = 0; i < n; i++) { dp[1 << i][i] = 0; } } else { dp[1 << must[0]][must[0]] = 0; } for (int i = 1; i < all; i++) { int num = one[i]; if (must[num] == -1) { for (int j = 0; j < n; j++) { //枚举结束位置 if (i & 1 << j && dp[i][j] != -inf) { for (int k = 0; k < n; k++) { //枚举下一次加的值 if (!(i & 1 << k)) { dp[i | 1 << k][k] = max(dp[i | 1 << k][k], dp[i][j] + a[k] * a[j]); } } } } } else { int k = must[num]; //下一个位置必须是a[k] if (i & 1 << k) { continue; //如果a[k]已经使用, 不更新 } for (int j = 0; j < n; j++) { if (i & 1 << j && dp[i][j] != -inf) { dp[i | 1 << k][k] = max(dp[i | 1 << k][k], dp[i][j] + a[j] * a[k]); } } } } int ans = -inf; for (int j = 0; j < n; j++) { ans = max(ans, dp[all - 1][j]); } printf("Case #%d:\n%d\n", ca++, ans); } return 0;}Snacks[HDU5692]
首先先弄成以0为根的一棵树，每个节点的权值为根节点到当前节点的价值之和。查询某个节点时，其价值之和的最大值应为该节点对应的子树中最大的权值。更新某个节点的权值时，则该节点对应的子树上每一个节点都会产生同样的变化。因此，可以通过dfs产生树的先根遍历，然后用线段树来进行更新和查询操作。
错的原因：线段树写错了，lazy处理的不对。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <stdio.h>#include <string.h>template <class T> class SegmentTree {public: T dat, lazy; int leftBorder, rightBorder, mid; SegmentTree * leftSon, * rightSon; T(* lazyfunc)(T, T); T(* mergefunc)(T, T); SegmentTree() { leftBorder = rightBorder = -1; leftSon = rightSon = NULL; } void pushdown(); void pushup(); void Build(T *, int, int, T(*)(T, T), T(*)(T, T)); void Modify(int, int, T); T Query(int, int); void Free();};template<class T> void SegmentTree<T>::pushdown() { if (lazy && leftBorder != rightBorder) { leftSon->dat = lazyfunc(leftSon->dat, lazy); rightSon->dat = lazyfunc(rightSon->dat, lazy); leftSon->lazy = lazyfunc(leftSon->lazy, lazy); rightSon->lazy = lazyfunc(rightSon->lazy, lazy); } lazy = (T)0;}template<class T> void SegmentTree<T>::pushup() { dat = mergefunc(leftSon->dat, rightSon->dat);}template<class T> void SegmentTree<T>::Build(T * S, int l, int r, T(* lfunc)(T, T), T(* mfunc)(T, T)) { if (l > r) { return; } lazy = (T)0; leftBorder = l; rightBorder = r; mid = (leftBorder + rightBorder) >> 1; lazyfunc = lfunc; mergefunc = mfunc; if (l == r) { dat = S[l]; return; } leftSon = new SegmentTree; leftSon->Build(S, l, mid, lfunc, mfunc); rightSon = new SegmentTree; rightSon->Build(S, mid + 1, r, lfunc, mfunc); pushup();}template<class T> void SegmentTree<T>::Modify(int l, int r, T NewDat) { if (l > r || l < leftBorder || rightBorder < r) { return; } if (leftBorder == l && rightBorder == r) { dat = lazyfunc(dat, NewDat); lazy = lazyfunc(lazy, NewDat); return; } pushdown(); if (r <= mid) { leftSon->Modify(l, r, NewDat); } else if (mid < l) { rightSon->Modify(l, r, NewDat); } else { leftSon->Modify(l, mid, NewDat); rightSon->Modify(mid + 1, r, NewDat); } pushup();}template<class T> T SegmentTree<T>::Query(int l, int r) { if (l > r || l < leftBorder || rightBorder < r) { return dat; } pushdown(); if (l == leftBorder && r == rightBorder) { return dat; } if (r <= mid) { return leftSon->Query(l, r); } else if (mid < l) { return rightSon->Query(l, r); } else { return mergefunc(leftSon->Query(l, mid), rightSon->Query(mid + 1, r)); }}template<class T> void SegmentTree<T>::Free() { if (leftSon != NULL) { leftSon->Free(); } if (rightSon != NULL) { rightSon->Free(); } delete leftSon; delete rightSon;}SegmentTree<long long> st;long long a[100005], b[100005], w[100005];int M, N;int head[100005], l[100005], r[100005];struct EDGE { int v, nex;} edge[200005];void addEdge(int a, int b) { edge[M].v = b; edge[M].nex = head[a]; head[a] = M++; edge[M].v = a; edge[M].nex = head[b]; head[b] = M++;}long long lazyfunc(long long x, long long y) { return x + y;}long long mergefunc(long long x, long long y) { return x > y ? x : y;}void dfs1(int f, int x) { int e = head[x]; while (e != -1) { int v = edge[e].v; if (f != v) { a[v] = a[x] + w[v]; dfs1(x, v); } e = edge[e].nex; }}void dfs2(int f, int x) { l[x] = N; b[N++] = a[x]; int e = head[x]; while (e != -1) { int v = edge[e].v; if (f != v) { dfs2(x, v); } e = edge[e].nex; } r[x] = N - 1;}int main() { int n, m, t, o, u, v; scanf("%d", &t); for (int q = 1; q <= t; q++) { scanf("%d%d", &n, &m); M = 0; memset(head, -1, sizeof(head)); for (int i = 1; i < n; i++) { scanf("%d%d", &u, &v); addEdge(u, v); } for (int i = 0; i < n; i++) { scanf("%lld", &w[i]); } a[0] = w[0]; dfs1(-1, 0); N = 0; dfs2(-1, 0); st.Free(); st.Build(b, 0, N - 1, lazyfunc, mergefunc); printf("Case #%d:\n", q); for (int i = 0; i < m; i++) { scanf("%d", &o); if (o == 0) { scanf("%d%d", &u, &v); st.Modify(l[u], r[u], v - w[u]); w[u] = v; } else { scanf("%d", &u); printf("%lld\n", st.Query(l[u], r[u])); } } } return 0;}D game[HDU5693]
首先只用考虑长度为2和3的等差数列就可以了，因为更长的等差数列都可以拆成几个2和3的小等差数列。
用f[i][j]表示从i到j的字段能否全部消除，能全部消除的情况总共有3种模式
[#####][#####]
O[#####]O
O[#####]O[#####]O
其他都可以用这三种形式表示出来。
dp[i]表示从1到i最多消去的个数。dp[i] = max(dp[i],dp[j - 1] + i - j + 1)
错的原因：①在转移前，dp[i]的值应先设为dp[i-1]，因为第i个数字可能并不在任何一个等差数列中。②二维数组f[i][j]写成了f[i,j]，编译器不会报错，因为i,j也是个表达式，二维数组用一维的下标访问也没有问题，但算出来的结果肯定不对了。③使用位运算的时候要注意加括号，比如x&1==0，如果x<0，结果就会出错。感觉原因是这样的：-x&1==0，程序先判断了(1==0)得到一个false，再由这个false去&前面的-x。所以应该写成(x&1)==0。
#include <stdio.h>#include <string.h>#include <map>std::map<long long, bool> mp;long long a[305], d;int dp[305];bool f[305][305];int main() { int n, m, t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } mp.clear(); for (int i = 1; i <= m; i++) { scanf("%lld", &d); mp[d] = true; } memset(f, false, sizeof(f)); for (int i = 1; i <= n; i++) { f[i][i - 1] = true; } for (int j = 2; j <= n; j++) { for (int i = 1; i + j - 1 <= n; i++) { for (int k = i + 1; k < i + j - 1; k++) { if (f[i][k] && f[k + 1][i + j - 1]) { f[i][i + j - 1] = true; } } if (mp[a[i + j - 1] - a[i]] && f[i + 1][i + j - 2]) { f[i][i + j - 1] = true; } if (((a[i + j - 1] - a[i]) & 1) == 0 && mp[(a[i + j - 1] - a[i]) >> 1]) { for (int k = i + 1; k < i + j - 1; k++) { if ((a[k] << 1) == (a[i] + a[i + j - 1]) && f[i + 1][k - 1] && f[k + 1][i + j - 2]) { f[i][i + j - 1] = true; } } } } } memset(dp, 0, sizeof(dp)); for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1]; for (int j = 1; j < i; j++) { if (f[j][i] && dp[j - 1] + i - j + 1 > dp[i]) { dp[i] = dp[j - 1] + i - j + 1; } } } printf("%d\n", dp[n]); } return 0;}BD String[HDU5694]
解法肯定是b(r)-b(l-1)，只要能写出来b(x)函数就行。观察他的字符串构造，中间有一个b，右边的串是左边翻转加回文构成的，回文不改变bd的数量，翻转使bd数量交换，所以左右两边b和d的数量加起来是相等的，中间多一个b。另外S(n)的长度为2*S(n-1)+1=2^n-1。所以当x=2^n-1时，直接得到b(x)=(x/2)+1。对于一般情况，找到x长度介于S(n)和S(n+1)之间的n。只要用S(n+1)里的b的数量减去从第x+1位到S(n+1)末尾中的b的数量即可，而这一部分与字符串的开头同样长度的部分的关系是db数量交换，可以递归求解。
#include <stdio.h>#include <string.h>long long b(long long x) { if (x == 0) { return 0; } long long l = 1; while (l < x) { l = l * 2 + 1; } if (l == x) { return l / 2 + 1; } return (l / 2 + 1) - (l - x - b(l - x));}int main() { int t; long long l, r; scanf("%d", &t); while (t--) { scanf("%lld%lld", &l, &r); printf("%lld\n", b(r) - b(l - 1)); } return 0;}Gym Class[HDU5695]
拓扑排序，每次输出可行的同学中id最高的那个。
错的原因：每个同学要等到所有嫌弃他的同学都过了之后才能变成可行的。
#include <stdio.h>#include <string.h>#include <queue>std::priority_queue<int> q;int f[100005];int M;int head[100005];struct EDGE { int v, nex;} edge[100005];void addEdge(int a, int b) { edge[M].v = b; edge[M].nex = head[a]; head[a] = M++;}int main() { int n, m, t, a, b; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); memset(f, 0, sizeof(f)); M = 0; memset(head, -1, sizeof(head)); for (int i = 1; i <= m; i++) { scanf("%d%d", &a, &b); addEdge(a, b); f[b]++; } while (!q.empty()) { q.pop(); } for (int i = 1; i <= n; i++) { if (f[i] == 0) { q.push(i); } } long long ans = 0; int min = 0x7FFFFFFF; while (!q.empty()) { int x = q.top(); q.pop(); if (x < min) { min = x; } ans += min; for (int e = head[x]; e != -1; e = edge[e].nex) { f[edge[e].v]--; if (f[edge[e].v] == 0) { q.push(edge[e].v); } } } printf("%lld\n", ans); } return 0;}
2016"百度之星" - 初赛（Astar Round2A）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。