高速道路の建設 / Construction of Highway

这个操作长得很像 LCT 中的 access。

于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。

因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ 的，所以时间复杂度 $\mathcal{O}(n\log^2 n)$。

代码

柵 / Fences

不会

テント / Tents

我们先不管不能为空的限制，最后减去 $1$ 即可。

设 $dp_{i,j}$ 为 $i$ 行 $j$ 列时的答案。转移时放若干个帐篷并强制在最后一行放一个：

  • 不放帐篷：$dp_{i-1,j}\to dp_{i,j}$；
  • 加一个帐篷，需要占用一行一列，方向任意：$4\times dp_{i-1,j-1}\times j\to dp_{i,j}$；
  • 加两个帐篷，需要占用一行两列：$dp_{i-1,j-2}\times {j\choose 2}\to dp_{i,j}$；
  • 加两个帐篷，需要占用两行一列：$dp_{i-2,j-1}\times j\times (i-1)\to dp_{i,j}$。

代码

修行 / Asceticism

我们相当于要求 $\sum_{i=1}^{n-1}[p_i>p_{i+1}]=k-1$ 的排列数。

有一个奇妙的结论是，当 $p_i$ 是 $[0,1)$ 中的实数时方案数和排列数是相等的。证明不会。

考虑构造 $a_i=[p_{i-1}>p_i]+p_i-p_{i-1}$。可以发现 $a_i\in[0,1)$，而且一组 $a_i$ 唯一对应一组 $p_i$。

那么我们相当于要求 $k-1\leq\sum a_i<k$ 的概率。容斥一下，变成求 $\sum a_i<k$ 的概率。

我们知道（其实我并不知道），$n$ 个 $[0,+\infty)$ 的随机实数的和 $<k$ 的概率为 $\frac{k^n}{n!}$。

然而现在有一个上界的限制，所以我们只要再容斥一下就好了。

代码

道路網の整備 / Road Service

猜想新加的 $k$ 条边都连到一个点上时是很优秀的。

那么直接瞎随机就好了，每个点跑几秒都可以拿到 $14$ 分，跑五个小时应该就能拿 $18$ 分了。反正我每个点只要跑一个小时就可以到 17.5 分以上（

参考代码 

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;
const double eps=1e-7;

mt19937 rnd(time(0));

int n,k,W0,s;
vector<int> E[N],G[N];
struct edge { int u,v; } e[N];

int dis[N];
int bfs(int s) {
    memset(dis,0,sizeof(dis)); dis[s]=1;
    queue<int> Q; Q.push(s);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (int v:E[u])
            if (!dis[v]) dis[v]=dis[u]+1,Q.push(v);
    }
    int res=0;
    for (int i=1;i<=n;++i) res+=dis[i]-1;
    return res;
}
ll calc() {
    for (int i=1;i<=n;++i) G[i]=E[i];
    for (int i=1;i<=k;++i) {
        E[e[i].u].emplace_back(e[i].v);
        E[e[i].v].emplace_back(e[i].u);
    }
    ll res=0;
    for (int i=1;i<=n;++i) res+=bfs(i);
    for (int i=1;i<=n;++i) E[i]=G[i];
    return res/2;
}

void print(ll ans) {
    double score=18*pow(20,1-1.0*ans/W0);
    printf("%.10lf\n",score);
    if (score>17.5) {
        FILE *fp=fopen("road.out","w");
        for (int i=1;i<=k;++i) fprintf(fp,"%d %d\n",e[i].u,e[i].v);
        fclose(fp); exit(0);
    }
}

int main() {
    freopen("road.in","r",stdin);
    n=read(),k=read(),W0=read();
    for (int i=1;i<n;++i) {
        int u=read(),v=read();
        E[u].emplace_back(v),E[v].emplace_back(u);
    }
    ll ans=1e18;
    s=rnd()%n+1;
    for (int i=1;i<=k;++i) e[i]=(edge){s,rnd()%n+1};
    ll now=calc();
    if (now<ans) ans=now,print(ans);
    while (1) {
        int p=rnd()%k+1,ov=e[p].v; e[p].v=rnd()%n+1;
        now=calc();
        if (now<ans) ans=now,print(ans);
        else e[p].v=ov;
    }
    return 0;
}

最悪の記者 3 / Worst Reporter 3

显然每个人的运动是有周期的，而这个周期可以直接算出来。还可以发现，每一个人的周期都是前一个人周期的倍数。

那么可能的周期只有 $\log$ 种，每次直接暴力对每种周期对应的区间求个交即可。

代码

航空路線図 / Airline Route Map

咕咕咕

ビ太郎のパーティー / Bitaro’s Party

注意到 $\sum y_i\leq 10^5$，因此可以考虑根号分治。

如果 $y_i\geq \sqrt{n}$，这样的询问只会有至多 $\mathcal{O}(\sqrt{n})$ 个，可以直接拓扑排序求最长路。

如果 $y_i<\sqrt{n}$，我们可以对每个点预处理出距离它最远的 $\sqrt{n}$ 个点，这样子直接查询即可。这个预处理相当于把所有入边对应的最远点合并，归并后每个点只保留最大的 $dis$ 即可。

代码

防犯ゲート / Security Gate

不会

飴 / Candies

和 CTSC2007 数据备份 是一个套路。

考虑贪心，我们每次选一个能选的最大的然后把旁边两个删掉即可，用堆维护。

然而这样子显然是有问题的，因为我们之后可能会放弃选这个而选旁边的两个。于是我们在选 $p$ 时把 $a_{l_p}+a_{r_p}-a_p$ 加入堆中即可（相当于维护反悔）。这个 $l_p$ 和 $r_p$ 可以用双向链表维护。

代码

図書館 / Library

我们可以先用 $\mathcal{O}(n)$ 次询问找到一个端点。

接着我们找到与这个端点相邻的数。考虑二分，假设 $[L,mid]$ 的答案和 $[L,mid]\cup{i}$ 的答案相同，说明相邻的数在 $[L,mid]$ 中，否则在 $[mid+1,R]$ 中。

重复这个过程就可以确定整个序列了。询问数是 $\mathcal{O}(n\log n)$ 的。

代码

イノシシ / Wild Boar

不会

最后修改：2020 年 10 月 24 日 11 : 15 AM
© 允许规范转载