Codeforces Round #701 (Div. 2)补题

发表于 更新于 分类于 阅读次数：

Codeforces Round #701 (Div. 2)民间题解

Heltion题解

补完把这个看看https://zhuanlan.zhihu.com/p/268630329

还有这个https://codeforces.com/contest/842/problem/D

C.Floor and Mod

题意

给定两个整数$x$与$y$，求解对于$1\le i \le x$与$1\le j\le y$之间有多少对$(i,j)$满足$\left\lfloor\dfrac{i}{j}\right\rfloor=i %j$。

思路

考虑枚举余数$k$，即$\left\lfloor\dfrac{i}{j}\right\rfloor=i %j =k$，那么此时$i=k\times j +k$。

因为$k<j$，我们可以得到$k^2 < k \times j+k=i \le x$，所以$k \le \sqrt{x}$，即为枚举范围。

对于一个固定的余数$k$，考虑如何$O(1)$计算此时$(i,j)$的对数。

因为$j>k,1\le j\le y,i=k\times j+k$，所以$j \in [k+1,y]$，对于该区间内的每个$j$，都有一个固定的$i$，只要判断这个$i$值是否合法即$i\le x$即可。

第一种情况是$x$相当大而$y$比较小，此时$j \in [k+1,y]$区间都合法，对于此时的$k$有$y-k$对。

第二种情况是$[k+1,y]$后段存在超出$x$的$i$值，我们需要计算出对于上限$x$合法的最大$j$值，可以通过$\left\lfloor\dfrac{x-k}{k}\right\rfloor$计算得到，之后计算有效对数同样可以通过右端点减左端点得到。

代码

1
2
3
4
5
6
7
int solve(int x,int y)
{
    int ans=0,lim=sqrt(x);
    for(int k=1;k<=lim&&k<y;k++)
        ans+=max(0ll,min(y,x/k-1)-k);
    return ans;
}

D.Multiples and Power Differences

思路

构造题，很邪门的一道题。

$a$的范围只有$16$，计算$lcm(1,2,\dots 16)=720720 < 10^6$。

所以$b$中每个格子都可以填$720720$，但是因为相邻两个格子的差不能为$0$，猜测减去一个整数$x$的$4$次幂仍合法，枚举发现对于$[1,16]$全部合法，于是可以黑白格子染色来构造。

通过打表验证可以知道，是一个小范围的特殊结论……

1
2
3
4
5
6
7
8
9
10
for(int i=1,g=1;i<=100;i++)
{
    g=g*i/__gcd(g,i);
    for(int j=1;j<=i;j++)
        if((g-i*i*i*i)%i)
        {
            printf("NO:i=%d,j=%d\n",i,j);
            system("pause");
        }
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[maxn][maxn],b[maxn][maxn];
signed main(signed argc, char const *argv[])
{
    int n,m;
    fill(a[0],a[0]+maxn*maxn,1);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];//b[i][j]是a[i][j]的倍数
    for(int i=1;i<=16;i++)//验证
        if((720720-i*i*i*i)%i)
            cout<<"NO"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if((i&1)==(j&1))
                b[i][j]=720720;
            else
                b[i][j]=720720-a[i][j]*a[i][j]*a[i][j]*a[i][j];
            cout<<b[i][j]<<(j==m?'\n':' ');
        }
    }
    return 0;
}

E.Move and Swap

一个节点数目为$n$的无向有根树，根节点为$1$，每个叶子到根节点的距离为$d$。

第$2,3,\dots n$个节点都有权值$a_2,a_3,\dots n$。

有两个硬币$r$与$b$，初始在根节点。按如下步骤进行$d$次操作：

  • 将硬币$r$移至其任意一子节点。
  • 将硬币$b$移至某一节点$b’$，$b’$到节点$1$的距离等于$b$到节点$1$的距离$+1$。
  • 你可以选择交换$r$与$b$。

每一轮结束后你都会获得$|a_r-b_b|$的分数，求出$d$次操作后最大可获得分数。

思路

树形$dp$，每一轮相当于如下两个操作选一个

  • $r$向其子节点移动，$b$任意向下移动。
  • $b$移动到$r$的任一子节点，$r$任意向下移动。

可以发现硬币$b$的位置无关紧要，对下一步并无影响，因此$dp$时只记录硬币$r$的位置即可。

$dp[x]$表示$x$作为$r$所在点时向下面行走可以得到的最大价值，即所在那一层权值并未计入。

转移方程$dp[v]=dp[x]+|a_v-a_{next_b}|$，$a_{next_b}$是$b$向下移动一格的节点的权值。

可以在每一层预处理极值来进行$O(1)$转移。
$$
u是v的父节点,x是与v同一深度的任一节点 \
\begin{cases}
dp[u]=max(dp[v]+a[v]-a[x],dp[v]-a[v]+a[x]) &,r与b不交换 \
dp[u]=max(dp[x]+a[x]-a[v],dp[x]-a[v]+a[v]) &,r与b交换
\end{cases}
$$
按深度进行树形$dp$，学到很多。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> G[maxn],g[maxn];
ll a[maxn],dp[maxn];//dp[i]表示r在节点i得到的最大权值
int maxd=0,fa[maxn],depth[maxn];
void dfs(int x,int f)
{//
    depth[x]=depth[f]+1;
    fa[x]=f;
    maxd=max(maxd,depth[x]);
    for(auto &v:G[x])
    {
        if(v==f)
            continue;
        dfs(v,x);
    }
}
void bfs(int d)
{//dp[x]表示x作为r所在点时向下面行走可以得到的最大价值
    for(int i=d;i>1;i--)
    {
        ll MIN=INF,MAX=-INF;
        for(int &v:g[i])
        {//当前深度最大最小权值
            MIN=min(MIN,a[v]);
            MAX=max(MAX,a[v]);
        }
        for(int &v:g[i])//不交换
        {//r从v->u,找到这层最大/最小的点即为b最优点
            int u=fa[v];
            dp[u]=max(dp[u],dp[v]+max(a[v]-MIN,MAX-a[v]));
        }
        //dp[u]=dp[v]+max(a[v]-a[b],a[b]-a[v])
        //交换节点,r从v跳到上一层,而b则为r的父节点
        ll p1=-INF,p2=-INF;
        for(int &j:g[i])
        {//预处理
            p1=max(p1,dp[j]+a[j]);
            p2=max(p2,dp[j]-a[j]);
        }
        for(int &v:g[i])
        {//r从j跳到了v的父节点u,这里的v是b原来所在点
            int u=fa[v];
            dp[u]=max(dp[u],p1-a[v]);
            dp[u]=max(dp[u],p2+a[v]);
        }
    }
}
signed main(signed argc, char const *argv[])
{
    int t,n,x;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            G[i].clear();
            g[i].clear();
            dp[i]=depth[i]=0;
        }
        maxd=0;
        for(int i=2;i<=n;i++)
        {
            cin>>x;
            G[x].push_back(i);
        }
        for(int i=2;i<=n;i++)
            cin>>a[i];
        dfs(1,0);//预处理父子关系和深度
        for(int i=1;i<=n;i++)//按深度对节点分组
            g[depth[i]].push_back(i);
        bfs(maxd);
        cout<<dp[1]<<endl;
    }
    return 0;
}
/*
 *https://blog.csdn.net/Fighting_Peter/article/details/113799925
 *似乎要记录球所在位置
 *如果把过程逆过来看
 *计算权值->r走到父节点->b跳到一个距离更短的节点 ->是否交换
*/

F.Copy or Prefix Sum

给定一个长度为$n$的数组$b_1,b_2,\dots b_n$，你要构造长度为$n$的序列$a$，使得对于每一个$i(1\le i\le n)$，满足以下条件其一

  • $b_i=a_i$.
  • $b_i=\sum\limits_{j=1}^ia_j$.

求出符合条件的序列$a$的数目并对$10^9+7$取模。

思路

计数dp，请无视下面的胡言乱语从正难则反开始看。

因为负数是可以的，不会因为前缀和过大使第二个条件无法满足。所以如果两个条件都可满足的话，那么答案为$2^{n-1}$，但是因为可能会有数值相同（$\sum\limits_{j=1}^{i-1}a_j=0$），会有重复计算。

令$s[i]$为$a$数组下标为$[1,i]$的前缀和，那么有两种方案

$$
\begin{cases}
s[i]=b[i] &,b_i=\sum\limits_{j=1}^ia_j\
s[i]=s[i-1]+b[i] &,a_i=b_i
\end{cases}
$$

令$dp[i][j]$表示前$i$个数前缀和$s[i]$为$j$的方案数，$dp[0][0]=1$。

为了避免重复计算，我们在统计$i$的影响时

因为第二维数值范围会很大，使用map来节省空间，我为人人转移。

1
2
3
4
5
6
7
8
9
10
dp[0][0]=1;
for(int i=0;i<n;i++)
{
    for(int j)
    {//j=sum(a_1 ~ a_i)
        if(j!=0)//b_i=a_i
            dp[i+1][j+b_i] = dp[i][j];
        dp[i+1][b_i] = dp[i][j];//b_i = sum(a_1 ~ a_i)
    }
}

正难则反，尝试对需要排除的情况进行计数$dp$。

第一维可以用滚动数组优化掉，即$dp[i]$表示当前状态下前缀和为$i$的被排除的情况数目，而第二种情况只会在$s=0$时被更新。

当前情况数=上一步情况数$\times2-s_{i-1}=0$的情况数。

若我们尝试填$a_i$时，记之前的$\sum\limits_{j=1}^{i-1}a_j=s$，则$a_i=\begin{cases}b_i \ b_i-s &,s\ne 0\end{cases}$.

状态转移的方式一是一个区间平移，则我们维护一个全局位移$level$，$dp[level]$表示对于此时$s=0$的状态数目，这部分的贡献是一次而不是两次，乘$2$后要减去。

有点类似威尼斯集合的思想。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int b[maxn];
map<ll,ll>dp;
signed main(signed argc, char const *argv[])
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>b[i];
        dp.clear();
        dp[0]=1;
        int ans=1,level=0;
        for(int i=1;i<=n;i++)
        {
            int pre=ans;
            ans=(ans*2%mod-dp[level])%mod;
            dp[level]=pre%mod;
            level+=b[i];//维护水位
        }
        cout<<(ans+mod)%mod<<endl;
    }
    return 0;
}