CSP-J 第二轮 模拟赛四补题报告

日期：2023年10月4日 星期四

学号：S07246

姓名：江守栋

目录

· 比赛概况

· 比赛过程

· 题目分析

T1【复读机  repeater】

1、题目大意

2、比赛中的思考

3、解题思路

4、AC代码

· 赛后总结

T2【小可的矛与盾  spearshield】

1、题目大意

2、比赛中的思考

3、解题思路

4、AC代码

T3【不合法字符串  illegality】

1、题目大意

2、比赛中的思考

3、解题思路

4、AC代码

T4【虚假的珂朵莉树  kodori】

1、题目大意

2、比赛中的思考

3、解题思路

4、AC代码

---

·  比赛概况

        总分：210 / 400

        T1 【复读机  repeater】 100分

        T2 【小可的矛与盾  spearshield】 90分

        T3 【不合法字符串  illegality】 20分

        T4 【虚假的珂朵莉树  kodori】 0分

·  比赛过程

第一题看起来很简单，就先做了，调了很久，AC了

第二题就更简单了，用了前缀和，但是漏了一种情况，扣了10分

第三题拿了特殊测试点的20分

第四题貌似不能骗分呢，直接输出了样例

·  题目分析

T1【复读机  repeater】

1、题目大意

给定一个长度为n的仅包含小写字母和数字的字符串。
小写字母表示消息，数字表示将数字前面的信息复读的次数。
字符串内可能包含多个数字，要从左到右解析字符串。

如a5b2，从左到右解析，a5表示将a复读5遍，原字符串变为aaaaab，

遇到数字 2 ，再全部复读 2 遍，即aaaaabaaaaab

输出复读后的字符串

2、比赛中的思考

用 string 存数据，循环处理

虽然是道水题，当时因为 for 写错了，调了好久，最后才看出来，也是直接AC

3、解题思路

多组输入，每次输入后清空所有数据（这次没有犯 Day 2的错误），我开了三个string

: 原字符串 

: 临时答案

: 最终输出的答案

因为可能会复读多次，就会多次改变最终的答案，所以要在每次处理之前将 

 将之前得到的答案赋值给临时答案，

然后 while 循环，如果当前字符是字母，则将其连接到答案后

如果是数字，就循环判断它是几位数，做一个类型的转换，赋给  也就是复读的次数

每次处理完后将  的值赋给  , 随后开始处理 “复读” ，以为已经赋过值，所以就相当于

已经复读了一次 ，  循环只需从 2 开始执行到  , 每次把临时的答案（  ） 连接到最终

答案后（  ），最后输出即可

有一个点需要注意，因为  循环内部已经对  做过增加，所以  循环的括号里就不需要

写 了，否则会漏掉字符

就是因为这个点卡我40分钟

4、AC代码

· 赛后总结

#include<bits/stdc++.h>
using namespace std;
int t,n;
string s="",ans="",ans1="";
int main()
{freopen("repeater.in","r",stdin);freopen("repeater.out","w",stdout);cin>>t;while(t--){s="",ans="",ans1="";cin>>n;cin>>s;for(int i=0;i<s.size();){ans1=ans;while(s[i]>='a'&&s[i]<='z'){ans1+=s[i];i++;}int x=0;while(s[i]>='0'&&s[i]<='9'){x=x*10+(s[i]-'0');i++;}ans=ans1;for(int j=2;j<=x;j++){ans+=ans1;}}cout<<ans<<endl;}fclose(stdin);fclose(stdout);return 0;
}

T2【小可的矛与盾  spearshield】

1、题目大意

有n个人站成一排（1到n），每人都有一个战斗力x​i​​=i，有的当矛，有的当盾，

矛的攻击力和盾的防御力与本身的战斗力相同，将他们分成两个阵营,

为第一阵营，只考虑矛的攻击力总和 ；

为第二阵营，只考虑盾的防御力总和 

求对于所有的，的值最小，求最小为多少。

2、比赛中的思考

也是一道水题

看到题之后就觉得用前缀和，然后取  ，过了样例，但是因为没有考虑左端点，扣掉了 10分

3、解题思路

开两个前缀和数组，分别来记录 盾和矛的 战斗力前缀和，预处理结束后，采用枚举的策略，枚举每一个  ，取  ,输出即可，注意要开 long long，还有最后的循环枚举时要从0开始，否则

会漏掉一个左端点，-10分

4、AC代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],ans1[100005],ans2[100005];
string s;
int main()
{freopen("spearshield.in","r",stdin);freopen("spearshield.out","w",stdout);cin>>n>>s;for(int i=1;i<=n;i++){a[i]=s[i-1]-'0';if(a[i]==0){ans1[i]=ans1[i-1]+i;ans2[i]=ans2[i-1];}if(a[i]==1){ans2[i]=ans2[i-1]+i;ans1[i]=ans1[i-1];		}}long long minn=1e18;for(int i=0;i<=n;i++){minn=min(minn,abs(ans1[i]-(ans2[n]-ans2[i])));}cout<<minn;fclose(stdin);fclose(stdout);return 0;
}

T3【不合法字符串  illegality】

1、题目大意

共T组输入，每次输入给出  个不合法的字符串  和一篇小说，要把小说中的不合法字符串用尽量少的  和谐掉，使小说中不含不合法字符，输出和谐后的小说

2、比赛中的思考

满分没想过，直接照着题目里 20% 的数据打的  ↓↓↓

20%的数据下：n = 1

最终拿到了这 20 分 

3、解题思路

其实这道题并没有多难，只要想清楚一个点，就大概率拿满分

和谐字符时，如果想要让用的  尽量少，就要让每次被  的字符影响尽量多的子串

想让一个字符被尽量多的子串覆盖，肯定是选择尽量靠后的字符，所以在删字符的时候，

如果出现了不合法字符串，就将小说中不合法字符串的最后一位  掉

至于判断是不是不合法字符串，可以先加一个特判，如果目前遍历到的字符串的长度小于不合法字符串的长度，则目前一定不需要和谐字符，  即可

否则就用到字符串的函数 ，截取小说从当前字符起， 个长度的字符，看看是否等于  ,如果相等则  掉小说中不合法字符串的最后一个字符

最后将和谐后的字符串输出即可

4、AC代码

#include<bits/stdc++.h>
using namespace std;
int T,n;
string ans,str[15];
int main()
{//freopen(".in","r",stdin);//freopen(".out","w",stdout);cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>str[i];cin>>ans;int m=ans.size();ans=' '+ans;		for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(i<str[j].size()) continue;if(ans.substr(i-str[j].size()+1,str[j].size())==str[j]){ans[i]='*';}}}for(int i=1;i<=m;i++) cout<<ans[i];cout<<endl;}//fclose(stdin);//fclose(stdout);return 0;
}

T4【虚假的珂朵莉树  kodori】

1、题目大意

一棵树，有n个节点，根节点为1，每个节点都有一个权值。
在这棵树上增加m条虚假边（增加的虚假边不会影响节点深度）。
之后进行q次操作。
操作1:让结点 u 的权值增加 k ，并对与结点 u 相邻的结点中，深度比结点 k 小的结点重复操作1。
操作2:让结点 u 的权值增加 k ，并对与结点 u 相邻的结点中，深度比结点 u 大的结点重复操作2。
求经过q次操作后所有节点的权值。

2、比赛中的思考

呵呵，样例都读不懂

3、解题思路

输入真实边后立即深搜确定每一个节点的深度

然后输入虚假边

用延迟更新的方法计算出方法一与方法二应该增加的权值

最后判断条件并更新

输出

4、AC代码

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mk make_pair
using namespace std;
const long long p=1e9+7;
struct node{int to,next;
}e[5000005];
vector<pr> g;
long long a[1000005],up[1000005],down[1000005];
int n,m,q,cnt,head[1000005],d[1000005];
void add(int u,int v){e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
void dfs(int u,int fa){g.push_back(mk(d[u],u));for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==fa) continue;d[v]=d[u]+1;dfs(v,u);}
}
int main(){cin>>n>>m>>q;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;add(u,v);add(v,u);}dfs(1,1);for(int i=1;i<=m;i++){int u,v;cin>>u>>v;add(u,v);add(v,u);}for(int i=1;i<=q;i++){int pd,u,v;cin>>pd>>u>>v;if(pd==1) up[u]=(up[u]+v)%p;else down[u]=(down[u]+v)%p;}sort(g.begin(),g.end());for(int i=0;i<g.size();i++){int x=g[i].second;for(int j=head[x];j;j=e[j].next){int y=e[j].to;if(d[y]>d[x]) down[y]=(down[y]+down[x])%p;}}reverse(g.begin(),g.end());for(int i=0;i<g.size();i++){int x=g[i].second;for(int j=head[x];j;j=e[j].next){int y=e[j].to;if(d[y]<d[x]) up[y]=(up[y]+up[x])%p;}}for(int i=1;i<=n;i++) cout<<(a[i]+up[i]+down[i])%p<<" ";return 0;
}

·  赛后总结

        今天相比昨天难度更降低了一些，总体来说除了第四题还是比较轻松的

        赛时我只想着拿到第一、二题的分数，因为以往的比赛，我一直将第三题看做我无法逾越的一道高墙，所以总是将问题想的很复杂，将目标放在部分分数上，但实际上第三题并没有多少难度，我如果再仔细一些说不定就AC了呢。

        第四题是一道图论，以我目前的水平，想要拿到满分是不太可能的事情，但是我是可以暴力拿部分分的，可是因为前面学图论时不够扎实，导致我忘记了邻接表的写法，想写暴力也写不了

这暴露出了我对知识遗忘的问题，看来以后不仅要注重平时的刷题，也要在刷题的同时复习好以前学习的内容！