博弈 1002 ZYB's Game
题意:中文
分析:假定两个人是绝顶聪明的,一定会采取最优的策略.所以如果选择X的左边的一个点,那么后手应该选择X的右边对称的点,如果没有则必输,否则必胜,然后再分析下就是奇数是1,偶数是0
树状数组+二分(逆序数) 1003 ZYB's Premutation
题意:已知每个点前缀逆序对数和,求原排列
分析:可以得知每个点前面有几个比它大,那么用树状数组维护,二分查询从i到n有几个数字,那么答案是i-1
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = 5e4 + 5;
int A[N], B[N], a[N];
struct BIT {
int c[N], sz;
void init(int n) {
memset (c, 0, sizeof (c));
sz = n;
}
void updata(int i, int x) {
while (i <= sz) {
c[i] += x;
i += i & (-i);
}
}
int query(int i) {
int ret = 0;
while (i) {
ret += c[i];
i -= i & (-i);
}
return ret;
}
int bsearch(int l, int r, int k) {
int ret = 0, rr = r;
while (l <= r) {
int mid = (l + r) >> 1;
int cnt = query (rr) - query (mid);
if (cnt == k) {
ret = mid; r = mid - 1;
}
else if (cnt > k) l = mid + 1;
else r = mid - 1;
}
return ret;
}
}bit;
int n; int main(void) {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
for (int i=1; i<=n; ++i) {
scanf ("%d", &A[i]);
}
B[0] = 0;
for (int i=2; i<=n; ++i) {
B[i] = A[i] - A[i-1];
}
bit.init (n);
for (int i=1; i<=n; ++i) {
bit.updata (i, 1);
}
for (int i=n; i>=1; --i) {
a[i] = bit.bsearch (1, n, B[i]);
bit.updata (a[i], -1);
}
for (int i=1; i<=n; ++i) {
printf ("%d%c", a[i], i == n ? '\n' : ' ');
}
} return 0;
}
树形DP 1004 ZYB's Tree
题意:一棵树,求所有点它到其他点的距离不大于K的个数的异或和
分析:dp[u][i] 表示u到子孙的距离为i的点的个数,dp[u][i+1] += dp[v][i].dp2[v][i] 表示v到上面的距离为i的点的个数,dp[v][i+1] += dp2[u][i] + dp[u][i] - dp[v][i-1]
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = 5e4 + 5;
int A[N], B[N], a[N];
struct BIT {
int c[N], sz;
void init(int n) {
memset (c, 0, sizeof (c));
sz = n;
}
void updata(int i, int x) {
while (i <= sz) {
c[i] += x;
i += i & (-i);
}
}
int query(int i) {
int ret = 0;
while (i) {
ret += c[i];
i -= i & (-i);
}
return ret;
}
int bsearch(int l, int r, int k) {
int ret = 0, rr = r;
while (l <= r) {
int mid = (l + r) >> 1;
int cnt = query (rr) - query (mid);
if (cnt == k) {
ret = mid; r = mid - 1;
}
else if (cnt > k) l = mid + 1;
else r = mid - 1;
}
return ret;
}
}bit;
int n; int main(void) {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
for (int i=1; i<=n; ++i) {
scanf ("%d", &A[i]);
}
B[0] = 0;
for (int i=2; i<=n; ++i) {
B[i] = A[i] - A[i-1];
}
bit.init (n);
for (int i=1; i<=n; ++i) {
bit.updata (i, 1);
}
for (int i=n; i>=1; --i) {
a[i] = bit.bsearch (1, n, B[i]);
bit.updata (a[i], -1);
}
for (int i=1; i<=n; ++i) {
printf ("%d%c", a[i], i == n ? '\n' : ' ');
}
} return 0;
}