国庆普及模拟赛-3
题目链接
file:///C:/Users/Administrator/Desktop/1003/%E4%B8%8B%E5%8F%91%E6%96%87%E4%BB%B61003/20241003.pdf
题解：file:///C:/Users/Administrator/Desktop/%E9%A2%98%E8%A7%A3.pdf
总结：本次考试反映出在字符串上面有很大问题，要转向复习，练题
T1：按照题目要求进行模拟，不用考虑复杂度
错因：在调试数字为两位数时，经常出错，所以选择只考虑数字为一位数的情况，最终30分
AC代码：
#include<bits/stdc++.h>
using namespace std;
int T,n,cnt,pos;
string a,b,c;
int main() {
freopen("letter.in","r",stdin);
freopen("letter.out","w",stdout);
cin >> T;
while(T--) {
cin >> n >> a;
a=" "+a,b="";
for(int i=1;i<=n;++i) {
if(a[i]>='a'&&a[i]<='z')b+=a[i];//直接在字符串后面补上当前字符
else {
cnt=0,pos=i;
while(a[pos]>='0'&&a[pos]<='9') {//计算要复读多少次
cnt*=10;
cnt+=a[pos]-'0';
pos++;
}
i=pos-1;
c=b,cnt--;
while(cnt--)b+=c;//复读
}
}
cout<<b<<endl;
}
return 0;
}T2：
思路：直接暴力模拟pos在哪，O（ n^2)的算法绝对会爆，n<10^6
所以考虑使用前缀合（见代码）
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long p1[N],p0[N];
signed main() {
freopen("soldier.in","r",stdin);
freopen("soldier.out","w",stdout);
long long n;
string s;
cin>>n>>s;
s =" "+ s;
for(int i=1; i<s.size(); i++) {
p1[i]=p1[i-1]+(s[i]=='1')*i;
p0[i]=p0[i-1]+(s[i]=='0')*i;
}
long long ans = 1e9;
for(int i=1; i<=n; i++) {
ans=min(ans,abs(p0[i-1]-p1[n]+p1[i-1]));
}
cout<<ans<<endl;
}T3：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int t,tot;
string a[N];
struct node{
int x,y;
}b[N];
bool operator <(node x,node y){
return x.y<y.y;
}
long long read() {
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int main() {
freopen("lie.in","r",stdin);
freopen("lie.out","w",stdout);
cin>>t;
while(t--) {
int n=read();
for(int i=1; i<=n; i++)cin>>a[i];
string s;
cin>>s;
int len=s.size();
for(int i=0; i<len; i++) {
for(int j=1; j<=n; j++) {
int cnta=-1,cntb=i-1;
int lenx=a[j].size();
while(cnta<lenx-1&&cntb<len-1&&a[j][cnta+1]==s[cntb+1]) cnta++,cntb++;
if(cnta==lenx-1) {
b[++tot].x=i,b[tot].y=cntb;
}
}
}
sort(b+1,b+tot+1);
int tmp=-1;
for(int i=1; i<=tot; i++) {
if(b[i].x<=tmp&&b[i].y>=tmp) continue;
s[b[i].y]='*';
tmp=b[i].y;
}
cout<<s<<endl;
tot=0;
}
return 0;
}T4：
#include<bits/stdc++.h>
using namespace std;
const int Mod=1e9+7,N=1e5+5;
int n,m,q,a[N],dep[N],b[N][2];
vector<int> v[N],vec;
void dfs(int x,int fa) {
dep[x]=dep[fa]+1;
for(int i=0; i<v[x].size(); i++) {
int y=v[x][i];
if(y==fa) continue;
dfs(y,x);
}
return;
}
bool cmp(int x,int y) {
return dep[x]<dep[y];
}
int main() {
freopen("kodori.in","r",stdin);
freopen("kodori.out","w",stdout);
cin>>n>>m>>q;
for(int i=1; i<=n; i++) {
cin>>a[i];
vec.push_back(i);
}
for(int i=1; i<n; i++) {
int x,y;
cin>>x>>y;
v[x].push_back(y),v[y].push_back(x);
}
dfs(1,0);
for(int i=1; i<=m; i++) {
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1; i<=q; i++) {
int t,u,k;
cin>>t>>u>>k;
b[u][t-1]=(b[u][t-1]+k)%Mod;
}
sort(vec.begin(),vec.end(),cmp);
for(int i=0; i<n; i++) {
int x=vec[i];
for(int j=0; j<v[x].size(); j++) {
int y=v[x][j];
if(dep[y]>dep[x]) b[y][1]=(b[y][1]+b[x][1])%Mod;
}
}
for(int i=n-1; i>=0; i--) {
int x=vec[i];
for(int j=0; j<v[x].size(); j++) {
int y=v[x][j];
if(dep[y]<dep[x]) b[y][0]=(b[y][0]+b[x][0])%Mod;
}
}
for(int i=1; i<=n; i++) {
int ans=((a[i]+b[i][1])%Mod+b[i][0])%Mod;
cout<<ans<<" ";
}
return 0;
}原文地址：https://blog.csdn.net/weixin_70468627/article/details/142695430
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！