清华计科考研2020复试机考

发表于 分类于

20年难度整体较低，仅T3稍有难度，但难度不大。

  • T1: 模拟
  • T2: 队列
  • T3: 分层图DP

传送门

T1 统计次数

计算$1 \sim n$这$n$个正整数十进制表示中$k$出现的次数。$n \le 10^6, 1\le k\le 9$

签到题，模拟即可。时间复杂度$O(n \log_{10}{n})$

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
int n,k,ans;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        for(int j=i;j;j/=10)
            ans+=j%10==k;
    printf("%d\n",ans);
    return 0;
}

T2 等差数列

输入一个矩阵，每一行每一列都是独立的等差数列，其中一些元素的值丢失了，需要尽可能地恢复丢失元素。$n, m \le 1000$

某行某列只要出现两个元素就能还原整行整列了，直接统计每行每列元素个数，嗯做即可。

但注意到，还原行可能带来新的可修复的列，而还原列可能带来新的可修复的行，如此往复。使用队列进行优化，每次还原时更新行列状态，满足条件时进队即可。

时间复杂度$O(nm)$

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
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 1010

int n,m,a[MAXN][MAXN];
vector<pair<int,int> >r[MAXN],c[MAXN];
vector<pair<pair<int,int>,int> >ans;
bool use[2][MAXN];
queue<pair<bool,int> >q;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j])
            {
                r[i].push_back(make_pair(j,a[i][j]));
                c[j].push_back(make_pair(i,a[i][j]));
            }
        }
    for(int i=1;i<=n;++i) if(r[i].size()>1) q.push(make_pair(0,i)),use[0][i]=true;
    for(int j=1;j<=m;++j) if(c[j].size()>1) q.push(make_pair(1,j)),use[1][j]=true;
    while(!q.empty())
    {
        pair<int,int> tmp=q.front();
        q.pop();
        if(!tmp.first)
        {
            int i=tmp.second;
            int step=(r[i][1].second-r[i][0].second)/(r[i][1].first-r[i][0].first);
            for(int j=1;j<=m;++j)
                if(!a[i][j])
                {
                    a[i][j]=r[i][0].second+step*(j-r[i][0].first);
                    ans.push_back(make_pair(make_pair(i,j),a[i][j]));
                    r[i].push_back(make_pair(j,a[i][j]));
                    c[j].push_back(make_pair(i,a[i][j]));
                    if(!use[0][i]&&r[i].size()>1) q.push(make_pair(0,i)),use[0][i]=true;
                    if(!use[1][j]&&c[j].size()>1) q.push(make_pair(1,j)),use[1][j]=true;
                }
        }
        else
        {
            int j=tmp.second;
            int step=(c[j][1].second-c[j][0].second)/(c[j][1].first-c[j][0].first);
            for(int i=1;i<=n;++i)
                if(!a[i][j])
                {
                    a[i][j]=c[j][0].second+step*(i-c[j][0].first);
                    ans.push_back(make_pair(make_pair(i,j),a[i][j]));
                    r[i].push_back(make_pair(j,a[i][j]));
                    c[j].push_back(make_pair(i,a[i][j]));
                    if(!use[0][i]&&r[i].size()>1) q.push(make_pair(0,i)),use[0][i]=true;
                    if(!use[1][j]&&c[j].size()>1) q.push(make_pair(1,j)),use[1][j]=true;
                }
        }
    }
    sort(ans.begin(),ans.end());
    for(auto it:ans) printf("%d %d %d\n",it.first.first, it.first.second, it.second);
    return 0;
}

T3 图

$n$个点$m$条边的有向图，点有点权边有边权，$q$次询问，每次询问从$u$开始走，路径总边权不超过$c$的最大途径点权和。多次路过边权和点权都重复计算。$n \le 2000, m \le 8000, q \le 10^5, c \le 800$

离线 + 分层图DP。

65分做法

询问离线，按$u$聚类。对于每个$u$，令$f_{i,j}$表示走到$i$代价不超过$j$的最大点权和，则有DP方程$f_{i,j}=\max(f_{k,j-dis(k,i)}+v_i)$，DP后求$\max(f_{i,y})$即可。

时间复杂度$O(kcm)$，其中$k$为不同$u$的个数。

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
// 65pts
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int> > to[2010];
int v[2010],ans[100010],f[2010][810];
vector<pair<pair<int,int>,int> >q;
int main()
{
    int n,m,cntq;
    int x,y,z;
    scanf("%d%d%d",&n,&m,&cntq);
    for(int i=1;i<=n;++i) scanf("%d",v+i);
    while(m--) scanf("%d%d%d",&x,&y,&z),to[x].push_back(make_pair(y,z));
    for(int i=1;i<=cntq;++i) scanf("%d%d",&x,&y),q.push_back(make_pair(make_pair(x,y),i));
    sort(q.begin(),q.end());
    int s=-1;
    for(auto it:q)
    {
        if(s!=it.first.first)
        {
            s=it.first.first;
            for(int i=1;i<=n;++i) for(int j=0;j<=800;++j) f[i][j]=0;
            f[it.first.first][0]=v[it.first.first];
            for(int j=0;j<=800;++j)
                for(int i=1;i<=n;++i)
                {
                    f[i][j+1]=max(f[i][j+1],f[i][j]);
                    for(auto jt:to[i])
                        if(j+jt.second<=800)
                            f[jt.first][j+jt.second]=max(f[jt.first][j+jt.second],f[i][j]+v[jt.first]);
                }
            for(int j=0;j<=800;++j)
                for(int i=1;i<=n;++i)
                    f[n][j]=max(f[n][j], f[i][j]);
        }
        ans[it.second]=f[n][it.first.second];
    }
    for(int i=1;i<=cntq;++i) printf("%d\n",ans[i]);
}

100分做法

在求结果的最后一步中，需要统计结束点为$i$的所有情况，而我们的询问正好是开始点为$i$……惊讶地发现，如果将所有边反过来，获得的就会正好是所需答案！

时间复杂度$O(cm)$。

65分思路很快就想到了，100分的还是在引导下才想出来的。老了……

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
// 100pts
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int> > to[2010];
int v[2010],f[2010][810];
int main()
{
    int n,m,q;
    int x,y,z;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i) scanf("%d",v+i);
    while(m--) scanf("%d%d%d",&x,&y,&z),to[y].push_back(make_pair(x,z));
    for(int i=1;i<=n;++i) f[i][0]=v[i];
    for(int j=0;j<=800;++j)
        for(int i=1;i<=n;++i)
        {
            f[i][j+1]=max(f[i][j+1],f[i][j]);
            for(auto it:to[i])
                if(j+it.second<=800)
                    f[it.first][j+it.second]=max(f[it.first][j+it.second],f[i][j]+v[it.first]);
        }
    while(q--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",f[x][y]);
    }
}