CSP-J 2024题解

compaq · 2025-04-24 16:11:55 · 题解

T1

排序，计数器。

测试点1:

n = 1时，答案为51。

测试点2～4:

判断出输入的牌各不相同后，答案为52 - n。

测试点5～7:

判定出牌以升序出现后，用每张牌和前一张作比较的道重复牌数，答案是52减去不重复牌数。

测试点8～10:

从保证升序的性质B获得启发，可以直接按字典序对牌排序，再统计不重复牌数。答案是52减去不重复牌数。

T2

二维数组，模拟。

测试点1～4:

k = 1时，只有一次操作，如果到达点没有越界且不是障碍物，则答案是2，否则答案为1。

测试点5、7:

地图均为空地，则执行k次操作， 只要没有越界，则可以前进，否则向右转。统计途径了几个点，即为答案。

其他测试点：

模拟k次操作，只要下一个格子不越界且不是障碍物，则可以前进，否则向右转。边走边打标记，答案即为途径的格子数。

T3

贪心，规律，分类讨论

测试点1:

若余数为6时，则答案为6 + k个8

T4

有 n个人，每个人都有一个数字序列。有 𝑞 次询问，每次询问给出 r 和 c，问是否存在 r次接龙的方法，使得最后一次接龙的数字是以数字 𝑐结尾。每一次接龙需要满足下面三个条件：

• 接龙序列一定是某一个人的数字序列中的一段连续子序列
• 接龙序列的长度在 [2,k]之间
• 不能出现连续两次接龙是同一个人的情况T

5分做法

注意到第 1个测试点 r=1 的情况，这意味着我们只需要判断 n 个人里面是否存在一个连续子序列以数字 1开头，并且以数字 𝑐 结尾。我们可以暴力枚举连续子序列的左右端点，判断是否符合要求即可。 注意：在枚举左右端点的过程中需要保证距离不超过 k。

单次询问的复杂度为 O(∑L×min(n,∑L)，一共 q 次询问，会超时。使用箱排序预处理，用 ans[c] 表示以数字 c结尾的连续子序列是否存在，就可以每次 O(1)地判断 ans[c] 的值来回答询问。

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n, k, q;
    cin >> n >> k >> q; 
    vector<int>L(n);
    vector<vector<int>> a(n);
    for(int i = 0; i < n; i++){
        cin >> L[i];
        a[i].resize(L[i]);
        for(int j = 0; j < L[i]; j++)
            cin >> a[i][j];
    }
    const int M = 2e5 + 10;
    vector<bool>ans(M);
    for(int i = 0; i < n; i++){
        for(int r = 0; r < L[i]; r++){
            for(int l = 0; l < r; l++){
                if(r - l + 1 <= k && a[i][l] == 1)
                    ans[a[i][r]] = true;        
            }
        }
    }
    while(q--){
        int r, c;
        cin >> r >> c;
        cout << ans[c] << '\n';
    }
}
int main(){
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

另外10分做法

(dfs暴力搜索) 注意到第 2、3个数据点的小数据范围：∑L⩽20，这提示我们可以使用 dfs.暴力搜索每一次接龙的结尾是哪个数字，同时还需要枚举一下当前这一次接龙开头的数字是哪一个，判断一下开头的数字是否和上一次接龙结尾的数字相同。

但是我们还需要注意到的一个条件就是：连续两次接龙的人不能是同一个。因此，在 dfs 的过程中除了需要记录上一次接龙的结尾数字是多少，还需要记录上一次接龙的人是哪一个。

至此，我们可以这样设计暴力搜索的函数去回答每一次询问：bool \ dfs(int \ t, int \ last, int \ x) 表示进行了 t次接龙，上一次接龙的人是 last，并且上一次接龙结尾的数字是 x。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k, q;
vector<int>L;
vector<int> a[N];

int r, c; 
bool dfs(int t, int last, int x){
    if(t == r) return x == c;

    for(int i = 0; i < n; i++){
        if(i == last) continue;
        for(int rr = 0; rr < L[i]; rr++){
            for(int ll = rr - 1; ll >= 0; ll--){
                if(rr - ll + 1 > k) break;
                if(a[i][ll] == x && dfs(t + 1, i, a[i][rr]))
                    return true;
            }
        }
    }
    return false;
}

void solve(){

    cin >> n >> k >> q; 
    L.resize(n);
    for(int i = 0; i < n; i++){
        cin >> L[i];
        a[i].resize(L[i]);
        for(int j = 0; j < L[i]; j++){
            cin >> a[i][j];
        }
    }

    while(q--){
        cin >> r >> c;
        if(dfs(0, -1, 1)) puts("1");
        else puts("0");
    }
}
int main(){
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

另外55分做法

(动态规划、降维、暴力枚举、特殊性质B) 回想一下暴力搜索的过程，如果我们知道第 t轮，以第 last个人的数字 x结尾的方法是存在的，那么对应的我们就能求出第 t+1轮，以其他人的其他数字结尾的方法。这很明显是一个由“本轮”递推到“下一轮”的过程，有递推的性质，我们就可以尝试往动态规划的方向去思考。 按照 dfs 函数的三个参数，设计出 dp 的状态：dp[r][i][c] 表示第 𝑟 轮接龙以第 i个人的数字 c结尾的方法是否存在，这是一个三维的 bool 数组。注意到 4∼5、7∼8、11∼12、15∼17这 9个测试点，它们的数据范围：r⩽10，n⩽1000，但是每个数字的范围最大是 2e5，没有足够的空间去定义 dp 数组。

对于第 1、3维，它们对应的是每一次询问给出的 t和 c，因此最好的选择是将第 2 维作为dp 数组降维后的值。至此，我们可以设计出一个新的 dp 状态：dp[r][c] 表示第 r 轮接龙以数字 c结尾的是哪一个人。

若 dp[r][c]=−1，则表示不存在能够接龙的人 若 dp[r][c]=i，则表示能够接龙的人是 i，并且是唯一的 若 dp[r][c]=∞，则表示能够接龙的人有两个及以上

接下来，我们需要所有状态对应的 dp 值：枚举 r表示第几轮接龙，枚举 i表示第几个人来接龙，枚举这个人的每一个数字 c表示以它作为接龙结尾的数字，接着再枚举另一个数字 x 表示接龙开头的数字。于是，我们可以得出如下的状态转移方程：

当 dp[r][c]=−1且 dp[r−1][x]=−1时，dp[r][c]=−1 当 dp[r][c]=−1且 dp[r−1][x]≠−1时，dp[r][c]=i 当 dp[r][c]≠−1且 dp[r][c]≠i 且 dp[r−1][x]≠−1时，dp[r][c]=∞

注意：如果上一轮接龙的人选如果是同一个人，那么是需要跳过当次转移的！

这个做法的时间复杂度是 O(r×∑L×min(k,∑L))

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k, q;
vector<int>L;
vector<int> a[N];

int r, c; 
int dp[110][N];

void solve(){

    cin >> n >> k >> q; 
    L.resize(n);
    for(int i = 0; i < n; i++){
        cin >> L[i];
        a[i].resize(L[i]);
        for(int j = 0; j < L[i]; j++){
            cin >> a[i][j];
        }
    }

    memset(dp, -1, sizeof dp);
    dp[0][1] = n; // 第0轮以1为结尾是可行，且方案很多。 

    for(int t = 1; t <= 10; t++){//第t轮 
        for(int i = 0; i < n; i++){//第i个人 
            for(int rr = 0; rr < L[i]; rr++){ // 右端点
                for(int ll = rr - 1; ll >= 0; ll--){ //左端点 
                    if(rr - ll + 1 > k) break;
                    int cc = a[i][rr], x = a[i][ll];

                    if(dp[t - 1][x] == i) continue; //上一轮同一个人 

                    if(dp[t][cc] == -1){
                        if(dp[t - 1][x] != -1)
                            dp[t][cc] = i;
                    }
                    else if(dp[t][cc] != i && dp[t - 1][x] != -1){  
                        dp[t][cc] = n;
                    }
                }
            }
        }
    }   
    while(q--){
        cin >> r >> c;
        if(dp[r][c] >= 0) puts("1");
        else puts("0");
    }
}
int main(){
    int T;
    cin >> T;
    while(T--)
        solve();

    return 0;
}

满分做法

到目前为止，动态规划的时间复杂度过高，瓶颈在于需要暴力枚举上一轮以哪一个数字为结尾，才能转移到本轮的状态。我们的做法是枚举每个人的区间，时间复杂度为\sum L \times min(\sum L, k)。

能不能不枚举区间？

现在考虑第t轮, 当前枚举到第i个人的第x个位置的数值cc能否成为结尾。

若在上一轮(第t - 1轮)中，dp[t - 1][cc] ! = i 并且 dp[t - 1][cc] != -1， 即上一轮能以cc为结尾，且不是同个人，则在这一轮当中，从cc的位置x出发，可以向后面不超过k-1个位置转移。

例如

第t-1轮，有dp[t - 1][1] >=0, 即可以以1为结尾。

那么第t轮，假设第i个人的数值为：\{1,2, 1,2,3,4\}，k = 3若dp[t - 1][1] ! = i 并且 dp[t - 1][1] != -1, 则第一个1能管后面2个位置，都能dp[t][2], dp[t][1]，枚举到第二个1，又可以管住后面2个位置。

整体时间复杂度为 O(r×∑L)

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k, q;
vector<int>L;
vector<int> a[N];

int r, c; 
int dp[110][N];

void solve(){

    cin >> n >> k >> q; 
    L.resize(n);
    for(int i = 0; i < n; i++){
        cin >> L[i];
        a[i].resize(L[i]);
        for(int j = 0; j < L[i]; j++){
            cin >> a[i][j];
        }
    }

    memset(dp, -1, sizeof dp);
    dp[0][1] = n; // 第0轮以1为结尾是可行，且方案很多。 

    for(int t = 1; t <= 100; t++){//第t轮 
        for(int i = 0; i < n; i++){//第i个人 
            int cnt = 0; // 能往后转移的长度 
            for(int x = 0; x < L[i]; x++){  
                    int cc = a[i][x]; 

                    if(cnt-- > 0) {
                        if(dp[t][cc] == -1)
                            dp[t][cc] = i;
                        else if(dp[t][cc] != i)
                            dp[t][cc] = n;
                    }

                    if(dp[t - 1][cc] != i && dp[t - 1][cc] != -1)
                        cnt = k - 1;    
            }
        }
    }   
    while(q--){
        cin >> r >> c;
        if(dp[r][c] >= 0) puts("1");
        else puts("0");
    }
}
int main(){
    int T;
    cin >> T;
    while(T--)
        solve();

    return 0;
}