清华计科考研2022复试机考-调剂

发表于 分类于

22年调剂机考整体难度较低。T3大模拟较费心力，但难度不大。

  • T1: 模拟
  • T2: DP
  • T3: 大模拟

传送门

T1 总k次方差

求$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} | a_i-a_j |$

签到题，排序后动态维护前缀和即可。

时间复杂度$O(n \log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[100010],s;
long long ans;
int main()
{
    scanf("%d%*d",&n);
    for(int i=1;i<=n;++i) scanf("%d",a+i),s+=a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i) ans=(ans+s-(1ll*a[i]*(n-i+1)))%998244353,s-=a[i];
    printf("%lld\n",ans<<1);
    return 0;
}

T2 考试

$s_i=0$时，$s_{i+1}=2$；$s_i=1$时，$s_{i+1}=3$；$s_i=2$时，$s_{i+1}=0/4$；$s_i=3$时，$s_{i+1}=2/3$。求$s_1=1$时长度为$n$的$s$有多少种可能情况。

令$f_{i,0/1/2/3}$表示长度为$i$的$s$，$s_i=0/1/2/3$的可能情况个数。DP方程参见代码12-15行。

时间复杂度$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
long long f[10001][4];
int main()
{
    scanf("%d",&n);
    f[1][0]=1;
    for(int i=2;i<=n;++i)
    {
        f[i][0]=f[i-1][2];
        f[i][1]=f[i-1][3];
        f[i][2]=(f[i-1][0]+f[i-1][3])%7654321;
        f[i][3]=(f[i-1][1]+f[i-1][2])%7654321;
    }
    printf("%lld\n",(f[n][0]+f[n][1]+f[n][2]+f[n][3])%7654321);
    return 0;
}

T3 租约机制

稍稍有点费时费神的大模拟，依题意作答即可。需要注意的是，题目要求同一时间有读有写时先写后读，但输入数据并不满足这一特征，故在处理时分别存储读写请求，用双指针进行矫正即可。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k,d;
int contract[100010];
int status; // 0:正常 1:更新
int endtime;

int t[2][1000010],x[2][1000010],cnt[2];

void calc(char mode, int t,int x)
{
    if(status!=0&&t>endtime) status=0;
    if(mode=='R')
    {
        if(t<=contract[x]) printf("B\n");
        else if(status==0) contract[x]=contract[0]=t+k,printf("RWB\n");
        else if(t<=contract[0])  contract[x]=contract[0],printf("RWB\n");
        else printf("RB\n");
    }
    else
    {
        if(status==0)
        {
            status=1;
            endtime=max(t+d-1,contract[0]+d);
        }
        else endtime+=d;
    }
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&d);
    memset(contract,-1,sizeof(contract));
    int tt,tx;
    char mode;
    while(m--)
    {
        scanf("%s%d%d",&mode,&tt,&tx);
        t[mode=='W'][++cnt[mode=='W']]=tt,x[mode=='W'][cnt[mode=='W']]=tx;
    }
    int it[2]={1,1};
    while(it[0]<=cnt[0]||it[1]<=cnt[1])
    {
        while(it[1]<=cnt[1]&&t[1][it[1]]<=t[0][it[0]]) calc('W',t[1][it[1]],x[1][it[1]]),++it[1];
        if(it[0]<=cnt[0]) calc('R',t[0][it[0]],x[0][it[0]]),++it[0];
    }
    return 0;
}