2021年9月20日模拟赛总结

这次考的是思维题,只做出了雨水

思维不够敏捷，要练

第一题：0

第二题：31（最高分56）

第三题：100

第四题：5

总分：136

排名：19

赛后AK

凑数2526

题义：

一个长度为$n+m+k$，包含$n$个数字$2$，$m$个数字$5$和$k$个数字$6$的序列，最多可能有多少个子序列是$2526$？

如果一个序列是数组的子序列，当且仅当这个序列可以由数组删去任意个元素，再将数组中的剩余元素按顺序排列而成。

推导：

思维题，若想最大，要均分$n$，$n/2$和$a-n/2$

比赛时想成排列组合了，Zero

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long t,a,b,c;
    scanf("%lld",&t);
    for(int i=1;i<=t;i++)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        printf("%lld\n",(a/2)*(a-a/2)*b*c);
    }
}

以后要好好分析，不要想复杂

最小乘积

题义：

在区间$[L,R]$中找两个不同的数，使得它们的乘积模2019最小

推导：

同样是水题

如果$r-l >2019$,中间必然有$2019$的倍数，输出0

然后直接枚举$2019*2019$不会爆，

比赛时的错误太羞耻了，过过过

代码：

#include <bits/stdc++.h>
using namespace std;
long long l, r, mn=1e11;
int main() {
    cin >> l >> r;
    if (r - l >= 2017 ) {
        cout << 0 << endl;
        return 0;
    }
    for (long long i = l; i <= r; i++) {
        for (long long j = i + 1; j <= r; j++) {
            mn = min(mn, i % 2019 * j % 2019);
        }
    }
    cout << mn << endl;
}

雨水

题义：

有$n$座山成环，$n$是奇数,两座山之间有一个水坝。

第$i$座山和第$i+1$座山之间的水坝称为第i个水坝。

第$n+1$座山也是第$1$座山，第$n+1$个水坝也是第$1$个水坝。

如果第i座山降雨量为$f_i$，则它的降雨量会平均地分到相邻两座水坝去。

假设水坝的水全是由山上的降雨提供。

现在给出每一座水坝收到的水量，问每座山的降雨量。

推导：

$a$已知，$f$未知

根据题义得

$a_i=(f_i+f_{i+1})/2$

交换得

$2*a_i=(f_i+f_{i+1})$

则

$f_i=2*a_i-f_{i+1}$

然后是重头戏

因为公式中有个未知数代码，要求$n$个公式，肯定不能For

能不能没有未知数？

以$n=3$为例，我们尝试消除未知数

求 $f_1$ 时，将 $f_2$ 的算式带入，求 $f_2$ 时,将$f_3$的算式带入

得

$f_1=2*a_1-2*a_2+2*a_3-f_1$

得

$2f_1=2*a_1-2*a_2+2*a_3$

得

$f_1=a_1-a_2+a_3$

Great!

推出其他未知数

有了$f_1$ 我们可以推出其他未知数

先推出 $f_n$,再倒退其他

代码：

先求$f_1$

根据上面的公式,奇数加，偶数减

    for(int i=1;i<=n;i++)
    {
        if(i%2==1)
        {
            f[1]+=a[i];
        }
        else
        {
            f[1]-=a[i];
        }
    }

求$f_n$,倒退

    f[n]=2*a[n]-f[1];
    for(int i=n-1;i>=1;i--)
    {
        f[i]=2*a[i]-f[i+1];
    }

完整代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],f[100005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(i%2==1)
        {
            f[1]+=a[i];
        }
        else
        {
            f[1]-=a[i];
        }
    }
    f[n]=2*a[n]-f[1];
    for(int i=n-1;i>=1;i--)
    {
        f[i]=2*a[i]-f[i+1];
    }
    for(int i=1;i<=n;i++)
    {
        cout<<f[i]<<' ';
    }
}

染色：

题义：

有一棵树，包含n个点，现在你要对所有的点染色，你一共有K种颜色。

两个距离小于等于2的不同顶点，它们必须染成不一样的颜色。

问有多少种染色的方案

推导：

DFS即可，实现难，但是思路还是很水的，直接模拟

代码：

请认真看批注！！

#include<bits/stdc++.h>
using namespace std;
struct node
{
    long long t,next;//前向星
}a[1000005];
long long n,k,x,y,t,h[1000005],b[1000005],flag,ans=1;
void add(int x,int y)//加边
{
    t++;
    a[t].t=y;
    a[t].next=h[x];
    h[x]=t;
}
void dfs(int x,int y,int z)
{
    ans*=k-y-z;//乘上可选方案数
    ans%=1000000007;
    int t=0;//表示兄弟数
    b[x]=1;//b表示是否到达过
    for(int i=h[x];i>0;i=a[i].next)
    {
        if(b[a[i].t]==0)
        {
            if(y+1<=2)//如果不是根或根的儿子，y=2，否则y+1
            {
                dfs(a[i].t,y+1,t);
            }
            else
            {
                dfs(a[i].t,y,t);
            }
            t++;       
        }

    }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n-1;i++)
    {
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,0,0);
    if(flag)//想一想，这个有什么用？
    {
        cout<<0<<endl;
        return 0;
    }
    cout<<ans<<endl;
}