联赛前第九阶段总结 联赛模拟测试31 联赛模拟测试30 上午小测6 联赛模拟测试29(lrd day2) 上午小测5 联赛模拟测试28(lrd day1) 上午小测4
A 异或
- 求出来每一位l到r每个数的0和1的个数，乘起来再乘这个位的值乘2加起来就是答案
Show Code
#include <cstdio>
#include <algorithm>
const int M = 1e9 + 7;
int T;
int main() {
freopen("xor.in", "r", stdin);
freopen("xor.out", "w", stdout);
scanf("%d", &T);
while (T--) {
int l, r, ans = 0;
scanf("%d%d", &l, &r);
l, r++;
for (int i = 1; i < r; i <<= 1) {
int s = r / (i << 1) * i + std::max(r % (i << 1) - i, 0);
s -= l / (i << 1) * i + std::max(l % (i << 1) - i, 0);
if ((ans += 1LL * s * (r - l - s) % M * i % M) >= M) ans -= M;
}
printf("%d
", ans * 2 % M);
}
return 0;
}
B 取石子 (Unaccepted)
- 大力puts("Yes"),10分到手
C 优化 (Unaccepted)
- 瞎写了个DP，样例都过不去，0分
D 计数 (Unaccepted)
- 拿了M=0的20分，暴搜好像打挂了
联赛模拟测试30
阶段排名 10
A maze
- 想出来是s关于k是单增的了，但当时只想这个函数怎么求，没想到二分，就写了10分
Show Code
#include <queue>
#include <cstdio>
const int N = 105;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
struct Edge {
int next, t; bool d;
}e[N*N<<2];
int head[N*N], edc;
void Add(int x, int y, bool d) {
e[++edc] = (Edge) {head[x], y, d};
head[x] = edc;
}
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int n, m, h[N][N], hc, s, t;
bool a[N][N], v[N*N];
double sd, d[N*N];
double Dij(double mid) {
std::priority_queue< std::pair<double, int> > q;
for (int i = 1; i <= n * m; ++i)
d[i] = 1e9, v[i] = 0;
q.push(std::make_pair(d[s] = 0, s));
while (!q.empty()) {
int x = q.top().second; q.pop();
if (x == t) return d[x];
if (v[x]) continue;
v[x] = 1;
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].t;
double dis = e[i].d ? 1 : mid;
if (d[y] > d[x] + dis) {
d[y] = d[x] + dis;
q.push(std::make_pair(-d[y], y));
}
}
}
}
int main() {
freopen("maze.in", "r", stdin);
freopen("maze.out", "w", stdout);
n = read(); m = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
h[i][j] = ++hc;
s = read(); s = h[s][read()];
t = read(); t = h[t][read()];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
a[i][j] = read();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j]) continue;
for (int k = 0; k < 4; ++k) {
int x = i + dx[k], y = j + dy[k];
if (x < 1 || x > n || y < 1 || y > m || a[i][j]) continue;
Add(h[i][j], h[x][y], k < 2);
}
}
}
scanf("%lf", &sd);
double l = 0, r = sd;
while (r - l > 1e-5) {
double mid = (l + r) / 2;
if (Dij(mid) >= sd) r = mid;
else l = mid;
}
printf("%.3lf
", l);
return 0;
}
B bird
-
写了个n^3暴力拿了50分
-
题目中说鸟每秒向负方向移动一个单位，但是鸟太多了，不好处理，所以就让人每秒向正方向移动一个单位
-
f[i]表示最后一枪打到i位置最多能打到多少只鸟，显然是要从i-k之前的找最大值转移，但是这道题一只鸟可能会很长，但一只鸟又不能算两次，我考场就写了个bitset判断
-
考虑将鸟都算在最后一枪上，前面的都不算当前可以打的到的鸟，当一只鸟在i位置打不到就可以对后面的做贡献，就加进去
-
所以维护一颗支持区间加，区间查询最大值的线段树即可，每个叶子节点是f[i]-i位置可以打的到的鸟
Show Code
#include <cstdio>
#include <vector>
#define ls (rt << 1)
#define rs (rt << 1 | 1)
const int N = 5e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
std::vector<int> a[N];
int n, k, m, s[N], ans, t[N<<2], tag[N<<2];
void Pushdown(int rt) {
t[ls] += tag[rt]; tag[ls] += tag[rt];
t[rs] += tag[rt]; tag[rs] += tag[rt];
tag[rt] = 0;
}
void Change(int rt, int l, int r, int x, int y, int w) {
if (x <= l && r <= y) return t[rt] += w, tag[rt] += w, void();
if (tag[rt]) Pushdown(rt);
int mid = l + r >> 1;
if (x <= mid) Change(ls, l, mid, x, y, w);
if (y > mid) Change(rs, mid + 1, r, x, y, w);
t[rt] = std::max(t[ls], t[rs]);
}
int Ask(int rt, int l, int r, int x, int y) {
if (x <= l && r <= y) return t[rt];
if (tag[rt]) Pushdown(rt);
int mid = l + r >> 1, ans = 0;
if (x <= mid) ans = Ask(ls, l, mid, x, y);
if (y > mid) ans = std::max(ans, Ask(rs, mid + 1, r, x, y));
return ans;
}
int main() {
freopen("bird.in", "r", stdin);
freopen("bird.out", "w", stdout);
m = read(); k = read();
while (m--) {
int l = std::max(0, read()) + 1, r = read() + 1;
if (r < 1) continue;
if (r > n) n = r;
s[l]++, s[r+1]--;
a[r].push_back(l);
}
for (int i = 1; i <= n; ++i) {
s[i] += s[i-1];
int f = i > k ? Ask(1, 1, n, 1, i - k) : 0;
Change(1, 1, n, i, i, f);
if ((f += s[i]) > ans) ans = f;
for (int j = 0; j < a[i].size(); ++j)
Change(1, 1, n, a[i][j], i, 1);
}
printf("%d
", ans);
return 0;
}
C stone (Unaccepted)
- 30分暴力数组开小拿了20
D 椎 (Unaccepted)
- 写了个Treap，过了样例，但前一半WA，后一半RE
上午小测6
阶段排名 7
A 大新闻
-
打出nm暴力之后就考虑怎么优化
-
求第k大肯定是套什么数据结构了，我知道的就权值线段树可以，好像还有什么平衡树，可是我太菜了
-
插入删除得把整个数组左右移动，但是一个很好的性质就是都是在开头进行处理，那把序列反过来，每次在结尾处理不就好了吗
-
问题就转换成在序列最后加入或删除一个数，然后就区间第k小，
-
动态区间第k小不久是主席树板子么，就多了一个删除，删除就直接n--就没事了
-
需要注意区间被倒过来了，查询k小的区间就不是[l,r]，而是[n-r+1, n-l+1]
Show Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls(x) t[x].l
#define rs(x) t[x].r
const int N = 4e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
struct tree {
int s, l, r;
}t[N*31];
int n, m, a[N], root[N], trc;
void Change(int &rt, int l, int r, int x) {
t[++trc] = t[rt]; rt = trc;
t[rt].s++;
if (l == r) return;
int mid = l + r >> 1;
if (x <= mid) Change(ls(rt), l, mid, x);
else Change(rs(rt), mid + 1, r, x);
}
int Ask(int lrt, int rrt, int l, int r, int k) {
if (l == r) return l;
int mid = l + r >> 1, s = t[ls(rrt)].s - t[ls(lrt)].s;
if (k <= s) return Ask(ls(lrt), ls(rrt), l, mid, k);
else return Ask(rs(lrt), rs(rrt), mid + 1, r, k - s);
}
int main() {
freopen("news.in", "r", stdin);
freopen("news.out", "w", stdout);
n = read(), m = read();
for (int i = n; i >= 1; --i)
a[i] = read();
for (int i = 1; i <= n; ++i)
Change(root[i] = root[i-1], 1, 1e9, a[i]);
while (m--) {
int od = read();
if (od == 1) n--;
else if (od == 2) n++, Change(root[n] = root[n-1], 1, 1e9, read());
else {
int r = n - read() + 1, l = n - read() + 1, k = read();
printf("%d
", Ask(root[l-1], root[r], 1, 1e9, k));
}
}
return 0;
}
B King's Inspection (Unaccepted)
- 暴力直接94
联赛模拟测试29(lrd day2)
阶段排名 10
A 串串香
-
最后检查的时候还在纠结要不要define int long long，后来没改，结果28行n乘的时候炸成90分了
-
前缀和后缀相等就转换成循环节问题，本来就有长度为m的循环节，然后让循环节尽可能小，就在m里再找循环节
Show Code
#include <cstdio>
typedef unsigned long long ull;
const int N = 1e6 + 5;
ull h[N], p[N];
long long ans, n, m;
int T;
char c[N];
ull Ask(int l, int r) {
return h[r] - h[l-1] * p[r-l+1];
}
int main() {
freopen("ccx.in", "r", stdin);
freopen("ccx.out", "w", stdout);
scanf("%d", &T);
p[0] = 1;
for (int i = 1; i < N; ++i)
p[i] = p[i-1] * 233;
while (T--) {
scanf("%lld%lld%s", &n, &m, c + 1);
for (int i = 1; i <= m; ++i)
h[i] = h[i-1] * 233 + c[i];
for (int i = 1; i * 2 <= m; ++i) {
if (m % i) continue;
if (Ask(1, m - i) == Ask(1 + i, m)) {
n *= m / i; m = i;
break;
}
}
ans = (n - 1) * m;
if (!ans) {
ans = -1;
for (int i = 1; i < m; ++i)
if (Ask(1, i) == Ask(m - i + 1, m))
ans = i;
}
printf("%lld
", ans);
}
return 0;
}
B 糊涂图 (Unaccepted)
- 概率跳过
C 木叶下 (Unaccepted)
- 瞎打部分分拿35
D Tiny Counting
-
离散化后二分查找a[i]的时候把范围1～m写成1～n了，就暴成70分了
-
树状数组求出每个点前面大的，小的，后面大的，小的
-
先不考虑ab和cd有重复，那就是正序对数乘逆序对数
-
当a=c,a=d,b=c,b=d的时候这样会有重复，就把这几种情况减去就可以了
Show Code
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 1e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9';c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int n, m, a[N], b[N], b1[N], b2, s1[N], s2, tb[N], ts[N];
long long sb, ss, ans;
void Addb(int x) {
for (; x; x -= x & -x)
tb[x]++;
}
int Askb(int x, int ans = 0) {
for (; x <= m; x += x & -x)
ans += tb[x];
return ans;
}
void Adds(int x) {
for (; x <= m; x += x & -x)
ts[x]++;
}
int Asks(int x, int ans = 0) {
for (; x; x -= x & -x)
ans += ts[x];
return ans;
}
signed main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
n = read();
for (int i = 1; i <= n; ++i)
a[i] = b[i] = read();
std::sort(b + 1, b + n + 1);
m = std::unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i)
a[i] = std::lower_bound(b + 1, b + m + 1, a[i]) - b;
for (int i = 1; i <= n; ++i) {
b1[i] = Askb(a[i] + 1); Addb(a[i]);
s1[i] = Asks(a[i] - 1); Adds(a[i]);
sb += b1[i];
ss += s1[i];
ans -= 1LL * b1[i] * s1[i];
}
ans += sb * ss;
memset(tb, 0, sizeof(tb));
memset(ts, 0, sizeof(ts));
for (int i = n; i >= 1; --i) {
b2 = Askb(a[i] + 1); Addb(a[i]);
s2 = Asks(a[i] - 1); Adds(a[i]);
ans -= 1LL * b2 * s2 + 1LL * b1[i] * b2 + 1LL * s1[i] * s2;
}
printf("%lld
", ans);
return 0;
}
上午小测5
阶段排名 9
A 砍树
-
考场上写的二分，后来发现没有单调性，就写了个40分暴力，不过暴力和二分一个分
-
说实话并没有搞懂
-
问题等价于求一个最大的d,满足
[sum_{i=1}^{n}( left lceil frac{a_i}{d}
ight
ceil-a_i)leq k
]
- 移项整理，得
[dsum_{i=1}^{n}left lceil frac{a_i}{d}
ight
ceilleq k+sum_{i=1}^{n}a_i
]
- 注意到对于每个(a_i, left lceil a_i/d ight ceil),只有(sqrt{a_i})种不同的取值,因此 (sum_{i=1}^{n}left lceil a_i/d ight ceil) 只有(nsqrt{a_i})种不同的取值,在它的值确定之后,只需要简单的除法就可以求出d的最大值。因此把所有的不同的d的取值预处理出来排序,然后暴力计算,检验求出的d是否在这个取值所要求的d的范围内,并更新答案即可。
Show Code
#include <cstdio>
#include <algorithm>
typedef long long ll;
ll read(ll x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int n, m, a[105], b[32000000];
ll k, ans;
int main() {
freopen("cut.in", "r", stdin);
freopen("cut.out", "w", stdout);
n = read(); k = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
k += a[i];
for (int j = 1; j * j <= a[i]; ++j)
b[++m] = j, b[++m] = (a[i] - 1) / j + 1;
}
std::sort(b + 1, b + m + 1);
m = std::unique(b + 1, b + m + 1) - b - 1;
for (int i = 1; i <= m; ++i) {
ll x = 0;
for (int j = 1; j <= n; ++j)
x += (a[j] - 1) / b[i] + 1;
x = k / x;
if (x >= b[i]) ans = x;
}
printf("%lld
", ans);
return 0;
}
B 超级树 (Unaccepted)
- 暴搜拿了10分。
联赛模拟测试28(lrd day1)
阶段排名 9
A 位运算
- 考场上inf的判断挂掉了
& |
| |
^ |
组成情况 |
|---|---|---|---|
| 0 | 0 | 0 | 0 0 |
| 0 | 1 | 1 | 0 1 / 1 0 |
| 1 | 1 | 0 | 1 1 |
- 根据上表分类讨论一下就行了（下面是修改后的考场代码，懒得重写了）
Show Code
#include <cstdio>
typedef long long ll;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
ll cnt = 0;
ll Pow(ll a, ll k, ll ans = 1) {
for (; k; k >>= 1, a *= a)
if (k & 1) ans *= a;
return ans;
}
int main() {
freopen("bit.in", "r", stdin);
freopen("bit.out", "w", stdout);
int T = read();
while (T--) {
int a = read(), b = read(), c = read(), mi = a == -1 ? 0 : a; cnt = 0;
if (a != -1 && c != -1 && (a & c)) puts("0");
else if (b == -1 && (a == -1 || c == -1)) puts("inf");
else if ((a != -1 && (a | b) != b) || (c != -1 && (b | c) != b))
puts("0");
else if (a != -1 && c != -1) {
for (int i = 0; i < 30; ++i)
if (!(a & (1 << i)) && (c & (1 << i))) cnt++;
printf("%lld
", Pow(2, cnt));
}
else if (c != -1) {
for (int i = 0; i < 30; ++i) {
if (a != -1 && !(a & (1 << i)) && (b & (1 << i)) && !(c & (1 << i))) {
cnt = -1; break;
}
if ((b & (1 << i)) && (c & (1 << i))) cnt++;
}
printf("%lld
", cnt == -1 ? 0 : Pow(2, cnt));
}
else if (a != -1) {
for (int i = 0; i < 30; ++i)
if (!(a & (1 << i)) && (b & (1 << i))) cnt++;
printf("%lld
", Pow(2, cnt));
}
else if (a == -1 && c == -1) {
for (int x = b; x; x -= x & -x) cnt++;
printf("%lld
", Pow(3, cnt));
}
}
return 0;
}
B 集合论
- 开个桶，加减就用tag标记，取交集就修改0点模拟清空，挺好写的
Show Code
#include <cstdio>
const int N = 1.1e6;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int b[N+N+5], d, z, siz;
long long s;
int main() {
freopen("jihe.in", "r", stdin);
freopen("jihe.out", "w", stdout);
int n = read();
for (int i = 1; i <= n; ++i) {
int od = read();
if (od == 1) {
int m = read();
while (m--) {
int x = read();
if (b[x-d+N] <= z)
b[x-d+N] = i, s += x, siz++;
}
}
else if (od == 2) {
int m = read(); s = siz = 0;
while (m--) {
int x = read();
if (b[x-d+N] > z)
b[x-d+N] = i, s += x, siz++;
}
z = i - 1;
}
else if (od == 3) d++, s += siz;
else if (od == 4) d--, s -= siz;
printf("%lld
", s);
}
return 0;
}
C 连连看 (Unaccepted)
- 小数据暴力，k=0特判，拿了20分
D Huge Counting (Unaccepted)
- 一分暴力没取模，然后就爆0了
上午小测4
阶段排名 1
第二次AK！又是一道很难但数据极其水的题让我骗了100分
A Travel
- 考了一个半小时我才看出来，直接离线做，把边和询问按便权排序，双指针扫一遍，并查集维护加边
Show Code
#include <cstdio>
#include <algorithm>
const int N = 1e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
struct Edge {
int x, y, d;
bool operator < (const Edge &b) const {
return d < b.d;
}
}e[N<<1];
struct Node {
int x, w, id;
bool operator < (const Node &b) const {
return w < b.w;
}
}a[N];
int n, m, q, f[N], siz[N], ans[N];
int Find(int x) {
return x == f[x] ? x : (f[x] = Find(f[x]));
}
int main() {
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
n = read(); m = read(); q = read();
for (int i = 1; i <= n; ++i)
f[i] = i, siz[i] = 1;
for (int i = 1; i <= m; ++i)
e[i] = (Edge) {read(), read(), read()};
for (int i = 1; i <= q; ++i)
a[i] = (Node) {read(), read(), i};
std::sort(e + 1, e + m + 1);
std::sort(a + 1, a + q + 1);
for (int i = 1, j = 1; i <= q; ++i) {
for (; j <= m && e[j].d <= a[i].w; ++j) {
int x = Find(e[j].x), y = Find(e[j].y);
if (x == y) continue;
f[x] = y;
siz[y] += siz[x];
}
ans[a[i].id] = siz[Find(a[i].x)];
}
for (int i = 1; i <= q; ++i)
printf("%d
", ans[i]);
return 0;
}
B Balanced Diet (Unaccepted)
- 考场上就写了一个O(ans*n)的写法，由于数据太水A掉了，在darkbzoj上搞到数据评测后是78分