【总结】2019.5.11模拟赛

两道水题,一道毒瘤题,前两道切掉,最后一道打了$20$分暴力,起码比$5$分骗分多

T1

题目内容

刷数组
【问题描述】
羊神有一个长度为n的数组a(下标从 1 开始),初始均为 0。羊神需要进行
q次操作,每次可以:
1 x y表示:把a[x ] 的值修改为y。
2 x y表示:把a[x ] 的值修改为a [x ] + y。
(也就是增加了y)
3 y表示:把数组中所有元素全部修改为y。
进行每次操作以后,你需要输出数组中所有元素的和。
【输入格式】
输入文件为 array.in。
第一行为两个整数n q,以空格隔开。
接下来q行,每行格式为1 x y或2 x y或3 y。
【输出格式】
输出文件为 array.out。
输出q行,每行表示进行完当前操作后数组中所有元素的和。
【样例输入】
5
1
3
2
3
3 3
2
3 3
【样例输出】
3
10
13
【样例解释】
一开始的数组是 [0,0,0,0,0] 。
第一次操作以后,数组变成了 [0,0,3,0,0] 。
第二次操作以后,数组变成了 [2,2,2,2,2] 。
第三次操作以后,数组变成了 [2,2,5,2,2] 。
【数据规模和约定】
对于 10%的数据,n = 1, q ≤ 10。
对于 40%的数据,n ≤ 10,000, q ≤ 1,000。
对于 70%的数据,n ≤ 1,000,000, q ≤ 100,000。
对于 100%的数据, 1 ≤ x ≤ n ≤ 10,000,000,1 ≤ q ≤ 1,000,000,0 ≤ y ≤ 100。

程序实现

离线,根据操作三分段,然后对于每一段暴力修改查询,每次操作$O(1)$

我的代码

#pragma GCC optimize(3)
#include <cstdio>
#include <cctype>
#include <map>

using namespace std;

const int MAXN = 1e7 + 5;
const int MAXQ = 1e6 + 5;

inline char gc() {
    static char buf[1 << 16], *p1 = buf, *p2 = buf;
    if (p1 == p2) {
        p1 = buf;
        p2 = buf + fread(buf, 1, 1 << 16, stdin);
    }
    return p1 == p2 ? EOF : *p1++;
}

inline int read() {
    register int f = 1, x = 0; register char ch = gc();
    while (!isdigit(ch)) f = (ch == '-') ? -1 : f, ch = gc();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = gc();
    return f * x;
}

void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int n, q, sum[MAXQ], init[MAXQ];
struct Query{
    int op, x, y, id;
}qr[MAXQ];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    n = read(); q = read();
    int cnt = 1;
    for (int i = 1; i <= q; i++) {//分段 
        qr[i].op = read();
        if (qr[i].op <= 2) {
            qr[i].x = read(); qr[i].y = read();
            qr[i].id = cnt;
        } else {
            qr[i].y = read();
            cnt++;
            qr[i].id = cnt;
            sum[cnt] = qr[i].y * n;
            init[cnt] = qr[i].y;
        }
    }
    map<int, bool> m1[cnt + 1]; //是否被修改过 
    map<int, int> m2[cnt + 1]; //当前值 
    for (int i = 1; i <= q; i++) {
        int id = qr[i].id, x = qr[i].x, y = qr[i].y;
        if (qr[i].op == 1) {
            int pre = m1[id][x] ? m2[id][x] : init[id];
            sum[id] += y - pre;
            m2[id][x] = y;
            m1[id][x] = true;
            write(sum[id]); putchar('\n');
        } else if (qr[i].op == 2) {
            sum[id] += y;
            m2[id][x] += y;
            m1[id][x] = true;
            write(sum[id]); putchar('\n');
        } else {
            write(sum[id]); putchar('\n');
        }
    }
    return 0;
}

T2

题目内容

LCA 的统计
【问题描述】
想必你一定知道什么叫做“二叉树”
。二叉树是一种有根树,每个节点有左
右两个子节点,每个子节点要么为空,要么也是二叉树。此外,每个节点可以
记录一些额外的信息,我们称之为权值。
现在我们定义某些带权二叉树是“神奇的”
。一个带权二叉树是神奇的,当
且仅当:
1每个节点的权值都是正整数。
2如果根节点的权值为 1,那么它的左右儿子都为空。
3如果根节点的权值大于 1,那么它的左右儿子都不为空,且均为“神奇
的”
。并且,如果根节点的权值是偶数,那么左右儿子的权值都等于根节点的一
半;如果根节点的权值是奇数,那么左右儿子的权值是与根节点权值的一半最
接近的两个正整数,且左儿子的权值比右儿子的权值大 1。
根据以上规则,如果我们知道了某个神奇二叉树的根节点的权值,那么这
棵树也就被唯一确定了。例如,根节点的权值是 3,那么它的左右孩子的权值
分别为 2 和 1,而 2 的左右孩子分别为 1 和 1,而 1 不会有孩子。
想必你一定知道什么叫做“最近公共祖先”
。在有根树上,从根到某个节点
的路径上的每个节点(包括根和它本身)都是这个点的祖先。对于树上的两个
点,如果我们寻找一个点同时成为他们的祖先,且离根最远,那么这个点就是
他们的最近公共祖先。
现在,给出一棵神奇的二叉树(事实上,只需要给出它根节点的权值),你
需要求出所有节点两两间最近公共祖先的权值之和。由于答案很大,你只需要
输出答案对 1,000,000,007 取模的结果。
你可以参照样例来更好地理解题目。
【输入格式】
输入文件为 lcastat.in。
每个输入文件具有多组数据,文件的第一行给出了数据组数T。
接下来T行,每行一个正整数n,给出了这个数据的神奇二叉树的根节点的权
值。
【输出格式】
输出文件为 lcastat.out。
对于每组数据,输出所有节点两两间最近公共祖先的权值之和,对
1,000,000,007 取模的结果。
【样例输入】
3
1
2
3
【样例输出】
1
16
62

程序实现

$O(n)$dp好写。考虑到每一个确定的值它的dp值相同,可以记忆化来避免重复操作,复杂度<$O(\ n)$,我也不知道多少

我的代码

#pragma GCC optimize(3)
#include <iostream>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>

using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7; 
typedef pair<LL,LL> poi;
map<LL, poi> dp;

poi Dfs(LL x) {//树的尺寸,答案 
    if (x == 1LL) return make_pair(1LL, 1LL);
    if (dp.count(x)) return dp[x];
    LL half = x / 2LL;
    poi r = Dfs(half), l = Dfs(x - half);
    LL ls = l.first, rs = r.first, la = l.second, ra = r.second;
    return dp[x] = make_pair((ls + rs + 1LL) % MOD, (la % MOD + ra % MOD + x % MOD + ls * (x % MOD) * 2LL % MOD + rs * (x % MOD) * 2LL % MOD + (ls * rs) % MOD * (x % MOD) * 2LL % MOD) % MOD);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    while (n--) {
        LL x;
        cin >> x;
        cout << Dfs(x).second << endl;
    }
    return 0;
}

T3

题目内容

快餐店
【问题描述】
羊神和华神打算在城市 C 开设两家外送快餐店。送餐到某一个地点的时间
与外卖店到该地点之间的最短路径长度是成正比的。华神把选址任务交给了羊
神,所以羊神决定:把自己的店选址在到每个顾客的最小距离之和最小的地方,而把华神的店选址在到每个顾客的最小距离之和最大的地方。
快餐店的顾客分布在城市 C 的N个建筑中,这N个建筑通过恰好M条双向道
路连接起来。任意两个建筑之间至少存在一条由双向道路连接而成的路径。快
餐店可以开设在任一建筑中,也可以开设在任意一条道路的某个位置上(该位
置与道路两端建筑的距离不一定是整数)。
现给定城市 C 的地图(道路分布及其长度)
,请找出最佳的快餐店地址,
输出其与每个顾客的距离之和。
【输入格式】
输入文件为 foodshop.in。
第一行为两个整数N M,以空格隔开。
接下来M行,每行 3 个整数,A i , B i , L i ,表示一条道路连接了建筑A i 与B i ,其
长度为L i 。
【输出格式】
输出文件为 foodshop.out。
输出一行两个实数,分别四舍五入保留恰好一位小数。表示羊神(最小)和
华神(最大)的最佳快餐店选址与每个顾客的最小距离之和。
注意:你的结果必须恰好有一位小数,小数位数不正确不得分。
【样例输入】
3
1
2
3
3
2 1
3 1
1 1
【样例输出】
2.0 2.5
【样例解释】
羊神的快餐店可以修在任何一个建筑中,最小距离之和为 0+1+1=2。
华神的快餐店可以修在任何一条道路的正中间,最小距离之和为
0.5+0.5+1.5=2.5。
【数据规模和约定】
对于 100%的数据,N ≥ 1, M ≥ 0,1 ≤ A i , B i ≤ N, L i ≥ 1。

程序实现

打了一个Floyd暴力,并且忽略了边,$20$分

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long LL;
const int MAXN = 1e3 + 5;

LL g[MAXN][MAXN];
int n, m;

void Floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

int main() {
    memset(g, 0x3f, sizeof(g));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) g[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        int x, y; LL z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
        g[y][x] = min(g[y][x], z);
    }
    Floyd();
    LL mx = 0, mn = 0x7fffffffffffffff;
    for (int i = 1; i <= n; i++) {
        LL sum = 0;
        for (int j = 1; j <= n; j++) sum += g[i][j];
        mx = max(mx, sum); mn = min(mn, sum);
    }
    cout << mn << ".0" << ' ' << mx << ".0" << endl;
    return 0;
} 

正解

【60 分算法】
考虑函数f(c)=∑_(i=1)^n min(du+c,dv+w−c)
显然 min(du+c,dv+w−c)的导数关于c是单调不增的,那么f(c)的导数
就是单调不增的,也就是几乎凸的。
那么这个式子关于c的最小值只可能在c=0 或c=w处取到,也就是羊神的店一
定开在点上。
最大值可以通过两种方式得到:
一,既然已经知道是几乎凸的就可以用三分法求解了。
二, min(du+c,dv+w−c)的导数会在c=(dv+w−du)/2 处突变。可
以证明,对于所有的i,取算出的c的中位数,就是f(c)的凸顶点,也就会在这里
取到最大值。
总的时间复杂度为O(n^3 )。
【100 分算法】
把最短路算法换成堆优化 Dijkstra 即可。
时间复杂度O(nm logn )。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define f(x, y, z) for(int x = (y); x <= (z); ++x)
#define foreach(x, y) for(__typeof(y.begin()) x = y.begin(); x != y.end(); ++x)

typedef long long LL;
typedef std::pair<int, int> PII;
const LL INF = 0x1f1f1f1f1f1f1f1fLL;

LL tree[2048];
inline void chg(int x, LL y){
    tree[x += 1024] = y;
    for(x >>= 1; x; x >>= 1) tree[x] = std::min(tree[x << 1], tree[x << 1 | 1]);
}
inline int gmin(){
    int x = 1;
    while(x < 1024) if(tree[x] == tree[x << 1]) x <<= 1; else x = (x << 1 | 1);
    int ret = x - 1024;
    tree[x] = INF;
    for(x >>= 1; x; x >>= 1) tree[x] = std::min(tree[x << 1], tree[x << 1 | 1]);
    return ret;
}

struct edge{
    int s, t, w;
} e[5007];

LL dist[1007], d[1007][1007], x[1007];
std::vector<PII> adj[1007];

int main(){
    freopen("foodshop.in", "r", stdin);
    freopen("foodshop.out", "w", stdout);
    int n, m; scanf("%d%d", &n, &m);
    f(i, 1, m){
        scanf("%d%d%d", &e[i].s, &e[i].t, &e[i].w);
        e[i].w *= 2;
        adj[e[i].s].push_back(PII(e[i].t, e[i].w));
        adj[e[i].t].push_back(PII(e[i].s, e[i].w));
    }
    LL ans = INF;
    f(S, 1, n){
        memset(dist, 0x1f, sizeof(dist));
        memset(tree, 0x1f, sizeof(tree));
        dist[S] = 0; chg(S, 0);
        while(tree[1] != INF){
            LL cd = tree[1]; int s = gmin();
            foreach(it, adj[s]){
                int t = it->first; LL nd = cd + (LL) it->second;
                if(dist[t] > nd){
                    dist[t] = nd;
                    chg(t, nd);
                }
            }
        }
        LL cans = 0;
        f(i, 1, n) cans += (LL) dist[i];
        if(cans < ans) ans = cans;
        memcpy(d[S], dist, sizeof(dist));
    }
    printf("%lld.%lld ", ans / 2LL, ans % 2LL * 5LL);
    ans = 0;
    f(ce, 1, m){
        int u = e[ce].s, v = e[ce].t, w = e[ce].w;
        f(i, 1, n) x[i] = (d[v][i] - d[u][i] + (LL) w) / 2LL;
        std::sort(x + 1, x + n + 1);
        LL c = x[(n + 1) / 2], cans = 0;
        if(c < 0) c = 0; if(c > w) c = w;
        f(i, 1, n) cans += std::min(d[u][i] + c, d[v][i] + (LL) w - c);
        if(cans > ans) ans = cans;
    }
    printf("%lld.%lld\n", ans / 2LL, ans % 2LL * 5LL);
    return 0;
}