The 2019 ICPC China Shaanxi Provincial Programming Contest

* A. Digit Mode

题意

令 $m(x)$ 为 $x$ 数码中出现次数最多的最大的数，求 $\sum\limits_{i=1}^nm(i)$ 。答案对 $10^9+7$ 取模。

题解

感觉是很难的数位dp啊！

设 $n$ 有 $r$ 位。我们考虑前 $p-1$ 位和 $n$ 相同，第 $p$ 位小于 $n$ ，那么第 $p+1$ 位到第 $r$ 位可以随便填了。此时我们枚举众数 $m$ 和出现次数 $c$ ，利用dp计算方案数。

设 $f_{i,j}$ 表示前 $i$ 个数码在第 $p+1$ 位到第 $r$ 位中填了 $j$ 个，有转移

f_{i,j}=\sum_kf_{i-1,j-k}\times\frac{j!}{(j-k)!}\times \frac{1}{k!}

这里的转移用到了多重集的排列数：

\binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!}

在转移时分子由 $(j-k)!$ 变为了 $j!$ ，分母还需要多除以 $k!$ ，所以式子就是上面这样了。

设 $m$ 在前 $p$ 位中出现次数为 $c'$ ，则方案数为

f_{9,(n-p+1)-(c-c')}\times\frac{(n-p+1)!}{((n-p+1)-(c-c'))!}\times\frac{1}{(c-c')!}

我们发现分子变来变去，但其实它始终是已经填入的数的个数。而最终填入的数个数为 $n-p+1$ ，所以我们在转移方程中不需要计算分子的变化了。相应地，修改一下最终结果。

转移：

f_{i,j}=\sum_kf_{i-1,j-k}\times\frac{1}{k!}

方案数：

f_{9,(n-p+1)-(c-c')}\times\frac{(n-p+1)!}{(c-c')!}

然后还需要考虑长度比 $n$ 短的数，枚举长度和第一位填入的数。还有考虑 $n$ 本身的贡献。

代码

D. Pick Up

题意

有一个正方形网格，有两个人 $A$ 和 $B$ ，速度分别为 $a$ 和 $b$ （ $a<b$ ），他们只能沿着网格线走。起始两人在 $(x_a,y_a)$ 和 $(x_b,y_b)$ ，目标地点在 $(x_c,y_c)$ 。当两人相遇时， $B$ 可以让 $A$ 搭便车，从而以速度 $b$ 行走。求 $A$ 到达目标地点的最小时间。

题解

非常重要的一点在于，想明白两个人可能会在什么地方相遇。这个位置一定要在两人的最短路径上，同时为了到达它不能绕路（相对终点而言）。

为了让两人尽快相遇，相遇点一定要选择以这两个人为对角点的矩形内。为了不绕路，选择矩形内（包括边界）离终点最近的点。这样一定是最优的。

那么我们只需要考虑两个人谁先到达相遇点：

如果 $A$ 先到，那么 $A$ 继续向终点走，如果中途两人相遇，就一起向终点走。此时的时间就是 $B$ 向终点走所需要的时间（也可能是 $A$ ）
如果 $B$ 先到，那么 $B$ 继续向着 $A$ 走，直到相遇，然后两个人一起向终点走。此时的时间就是两人相遇的时间，加上从相遇位置到终点 $B$ 所需要的时间。

代码

#include <bits/stdc++.h>
using namespace std;
double cal(int x1,int y1,int x2,int y2,int v)
{
    return (abs(x1-x2)+abs(y1-y2))*1.0/v;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int a,b,xa,ya,xb,yb,xc,yc;cin>>a>>b>>xa>>ya>>xb>>yb>>xc>>yc;
        double ans=cal(xa,ya,xc,yc,a);
        int l=min(xa,xb),r=max(xa,xb),d=min(ya,yb),u=max(ya,yb);
        int xd=max(l,min(xc,r)),yd=max(d,min(yc,u));
        double ta=cal(xa,ya,xd,yd,a),tb=cal(xb,yb,xd,yd,b);
        if(ta<tb) ans=min(ans,cal(xb,yb,xc,yc,b));
        else
        {
            double t=cal(xa,ya,xb,yb,a+b);
            double dis=abs(xa-xc)+abs(ya-yc)-a*t;
            ans=min(ans,t+dis/b);
        }
        cout<<fixed<<setprecision(10)<<ans<<'\n';
    }
    return 0;
}

*G. Paper-cutting

题意

给出一张 $01$ 组成的剪纸，可以折叠，折叠区域与被覆盖的区域要完全相同。要求最终 $0$ 组成的连通块数量最少。

题解

四个方向各不影响。每个方向上能折就折，得到的结果一定是最优的。利用Manacher判断就可以了。

代码

H. To the Park

题意

将 $1\sim n$ 中尽可能多的数两两配对，要求每对的 $\gcd$ 大于 $1$ 。

题解

首先考虑答案的上界： $1$ 和 $1\sim n$ 中所有 $2\times p>n$ 的质数 $p$ 一定无法配对，剩余的数两两配对。

这个上界总是可以取到的，考虑这样的一种构造方法：

从大到小枚举所有大于 $2$ 的质数 $p$ ，记它的所有倍数中未配对的数量为 $k$ 。如果 $k$ 是偶数，则它们两两配对，否则将 $2p$ 留下，其它数两两配对。 $2p$ 此前一定未被配对，因为它的因子只有 $2$ 和 $p$ 。

最后剩下的数一定都是偶数，我们将它们两两配对。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int cnt,pri[maxn];
bool vis[maxn],vis0[maxn];
void init()
{
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt&&i*pri[j]<maxn;j++)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++) vis0[i]=0;
        int m=0;
        while(2*pri[m+1]<=n) m++;
        vector<pair<int,int>> ans;
        for(int i=m;i>1;i--)
        {
            vector<int> v;
            v.push_back(pri[i]);
            for(int j=3*pri[i];j<=n;j+=pri[i])    
                if(!vis0[j]) v.push_back(j);
            if(v.size()&1) v.push_back(2*pri[i]);
            for(int j=0;j<v.size();j+=2)
                ans.push_back(make_pair(v[j],v[j+1])),vis0[v[j]]=vis0[v[j+1]]=1;
        }
        vector<int> v;
        for(int i=1;i<=n;i++)
            if(i%2==0&&!vis0[i]) v.push_back(i);
        for(int i=0;i<v.size();i+=2) 
            if(i+1<v.size()) ans.push_back(make_pair(v[i],v[i+1]));
        cout<<ans.size();
        for(auto i:ans) cout<<' '<<i.first<<' '<<i.second;
        cout<<'\n';
    }
    return 0;
}

I. Unrooted Trie

题意

给出一棵树，每条边上有一个字母。求有多少个点可以成为根，使得构成的字典树合法（每个点所代表的字符串各不相同）。

题解

不难发现，当一个点连出三条边字母相同或是不止一对边字母相同时，无解。若连出的边各不相同，则没有影响。我们处理有一对边字母相同的情况：

无根树不太好处理，我们任意指定一个点为根进行dfs。记当前结点 $u$ 有两条边 $(u,x),(u,y)$ 字母相同，那么有以下两种情况：

$x,y$ 都是 $u$ 的子结点，这时，最终能成为根的点一定在 $x$ 的子树内或者在 $y$ 的子树内。
$x,y$ 中有一个为 $u$ 的父结点，不妨设为 $x$ 。这时，能成为根的点在 $u$ 子树外或是 $y$ 子树内。

上述信息可以求出dfs序后用树上差分进行维护。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct edge
{
    int v;
    char w;
};
vector<edge> g[maxn];
int dfn,l[maxn],r[maxn],d[maxn];
void dfs(int u,int fa)
{
    l[u]=++dfn;
    for(auto i:g[u])
        if(i.v!=fa) dfs(i.v,u);
    r[u]=dfn;
}
void solve()
{
    int n;cin>>n;
    dfn=0;
    for(int i=1;i<=n;i++) g[i].clear(),d[i]=0;
    for(int i=1;i<n;i++)
    {
        int u,v;char w;
        cin>>u>>v>>w;
        g[u].push_back({v,w}),g[v].push_back({u,w});
    }
    dfs(1,0);
    for(int u=1;u<=n;u++)
    {
        vector<int> vec[26];
        for(auto i:g[u])
            vec[i.w-'a'].push_back(i.v);
        int idx=-1;
        for(int i=0;i<26;i++)
        {
            if((int)vec[i].size()>2) 
            {
                cout<<0<<'\n';
                return;
            }
            else if((int)vec[i].size()==2)
            {
                if(idx!=-1) 
                {
                    cout<<0<<'\n';
                    return;
                }
                idx=i;
            }
        }
        if(idx==-1) continue;
        int x=vec[idx].front(),y=vec[idx].back();
        if(l[x]>l[y]) swap(x,y);
        if(l[x]>l[u])
        {
            d[1]++,d[n+1]--;
            d[l[x]]--,d[r[x]+1]++;
            d[l[y]]--,d[r[y]+1]++;
        }
        else
        {
            d[l[u]]++,d[r[u]+1]--;
            d[l[y]]--,d[r[y]+1]++;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) 
    {
        d[i]+=d[i-1];
        if(!d[i]) ans++;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}

K. Escape Plan

题意

给定一张无向图，从结点 $1$ 出发，有若干个出口。每到达点 $i$ 时，会有与点 $i$ 相连的 $d_i$ 条边被禁止走，离开点 $i$ 时这些边恢复通行。求在最坏情况下离开这张图的最短距离。

题解

考虑dijkstra。从终点出发，倒着将剩下的点加入集合内。当点 $u$ 第一次被访问到时，表示从 $u$ 出发走这条边可以最快到达终点，那么显然到达 $u$ 时这条边必须被禁止。依此类推，直到点 $u$ 第 $d_u+1$ 次被访问，才能得到它到终点的距离，并将该点加入集合内。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
struct edge 
{
    int v,w;
};
struct node 
{
    int dis,u;
    bool operator < (const node& a)const {return dis>a.dis;}
};
vector<edge> g[maxn];
int n,m,k,e[maxn],d[maxn],dis[maxn];
bool vis[maxn];
void dijkstra() 
{
    for(int i=1;i<=n;i++) vis[i]=0,dis[i]=inf;
    priority_queue<node> q;
    for(int i=1;i<=k;i++) q.push({0,e[i]});
    while(!q.empty()) 
    {
        int u=q.top().u,w=q.top().dis;q.pop();
        if(vis[u]) continue;
        if(--d[u]>=0) continue;
        vis[u]=1;dis[u]=w;
        for(auto e:g[u]) 
        {
            int v=e.v,w=e.w;
            if(vis[v]) continue;
            q.push({dis[u]+w,v});
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=1;i<=k;i++) cin>>e[i];
        for(int i=1;i<=n;i++) cin>>d[i];
        for(int i=1;i<=m;i++)
        {
            int x,y,w;cin>>x>>y>>w;
            g[x].push_back({y,w}),g[y].push_back({x,w});
        }
        for(int i=1;i<=k;i++) d[e[i]]=0;
        dijkstra();
        if(!vis[1]) cout<<-1<<'\n';
        else cout<<dis[1]<<'\n';
    }
    return 0;
}

ACM

#构造 #数位dp #最短路 #分类讨论 #马拉车 #dfs序 #树上差分

The 2019 ICPC China Shaanxi Provincial Programming Contest

https://je3ter.github.io/2023/07/23/ACM/The 2019 ICPC China Shaanxi Provincial Programming Contest/

作者

Je3ter

发布于

2023年7月23日

许可协议

The 10th Shandong Provincial Collegiate Programming Contest 上一篇

UESTC 2023 Summer Training 下一篇