solved 7/11
2016 Multi-University Training Contest 10
分类讨论 1001 Median(BH)
题意:
有长度为n排好序的序列,给两段子序列[l1,r1],[l2,r2]构成新的序列,问中间的数字。
思路:
根据不同情况分类讨论即可。时间复杂度O(1)。
代码:
#include <bits/stdc++.h> const int N = 1e5 + 5; int a[N]; int n, m; int l1, r1, l2, r2; int L1, L2, L; int odd; double find3(int pos) { int x = r2 - l2 + 1; int d1 = l2 - l1; int d2 = r1 - r2; int id = 0; double ret; if (pos <= d1) { id = l1 + pos - 1; ret = a[id]; if (!odd) { ret = (ret + a[id+1]) / 2.0; } } else if (pos <= d1 + 2 * x) { id = l2 + (pos - d1 - 1) / 2; ret = a[id]; if (!odd) { if ((pos-d1) % 2 == 0) ret = (ret + a[id+1]) / 2.0; } } else { id = l1 + (pos - x) - 1; ret = a[id]; if (!odd) ret = (ret + a[id+1]) / 2.0; } return ret; } double find2(int pos) { int x = r1 - l2 + 1; int d1 = l2 - l1; int d2 = r2 - r1; int id = 0; double ret; if (pos <= d1) { id = l1 + pos - 1; ret = a[id]; if (!odd) { ret = (ret + a[id+1]) / 2.0; } } else if (pos <= d1 + 2 * x) { id = l2 + (pos - d1 - 1) / 2; ret = a[id]; if (!odd) { if ((pos-d1) % 2 == 0) ret = (ret + a[id+1]) / 2.0; } } else { id = l1 + (pos - x) - 1; ret = a[id]; if (!odd) ret = (ret + a[id+1]) / 2.0; } return ret; } double find(int pos) { int id = 0; double ret; if (pos <= L1) { id = l1 + pos - 1; ret = a[id]; if (!odd) { if (id + 1 > r1) ret = (ret + a[l2]) / 2.0; else ret = (ret + a[id+1]) / 2.0; } } else { id = l2 + (pos - L1) - 1; ret = a[id]; if (!odd) { ret = (ret + a[id+1]) / 2.0; } } return ret; } int main() { int T; scanf ("%d", &T); while (T--) { scanf ("%d%d", &n, &m); for (int i=1; i<=n; ++i) scanf ("%d", a+i); while (m--) { scanf ("%d%d%d%d", &l1, &r1, &l2, &r2); if (l1 > l2) { std::swap (l1, l2); std::swap (r1, r2); } L1 = r1 - l1 + 1; L2 = r2 - l2 + 1; L = L1 + L2; int mid = (L + 1) / 2; odd = L & 1 ? 1 : 0; double ans = 0; if (r1 < l2) { ans = find (mid); } else if (r1 <= r2) { ans = find2 (mid); } else { ans = find3 (mid); } printf ("%.1f ", ans); } } return 0; }
数学 1002 Hard problem(CYD)
递推(约瑟夫环变形) 1004 Death Sequence(BH)
题意:
n个人排成一排,第一次:第1个人,第1+k个人,第1+2k个人。。。出队(枪毙);第二次剩下的人里第1个人,第1+k个人。。。出队。例子:1 2 3 4 5 6 7-> (1 3 5 7)(2 6)(4)。q次询问,每次问n个人出队后构成新的序列中第x个人。
思路:
pair类型a[i]储存第i个数字是第几次出队的以及这个数字i。那么有递推式子:;。前者的意思我想了想应该是i这个人在第x次第y个人出队,他和(i-(i-1)%k-1)这个人在第x-1次第y个人出队的命运类似,怎么推出来的呢,减去的是i前面有多少个在第1次出队的人数。然后只要sort一下,O(1)询问即可。
代码:
#include <bits/stdc++.h> const int N = 3e6 + 5; std::pair<int, int> a[N]; int ans[N]; int main() { int T; scanf ("%d", &T); while (T--) { int n, k, q; scanf ("%d%d%d", &n, &k, &q); for (int i=1; i<=n; ++i) { if ((i-1) % k == 0) a[i].first = 1; else a[i].first = a[i-(i-1)/k-1].first + 1; a[i].second = i; } std::sort (a+1, a+1+n); while (q--) { int id; scanf ("%d", &id); printf ("%d ", a[id].second); } } return 0; }
线段树 1005 Road(BH)
代码:
#include <bits/stdc++.h> typedef long long ll; const int N = 2e5 + 5; const int INF = 0x3f3f3f3f; int a[N]; int n, m; #define lch o << 1 #define rch o << 1 | 1 int mn[N<<2], mx[N<<2]; int sum[N<<2]; void push_down(int o) { if (mn[o] != INF) { mn[lch] = std::min (mn[lch], mn[o]); mx[lch] = std::max (mx[lch], mx[o]); mn[rch] = std::min (mn[rch], mn[o]); mx[rch] = std::max (mx[rch], mx[o]); } } void build(int o, int l, int r) { mn[o] = INF; mx[o] = 0; sum[o] = 0; if (l == r) return ; int mid = l + r >> 1; build (lch, l, mid); build (rch, mid+1, r); } void modify(int o, int l, int r, int ql, int qr, int tim) { if (ql <= l && r <= qr) { mn[o] = std::min (mn[o], tim); mx[o] = std::max (mx[o], tim); return ; } push_down (o); int mid = l + r >> 1; if (ql <= mid) modify (lch, l, mid, ql, qr, tim); if (qr > mid) modify (rch, mid+1, r, ql, qr, tim); } void push_up(int o) { sum[o] = sum[lch] + sum[rch]; } void modify2(int o, int l, int r, int pos, int v) { if (l == r) { sum[o] += v; return ; } int mid = l + r >> 1; if (pos <= mid) modify2 (lch, l, mid, pos, v); else modify2 (rch, mid+1, r, pos, v); push_up (o); } struct Data { int t, p, f; bool operator < (const Data &rhs) const { return t < rhs.t; } }data[N<<1]; int tot; void query(int o, int l, int r) { if (l == r) { if (mn[o] != INF) { data[tot++] = {mn[o], l, 1}; data[tot++] = {mx[o]+1, l, -1}; } return ; } push_down (o); int mid = l + r >> 1; query (lch, l, mid); query (rch, mid+1, r); } int l[N], r[N]; int main() { while (scanf ("%d%d", &n, &m) == 2) { n--; for (int i=1; i<=n; ++i) { scanf ("%d", &a[i]); } build (1, 1, n); for (int i=1; i<=m; ++i) { scanf ("%d%d", &l[i], &r[i]); if (l[i] > r[i]) std::swap (l[i], r[i]); r[i]--; modify (1, 1, n, l[i], r[i], i); } tot = 0; query (1, 1, n); std::sort (data, data+tot); int i = 0; for (int day=1; day<=m; ++day) { while (i<tot && data[i].t<=day) { modify2 (1, 1, n, data[i].p, a[data[i].p]*data[i].f); i++; } printf ("%d ", sum[1]); } } return 0; }
线段树(线段涂色)1006 Counting Intersections(BH)
题意:
有n条与坐标轴平行的线段,问横竖交叉点的个数。
思路:
读完题目后能看出这题应该是数据结构题。如下图所示,也就是求所有蓝线和红线交点的个数。红线涂色,蓝线询问,按照x坐标排序,线段树询问y区间红线的当前x上条数。线段[x1,x2]都是可以相交的,我在x1的位置+1,代表插入这条线段,x2+1的位置-1,这条线段就没有了。时间复杂度O(nlogn)。
这题思路+代码完成没有困难,可是比赛时出现两个失误:1. 数组开小了+数据结构使用不当(树状数组才过)T了好久;2. 数据范围估计出错了,原来要long long,1e5的数据,极限的测试数据:5e4的横线和5e4的竖线全部相交,5e4*5e4=25亿,超了int一点点。一定要注意这两个个问题。
代码:
#include <bits/stdc++.h> const int N = 1e5 + 5; struct Fenwick_Tree { int C[N<<1], n; void init(int n) { memset (C, 0, sizeof (C)); this->n = n; } void modify(int i, int v) { for (; i<=n; i+=i&(-i)) C[i] += v; } int query(int i) { int ret = 0; for (; i; i-=i&(-i)) ret += C[i]; return ret; } int query(int ql, int qr) { return query (qr) - query (ql-1); } }bit; struct Point { int x, y, c; bool operator < (const Point &rhs) const { return x < rhs.x; } }p[N<<1]; struct Query { int x, y1, y2; bool operator < (const Query &rhs) const { return x < rhs.x; } }q[N]; int Y[N<<1]; int xm, ym; int n, pm, qm; int get_y(int y) { return std::lower_bound (Y, Y+ym, y) - Y + 1; } long long solve() { std::sort (Y, Y+ym); ym = std::unique (Y, Y+ym) - Y; std::sort (p, p+pm); std::sort (q, q+qm); if (qm == 0 || pm == 0) return 0; bit.init (ym); long long ret = 0; int i = 0, j = 0; int qx = q[0].x; while (i < pm) { int tx = p[i].x; int ty = get_y (p[i].y); if (tx <= qx) { bit.modify (ty, p[i].c); i++; } else { int qy1 = get_y (q[j].y1); int qy2 = get_y (q[j].y2); ret += bit.query (qy1, qy2); j++; if (j == qm) break; qx = q[j].x; } } return ret; } int main() { int T; scanf ("%d", &T); while (T--) { scanf ("%d", &n); pm = qm = 0; xm = ym = 0; int x1, y1, x2, y2; for (int i=0; i<n; ++i) { scanf ("%d%d%d%d", &x1, &y1, &x2, &y2); if (y1 == y2) { if (x1 > x2) std::swap (x1, x2); p[pm++] = {x1, y1, 1}; p[pm++] = {x2+1, y2, -1}; Y[ym++] = y1; } else { if (y1 > y2) std::swap (y1, y2); q[qm++] = {x1, y1, y2}; Y[ym++] = y1; Y[ym++] = y2; } } printf ("%I64d ", solve ()); } return 0; }
DP+矩阵快速幂 1007 cjj's string game(BH)
代码:
#include <bits/stdc++.h> typedef long long ll; const int MOD = 1000000007; const int N = 15; struct Matrix { int row, col; int arr[N][N]; Matrix(int r=0, int c=0) { row = r; col = c; memset (arr, 0, sizeof (arr)); } Matrix operator * (const Matrix &B) { Matrix ret(row, B.col); for (int i=0; i<row; ++i) { for (int j=0; j<B.col; ++j) { for (int k=0; k<col; ++k) { ret.arr[i][j] = (ret.arr[i][j] + (ll) arr[i][k] * B.arr[k][j]) % MOD; } } } return ret; } void unit(int n) { row = col = n; for (int i=0; i<n; ++i) { arr[i][i] = 1; } } }; Matrix operator ^ (Matrix X, int n) { Matrix ret; ret.unit (X.col); while (n) { if (n & 1) { ret = ret * X; } X = X * X; n >>= 1; } return ret; } int main() { int T; scanf ("%d", &T); while (T--) { int n, m, k; scanf ("%d%d%d", &n, &m, &k); Matrix x (m+1, m+1); for (int i=0; i<=m; ++i) { x.arr[i][0] = k * k - k; if (i < m) x.arr[i][i+1] = k; } x = x ^ n; int ans = 0; for (int i=0; i<=m; ++i) { ans = (ans + x.arr[0][i]) % MOD; } Matrix y (m, m); for (int i=0; i<m; ++i) { y.arr[i][0] = k * k - k; if (i < m - 1) y.arr[i][i+1] = k; } y = y ^ n; for (int i=0; i<m; ++i) { ans = (ans - y.arr[0][i] + MOD) % MOD; } printf ("%d ", ans); } return 0; }
模拟 1011 Water problem(CYD)