文件操作不要出错啊！！！！！
模拟赛四补题报告
日期：\(2023\)—\(10\)—\(5\) 学号：\(S11390\)
一、总分：
\(T1\) 复读机:\(100\)分
\(T2\) 小可的矛与盾:\(0\)分
\(T3\) 不合法字符串:\(100\)分
\(T4\) 虚假的珂朵莉树:\(0\)分
共：\(200\) 分
二、比赛过程
-
在第一题中，通过模拟的思路，遍历字符串，成功想到了正解，但在模拟期间，有了很多小问题，花费了较长时间，在最后也是改好了。成功 \(AC\)。
-
在第二题中，没有想到能够通过前缀和或者递推的思想来进行做题，只能通过暴力枚举的方法来往后遍历，想骗几分，但也没骗到就得了 \(0\) 分。
-
在第三题中，也是没有想到好的思路，想通过暴力枚举的思路骗点分，但最后也是卡这数据通过了这道题，没想到能够 \(AC\)。
-
在第四题中，碰巧遇到了我之前做过的一道挺像的题，就通过之前的思路做了做，最后过了大样例。但因为评测机，让得我少 \(A\) 了一道题。
三、题目分析
\(T1\) 复读机
通过模拟的思路将给定的字符串进行复制，一个一个字符遍历，如果遇到数字就进行复制，字母部分表示一段信息，数字表示将此位置前的所有信息内容复制的次数。
注意：在复制时之前复制的也要进行复制哦！！！
比如：\(a5b2\) 那么要先为 \(aaaaab\) 然后在复制变为 \(aaaaabaaaaab\)。之后就是模拟了。
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int t;
string s;
char c[N],w[N];
int n;
int shuzi,len_q;
void fu()
{
int len_h=0;
for(int i=1;i<=shuzi;i++)
{
for(int j=1;j<=len_q;j++)
{
w[++len_h]=c[j];
}
}
for(int i=1;i<=len_h;i++)
{
c[i]=w[i];
}
len_q=len_h,shuzi=0;
}
signed main()
{
// freopen("repeater.in","r",stdin);
// freopen("repeater.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
cin>>n>>s;
len_q=0;
shuzi=0;
memset(c,0,sizeof(c));
memset(w,0,sizeof(w));
for(int i=0;i<n;i++)
{
if(s[i]>='a'&&s[i]<='z')
{
if(shuzi!=0)
fu();
c[++len_q]=s[i];
}
else
{
//记录数字出现的次数
shuzi=shuzi*10+(s[i]-'0');
//cout<<shuzi<<endl;
}
}
if(shuzi!=0)
fu();
cout<<c+1<<endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T2\) 小可的矛与盾
这道题可以通过前缀和或者递推的思想来进行做题，通过用两个数组来记录相应的攻击力或防御力。选定一个值求出差的最小值。
需要注意盾和矛的总值需要遍历字符串进行预处理。如果是 \(0\) 则矛进行加和，反之盾进行加和。
-
可以使用前缀和分别算出从左端点到每一位置上的盾和矛的权值和。
-
也可以在遍历到每一个点的时候直接给到防御阵营里，这就是递推的思想。
注意：需要考虑 \(k=0\) 时的情况，就是全在攻击或者防御阵营里。
正解 _ 前缀和
//前缀和
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int sfs[N],sgj[N];
string s;
int n;
int minn=0x3f3f3f3f3f;
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>s;
for(int i=0;i<n;i++)
{
if(s[i]=='0')
sfs[i]=sfs[i-1],sgj[i]=sgj[i-1]+i+1;
else
sgj[i]=sgj[i-1],sfs[i]=sfs[i-1]+i+1;
}
for(int i=-1;i<n;i++)
{
minn=min(minn,abs(sgj[i]-(sfs[n-1]-sfs[i])));
}
cout<<minn<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
正解_ 递推
//递推
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int gj[N],fs[N];
string s;
int n,ans;
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>s;
s=' '+s;
long long x1=0,y1=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='0')
{
y1+=i;
gj[i]=i;
}
else
{
fs[i]=i;
}
}
ans=y1;
//cout<<ans<<endl;
for(int i=n;i>=1;i--)
{
x1+=fs[i];
y1-=gj[i];
//cout<<y1-x1<<endl;
ans=min((abs(y1-x1)),ans);
}
cout<<ans<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T3\) 不合法字符串
本题的思路就是通过遍历字符串，在字符串中出现了当只有一个单词时，对于可以在字符串中找到的单词，我们可以将其任意一位改成 \(*\)，即可使单词无法被找到，我们就可以将最后一位改为 \(*\)，那么就是能够改动的最小数量。
本题的枚举是对字符串每一位往前寻找，然后若是找到任意一个以这一位结尾的单词，则更改这一位。
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int t,n;
string s1; //小说
string s2[100]; //不合法字符串
signed main()
{
freopen("illegality.in","r",stdin);
freopen("illegality.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s2[i];
}
cin>>s1;
for(int i=0;i<s1.size();i++)
{
for(int j=1;j<=n;j++)
{
if(i+1<s2[j].size())
continue;
if(s1.substr(i-s2[j].size()+1,s2[j].size())==s2[j])
s1[i]='*';
}
}
cout<<s1<<endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T4\) 虚假的珂朵莉树
这道题我是深有感触，这是我在考试以来做对的第一道第四题，但没得分，真服了。
这个题我来好好讲讲。
-
先进行存图。
-
在加入虚边之前，求出每一个结点的深度，因为加入虚边后不会影响树的深度，通过 \(dfs(1,1)\) 来进行遍历求树的深度，前一个参数表示从根节点 \(1\) 来开始，后一个参数表示此时树的深度。
-
此时在加入虚边。
-
我们可以发现有 \(q\) 个操作。
-
1 u v表示将节点 \(u\) 和 \(u\) 所有相邻节点中深度比它小的节点的权值增加 \(v\)。 -
2 u v表示将节点 \(u\) 和 \(u\) 所有相邻节点中深度比它大的节点的权值增加 \(v\)。
但是这些操作是互不影响的，因此我们可以通过预处理将这些操作的权值放到数组里，这样在遍历时只需要一次遍历，就可以将结点权值算出来。
每个操作的权值为多次操作的权值和，而由其他结点传递过来的操作也可以和当前结点的操作进行合并。用两个权值数组：up[] down[] 即可。
通过这样进行累加求出最终的权值和。
- 接着我们进行遍历求权值。
-
对于操作 \(1\)，我们可以根据结点深度从大到小进行遍历结点，因为小于此时结点的深度的话，就不会进行操作，这样只需要进行一次遍历即可完成所有的操作 \(1\) 操作。
-
对于操作 \(2\) 也同样如此，我们可以根据结点深度从小到大进行遍历结点，因为大于此时结点的深度的话，就不会进行操作，这样也是只需要进行一次遍历即可完成所有的操作 \(2\) 操作。
- 最后就输出
(w[i]+up[i]+down[i])%1e9+7
正解1
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
const int mod = 1e9+7;
vector<int > g[N<<1];
int n,m,q;
int w[N];
int wt[N];
struct node
{
int we,id;
}a[N];
int xiao[N],da[N];
void dfsxiao(int u,int k){ xiao[u]=(xiao[u]+k)%mod; }
void dfsda(int u,int k){ da[u]=(da[u]+k)%mod; }
void dfs(int x,int cnt)
{
a[x].id=x;
a[x].we=wt[x]=cnt;
for(auto e:g[x])
{
if(!a[e].we)
dfs(e,cnt+1);
}
}
bool cmpda(node a,node b)
{
if(a.we!=b.we)
return a.we<b.we;
else
return a.id<b.id;
}
bool cmpxiao(node a,node b)
{
if(a.we!=b.we)
return a.we>b.we;
else
return a.id>b.id;
}
signed main()
{
// freopen("kodori.in","r",stdin);
// freopen("kodori.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
cin>>w[i];
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1,1);
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
for(int i=1;i<=q;i++)
{
int t,u,k;
cin>>t>>u>>k;
if(t==1)
dfsxiao(u,k);
else
dfsda(u,k);
}
sort(a+1,a+n+1,cmpxiao);
for(int i=1;i<=n;i++)
{
int res=a[i].id;
for(auto e:g[res])
{
if(wt[e]<wt[res])
xiao[e]=(xiao[e]+xiao[res])%mod;
}
}
sort(a+1,a+n+1,cmpda);
for(int i=1;i<=n;i++)
{
int res=a[i].id;
for(auto e:g[res])
{
if(wt[e]>wt[res])
da[e]=(da[e]+da[res])%mod;
}
}
for(int i=1;i<=n;i++)
{
cout<<(w[i]+da[i]+xiao[i])%mod<<" ";
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
正解2
#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];//up数组表示的是这个结点给自己以及深度比他小的结点增加的权值 down数组 是大
int n,m,q,cnt,head[1000005],d[1000005];
void add(int u,int v) {
e[++cnt].to=v;//cnt这条边的终点
e[cnt].next=head[u];//cnt这条边的下一条边
head[u]=cnt;//u后面的第一条边的编号更改
}
void dfs(int u,int fa) {
g.push_back(mk(d[u],u));//把这个结点的度和这个结点 构成一个结构体，放到g向量里
for(int i=head[u]; i; i=e[i].next) {//去找u的所有邻接点
int v=e[i].to;
if(v==fa) continue;//如果找到的是父亲 就跳过
d[v]=d[u]+1;//否则，这个点的深度就是父结点的深度+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++) {//n个结点，n-1条边，输入进去
int u,v;
cin>>u>>v;
add(u,v);//链式前向星存储 因为有虚边，所以都加上 变成一棵树
add(v,u);
}
dfs(1,1);//计算每个结点的深度
for(int i=1; i<=m; i++) {//m条虚边，加进去
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1; i<=q; i++) {//把所有增加的，先存起来 比如 1 7 5 1 7 10
int pd,u,v; //再比如 2 5 5 2 5 9 这种
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) {//找x结点的邻接点
int y=e[j].to;//邻接点是y
if(d[y]>d[x]) down[y]=(down[y]+down[x])%p;//如果y的深度比x大，那就给y增加权值
}
}
// reverse(g.begin(),g.end());//按照深度从大到小排序，更新操作一增加的权值
for(int i=g.size()-1; i>=0;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;
}