Codeforces Round #539 (1113,1109) 个人题解

Author： xzm2019
发布时间：February 17, 2019
3216views
No comments
975字数
Categories：算法

| Upsolved |  2A  |  2B  | 2C/1A | 2D/1B | 2E/1C | 2F/1D |  1E  |  1F  |
| :------: | :--: | :--: | :---: | :---: | :---: | :---: | :--: | :--: |
|   5/8    |  Ø   |  Ø   |   Ø   |   Ø   |   .   |   Ø   |  .   |  .   |

- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet

## Problem 2A ([1113A][1])

> 你要跑一段长度为$n(2 \leq n \leq 100)$的路，你起始在1号位置，你的油箱容量最大是$v(1 \leq v \leq 100)$，在第$i$个点加油油价是$i$元/升，每升油可以跑1km，问最少花费。

很显然，在第一个点把油箱加满，并且在后面每个点都及时补充油量即可，由于$n$范围较小，可以用循环代替等差数列求和。

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

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    long long ans=min(m,n-1);
    for (int i=2;i<=n-m;i++)
        ans+=i;
    printf("%lld\n",ans);
    return 0;
}
```

## Problem 2B ([1113B][2])

> 给你一个长度为$n(2 \leq n \leq 5\cdot10^4)$的序列，每个数在1至100之间。你可以讲其中一个数$/x$并使另一个数$*x$，求操作后的序列的和的最小值。

显然，乘法一定是做在最小的数上面的，只要枚举除法是哪一个数的哪一个因子即可。

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

int a[50005];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int sum=0;
    for (int i=1;i<=n;i++) sum+=a[i];
    int ans=sum;
    for (int i=2;i<=n;i++)
    {
        for (int j=2;j<a[i];j++)
            if (a[i]%j==0)
            {
                ans=min(ans,sum-a[i]-a[1]+j+a[1]*(a[i]/j));
            }
    }
    printf("%d\n",ans);
    return 0;
}
```

## Problem 2C/1A ([1113C][3]/[1109A][4])

> 给你一个长度为$n(2 \leq n \leq 3\cdot10^5)$的序列，求出其中长度为偶数并且前半段的异或和等于后半段的异或和的子序列的个数。

显然，如果前半段的异或和等于后半段的异或和，那么整段的异或和就是0。因此，只要做前缀异或和找出相等的位置即可。

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

pair<int,int> pre[300005];
int cnt[2];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&pre[i].first);
        pre[i].first^=pre[i-1].first;
        pre[i].second=i;
    }
    sort(pre+1,pre+n+1);
    int last=0; cnt[0]=1;
    pre[n+1].first=pre[n].first+1;
    long long ans=0;
    for (int i=1;i<=n+1;i++)
    {
        if (pre[i].first==pre[i-1].first)
        {
            cnt[pre[i].second%2]++;
        }
        else
        {
            ans+=1LL*cnt[0]*(cnt[0]-1)/2+1LL*cnt[1]*(cnt[1]-1)/2;
            memset(cnt,0,sizeof(cnt));
            cnt[pre[i].second%2]++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}
```

## Problem 2D/1B ([1113D][5]/[1109B][6])

> 给你一个字符串$s(1 \leq |s| \leq 5\,000)$，问最少需要割几下使得切割下来的重拼起来还是回文串且和原串不同。如果不可能，请输出`Impossible`。

显然，当且仅当字符串是`aaaaa`或者`aabaa`的形式的时候，答案是`Impossible`。否则的话答案一定是1或2。

- 答案一定$\leq 2$。假设字符串是`aaabcddcbaaa`的形式，前后切割`aaab`和`baaa`然后交换，形成`baaacddcaaab`，符合条件。
- 当存在可以循环回文的时候，答案为1，如题目样例4所示。

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

char s[10005];
bool isok(char *t,int len)
{
    for (int i=0,j=len-1;i<=j;i++,j--)
        if (t[i]!=t[j]) return false;
    for (int i=0;i<len;i++)
        if (t[i]!=s[i]) return true;
    return false;
}
int main()
{
    scanf("%s",s);
    int cnt=0;
    for (int i=1;s[i];i++)
        if (s[i]!=s[0]) cnt++;
    if (cnt<=1)
        return printf("Impossible\n"),0;
    int len=strlen(s);
    for (int i=0;i<len;i++) s[len+i]=s[i];
    for (int i=1;i<len;i++)
        if (isok(s+i,len))
            return printf("1\n"),0;
    printf("2\n");
    return 0;
}
```

## Problem 2F/1D ([1113F][7]/[1109D][8])

> $n(2 \leq n \leq 10^6)$个点的一棵树，每条边的权值范围是$[1,m](1 \leq m \leq 10^6)$，要求给定两点的树上最短距离是$m$，求方案数对$1\,000\,000\,007$取模的值。

其实很显然答案和点编号无关，只需要枚举这两点间有几条边构成，答案就是$\sum$每种边数对应的答案。

对于每种边数（假设有$x$条边）对应的答案，用乘法原理考虑：

- 设其边权分别为$c_1,c_2,\cdots,c_x$，则其形成了一个不定方程$c_1+c_2+\cdots+c_x=m(x \leq m)$，根据隔板法，可以得知，其整数解的个数是$C_{m-1}^{x-1}$。
- 考虑其中路径上的点，一共要在$n-2$个点中选出$x-1$个点形成排列，其方案数是$A_{n-2}^{x-1}$。
- 对于剩下的边，每个边的边权是任意的，所以方案数是$m^{n-x-1}$。
- 最后一个问题，就是要把剩下的点连接到原路径的方案数。我们可以先不考虑已经确定的$x$条边，剩下的相当于是由$n$个点，形成一个有$x+1$个联通快的森林的方案数。根据[凯莱公式的一般形式][9]，可以知道，答案是
  - $(x+1)\cdot n^{n-x-2},x+1<n$
  - $1,x+1=n$

综上，使用乘法原理把几部分相乘即可。

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

const int maxn=1'000'005,mod=1'000'000'007;
long long fac[maxn],inv[maxn];
long long qpow(long long a,long long n)
{
    long long ret=1;
    while (n)
    {
        if (n&1) ret=ret*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ret;
}
void init(int n)
{
    fac[0]=1;
    for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2);
    for (int i=n;i>0;i--)
        inv[i-1]=inv[i]*i%mod;
}
inline long long C(int n,int m)
{
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline long long A(int n,int m)
{
    return fac[n]*inv[n-m]%mod;
}
inline long long f(int x,int y)
{
    if (x==y) return 1;
    return 1LL*y*qpow(x,x-y-1)%mod;
}
int main()
{
    init(1'000'000);
    int n,m,a,b;
    scanf("%d%d%d%d",&n,&m,&a,&b);
    long long ans=0;
    for (int i=1;i<=n-1&&i<=m;i++)
    {
        long long cur=0;
        cur=A(n-2,i-1)*f(n,i+1)%mod;
        cur=cur*C(m-1,i-1)%mod;
        cur=cur*qpow(m,n-i-1)%mod;
        ans+=cur;
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}
```
[1]: https://codeforces.com/contest/1113/problem/A
[2]: https://codeforces.com/contest/1113/problem/B
[3]: https://codeforces.com/contest/1113/problem/C
[4]: https://codeforces.com/contest/1109/problem/A
[5]: https://codeforces.com/contest/1113/problem/D
[6]: https://codeforces.com/contest/1109/problem/B
[7]: https://codeforces.com/contest/1113/problem/F
[8]: https://codeforces.com/contest/1109/problem/D
[9]: https://bit.ly/2S1EWbr

Last modification：February 28th, 2019 at 09:27 am

If you think my article is useful to you, please feel free to appreciate

Comment *

私密评论

Name *

Email *

Site

Codeforces Round #539 (1113,1109) 个人题解

xzm2019 • 2019 年 02 月 17 日

- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet

## Problem 2A ([1113A][1])

很显然，在第一个点把油箱加满，并且在后面每个点都及时补充油量即可，由于$n$范围较小，可以用循环代替等差数列求和。

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

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    long long ans=min(m,n-1);
    for (int i=2;i<=n-m;i++)
        ans+=i;
    printf("%lld\n",ans);
    return 0;
}
```

## Problem 2B ([1113B][2])

> 给你一个长度为$n(2 \leq n \leq 5\cdot10^4)$的序列，每个数在1至100之间。你可以讲其中一个数$/x$并使另一个数$*x$，求操作后的序列的和的最小值。

显然，乘法一定是做在最小的数上面的，只要枚举除法是哪一个数的哪一个因子即可。

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

## Problem 2C/1A ([1113C][3]/[1109A][4])

> 给你一个长度为$n(2 \leq n \leq 3\cdot10^5)$的序列，求出其中长度为偶数并且前半段的异或和等于后半段的异或和的子序列的个数。

显然，如果前半段的异或和等于后半段的异或和，那么整段的异或和就是0。因此，只要做前缀异或和找出相等的位置即可。

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

## Problem 2D/1B ([1113D][5]/[1109B][6])

> 给你一个字符串$s(1 \leq |s| \leq 5\,000)$，问最少需要割几下使得切割下来的重拼起来还是回文串且和原串不同。如果不可能，请输出`Impossible`。

显然，当且仅当字符串是`aaaaa`或者`aabaa`的形式的时候，答案是`Impossible`。否则的话答案一定是1或2。

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

## Problem 2F/1D ([1113F][7]/[1109D][8])

> $n(2 \leq n \leq 10^6)$个点的一棵树，每条边的权值范围是$[1,m](1 \leq m \leq 10^6)$，要求给定两点的树上最短距离是$m$，求方案数对$1\,000\,000\,007$取模的值。

其实很显然答案和点编号无关，只需要枚举这两点间有几条边构成，答案就是$\sum$每种边数对应的答案。

对于每种边数（假设有$x$条边）对应的答案，用乘法原理考虑：

综上，使用乘法原理把几部分相乘即可。

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

Codeforces Round #539 (1113,1109) 个人题解

Leave a Comment

2019南昌邀请赛网络赛个人记录（附官方题解）

北京理工大学第七届程序设计新生赛题解（unofficial）

第 43 届 ACM/ICPC 亚洲区域赛（南京）总结

北京理工大学第八届程序设计新生赛题解

Beijing Institute of Technology 2019.6 Monthly Contest 题解

HQ Trivia UK 20180914 9pm BST 题目瞎扯

北京理工大学第八届程序设计新生赛（热身赛）题解

北京理工大学2020年蓝桥杯校内选拔赛题解

北京理工大学计算机学院科技创新创业基地2019年寒假集训算法总结赛题解

第十三届北邮校赛（2019）个人存档

Codeforces Round #539 (1113,1109) 个人题解