2023-11-11
T1【GDOI2017模拟7.19】小X调顺序
Problem Description
Input
Output
Sample Input Copy
3 1 2 2 1Sample Output Copy
1Data Constraint
求逆序对然后减去 \(k\) 即可，思维题。
#include <cstdio>
#include <algorithm>
#define ll long long
#define N 100010
using namespace std;
ll n, k;
ll a[N], b[N], ans;
void solve(ll l, ll r) {
if(l == r) return;
ll mid = (l + r) >> 1;
solve(l, mid);
solve(mid + 1, r);
ll pos1 = l, pos2 = mid+1;
for(ll i = l; i <= r; i++) {
if(pos1 > mid) {
b[i] = a[pos2++];
} else if(pos2 > r) {
b[i] = a[pos1++];
} else if(a[pos1] > a[pos2]) {
b[i] = a[pos1++];
ans += r - pos2 + 1;
} else {
b[i] = a[pos2++];
}
}
for(ll i = l; i <= r; i++) {
a[i] = b[i];
}
}
int main() {
scanf("%lld %lld", &n, &k);
for(ll i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
solve(1, n);
printf("%lld", max(ans - k, 0ll));
}
T2 【GDOI2017模拟7.19】小X捏彩泥
Problem Description
Input
Output
Sample Input Copy
5 6 2 8 7 1 0 5 2 10 20Sample Output Copy
10Data Constraint
这道题实际上安排时间不合理，打的时候只剩下10分钟了。
这题其实是一道dp，维护前后相等的值然后用： \(f[i]=\min(f[j]+合并前面的代价+合并后面的代价)\) 维护即可。
属于我赛时想不到，瞄一眼就会的题目了。自己dp水平太低了，需要加强！
#include <cstdio>
#include <algorithm>
#define ll long long
#define N 10010
using namespace std;
ll n, ans;
ll v[N], a[N];
ll cntl[N], cntr[N], cnt, xl, xr;
ll f[N];
int main() {
scanf("%lld", &n);
for(ll i = 1; i <= n; i++) {
scanf("%lld", &v[i]);
}
for(ll i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
ll l = 1, r = n;
while(l <= r) {
if(xl > xr) {
xr += v[r];
r--;
} else {
xl += v[l];
l++;
}
if(xl == xr) {
cntl[++cnt] = l - 1;
cntr[cnt] = r + 1;
}
}
cntr[0] = n+1;
ll ans = 1e15;
for(ll i = 1; i <= cnt; i++) {
f[i] = 1e15;
for(ll j = 0; j < i; j++) {
f[i] = min(f[i], a[cntl[i] - cntl[j]] + f[j] + a[cntr[j] - cntr[i]]);
}
ans = min(ans, f[i] + a[(cntr[i]-1) - (cntl[i]+1) + 1]);
}
printf("%lld", min(ans, a[n]));
}
T3 【GDOI2017模拟7.19】小X做实验
Problem Description
Input
Output
Sample Input Copy
5 5 D 5 5 Q 5 6 D 2 3 D 1 2 Q 1 7Sample Output Copy
2 3Data Constraint
之前在睡觉时想到一个题目，与别人交流了一下，大致是维护一个数列，实现插入数列、删除和查询功能。当时我自己想到的一个优秀解法是用线段树维护一个点表示一个数列，把数列上的下表转换为线段树的下标，是通过在线段树上二分求解得到的，时间复杂度：\(O(n\log^2n)\) 的，当时自己打了一个发现可以过 \(1e6\)（洛谷ide）。
然后今天做这道题时发现和之前与别人讨论的题做法一模一样（另一种意义上的撞题），于是就打出来了，造了一个 \(1e5\) 的数据发现OJ上过不了，大概是因为OJ机子比较慢，被卡常了。
其实有更优秀的不需要二分的做法，类比搜索树的做法，效仿取第 \(k\) 大的操作模拟即可。
另外，后面在看题解的时候发现这道题很像CSPST3。自己的代码实现能力较好，但是思考能力比较差。
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
#define N 100010
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
ll n, m;
ll qpow(ll n, ll p) {
if(p == 0) return 1;
if(p % 2 == 1) return n*qpow(n, p-1);
ll tmp = qpow(n, p/2);
return tmp*tmp;
}
struct node {
ll mx, siz;
} t[4*N];
node add(node x, node y) {
x.mx = max(x.mx, y.mx);
x.siz += y.siz;
return x;
}
ll lazy[4*N]; // 翻了多少倍
void pushup(ll pos) {
t[pos].mx = max(t[ls(pos)].mx, t[rs(pos)].mx);
t[pos].siz = t[ls(pos)].siz + t[rs(pos)].siz;
}
void f(ll k, ll pos) {
t[pos].mx *= qpow(2, k);
t[pos].siz *= qpow(2, k);
lazy[pos] += k;
}
void pushdown(ll pos) {
f(lazy[pos], ls(pos));
f(lazy[pos], rs(pos));
lazy[pos] = 0;
}
void build(ll l, ll r, ll pos) {
if(l == r) {
t[pos].mx = t[pos].siz = 1;
return;
}
ll mid = (l + r) >> 1;
build(l, mid, ls(pos));
build(mid + 1, r, rs(pos));
pushup(pos);
}
void update(ll nl, ll nr, ll l, ll r, ll pos) {
if(nl <= l && r <= nr) {
t[pos].mx *= 2;
t[pos].siz *= 2;
lazy[pos]++;
return;
}
pushdown(pos);
ll mid = (l + r) >> 1;
if(nl <= mid)
update(nl, nr, l, mid, ls(pos));
if(mid < nr)
update(nl, nr, mid + 1, r, rs(pos));
pushup(pos);
}
void updateone(ll x, ll l, ll r, ll pos, ll k) {
if(x <= l && r <= x) {
t[pos].mx += k;
t[pos].siz += k;
return;
}
pushdown(pos);
ll mid = (l + r) >> 1;
if(x <= mid)
updateone(x, l, mid, ls(pos), k);
if(mid < x)
updateone(x, mid + 1, r, rs(pos), k);
pushup(pos);
}
node query(ll nl, ll nr, ll l, ll r, ll pos) {
if(nl > nr) return node({0, 0});
if(nl <= l && r <= nr) {
return t[pos];
}
pushdown(pos);
ll mid = (l + r) >> 1;
node res;res.mx = 0, res.siz = 0;
if(nl <= mid)
res = add(res, query(nl, nr, l, mid, ls(pos)));
if(mid < nr)
res = add(res, query(nl, nr, mid + 1, r, rs(pos)));
return res;
}
ll gt(ll x, ll l, ll r, ll pos) {
if(l == r) {
return l;
}
pushdown(pos);
ll mid = (l + r) >> 1;
if(x <= t[ls(pos)].siz)
return gt(x, l, mid, ls(pos));
else
return gt(x - t[ls(pos)].siz, mid + 1, r, rs(pos));
}
int main() {
// freopen("C://experiment4.in", "r", stdin);
scanf("%lld %lld", &n, &m);
build(1, n, 1);
while(m--) {
char op[10];
ll l, r;
scanf("%s %lld %lld", op, &l, &r);
if(op[0] == 'D') {
ll st = gt(l, 1, n, 1), ed = gt(r, 1, n, 1);
if(l > query(1, st - 1, 1, n, 1).siz + 1) st++;
if(query(1, ed, 1, n, 1).siz > r) ed--;
// printf("Debug:%lld %lld\n", st, ed);
// st的起点 - 查询的起点 = 多算的点数 查询的终点 - ed的终点 = 多算的点数
ll a = (query(1, st - 1, 1, n, 1).siz + 1) - l, b = r - (query(1, ed, 1, n, 1).siz);
if(st <= ed) update(st, ed, 1, n, 1);
if(st - 1 == ed + 1) updateone(st - 1, 1, n, 1, r-l+1); // 是同一个，但我不知道怎么修，直接特判吧
else {
if(st - 1 >= 1) updateone(st - 1, 1, n, 1, a);
if(ed + 1 <= n) updateone(ed + 1, 1, n, 1, b);
}
} else if(op[0] == 'Q') {
ll st = gt(l, 1, n, 1), ed = gt(r, 1, n, 1);
if(l > query(1, st - 1, 1, n, 1).siz + 1) st++;
if(query(1, ed, 1, n, 1).siz > r) ed--;
// printf("Debug:%lld %lld\n", st, ed);
ll a = (query(1, st - 1, 1, n, 1).siz + 1) - l, b = r - (query(1, ed, 1, n, 1).siz);
ll ans = query(st, ed, 1, n, 1).mx;
if(st - 1 == ed + 1) ans = max(ans, r - l + 1); // 是同一个，但我不知道怎么修，直接特判吧
else {
ans = max(ans, a);
ans = max(ans, b);
}
printf("%lld\n", ans);
}
// for(ll i = 1; i <= n; i++) {
// printf("%lld ", query(i, i, 1, n, 1).siz);
// }
// printf("\n");
}
}
T4 【GDOI2017模拟7.19】区间集合
Problem Description
Input
Output
Sample Input Copy
输入1： 10 20 5 输入2： 10 20 3Sample Output Copy
输出1： 9 输出2： 7Data Constraint
因为 \(A\)、\(B\) 差为 \(1e6\)，所以可以直接暴力维护，并查集即可。其实考试时想到了，但是以为时间复杂度很大……
因为质数 \(p\) 至多联向 \(\frac{n}{p}\) 个数（\(n=b-a+1\)）。然后有：
\[\begin{aligned} \frac{n}{2}+\frac{n}{3}+\frac{n}{5}+\frac{n}{7}+\cdots+\frac{n}{n} &= n(\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\cdots+\frac{1}{n}) \\ &≈ ne \end{aligned} \]所以可以通过。
#include <cstdio>
#define ll long long
#define N 1000010
ll a, b, p;
ll flag[N];
ll prime[N], cnt;
ll fa[N];
ll v[N];
void init() {
for(ll i = 2; i <= 1000000; i++) {
if(flag[i] == 0) {
prime[++cnt] = i;
}
for(ll j = 1; j <= cnt && prime[j] * i <= 1000000; j++) {
flag[prime[j] * i] = 1;
if(prime[j] % i == 0) break;
}
}
}
ll find(ll x) {
if(x ==fa[x]) return x;
return fa[x] = find(fa[x]);
}
int main() {
scanf("%lld %lld %lld", &a, &b, &p);
init();
for(ll i = a; i <= b; i++) fa[i - a] = i - a;
for(ll i = 1; i <= cnt; i++) if(prime[i] >= p){
ll st = 0;
for(ll j = a / prime[i] * prime[i]; j <= b; j += prime[i]) {
if(j < a) continue;
if(!st) {
st = j;
continue;
}
fa[find(j - a)] = find(st - a);
}
}
ll ans = 0;
for(ll i = a; i <= b; i++) {
if(!v[find(i-a)]) {
v[fa[i-a]] = 1;
ans++;
}
// printf("%lld ", fa[i-a] + a);
}
printf("%lld", ans);
}