CSP2023-S2题解汇总

xinxijishu110 · 2023-10-28 21:55:39 · 个人记录

第一题

[CSP-S 2023] 密码锁【民间数据】

题目描述

小 Y 有一把五个拨圈的密码锁。如图所示，每个拨圈上是从 0 到 9 的数字。每个拨圈都是从 0 到 9 的循环，即 9 拨动一个位置后可以变成 0 或 8，

因为校园里比较安全，小 Y 采用的锁车方式是：从正确密码开始，随机转动密码锁仅一次；每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。

当小 Y 选择同时转动两个相邻拨圈时，两个拨圈转动的幅度相同，即小 Y 可以将密码锁从 \tt{0\;0\;1\;1\;5} 转成 \tt{1\;1\;1\;1\;5}，但不会转成 \tt{1\;2\;1\;1\;5}。

时间久了，小 Y 也担心这么锁车的安全性，所以小 Y 记下了自己锁车后密码锁的 n 个状态，注意这 n 个状态都不是正确密码。

为了检验这么锁车的安全性，小 Y 有多少种可能的正确密码，使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部 n 个状态。

输入格式

输入的第一行包含一个正整数 n，表示锁车后密码锁的状态数。

接下来 n 行每行包含五个整数，表示一个密码锁的状态。

输出格式

输出一行包含一个整数，表示密码锁的这 n 个状态按照给定的锁车方式能对应多少种正确密码。

样例 #1

样例输入 #1

1
0 0 1 1 5

样例输出 #1

81

提示

【样例 1 解释】

一共有 81 种可能的方案。

其中转动一个拨圈的方案有 45 种，转动两个拨圈的方案有 36 种。

【样例 2】

见选手目录下的 lock/lock2.in 与 lock/lock2.ans。

【数据范围】

对于所有测试数据有：1 \leq n \leq 8。

特殊性质 A：保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的 n 个状态。

题解

首先可以将所有的00000~99999的字符串映射（map<string,int>）为编号0~99999，，也可以直接i*10000+j*1000+k*100+le*10+m 做为编号，效果相同；

然后用 桶 统计编号出现的次数；

如果枚举每个正确答案，尝试按要求旋转45+36次，看看能否推出所有的n个错误答案，复杂度为100000*81*8,写起来也麻烦，因为每次转一个新的串，都要和n个错误答案比对一下；

因此可以逆向思维，由于n个答案是错误的，那么从每个错误答案可以逆推45+36=81次，每个错误答案最多可以推出81个新串（有些串 不新 ，是因为可能由错误答案串推出其他错误答案串，这些串需要排除），这些新串都可能是正确答案，最后遍历所有的100000个桶，如果当前编号桶的数值为n，则说明这个串可以由所有n个错误答案推出，累积给ans即可，时间复杂度骤降至 100000*2+n*81

代码一：map<string,int>mp；

建立串和编码的映射，编码放桶中

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

map<string,int>mp;
int tong[N];
string tt[N];
int n,ans;

int main()
{
    //freopen("lock.in","r",stdin);
    //freopen("lock.out","w",stdout);
    int cnt=1;
    cin>>n;
    if(n==1)
    {
        puts("81");
        return 0;
    }
    for(int i=0;i<=9;++i)
     for(int j=0;j<=9;++j)
      for(int k=0;k<=9;++k)
       for(int l=0;l<=9;++l)
        for(int m=0;m<=9;++m)
        {
            string st;
            st+=(char)(i+'0');
            st+=(char)(j+'0');
            st+=(char)(k+'0');
            st+=(char)(l+'0');
            st+=(char)(m+'0');
            mp[st]=cnt;
            cnt++;
            //cout<<st<<endl;   
        }
    int x;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=5;++j)
        {
            scanf("%d",&x);
            tt[i]+=(char)(x+'0');
        }
        tong[mp[tt[i]]]=-1;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=4;++j)   //tt[i]
        {
            for(int k=1;k<=9;++k)
            {
                string st=tt[i];
                //cout<<"处理前："<<st<<endl;
                st[j]=(char)((st[j]-'0'+k)%10+'0');
                if(tong[mp[st]]==-1)continue;
                //cout<<st<<endl;
                tong[mp[st]]++;
            }
        }
        for(int j=0;j<=3;++j)
        {
            for(int k=1;k<=9;++k)
            {
                string st=tt[i];
                st[j]=(char)((st[j]-'0'+k)%10+'0');
                st[j+1]=(char)((st[j+1]-'0'+k)%10+'0');
                if(tong[mp[st]]==-1)continue;
                //cout<<st<<endl;
                tong[mp[st]]++;
            }
        }
    }
    for(int i=1;i<=cnt;++i)
     if(tong[i]==n)
        ans++;
    cout<<ans<<endl;
    return 0;
}

代码二：直接处理每个串形成的数值

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

int tong[N];
int a[10][6],b[10];
int n,ans;

int main()
{
    //freopen("lock.in","r",stdin);
    //freopen("lock.out","w",stdout);
    cin>>n;
    if(n==1)
    {
        puts("81");
        return 0;
    }
    int x;
    for(int i=1;i<=n;++i)
    {
        int st=0;
        for(int j=1;j<=5;++j)
        {
            st*=10;
            scanf("%d",&x);
            a[i][j]=x;
            st+=x;
        }
        b[i]=st;
        tong[st]=-1;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=5;++j)   
        {
            int p=(int)pow(10,5-j);
            for(int k=1;k<=9;++k)
            {
                int st=b[i];
                st-=a[i][j]*p;  //当前位清0再转 
                int xx=(a[i][j]+k)%10;
                st+=xx*p;
                if(tong[st]!=-1)
                    tong[st]++;
            }
        }
        for(int j=1;j<=4;++j)
        {
            int p=(int)pow(10,5-j);
            int q=(int)pow(10,5-j-1); 
            for(int k=1;k<=9;++k)
            {
                int st=b[i];
                st-=a[i][j]*p;  //当前位清0再转 
                st-=a[i][j+1]*q;
                int xx=(a[i][j]+k)%10;
                int yy=(a[i][j+1]+k)%10;
                st+=xx*p+yy*q;
                if(tong[st]!=-1)
                    tong[st]++;
            }
        }
    }
    for(int i=1;i<=100000;++i)
     if(tong[i]==n)
        ans++;
    cout<<ans<<endl;
    return 0;
}

第二题

[CSP-S 2023] 消消乐【民间数据】

题目背景

本题提供两个版本的民间数据，供参考。

题目描述

小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两 个相邻的元素。

现在，他有一个长度为 n 且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。

其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。

小 L 想知道，这个字符串的所有非空连续子串中，有多少个是可消除的。

输入格式

输入的第一行包含一个正整数 n，表示字符串的长度。

输入的第二行包含一个长度为 n 且仅由小写字母构成的的字符串，表示题目中询问的字符串。

输出格式

输出一行包含一个整数，表示题目询问的答案。

样例 #1

样例输入 #1

8
accabccb

样例输出 #1

5

提示

【样例 1 解释】

一共有 5 个可消除的连续子串，分别是 cc、acca、cc、bccb、accabccb。

【样例 2】

见选手目录下的 game/game2.in 与 game/game2.ans。

【样例 3】

见选手目录下的 game/game3.in 与 game/game3.ans。

【样例 4】

见选手目录下的 game/game4.in 与 game/game4.ans。

【数据范围】

对于所有测试数据有：1 \le n \le 2 \times 10^6，且询问的字符串仅由小写字母构成。

特殊性质 A：字符串中的每个字符独立等概率地从字符集中选择。

特殊性质 B：字符串仅由 a 和 b 构成。

题解

第一种方法：暴力

考虑枚举每个点为起点，之后连续的可消除串有多少，可过8000*8000，获得高贵的50分

#include<bits/stdc++.h>
using namespace std;
int n,cnt,pre,ans;
string st;

int main()
{
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    cin>>n>>st;
    for(int i=0;i<n;++i)
    {
        pre=0;  
        stack<char>zhan;
        for(int j=i;j<n;++j)
        {
            zhan.push(st[j]);
            while(zhan.size()&&st[j+1]==zhan.top()) //while非常精妙，感谢蔡睿
            {
                zhan.pop();
                j++;
            }
            if(zhan.size()==0)  //这里只要栈空即累加答案
                pre++;
        }
        ans+=pre;
    }
    cout<<ans<<endl;
    return 0;
}

正解1：正向DP

知乎题解1

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e6 + 5;
char a[N];
int f[N], g[N][26];
int main() {
    int n;
    scanf("%d%s", &n, a + 1);
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        int x = a[i] - 'a';
        int k = g[i - 1][x] - 1;  // 消掉最近的一段后，上一段的结尾是k
        if (k >= 0) {
            ans += f[i] = f[k] + 1;
            for (int j = 0; j < 26; j++) g[i][j] = g[k][j];
        }
        g[i][x] = i;
    }
    printf("%lld\n", ans);
    return 0;
}

正解2：逆向DP

题解2

#include<bits/stdc++.h>
using namespace std;
#define int long long
/*
括号匹配的dp思想：
nxt[i]状态：表示存放下一个匹配的字符的位置
dp[i]状态：表示以i作为开头的匹配序列的数量
状态转移方程：dp[i]=dp[nxt[i]+1]+1
时间复杂度-O（n）-100pts
*/
const int N = 2e6 + 10;
int n;
string str;
int nxt[N], dp[N];
map<int, int> mp[N];//mp数组，用于存放每个位置之后的字符及其对应的位置
signed main() {
  cin >> n >> str;
  str = ' ' + str;
  //初始化dp和nxt数组
  for (int i = 1; i <= n + 1; i++) dp[i] = 0, nxt[i] = -1;

  //倒着遍历字符序列
  for (int i = n; i >= 1; i--) {
    //在i+1位置之后查找是否存在与当前i位置相同的字符
    if (mp[i + 1].count(str[i])) {
      int pos = mp[i + 1][str[i]];//找到与当前i位置相同的字符位置pos
      nxt[i] = pos;//记录匹配位置
      swap(mp[i], mp[pos + 1]);//更新mp
      if (pos < n) mp[i][str[pos + 1]] = pos + 1;//更新mp
    }
    mp[i][str[i]] = i;//更新mp
  }
  int ans = 0;
  for (int i = n; i >= 1; i--) {
    if (nxt[i] == -1) continue;
    dp[i] = dp[nxt[i] + 1] + 1;//计算dp[i]
    ans += dp[i];
  }
  cout << ans << endl;
  return 0;
}

正解3：Trie树（字典树）

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL mod = 1e9 + 7;
const int N = 2e6 + 5;

char a[N];  //字符串序列 
char s[N];  //模拟栈 
int trie[N][26], fa[N], val[N], ck = 1;
//ch[N][26]是建立字典树，fa[N]用来继承前序，val[N]表示当前可以继承的可消除串数量 
int main() {
    int n;
    scanf("%d%s", &n, a + 1);
    LL ans = 0;
    int tot = 0, u = ck;
    val[u]++;
    for (int i = 1; i <= n; i++) {
        //printf("正在处理第%d个字符，当前字符为:%c\n",i,a[i]);
        if (s[tot] == a[i]) {
            tot--;
            //printf("当前%c和栈顶相同，消除栈顶，%d上跳到fa[%d]=",a[i],u,u);
            u = fa[u];  //u上跳到 fa[u] 
            //printf("%d\n",u);
        } 
        else {
            s[++tot] = a[i];
            //printf("%c入栈，",a[i]);
            int &v = trie[u][a[i] - 'a'];
            //printf("当前v=trie[%d][%d]=%d\n",u,a[i]-'a',v);
            //int &v这里是“引用”的用法 ，对v的处理会同步处理给 ch[u][a[i] - '0'];
            if (v == 0) 
            {
                //printf("因为trie[%d][%d]==0，因此建立新节点；\n",u,a[i]-'a');
                v = ++ck, fa[v] = u;    //建立trie树新节点和继承关系 
                //printf("令trie[%d][%d]=%d,fa[%d]=%d;\n",u,a[i]-'a',ck,v,u);
            }
            //printf("u=%d下跳到",u);
            u = v;  //u下跳到 v 
            //printf("v=%d;\n",u);
        }
        ans += val[u];  //每次到 u，都需要更新 u累积的可消除子串数量 
        //printf("val[%d]=%d,ans=ans+val[%d]=%d,然后val[%d]++，变为了",u,val[u],u,ans,u);
        val[u]++;   //每次回到 u，正明有一个新的可消除串回到了 u，val[u]++; 
        //printf("%d\n",val[u]);
        //puts("");
    }
    printf("%lld\n", ans);
    return 0;
}

第三题需要类，暂时跳过

第四题

[CSP-S 2023] 种树【民间数据】

题目描述

你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。

森林的地图有 n 片地块，其中 1 号地块连接森林的入口。共有 n-1 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。

你的目标是：在每片地块上均种植一棵树木，并使得 i 号地块上的树的高度生长到不低于 a_i 米。

你每天可以选择一个未种树且与某个已种树的地块直接邻接（即通过单条道路相连）的地块，种一棵高度为 0 米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第 1 天你只能在 1 号空地种树。

对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第 x 天，i 号地块上的树会长高 \max(b_i + x \times c_i, 1) 米。注意这里的 x 是从整个任务的第一天，而非种下这棵树的第一天开始计算。

你想知道：最少需要多少天能够完成你的任务？

输入格式

输入的第一行包含一个正整数 n，表示森林的地块数量。

接下来 n 行：每行包含三个整数 a_i, b_i, c_i，分别描述一片地块，含义如题目描述中所述。

接下来 n-1 行：每行包含两个正整数 u_i, v_i，表示一条连接地块 u_i 和 v_i 的道路。

输出格式

输出一行仅包含一个正整数，表示完成任务所需的最少天数。

样例 #1

样例输入 #1

4
12 1 1
2 4 -1
10 3 0
7 10 -2
1 2
1 3
3 4

样例输出 #1

5

提示

【样例 1 解释】

第 1 天：在地块 1 种树，地块 1 的树木长高至 2 米。

第 2 天：在地块 3 种树，地块 1, 3 的树木分别长高至 5, 3 米。

第 3 天：在地块 4 种树，地块 1, 3, 4 的树木分别长高至 9, 6, 4 米。

第 4 天：在地块 2 种树，地块 1, 2, 3, 4 的树木分别长高至 14, 1, 9, 6 米。

第 5 天：地块 1, 2, 3, 4 的树木分别长高至 20, 2, 12, 7 米。

【样例 2】

见选手目录下的 tree/tree2.in 与 tree/tree2.ans。

【样例 3】

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。

【样例 4】

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。

【数据范围】

对于所有测试数据有：1 ≤ n ≤ 10^5,1 ≤ a_i ≤ 10^{18}, 1 ≤ b_i ≤ 10^9,0 ≤ |c_i| ≤ 10^9, 1 ≤ u_i, v_i ≤ n。保证存在方案能在 10^9 天内完成任务。

特殊性质 A：对于所有 1 ≤ i ≤ n，均有 c_i = 0；

特殊性质 B：对于所有 1 ≤ i < n，均有 u_i = i,v_i = i + 1；

特殊性质 C：与任何地块直接相连的道路均不超过 2 条；

特殊性质 D：对于所有 1 ≤ i < n，均有 u_i = 1。

性质A：

每天增长量必然大于1，a[i]/b[i]算出每个位置需要的成长天数，可以暴力贪心，枚举已经种树的点，找到与这些点连接的 尚未种树的儿子中 的最大需要天数的儿子去种（最大需要天数的坑一定先种，这样他成长的天数可以覆盖掉其他树一部分成长天数成本，一定最优，种树后将他所有的儿子加入优先队列，优先队列中的点就是下一天可以种的坑）。

开个优先队列（大根堆），其中存放着准备种树的点（开始只有1号坑），每次取出堆顶（要种的坑），然后将他所有儿子加入堆（以需要的成长天数排序），种的次序（计数）就是他开始的天数，加上他的需要成长天数，所有坑中的最大值就是答案。时间复杂度O(n)获得高贵的15分。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
int n;
int a[N],b[N],c[N],vis[N],dp[N],cnt=0,ans=0;

priority_queue<pair<int,int> >que;
vector<int>vec[N];

signed main()
{
    //freopen("tree.in","r",stdin);
    //freopen("tree.out","w",stdout);
    cin>>n;
    int flag=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
        if(c[i]!=0)
            flag=1; //判断是否为性质A 
    }   
    int x,y;
    for(int i=1;i<n;++i)
    {
        scanf("%lld%lld",&x,&y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    if(flag==0)
    {
        que.push(make_pair(ceil(a[1]/b[1]),1));
        while(que.size())
        {
            int u=que.top().second;
            que.pop();
            vis[u]=1;
            dp[u]=cnt+ceil(a[u]/b[u]);
            //printf("当前是第cnt=%lld天,在种u=%lld号坑,dp[%lld]=%lld\n",cnt,u,u,dp[u]);
            ans=max(ans,dp[u]);
            ++cnt;
            for(int i=0;i<vec[u].size();++i)
            {
                int v=vec[u][i];
                if(vis[v])continue;
                que.push(make_pair(ceil(a[v]/b[v]),v));
            }
        }
        printf("%lld\n",ans);
    } 
    return 0;
}

性质B：

单链可以每棵树依次计算，二分答案需要的天数x，检测x天能否满足每个坑都长够a[i]，获得高贵的10分；

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 100005;

int n;
LL a[N], b[N], c[N];
vector<int> G[N];
// 首项 v 公差 d，总和需要至少s，求至少需要的天数
LL cal(LL v, LL d, LL s) {
    if (d == 0) return (s + v - 1) / v;
    if (d > 0) {
        LL l = 1, r = s / v + 1;
        while (l < r) {
            LL mid = l + r >> 1;
            if (mid * v + (__int128)(mid - 1) * mid / 2 * d >= s)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
    LL x = (v - 1 + -d - 1) / -d;         // 第x+1天开始 都=1
    LL s0 = x * v + (x - 1) * x / 2 * d;  // 前x天总和,这里不会爆LL
    if (s > s0) return x + s - s0;
    LL l = 1, r = x;
    while (l < r) {
        LL mid = l + r >> 1;
        if (mid * v + (mid - 1) * mid / 2 * d >= s)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}
int main() {
    bool case_B = true;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
        if (u != i || v != i + 1) case_B = false;
    }
    if (case_B) {
        LL ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, i + cal(max(b[i] + i * c[i], 1LL), c[i], a[i]) - 1);
            //注意这里每棵树在第i天种下时的增长起点max(b[i] + i * c[i],1),这里x就是i，有助于理解本行代码
        }
        printf("%lld\n", ans);
    } else {
        puts("114514");  // 随便猜一个了
    }
    return 0;
}