Codeforces Round #333(Div.1) 解题报告

发布于 2020-03-22  27 次阅读



A - The Two Routes
由题可得,1 到 n 的这条边要么是公路,要么是铁路,也就是说要么公交车直达,要么火车直达。如果是公路的话,铁路的最短路就是答案;如果是铁路的话,公路的最短路就是答案。
Code by ZXyang

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(),(x).end()
#define lowbit(x) x&-x
#define pb push_back
#define ls (id<<1)
#define rs (id<<1|1)
typedef long long ll;
typedef pair<ll,ll> pii;
typedef double db;
const int MAXN=3e6+10,MAXM=2e6+10;
const int INF=INT_MAX,SINF=0x3f3f3f3f;
const ll llINF=LLONG_MAX;
const int MOD=1e9+7,mod=998244353;
const int inv2=5e8+4;
struct Dijkstra_with_pile
{
    int head[MAXN],to[MAXM],_next[MAXM],ecnt=0;
    ll val[MAXM];
    void init(int n=MAXN)
    {
        memset(head,0,n*sizeof(ll));
        ecnt=0;
    }
    void add_Edge(int u,int v,ll w)
    {
        _next[++ecnt]=head[u];
        to[ecnt]=v;
        val[ecnt]=w;
        head[u]=ecnt;
    }
    ll dis[MAXN];
    priority_queue<pii,vector<pii>,greater<pii> >pq;
    void dijkstra(int s)
    {
        memset(dis,0x3f,sizeof(dis));
        dis[s]=0;
        while(!pq.empty())pq.pop();
        pq.push({0,s});
        while(!pq.empty())
        {
            int u=pq.top().second;
            pq.pop();
            for(int i=head[u];i;i=_next[i])
            {
                int v=to[i];
                if(dis[v]>dis[u]+val[i])
                {
                    dis[v]=dis[u]+val[i];
                    pq.push({dis[v],v});
                }
            }
        }
    }
}G;
int g[405][405],n,m;
int main()
{
    scanf(
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf(
        g[u][v]=g[v][u]=1;
    }
    if(g[1][n])
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        g[i][j]^=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(g[i][j])G.add_Edge(i,j,1);
    G.dijkstra(1);
    if(G.dis[n]>INF)return puts("-1"),0;
    cout<<G.dis[n];
    return 0;
}

B - Lipshitz Sequence
不难发现 $\lceil\frac{|h_j-h_i|}{j-i}\rceil$ 取最大的一个必要条件就是 $|i-j|=1$,即相邻。这个画画图实际上就很显然了。
然后,这题要求所有的子区间的 $L(h)$,我们可以发现,对于一个最大的 $L(h)$,它可以影响一部分区间。我们先对 $h_i$ 做差分,然后实际上就是要找当前这个差分值所影响的区间。这个可以用单调栈来预处理,然后查询就很简单了。
Code by Vingying

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100050;
int n,q;
ll h[N],c[N];
int s[N],top;
ll L[N],R[N];
void gao()
{
    for(int i=2;i<=n+1;++i)
    {
        while(top&&c[s[top]]<c[i])R[s[top--]]=i-1;
        L[i]=s[top]+1;
        s[++top]=i;
    }
}
void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;++i)scanf(
    for(int i=1;i<=n;++i)c[i]=abs(h[i]-h[i-1]);
    c[n+1]=INT_MAX;
    gao();
    while(q--)
    {
        int l,r;
        scanf(
        ll ans=0;
        for(int i=l+1;i<=r;++i)
        {
            ll LL=max(l*1ll,L[i]-1);
            ll RR=min(r*1ll,R[i]);
            ans+=c[i]*(i-LL)*(RR-i+1);
        }
        cout<<ans<<'\n';
    }
}
int main()
{
    int Test=1;
//    cin>>Test;
    while(Test--)
    {
        solve();
    }
    return 0;
}

C - Kleofáš and the n-thlon
期望dp嘛。设 $dp(i,j)$ 表示一个人打到第 $i$ 场比赛,当前得分为 $j$ 的概率。
对于前面而言,转移的时候我们实际上不需要管每个人的具体得分是多少,而是看这个人得这分数的概率是多少。首先,我们知道 Kleofáš 每一场的分数,那么对于其他人而言,他这一场肯定不能得与 Kleofáš 相同的分数。于是转移方程就出来了:$dp(i,j)=\sum\limits_{k=1}^{k\ne x_i and \min(j,m)}\frac{dp(i-1,j-k)}{(m-1)}$,最后我们只需要求 $\sum\limits_{j=1}^{(\sum{x_i})-1}dp(n,j)$ 就行。
Code by ZXyang

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(),(x).end()
#define lowbit(x) x&-x
#define pb push_back
#define ls (id<<1)
#define rs (id<<1|1)
typedef long long ll;
typedef pair<ll,ll> pii;
typedef double db;
const int MAXN=3e6+10,MAXM=2e6+10;
const int INF=INT_MAX,SINF=0x3f3f3f3f;
const ll llINF=LLONG_MAX;
const int MOD=1e9+7,mod=998244353;
const int inv2=5e8+4;
int n,m,x[MAXN],sum;
long double dp[105][100005];
int main()
{
    scanf(
    if (m==1) return puts("1"),0;
    for(int i=1;i<=n;i++)
    {
        scanf(
        sum+=x[i];
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        double tmp=dp[i-1][0]/(m-1);
        for(int k=1;k<=i*m;k++)
        {
            if(k>=x[i])dp[i][k]-=dp[i-1][k-x[i]]/(m-1);
            dp[i][k]+=tmp;
            tmp+=dp[i-1][k]/(m-1);
            if(k>m)tmp-=dp[i-1][k-m]/(m-1);
        }
    }
    db ans=0;
    for(int i=1;i<sum;i++)ans+=dp[n][i];
    printf(
    return 0;
}

D - Acyclic Organic Compounds
据 hrdg 说这就是一个裸的 Trie 树合并......
Code by HeRaNO

#include <bits/stdc++.h>
#define MAXN 300005
using namespace std;
int n,tot,cnt,ans,u,v,a[MAXN],son[MAXN][26],siz[MAXN];
char s[MAXN];
vector <int> g[MAXN];
inline void add(int u,int v)
{
	g[u].push_back(v);g[v].push_back(u);
	return ;
}
inline int merge(int x,int y)
{
	int nxt=s[y]-'a',siz=1;
	if (!son[x][nxt]){son[x][nxt]=y;return 0;}
	for (int i=0;i<26;i++)
		if (son[y][i]) siz+=merge(son[x][nxt],son[y][i]);
	return siz;
}
inline void dfs(int x,int fa)
{
	siz[x]=1;
	for (auto v:g[x])
		if (v!=fa)
		{
			dfs(v,x);
			siz[x]+=siz[v]-merge(x,v);
		}
	if (a[x]+siz[x]>ans)
	{
		ans=a[x]+siz[x];
		cnt=1;
	}
	else if (a[x]+siz[x]==ans) ++cnt;
	return ;
}
int main()
{
	scanf(
	for (int i=1;i<=n;i++) scanf(
	scanf(
	for (int i=1;i<n;i++) scanf(
	dfs(1,-1);
	printf(
	return 0;
}

E - A Museum Robbery
来啦来啦,动态维护 0-1 背包题来辣(
这个题第三种操作刚开始愣是没看懂,结果是让求当背包容量为 $1,2,...,k$ 时的最大价值。
来复习一下 0-1 背包吧:设 $dp(i,j)$ 表示当前到第 $i$ 个物品,背包容量为 $j$ 的最大价值。容易写出方程:$dp(i,j)=max(dp(i-1,j),dp(i-1,j-w_i)+v_i)$ ,其中 $w_i$ 是物品体积,$v_i$ 是物品价值。其中 $j$ 要倒序枚举,因为每种物品我们只能选一个。
回到这道题:我们显然不能每次都去求一次 0-1 背包,否则复杂度为 $\mathcal{O}(nkq)$,显然接受不了。
注意到:我们每一次增删物品对哪些询问会有影响呢?对于每一个询问,显然是询问当前有的物品。我们可以预处理出每一个物品在集合内出现的时间(记为 $s_i$)和被删的时间(记为 $e_i$),那么设时间区间为 $[l,r]$,如果一个询问在这个时间范围内,那么显然所询问的就是满足 $s_i\leq l$ 且 $r\leq e_i$ 的物品,因为这些物品在我询问的时候一定都在这个区间内。
所以,我们可以考虑对时间分治:将满足条件的物品拿来跑一次 0-1 背包,得到的答案可能会影响好几个询问,然后对于剩下的物品,就直接划分到左右两个区间依次分治下去就行。复杂度 $\mathcal{O}(nk\log q)$。
然后算答案的时候不要用快速幂......可以先预处理出不同幂的值然后再计算,否则会 t 掉。
话说 C++17 64位 跑得是真的快......不过本身好像比较玄学?
Code by Vingying

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=55050;
const ll p=1e7+19,Q=1e9+7;
int n,k,q,tot,tim=1;
inline ll mi(ll a,ll b){ll ret=1;while(b){if(b&1)ret*=a,re
struct entity
{
    ll v,w;
    int s,e;
}a[N];
ll dp[35][1050];
int query[100050];
void cdq(int l,int r,int dep,vector<int>vec)
{
    if(l>r)return;
    for(int i=1;i<=k;++i)dp[dep][i]=dp[dep-1][i];
    for(int i=0;i<vec.size();++i)
    {
        if(a[vec[i]].s>l||a[vec[i]].e<r)continue;
        for(int j=k;j;--j)
        {
            if(a[vec[i]].w>j)continue;
            dp[dep][j]=max(dp[dep][j],dp[dep][j-a[vec[i]].w]+a[vec[i]].v);
        }
    }
    if(l==r)
    {
        ll ans=0;
        for(int i=k;i;--i)ans*=p,an
        for(int i=1;i<=query[l];++i)printf(
        return;
    }
    vector <int> L,R;
    int mid=(l+r)>>1;
    for(auto i:vec)
    {
        if(a[i].s<=l&&a[i].e>=r)continue;
        if(a[i].e<=mid)L.push_back(i);
        else if(a[i].s>mid)R.push_back(i);
        else
        {
            L.push_back(i);
            R.push_back(i);
        }
    }
    cdq(l,mid,dep+1,L);
    cdq(mid+1,r,dep+1,R);
}
vector <int> t;
int main()
{
    cin>>n>>k;
    tot=n;
    for(int i=1;i<=n;++i)
    {
        scanf(
        a[i].s=1;
    }
    cin>>q;
    while(q--)
    {
        int op;scanf(
        switch(op)
        {
        case 1:
            {
                ll v,w;
                scanf(
                ++tim;++tot;
                a[tot].s=tim;
                a[tot].v=v;a[tot].w=w;
                break;
            }
        case 2:
            {
                int id;scanf(
                a[id].e=tim;++tim;
                break;
            }
        case 3:
            {
                query[tim]++;
                break;
            }
        }
    }
    for(int i=1;i<=tot;++i)
    {
        t.push_back(i);
        if(a[i].e==0)a[i].e=tim;
    }
    cdq(1,tim,1,t);
    return 0;
}