神崎兰子

2021-09-11 18:06 已编辑偶像大师灰姑娘女孩后端工程师

关注

【题解】北京信息科技大学第十三届程序设计竞赛题解

出题人：
A~E 走到湖边就会哈啦一下买一杯美式

F~L 神崎兰子

难度估计：

签到题(-800)：J

简单题(800-1000)：C H F

次简单题(1000-1300)：G K

中等题(1300-1700)：B E L

较难题(1700-2100)：A D

防ak题(2100-)：I

A 蹦！蹦！蹦！

题意：给一个数组，模拟蹦床的弹力值，每次跳跃使当前起跳蹦床弹力值-1，可以自由选择开始跳跃的蹦床，最少的趟数将所有蹦床弹力值归一。

知识点：贪心，差分；

Solution：

不难发现贪心的规律：在弹力值为1的蹦床上起跳相当于从该蹦床往后第一个不为1的蹦床起跳，显然从最左边第一个不为1的蹦床开始这一趟的起跳是最优的。

如果从每次都从起跳的蹦床完成跳跃一趟的模拟，时间复杂度为 $O(\sum a_i)$ ，会造成超时的错误。

考虑从左往右遍历所有的蹦床，使当前蹦床弹力值归1，该蹦床能影响的范围会使得 $[i+1,i+a_i]$ 范围内得所有蹦床弹力值-1，我们只需要判断当前访问的蹦床被先前的蹦床影响的累积是否大于等于 $a_i-1$ ，分类讨论。

区间维护使用差分等能够快速对区间进行维护的数据结构。

复杂度 $O(n)$

B 踩石头过河

题意：在二维平面中给定两条平行不重合直线，给定若干个圆形，判断是否存在一组圆形组成了一个横跨两条直线的通路。

知识点：计算几何，并查集

Solution：

首先我们先明确两个圆相交的判定条件，显然：

$dis(c_1,c_2)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\leq r_1+r_2$

为了避免出现浮点数，也可以将两边同时做平方处理。

预先维护所有跟下界直线 $l_1$ ，上界直线 $l_2$ 相交的圆，将他们的序号分别存进 $top[],bottom[]$ 两个数组当中。

将所有的圆用并查集维护彼此是否在同一个集合当中。

最后将 $top[],bottom[]$ 彼此一一组对判断存在一对 $(top[i],bottom[j])$ 在同一个集合当中，如果存在则判断YES。

C 旅行家问题1

题意：

在数轴上给若干个点，给定起点，求从起点出发访问完所有点的总距离。

知识点：思维，分类讨论

Solution：

首先我们求出若干个点的区间，分类讨论起点在该区间左边，中间，右边的情况。记录起点为x。

在左边： $ans=R-x$

在右边： $ans=x-L$

在中间： $ans=2*min(R-x,x-L)+max(R-x,x-L)$

D 旅行家问题2

题意：一个城市向另一个城市转移的花费是 $max(c_i,a_j-a_i)$

向另一个城市转移的花费是从一号城市出发，访问所有城市并返回一号城市的最小花费。

知识点：贪心、最短路、迪杰斯特拉。

Solution1：

我们采用贪心的思想，不难证明，每座山都只需到达一次并离开一次，访问的路径则是一个环；换而言之，出发点的选择可以是任意的，因为无论从哪里出发，每座山都只会到达一次并离开一次。

从这个角度出发，我们可以把问题看成以下模型：

每个梯子都使用一次，总费用为 $\sum c_i$

然后如果梯子无法够到，那么费用要加上 $(a_j-a_i-c_i)$

即为： $max(0,a_j-a_i-c_i)$

总花费则为： $\sum c_i + \sum max(0,a_j-a_i-c_i)$

使这个花费 $max(0,a_j-a_i-c_i)$ 达到最少，我们可知，当向比当前山矮的山转移时，不会造成多余花费，也就是当我们攀登到一个比较高的山上时，所有比这座山矮的山都可以由这座山转移。我们记录每次攀爬后可大的最高点 $（a_i+c_i）$ 即可。

时间复杂度 $O(n)$

Solution2：迪杰斯特拉建边处理，需要进行堆优化。

时间复杂度 $O(nlogn)$

E 小菲与Fib数列

题意：给定一种运算 $g(x,y)=(x*y+1) mod 2$

求解 $\sum _{i=1} ^n \sum _{j=i+1} ^n g(f_i,f_j)$

知识点：思维，数学

Solution：

我们发现g函数的结果只跟x,y奇偶性有关。不难发现，Fibonacci数列通项存在奇数、奇数、偶数、奇数、奇数、偶数……的规律。两个奇数不贡献，一奇数一偶数贡献1，两个偶数贡献1。我们可以将数列每三个元素分一组、简单手推一下公式即可，注意处理无法整分的最后几个元素的情况。

最终结果为

$t=n/3,k=n\%3$

$ans=(3*(t-1)+2*k)*t/2+t*(t+1)/2$

F 制作谱面

知识点：模拟

按照题意进行模拟即可。注意谱面是时间倒序的，所以输出时要格外注意。

#include<bits/stdc++.h>
using namespace std;
string s[100010];
int main(){
    int t;
    int p=1;
    int n,m,i,j;
    cin>>n>>m;
    s[0]="+-------+";
    for(i=1;i<=m;i++)s[i]="|-------|";
    for(i=0;i<n;i++){
        string temp;
        int t,h;
        cin>>temp>>t>>h;
        if(temp=="tap")s[t][h]='O';
        else s[t][h]='X';
    }
    for(i=1;i<=m;i++){
        for(j=1;j<=7;j++){
            if(s[i][j]!='-')break;
            s[i][j]=' ';
        }
        for(j=7;j>=0;j--){
            if(s[i][j]!='-')break;
            s[i][j]=' ';
        }
    }
    for(i=m;i>=0;i--){
        cout<<s[i];
        if(i!=0)cout<<endl;
    }


}

G ranko的手表

知识点：枚举 / 贪心（不推荐）

这道题用思维的方法也可以做，但需要处理的细节很多。

我们可以观察到一天的分钟总数为24*60=1440，因此 $O(n^2)$ 进行枚举也仅有1e6级别的复杂度，完全可以接受。

所以可以枚举每个时刻是否合法。然后在所有合法时间里求最小值和最大值。

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int main(){
    int j,i;
    cin>>s1>>s2;
    vector<int>v1,v2;
    for(i=0;i<24*60;i++){
        int h=i/60,m=i%60;
        if((h/10==s1[0]-'0'||s1[0]=='?')&&(h%10==s1[1]-'0'||s1[1]=='?')&&(m/10==s1[3]-'0'||s1[3]=='?')&&(m%10==s1[4]-'0'||s1[4]=='?'))v1.push_back(i);
        if((h/10==s2[0]-'0'||s2[0]=='?')&&(h%10==s2[1]-'0'||s2[1]=='?')&&(m/10==s2[3]-'0'||s2[3]=='?')&&(m%10==s2[4]-'0'||s2[4]=='?'))v2.push_back(i);
    }
    int mi=1e9,ma=0;
    for(i=0;i<v1.size();i++){
        for(j=0;j<v2.size();j++){
            if(v1[i]<v2[j]){
                ma=max(ma,v2[j]-v1[i]);
                mi=min(mi,v2[j]-v1[i]);
            }
        }
    }
    cout<<mi<<" "<<ma<<endl;
}

h 字母收集

知识点：动态规划

非常简单的动态规划题，一个经典模型的变种。

转移方程

$dp[i][j]=max(dp[i-1][j],dp[i][j-1])+val[i][j]$

#include<bits/stdc++.h>
using namespace std;

int dp[1010][1010];
string s[1010];
int f(char c){
    if(c=='l')return 4;
    if(c=='o')return 3;
    if(c=='v')return 2;
    if(c=='e')return 1;
    return 0;
}
int main(){
    int n,m;
    cin>>n>>m;
    int i,j;
    for(i=0;i<n;i++)cin>>s[i];
    dp[0][0]=f(s[0][0]);
    for(j=1;j<m;j++){
        dp[0][j]=dp[0][j-1]+f(s[0][j]);
    }
    for(i=1;i<n;i++){
        dp[i][0]=dp[i-1][0]+f(s[i][0]);
        for(j=1;j<m;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+f(s[i][j]);
        }
    }
    cout<<dp[n-1][m-1];
}

I 数字染色

知识点：数论、容斥原理

我们可以先这样想：

把所有 $2$ 的倍数放在一个集合里，显然在这个集合随便取任意个数，gcd一定大于1。共有 $2^{size}-1$ 种方案。

$3$ 的倍数放在一个集合里，显然在这个集合随便取任意个数，gcd一定大于1。共有 $2^{size}-1$ 种方案。

……

$p$ （ $p$ 是素数）的倍数放在一个集合里，显然在这个集合随便取任意个数，gcd一定大于1。共有 $2^{size}-1$ 种方案。

经过以上计算，会发现有的数被计算了多次：形如 $p1*p2$ 倍数的数，在 $p1$ 和 $p2$ 时各被计算了一次，应该减去。

同理，形如 $p1*p2*p3$ 倍数的数，在计算时应该加回来。此为容斥的思想。

因此得到最终的答案：

$ans=\sum _{i=2}^n μ(i)*(2^{f(i)}-1)$

其中， $f(i)$ 代表数组中 $i$ 的倍数的数量， $μ(i)$ 为莫比乌斯函数，定义是：

$μ(x)=\left\{ \begin{array}{rcl} 1 & {x=1}\\ (-1)^k &{x无平方数因子，且x=p_1p_2...p_k}\\ 0 &{x有大于1的平方数因子} \end{array} \right.$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAX=1e5;
int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
bool check[MAX+10];
int prime[MAX+10];
int mu[MAX+10];
void Moblus()
{
    memset(check,false,sizeof(check));
    mu[1] = 1;
    int tot = 0;
    for(int i = 2; i <= MAX; i++)
    {
        if( !check[i] ){
            prime[tot++] = i;
            mu[i] = 1;
        }
        for(int j = 0; j < tot; j++)
        {
            if(i * prime[j] > MAX) break;
            check[i * prime[j]] = true;
            if( i % prime[j] == 0){
                mu[i * prime[j]] = 0;
                break;
            }else{
                mu[i * prime[j]] = -mu[i];
            }
        }
    }
}
int a[100010],tong[100010],sv[100010];
int main(){
    Moblus();
    int n,i,j,k;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i],tong[a[i]]++;
    for(i=2;i<=1e5;i++){
        for(j=1;j*j<i;j++){
            if(i%j==0){
                sv[j]+=tong[i];
                sv[i/j]+=tong[i];
            }
        }
        if(j*j==i)sv[j]+=tong[i];
    }
    ll res=0;
    for(i=2;i<=1e5;i++){
       // cout<<sv[i]<<endl;
        res+=mu[i]*(power(2,sv[i])-1);
    }
    cout<<(res%mod+mod)%mod;
}

J 小红的心愿

知识点：无

签到题，直接输出10即可通过。

#include<bits stdc++.h>
using namespace std;
int main(){
    cout<<10;
}

K 小红的树

知识点：dfs

这道题按题意建树然后搜索就可以了，用一个数组来存它子树红色节点的数量。

#include<bits/stdc++.h>
using namespace std;
vector<int>g[100020];
int dp[100010];
string s;
int dfs(int x){
    int i,sum=s[x-1]=='R';
    for(i=0;i<g[x].size();i++){
        sum+=dfs(g[x][i]);
    }
    return dp[x]=sum;
}
int main(){
    int n,i;
    cin>>n;
    for(i=2;i<=n;i++){
        int x;
        cin>>x;
        g[x].push_back(i);
    }

    cin>>s;
    dp[1]=dfs(1);
    int q;
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        cout<<dp[x]<<endl;
    }

}

l 重排字符串

知识点：构造

判断字符串能否构造的方法很简单：设出现次数最多的字母出现次数为 $x$ ，判断 $\frac {len(str)+1}{2}$ 和 $x$ 的大小关系即可。

构造的方法有很多，这里介绍两种：

①先按字母出现次数降序排序，然后在一个二维数组竖着排，横着输出。

②找到出现次数最大的字母c1和次大的字母c2，然后按照 c1->(非c1非c2)->c1->(非c1非c2)……以上顺序进行构造，直到c1和c2出现次数相等。之后按字母表顺序进行构造即可。

下面给出第二种构造方法的代码：

#include<bits/stdc++.h>
using namespace std;
int tong[26]={0};
int main(){
    int n,i,j;
    string s;
    cin>>n>>s;
    for(i=0;i<s.length();i++)tong[s[i]-'a']++;
    int ma=0,m1=0;
    vector<int>temp;
    for(i=0;i<26;i++){
        temp.push_back(tong[i]);
        if(ma<tong[i])ma=tong[i],m1=i;
    }
    sort(temp.begin(),temp.end());
    int cd=temp[24];

    for(i=0;i<26;i++)if(tong[i]==cd)break;

    int ttemp=i;
  //  cout<<ma<<" "<<n<<endl;
    if(ma>(n+1)/2){cout<<"no";return 0;}
    int temp1;
    int jud=0;
    cout<<"yes\n";
    while(ma>cd){
        cout<<(char('a'+m1));
        temp1=m1;
        tong[m1]--;
        for(i=0;i<26;i++){
            if(tong[i]&&i!=m1&&i!=ttemp){
                cout<<(char('a'+i));
                temp1=i;
                tong[i]--;
                break;
            }


        }
        ma--;

    }

    for(j=0;j<n;j++)
    for(i=temp1+1;i<temp1+27;i++){
        if(tong[i%26]){
            tong[i%26]--;
            cout<<char('a'+i%26);
        }
    }

}