2019-09-28 普及模拟赛 题解

发表于 分类于

出给学弟的普及模拟赛，现在题解搬到这里来，估计也没人看了，坟贴一个。

T1 函数(function)

题意

给定两个自变量是 xx 因变量是 yy 的函数，这两个函数有可能为二次函数、一次函数或常函数。求两个函数图像交点个数。

对于 100%100\% 的数据，保证两个函数中每项的系数的绝对值不超过 100100。

算法一

基础题，注意判断为直线或者抛物线，再注意一下交点有无数个的情况，期望得分 100100 分。

Code

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
#include <stdio.h>
using namespace std;

int a,b,c,a1,b1,c1,D;

int main()
{
    freopen("function.in","r",stdin),freopen("function.out","w",stdout);

    scanf("%d%d%d%d%d%d",&a,&b,&c,&a1,&b1,&c1),a-=a1,b-=b1,c-=c1;

    if (a==0)
    {
        if (b==0)
        {
            if (c==0) printf("W");
            else printf("0");
        }
        else printf("1");
    }
    else
    {
        D=b*b-4*a*c;
        if (D<0) printf("0");
        if (D==0) printf("1");
        if (D>0) printf("2");
    }
    
    return 0;
}

T2 麻将(majiang)

题意

有一种新型的麻将，这麻将没有饼条万这样的花色，只有一种花色，也没有字牌；序数也不限于 11 到 99 ，而是在 11 到 nn 的范围内。

关于新型麻将的概念：

胡牌：即完成的牌，由 3m+23m+2 张牌组成，其中有一个对子（两张一样的牌）和 mm 个顺子（三张序数相连的序数牌，如 234234 、 678678 ）或刻子（三张一样的牌）。

听牌：一组听牌的牌是指一组 3m+13m+1 张牌，且再加上某一张牌就可以组成胡牌。那一张加上的牌可以称为等待牌。

判断一副牌是不是听牌，若是，找出所有的等待牌。

对于 70%70\% 的数据，n≤200,m≤800n \le 200,m \le 800。
对于 100%100\% 的数据，9≤n≤400,4≤m≤10009≤n≤400,4≤m≤1000。

算法一

用深搜来寻找答案，我们先枚举每一张听牌，那么很显然，时间复杂度就是 O(n)O(n)， 再用深搜来判断可否胡牌。

我们用 cntxcnt_x 来表示数值为 xx 的牌出现了多少次。那么我们就从 11 到 nn 枚举对子，再枚举刻子和顺子。那么深搜的时间复杂度是 O(2n2)O(2n^2)，合起来就是 O(2n3)(2n^3)，空间复杂度为 O(n)O(n)，期望得分 7070 分。

算法二

先枚举对子。

这是为何？两个原因：

  • 先凑出对子，听的牌如果是顺子就可能有两张听牌。
  • 确定对子容易确定自己的顺子或刻子要怎么拼凑。

枚举对子后，因为剩下的都是三张三张的，就容易枚举了，直接考虑刻子和顺子的两种情况即可。时间复杂度为 O(n3)O(n^3)，空间复杂度为 O(n)O(n)，期望得分 100100 分。

Code

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
#include <stdio.h>
#define il inline
using namespace std;
const int N=4005;

int n,m,tuc[N],tuf[N];

il int check()
{
    int i,j,o;
    for (i=1; i<=n; i++) if (tuc[i]>=2)
    {
        for (j=o=1,tuc[i]-=2; j<=n+2; j++) tuf[j]=tuc[j];
        for (j=1; j<=n+2; j++)
        {
            if (tuf[j]<0){o=0;break;}
            tuf[j]%=3,tuf[j+1]-=tuf[j],tuf[j+2]-=tuf[j];
        }  
        tuc[i]+=2; 
        if (o) return 1;
    }
    return 0;
}

int main()
{
    freopen("majiang.in","r",stdin),freopen("majiang.out","w",stdout);

    scanf("%d%d",&n,&m); int i,x,o=0;
    for (i=1; i<=3*m+1; i++) scanf("%d",&x),tuc[x]++;
    for (i=1; i<=n; i++)
    {
        tuc[i]++;
        if (check()) o=1,printf("%d ",i); 
        tuc[i]--;
    }
    if (!o) puts("NO");
    
    return 0;
}

T3 交作业(homework)

题意

一个人带着若干个物品奔跑，速度为每秒一个单位长度。有 nn 个站点，第 ii 个站点在位置 sis_i 处，这个人要将 hih_i 个物品放到此处，放下后这个人就不在带着这些物品奔跑了。

在时刻 tt 把物品放到 ii 站点处会增加 fi×tf_i\times t 的疲劳值，带着 kk 个物品奔跑一个单位长度会增加 kk 的疲劳值。

对于 20%20\% 的数据，n≤20n≤20。
对于 70%70\% 的数据，n≤100n≤100。
对于 100%100\% 的数据，n≤1000,∣si∣≤100,1≤hi,fi≤40n\le 1000,|s_i|≤100,1≤h_i,f_i≤40。

算法一

暴力深搜，每次枚举往左走或者往右走，时间复杂度为 O(2n)O(2^n)，空间复杂度为 O(n)O(n)，期望得分 2020 分。

算法二

首先肯定先以 ss 为关键字排序。

很显然的一点，如果你经过一个站点却不放东西一定不是最优的。那么不论何时，已经处理好的站点的编号一定是一个连续的区间。

自然联想到区间 DP。设 dpi,jdp_{i,j} 表示编号从 ii 到 jj 的站点都处理好时的最小疲惫值。但还有是在左边还是在右边的问题，于是再来一维： dpi,j,0/1dp_{i,j,0/1} 表示编号从 ii 到 jj 的老师都处理好且处在 ii 或 jj 时的最小疲惫值。

dpi,j,1/0dp_{i,j,1/0} 显然可以由 dpi+1,j,1/0dp_{i+1,j,1/0} 或 dpi,j−1,1/0dp_{i,j-1,1/0} 转移过来。 设 HiH_i 表示 hih_i 的前缀和，FiF_i 表示 fif_i 的前缀和。那么如果第 ii 到 jj 个站点已经处理完，此时带着 Hn−Hi−1+HjH_n-H_{i-1}+H_j 个物品，并且每秒疲劳值会增加 Fn−Fi−1+FjF_n-F_{i-1}+F_j 次。于是有转移方程：

fi,j,0=min⁡{fi+1,j,0+(si+1−si)(Fn−Fi+Fj+Hn−Hi+Hj),fi+1,j,1+(sj−si)(Fn−Fi+Fj+Hn−Hi+Hj)}f_{i,j,0}=\min\{f_{i+1,j,0}+(s_{i+1}-s_i)(F_n-F_i+F_j+H_n-H_i+H_j),f_{i+1,j,1}+(s_j-s_i)(F_n-F_i+F_j+H_n-H_i+H_j)\}

剩下的同理，DP 的复杂度为 O(n2)O(n^2)。

我们枚举一下出发点，总时间复杂度 O(n3)O(n^3)，空间复杂度为 O(n2)O(n^2)，期望得分 7070 分。

算法三

发现根本不需要枚举出发点，直接将 fi,i,1/0f_{i,i,1/0} 全部设为 00，然后 DP 即可，时空复杂度均为 O(n2)O(n^2)，期望得分 100100 分。

Code

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define il inline
#define int long long
using namespace std;
const int N=1005,I=0X3f3f3f3f;

int n,F[N],H[N],f[N][N][2];
struct teacher{int s,h,f;}t[N];

il bool cmp(teacher a,teacher b){return a.s<b.s;}

signed main()
{
    freopen("homework.in","r",stdin),freopen("homework.out","w",stdout); 
	
    scanf("%lld",&n); int i,j,l;
    for (i=1; i<=n; i++) scanf("%lld%lld%lld",&t[i].s,&t[i].h,&t[i].f);
    sort(t+1,t+n+1,cmp);
    for (i=1; i<=n; i++) F[i]=F[i-1]+t[i].f,H[i]=H[i-1]+t[i].h;
    memset(f,I,sizeof f);
    for (i=1; i<=n; i++) f[i][i][0]=f[i][i][1]=0;
	
    for (l=2; l<=n; l++) for (i=1; (j=i+l-1)<=n; i++)
        f[i][j][0]=min(f[i+1][j][0]+(t[i+1].s-t[i].s)*(F[i]+F[n]-F[j]+H[i]+H[n]-H[j]),f[i+1][j][1]+(t[j].s-t[i].s)*(F[i]+F[n]-F[j]+H[i]+H[n]-H[j])),
        f[i][j][1]=min(f[i][j-1][1]+(t[j].s-t[j-1].s)*(F[i-1]+F[n]-F[j-1]+H[i-1]+H[n]-H[j-1]),f[i][j-1][0]+(t[j].s-t[i].s)*(F[i-1]+F[n]-F[j-1]+H[i-1]+H[n]-H[j-1]));
	
    printf("%lld",min(f[1][n][0],f[1][n][1]));
    
    return 0;
}

T4 数列的 F(seriesf)

改编自 2019 高中数学联赛二试第二题。

题意

有一个长度为 nn 的整数数列 ai{a_i} ，且满足 1=a1≤a2≤⋯≤an−1≤an=m1=a_1≤a_2≤\cdots≤a_{n-1}≤a_n=m 。

记 f=(a12+a22+⋯+an−12+an2)−(a1a3+a2a4+⋯+an−2an)f=(a_1^2+a_2^2+\cdots+a_{n-1}^2+a_n^2)-(a_1a_3+a_2a_4+\cdots+a_{n-2}a_n) 。

求出 ff 的最小值 f0f_0 ，并求出使 f=f0f=f_0 成立的 nn 元组 (a1,a2,…,an−1,an)(a_1,a_2,\ldots,a_{n-1},a_n) 的个数。

两个数都模 10000000071000000007。

对于 50%50\% 的数据，m=5,5≤n≤10m=5,5≤n≤10。
对于 100%100\% 的数据，5≤m≤n≤1000005≤m≤n≤100000 且 mm 为奇数。

算法一

直接暴力搜索每个位置填上什么数，时间复杂度为 O(mn)O(m^n)，空间复杂度为 O(n)O(n)，期望得分 5050 分。

算法二

以下是 恐怖的 数学推导。

由已知：

2f=a12+a22+an−12+an2+∑i=1n−2(ai+2−ai)22f=a_1^2+a_2^2+a_{n-1}^2+a_n^2+\sum\limits_{i=1}^{n-2}{(a_{i+2}-a_i)^2}

因为 ai(i=1,2,⋯ ,n)a_i(i=1,2,\cdots,n) 为整数且 1=a1≤a2≤⋯≤an−1≤an=m1=a_1\le a_2\le \cdots\le a_{n-1}\le a_n=m，
所以显然：

(ai+2−ai)2≥ai+2−ai,a12≥a1,a22≥a2(a_{i+2}-a_i)^2\ge a_{i+2}-a_i,a_1^2\ge a_1,a_2^2\ge a_2

那么：

a12+a22+∑i=1n−3(ai+2−ai)2≤a1+a2+∑i=1n−3(ai+2−ai)=an−2−an−1a_1^2+a_2^2+\sum\limits_{i=1}^{n-3}{(a_{i+2}-a_i)^2}\le a_1+a_2+\sum\limits_{i=1}^{n-3}{(a_{i+2}-a_i)}=a_{n-2}-a_{n-1}

再结合 an−2≤an−1≤an=ma_{n-2}\le a_{n-1}\le a_n=m 便有：

2f≥(an−an−2)2+an−12+an2+an−2+an−1≥(m−an−2)2+an−22+m2+2an−22f\ge (a_n-a_{n-2})^2+a_{n-1}^2+a_n^2+a_{n-2}+a_{n-1}\ge (m-a_{n-2})^2+a_{n-2}^2+m^2+2a_{n-2}

f≥12(m2−2man−2+an−22+m2+2an−2)=an−22−(m−1)an−2+m2=(an−2−m−12)2+3m2+2m−14f\ge \frac{1}{2}(m^2-2ma_{n-2}+a_{n-2}^2+m^2+2a_{n-2})=a_{n-2}^2-(m-1)a_{n-2}+m^2=(a_{n-2}-\frac{m-1}{2})^2+\frac{3m^2+2m-1}{4}

又因为 mm 为奇数，所以 m−12\frac{m-1}{2} 与 3m2+2m−14\frac{3m^2+2m-1}{4} 均为整数。故当 a1=a2=1,an−1=an=m−12a_1=a_2=1,a_{n-1}=a_n=\frac{m-1}{2} 且 ai+2−ai∈{0,1}(i=1,2,⋯ ,n−3)a_{i+2}-a_i\in \{0,1\}(i=1,2,\cdots,n-3) 时，ff 有最小值 f0=3m2+2m−14f_0=\frac{3m^2+2m-1}{4}。

考虑组数，若要使等号成立，则要有 1=a1≤a2≤⋯≤an−1=m−121=a_1\le a_2\le \cdots\le a_{n-1}=\frac{m-1}{2}，并且对于每个 k(1≤k≤m−12)k(1\le k\le \frac{m-1}{2})，a1,a2,⋯ ,an−1a_1,a_2,\cdots,a_{n-1} 中至少有两项等于 kk，易证这和上面的取等条件是等价的。
对于每个 k(1≤k≤m−12)k(1\le k\le \frac{m-1}{2})，设 a1,a2,⋯ ,an−1a_1,a_2,\cdots,a_{n-1} 中等于 kk 的项数为 1+gk1+g_k，gkg_k 是正整数。
则有 (1+g1)+(1+g2)+⋯+(1+gm−12)=n−1(1+g_1)+(1+g_2)+\cdots+(1+g_{\frac{m-1}{2}})=n-1，即 g1+g2+⋯+gm−12=2n−m−32g_1+g_2+\cdots+g_{\frac{m-1}{2}}=\frac{2n-m-3}{2}。
使等式成立的 m−12\frac{m-1}{2} 元组 (g1,g2,⋯ ,gm−12)(g_1,g_2,\cdots,g_{\frac{m-1}{2}}) 的个数为 (m−122n−m−32)\dbinom{\frac{m-1}{2}}{\frac{2n-m-3}{2}},且每个 (g1,g2,⋯ ,gm−12)(g_1,g_2,\cdots,g_{\frac{m-1}{2}}) 对应唯一的一个 (a1,a2,⋯ ,an)(a_1,a_2,\cdots,a_n)，所以组数是 (m−122n−m−32)\dbinom{\frac{m-1}{2}}{\frac{2n-m-3}{2}}。

然后我们就做完了这个大结论题 (逃），期望得分 100100 分。

Code

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
#include <stdio.h>
#define il inline
#define int long long
#define N 100001
using namespace std;
const int mod=1e9+7; 

int n,m,fac[N],iac[N];

il int ksm(int a,int b)
{
	int res=1;
	for ( ; b; b>>=1,a=a*a%mod) if (b&1) res=res*a%mod;
	return res;
}
il int C(int x,int y){return fac[x]*iac[y]%mod*iac[x-y]%mod;}

signed main()
{
    freopen("seriesf.in","r",stdin),freopen("seriesf.out","w",stdout);

    scanf("%lld%lld",&n,&m);
    int i;
    for (i=fac[0]=1; i<N; i++) fac[i]=fac[i-1]*i%mod;
    for (i=n,iac[n]=ksm(fac[n],mod-2); i>=1; i--) iac[i-1]=iac[i]*i%mod;
    
	printf("%lld\n%lld",(3ll*m*m+2ll*m-1ll)/4%mod,C((2*n-m-3)/2,(m-3)/2)); 
    
	return 0;
}