5月4日 —— hzwer模拟题

                    wsndy

题解

题面

小奇挖矿2(mining)
【题目背景】
小奇飞船的钻头开启了无限耐久+精准采集模式！这次它要将原矿运到泛光之源的矿石交易市场，以便为飞船升级无限非概率引擎。

【问题描述】
现在有 $m+1$ 个星球，从左到右标号为 $0$ 到 $m$，小奇最初在 $0$ 号星球。
有 $n$ 处矿体，第 $i$ 处矿体有 $ai$ 单位原矿，在第 $bi$ 个星球上。
由于飞船使用的是老式的跳跃引擎，每次它只能从第 $x$ 号星球移动到第 $x+4$ 号星球或 $x+7$ 号星球。每到一个星球，小奇会采走该星球上所有的原矿，求小奇能采到的最大原矿数量。
注意，小奇不必最终到达 $m$ 号星球。

【输入格式】
第一行 $2$ 个整数 $n，m$ 。
接下来 $n$ 行，每行 $2$ 个整数 $ai，bi$ 。

【输出格式】
输出一行一个整数，表示要求的结果。

【样例输入】

3 13
100 4
10 7
1 11

【样例输出】

101

【样例解释】
第一次从 $0$ 到 $4$ ，第二次从 $4$ 到 $11$，总共采到 $101$ 单位原矿。

【数据范围】
对于20%的数据 $n=1，m<= 10^5$
对于40%的数据 $n<=15，m<=10^5$
对于60%的数据 $m<=10^5$
对于100%的数据 $n<=10^5，m<=10^9，1<=ai<=10^4，1<=bi<=m$

---

小奇的矩阵(matrix)
【题目背景】
小奇总是在数学课上思考奇怪的问题。

【问题描述】
给定一个 $n*m$ 的矩阵，矩阵中的每个元素 $a_{ij}$ 为正整数。
接下来规定
$1.$ 合法的路径初始从矩阵左上角出发，每次只能向右或向下走，终点为右下角。
$2.$ 路径经过的 $n+m-1$ 个格子中的元素为 $A1,A2…A(n+m-1)$，$Aavg$ 为 $A_i$ 的平均数，路径的 $V$ 值为$(n+m-1)*\sum(Ai-Aavg)^2$ $(1<=i<=n+m-1)$
求 $V$ 值最小的合法路径，输出V值即可，有多组测试数据。

【输入格式】
第一行包含一个正整数 $T$ ，表示数据组数。
对于每组数据：
第一行包含两个正整数 $n$ 和 $m$ ，表示矩阵的行数和列数。
接下来 $n$ 行，每行 $m$ 个正整数 $a_{ij}$，描述这个矩阵。

【输出格式】
对于每次询问，输出一行一个整数表示要求的结果

【样例输入】

1
2 2
1 2
3 4

【样例输出】

14

【数据范围】
对于30%的数据 $n<=10，m<=10$
有另外40%的数据 $n<=15 m<=15$，矩阵中的元素不大于 $5$
对于100%的数据 $T<=5，n<=30，m<=30$，矩阵中的元素不大于 $30$

---

小奇的仓库(warehouse)
【题目背景】
小奇采的矿实在太多了，它准备在喵星系建个矿石仓库。令它无语的是，喵星系的货运飞船引擎还停留在上元时代！

【问题描述】
喵星系有 $n$ 个星球，星球以及星球间的航线形成一棵树。
从星球 $a$ 到星球 $b$ 要花费 $[dis(a,b) Xor M]$秒。（ $dis（a,b）$表示 $a,b$ 间的航线长度，$Xor$ 为位运算中的异或）
为了给仓库选址，小奇想知道，星球 $i（1<=i<=n）$ 到其它所有星球花费的时间之和。

【输入格式】
第一行包含两个正整数 $n，M$ 。
接下来 $n-1$ 行，每行 $3$ 个正整数 $a,b,c$，表示 $a，b$ 之间的航线长度为 $c$。

【输出格式】
$n$ 行，每行一个整数，表示星球 $i$ 到其它所有星球花费的时间之和。

【样例输入】

4 0
1 2 1
1 3 2
1 4 3

【样例输出】

6
8
10
12

【数据范围】

测试点编号	N	M
1	6	0
2	100	5
3	2000	9
4	50000	0
5	50000	0
6	50000	1
7	50000	6
8	100000	10
9	100000	13
10	100000	15

保证答案不超过 $2*10^9$

---

题解

T1

$1.$ 将所有矿物排序，$f_i$ 为到第 $i$ 个矿体能获得的最大原矿数，那么 $f_i=max{f_j}+x_i$，其中，$i-j$ 满足能拆分成 $4$ 和 $7$。
这样 $dp$ 需要 $n^2$ 的复杂度，但是我们发现，相距超过 $17$ (Noip 2017 Day1 T1 Woc)的一定可达，那么不超过 $17$ 的范围内暴力，超过 $17$ 的取个最大值即可，复杂度 $O(n)$
$2.$ 可以把相邻的星球距离超过 $17$ 的压缩成 $18$ ，按照 $O(m)$的 做法 $dp$
吐槽
$O(m)$ 竟然只能的 $30$, 位置竟然可以重复，$++$

#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define inf 1000000000
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct data{
    int a,b;
    friend bool operator<(data a,data b){
        return a.a<b.a;
    }
}a[100005];
int n,m;
int v[2000005],f[2000005];
int main()
{
    memset(f,-1,sizeof(f));
    n=read();m=read();
    for(int i=1;i<=n;i++)
        a[i].b=read(),a[i].a=read();
    sort(a+1,a+n+1);
    int now=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].a-a[i-1].a>17)now+=18,v[now]+=a[i].b;
        else now+=a[i].a-a[i-1].a,v[now]+=a[i].b;
    }
    int ans=0;
    f[0]=0;
    for(int i=0;i<=now;i++)
        if(f[i]!=-1)
        {
            f[i+4]=max(f[i+4],f[i]+v[i+4]);
            f[i+7]=max(f[i+7],f[i]+v[i+7]);
            ans=max(ans,f[now]);
        }
    printf("%d\n",ans);
    return 0;
}

T2

对于30%的数据，把所有的路径深搜出来取最优，复杂度是 $T*C_{2n} ^n*n$

这道题乍一看像是 $dp$，但是问题在于因为求的是方差与平均数有关，每一步的代价似乎不能直接得出

对于另外40%的数据，我们发现路径 $A_i$ 和 $SN$ 不超过 $120$，考虑枚举 $SN$，平均值为 $av=SN/N（N=n+m-1）$，那我们就能得到每一步的代价，但是要保证求的路径符合 $Ai$ 和为$SN$，设计 $f_(s,i,j)$ 表示到 $（i,j）$，和为 $s$ 的最小代价

$$f(s,i,j)=min{f(s-a[i][j],i,j-1),f(s-a[i][j],i-1,j)}+(av-a[i][j])^2$$
复杂度是 $T*SN^2*n^2$

事实上，路径 $Ai$ 和不等于 $SN$ 也无所谓，因为对于一条路径，只有我们枚举的 $SN$ 等于路径 $A_i$ 和时，这条路径的方差才最小

设我们枚举的 $SN$ 比真实的 $Ai$ 和小 $E$ ，$E$ 是任意实数
很容易证明 $\sum(Ai-Aavg)^2<\sum(Ai-av+E)^2$

所以直接去掉 $dp$ 的第一维，复杂度是 $T*SN*n^2$ ,可以通过100%的数据

#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define inf 1000000000
#define ll long long
#define N (n+m)*30
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int ans;
int T,n,m;
int a[35][35];
int f[1805][35][35];
void dp()
{
    f[a[1][1]][1][1]=a[1][1]*a[1][1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<=N;k++)
                if(f[k][i][j]!=1000000)
                {
                    int x=i+1,y=j,v=a[x][y];
                    f[k+v][x][y]=min(f[k+v][x][y],f[k][i][j]+v*v);
                    x=i,y=j+1,v=a[x][y];
                    f[k+v][x][y]=min(f[k+v][x][y],f[k][i][j]+v*v);
                }
    for(int i=1;i<=N;i++)
        if(f[i][n][m]!=1000000)
            ans=min(ans,(n+m-1)*f[i][n][m]-i*i);
}
int main()
{
    T=read();
    for(int cas=1;cas<=T;cas++)
    {
        ans=inf;
        n=read();m=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++)
                for(int k=0;k<=N;k++)
                    f[k][i][j]=1000000;
        dp();
        printf("%d\n",ans);
    }
    return 0;
}

T3

$floyd$，就有10分
在 $floyd$ 的基础上，我们对每条边处理一下 $xor$，就有 $20$ 分
简单的树形 $DP$ ，或者 $nlogn$ 的 $dij$ ，处理完每个点到其它点的最短路后再加上 $xor$, $30$ 分
第 $4、5$ 个点无需 $xor$ ，那么我们树形 $DP$ 扫一个节点与其它所有节点的路径长度之和，可以合并信息，最终均摊 $O(1)$，$50$分。
第 $6$ 个点 $xor$ $1$，那么我们树形 $DP$ 到一个点时记录有多少个 $0$ ，多少个 $1$，然后每当一条路径到 $2$，那部分就再记录一个值，$60$分到手。
一样的，就是原来的$“0”$、$“1”$、大于等于 $2$ 变成了 $0~16$ 么, $100$ 分
为什么 $n^2logn$ 的树剖会 $WA$ 掉 $20$ 分

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
#define mod 45989
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int bin[20];
int n,m,cnt;
int dis[100005],last[100005];
int f[100005][16],g[100005],t[16];
struct edge{
    int to,next,v;
}e[200005];
void insert(int u,int v,int w)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}
void dfs1(int x,int fa)
{
    for(int i=last[x];i;i=e[i].next)
        if(e[i].to!=fa)
        {
            dfs1(e[i].to,x);
            g[x]+=g[e[i].to]+e[i].v/16;
            f[x][e[i].v%16]++;
            for(int j=0;j<16;j++)
            {
                int k=j+e[i].v;
                g[x]+=k/16*f[e[i].to][j];
                f[x][k%16]+=f[e[i].to][j];
            }
        }
}
void dfs2(int x,int fa)
{
    for(int i=last[x];i;i=e[i].next)
        if(e[i].to!=fa)
        {
            int tmp=g[x]-g[e[i].to];
            for(int j=0;j<16;j++)
            {
                int k=j+e[i].v;
                tmp-=k/16*f[e[i].to][j];
                t[k%16]=f[x][k%16]-f[e[i].to][j];
            }
            t[e[i].v%16]--;
            g[e[i].to]+=tmp;
            f[e[i].to][e[i].v%16]++;
            for(int j=0;j<16;j++)
            {
                int k=j+e[i].v;
                g[e[i].to]+=k/16*t[j];
                f[e[i].to][k%16]+=t[j];
            }
            dfs2(e[i].to,x);
        }
}
int main()
{
    bin[0]=1;
    for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
    n=read(),m=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read(),w=read();
        insert(u,v,w);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)
    {
        ll ans=g[i]*16;
        for(int j=0;j<16;j++)ans+=(j^m)*f[i][j];
        printf("%I64d\n",ans);
    }
    return 0;
}

//不知道咋WA的树剖
#include <iostream>
#include <cstdio>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
const int oo = 2e9;
#define gc getchar()
int n, m;
LL f[105][105];
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
void Work_1() {
    for(int i = 1; i <= n; i ++) 
        for(int j = 1; j <= n; j ++)
            f[i][j] = oo;
    for(int i = 1; i <= n; i ++)
        f[i][i] = 0;
    for(int i = 1; i < n; i ++) {
        int a = read(), b = read(), c = read();
        f[a][b] = f[b][a] = c;
    }
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                f[i][j] = min(f[i][k] + f[k][j], f[i][j]);
    /*for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++)
            cout << f[i][j] << " ";
        cout << endl;
    }*/
    LL Answer(0);
    for(int i = 1; i <= n; i ++) {
        Answer = 0;
        for(int j = 1; j <= n; j ++) {
            Answer += (f[i][j] ^ m);
        }
        cout << Answer << endl;
    }
}
struct Node {int u, v, w, nxt;} G[4010];
int head[N], topp[N], dis[N], fa[N], deep[N], size[N], son[N]; 
int now = 1;
inline void Add(int u, int v, int w) {
    G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;
} 
void Dfs_1(int u, int f_, int dep) {
    fa[u] = f_, deep[u] = dep;
    size[u] = 1;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(v != f_) {
            dis[v] = dis[u] + G[i].w;
            Dfs_1(v, u, dep + 1);
            size[u] += size[v];
            if(size[v] > size[son[u]]) son[u] = v;
        }
    }
}
void Dfs_2(int u, int tp) {
    topp[u] = tp;
    if(!son[u]) return ;
    Dfs_2(son[u], tp);
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(v != fa[u] && v != son[u]) Dfs_2(v, v);
    }
}
inline int Lca(int x, int y) {
    int tp1 = topp[x], tp2 = topp[y];
    while(tp1 != tp2) {
        if(deep[tp1] < deep[tp2]) swap(x, y), swap(tp1, tp2);
        x = fa[tp1];
        tp1 = fa[x];
    }
    return deep[x] < deep[y] ? x : y;
}
void Work_2() {
    for(int i = 1; i <= n; i ++) head[i] = -1;
    for(int i = 1; i < n; i ++) {
        int u = read(), v = read(), w = read();
        Add(u, v, w); Add(v, u, w);
    }
    Dfs_1(1, 0, 1);
    Dfs_2(1, 1);
    for(int i = 1; i <= n; i ++) {
        LL Answer = 0;
        for(int j = 1; j <= n; j ++) {
            if(i == j) continue ;
            int lca = Lca(i, j);
            Answer += ((dis[i] + dis[j] - dis[lca] - dis[lca]) ^ m);
        }
        printf("%lld\n", Answer);
    }
}
int main() {
    freopen("warehouse.in", "r", stdin);
    freopen("warehouse.out", "w", stdout);
    n = read();
    m = read();
    if(n <= 100) Work_1();
    else if(n == 2000) Work_2();
    return 0;
}

总结

暴力都不知道咋 $WA$
$3$ 道 $dp$，不擅长