11.6NOIP模拟赛解题报告

心路历程

预计得分:\(100 + 100 + 100 = 300\)

实际得分:\(100 +100 +100 = 300\)

学OI两年终于AK了一次qwq(虽然题目炒鸡水。。)

纪念一下这令人激动的时刻。。

8点开始考,9:40就都拍上了。。可见题目确实水。。然后又去做了做另一套

Sol

T1

题目中给的两个数组没啥卵用,都是可以直接求的

然后离散化+树状数组就完了

#include<cstdio>
#include<algorithm>
#include<iostream>
#define lb(x) (x & (-x))
#define LL long long 
using namespace std;
const LL MAXN = 1e6 + 10;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
LL N, f[MAXN], g[MAXN], a[MAXN], mod;
LL add(LL x, LL y) {
    if(x + y < 0) return x + y + mod;
    return x + y >= mod ? x + y - mod : x + y;
}
LL mul(LL x, LL y) {
    return 1ll * x * y % mod;
}
LL fp(LL a, LL p) {
    LL base = 1;
    while(p) {
        if(p & 1) base = mul(base, a); 
        a = mul(a, a); p >>= 1;
    }
    return base;
}
LL date[MAXN], num;
void Des() {
    sort(date + 1, date + num + 1);
    num = unique(date + 1, date + num + 1) - date - 1;
    for(LL i = 1; i <= N; i++) f[i] = lower_bound(date + 1, date + num + 1, f[i]) - date, 
                                g[i] = lower_bound(date + 1, date + num + 1, g[i]) - date;
}
LL T[MAXN];
void Add(LL x, LL val) {
    while(x <= num) T[x] += val, x += lb(x);
}
LL Query(LL x) {
    LL ans = 0;
    while(x) ans += T[x], x -= lb(x);
    return ans;
}
int main() { 
    freopen("calc.in", "r", stdin);
    freopen("calc.out", "w", stdout);
    N = read(); mod = read();
    for(LL i = 1; i <= N; i++) a[i] = read(), f[i] = fp(i, a[i]), g[i] = fp(a[i], i), 
                                               date[++num] = f[i], date[++num] = g[i];
    Des();
    LL ans = 0;
    for(LL i = N; i >= 1; i--) {
        ans += Query(f[i] - 1);
        Add(g[i], 1);
    }
    cout << ans;
    return 0;
}

T2

这题比较interesting啊。

我是先做的T3再回来做的T2

首先二分答案

很显然的一个贪心是从左往右扫,如果遇到一个不合法的点\(i\),那么升级\(i + R\)处的炮台。。

和暴力拍了10000多组没错误。。赢了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define LL long long 
using namespace std;
const LL MAXN = 2e6;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
LL N, R;
LL  tag[MAXN], s[MAXN], a[MAXN], b[MAXN], K;
bool check(LL val) {
    memset(tag, 0, sizeof(tag)); 
    LL now = 0, res = K, flag = 1;
    for(LL i = 1; i <= N; i++) {
        now += tag[i];
        a[i] += now;
        if(a[i] < val) now += val - a[i], tag[i + 2 * R + 1] -= val - a[i], res -= val - a[i];
        if(res < 0) {flag = 0; break;}
    }
    memcpy(a, b, sizeof(a));
    return flag;
}
LL Query(LL l, LL r) {
    r = min(r, N);
    if(l < 0) return s[r];
    return s[r] - s[l];
}
int main() {
    freopen("game.in", "r", stdin); freopen("game.out", "w", stdout);
    N = read(); R = read(); K = read();
    for(LL i = 1; i <= N; i++) a[i] = read(), s[i] = s[i - 1] + a[i]; 
    for(LL i = 1; i <= N; i++) a[i] = Query(i - R - 1, i + R);
    for(LL i = 1; i <= N; i++) b[i] = a[i];
    LL l = 0, r = 3e18, ans = 0;
    while(l <= r) {
        LL mid = (l + r) >> 1;
        if(check(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    cout << ans;
    return 0;
}

T3

出题人还能再套路一点么。。

首先把询问离线后从小到大排序

合并的时候用带权并查集维护一下

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define Pair pair<LL, LL>
#define MP make_pair
#define fi first
#define se second 
#define LL long long 
using namespace std;
const LL MAXN = 1e6 + 10, INF = 1e9 + 10;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
LL N, M, Q, cnt, fa[MAXN], w[MAXN], ans, out[MAXN];
struct Edge {
    LL u, v, w;
    bool operator < (const Edge &rhs) const {
        return w < rhs.w;
    }
}E[MAXN];
Pair q[MAXN];
LL find(LL x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
void AddEdge(LL i) {
    LL x = E[i].u, y = E[i].v, v = E[i].w;
    LL fx = find(x), fy = find(y);
    if(fx == fy) w[fx] += v, ans = max(ans, w[fx]);
    else {
        fa[fx] = fy; w[fy] += v + w[fx]; w[fx] = 0;
        ans = max(ans, w[fy]);
    }
}
int main() {
    freopen("graph.in", "r", stdin); freopen("graph.out", "w", stdout);
    N = read(); M = read(); Q = read();
    for(LL i = 1; i <= N; i++) fa[i] = i;
    for(LL i = 1; i <= M; i++) E[i].u = read(), E[i].v = read(), E[i].w = read();
    sort(E + 1, E + M + 1);
    for(LL i = 1; i <= Q; i++) q[i] = MP(read(), i);
    sort(q + 1, q + Q + 1);
    LL j = 1;
    for(LL i = 1; i <= Q; i++) {
        while(j <= M && E[j].w <= q[i].fi) 
            AddEdge(j++);
        out[q[i].se] = ans;
    }
    for(LL i = 1; i <= Q; i++) printf("%I64d\n", out[i]);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2017.5.13阶段模拟考试

预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

35660
来自专栏数据结构与算法

BZOJ3398: [Usaco2009 Feb]Bullcow 牡牛和牝牛(dp)

设$f[i]$表示到第$i$个位置,该位置放了牡牛的方案,$g[i]$表示到第$i$个位置,且该位置放了牝牛的方案数

7810
来自专栏owent

PKU POJ 2728 Desert King 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2728

8830
来自专栏数据结构与算法

各种数论模板 不断更新 绝对精品

1.筛法求素数 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #inclu...

35190
来自专栏数据结构与算法

codeforces1025

首先考虑一个很显然的区间dp, $f[l][r][root]$表示$(l, r)$区间内,以$root$为根是否可行

6710
来自专栏数据结构与算法

模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板

图论 最短路 SPFA 1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 using...

297110
来自专栏数据结构与算法

LOJ#2552. 「CTSC2018」假面(期望 背包)

转移的时候若要淦这个人,那么\(f[i][j] = (f[i - 1][j] + 1) * p + (f[i - 1][j]) * (1 - p)\)

15940
来自专栏数据结构与算法

洛谷P1351 联合权值(树形dp)

8820
来自专栏ACM小冰成长之路

POJ-3866-Exclusive Access 2

ACM模版 描述 ? ? ? 题解 这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。 简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执...

19680
来自专栏数据结构与算法

codevs 1664 清凉冷水

1664 清凉冷水 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description      ...

32380

扫码关注云+社区

领取腾讯云代金券