当前位置：首页 > news >正文

河南萌新2024第二场

news 2025/11/23 1:05:00

H 狼狼的备忘录

题目大意：

给定n本备忘录，里面记录了一个人的m个星座信息，要求按一下要求整理备忘录

A：同一个成员的星座信息 x 是星座信息 y 的后缀，那么星座信息 x 会没有星座信息 y 完整，从而应该只保留星座信息 y ，删除星座信息 x 。
同一个成员的星座信息可能以相同格式出现多次，那么只保留该信息一次。

思路：

通过备忘录的整理规则

set < string >容器可以完成排序功能

substr(i：1~n) 可以枚举出所有以i结尾的后缀

将用户名和对应信息set映射到map中: map< string ,set< string > > 方便了存储

之后就是模拟

Solved：

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N=1e6+10;signed main()
{map<string,set<string>> mp;int n;cin>>n;while(n--){//n本备忘录 string s;cin>>s;//用户名 int m;cin>>m;//个数 while(m--){//存用户名里面的信息 string ss;cin>>ss;mp[s].insert(ss);}}for(auto &[x,y]:mp){//枚举所有用户 for(auto &xx:y){//枚举每个用户中所有的信息 for(int i=1;i<=xx.size();i++){//枚举每个信息的每个后缀string str=xx.substr(i);//如果该信息的后缀 在y中出现，则将str从y中删去 if(y.count(str)){ y.erase(str);}}}}cout<<mp.size()<<endl;for(auto &[x,y]:mp){cout<<x<<" ";cout<<y.size()<<" ";for(auto &xx:y){cout<<xx<<" ";}cout<<endl;}return 0;
}

D A*BBBB

题目大意：

给两个整数a和b，输出a∗b 但是a,b非常大，0<=a,b<=10^1000000

b的每一位都相同

思路：

因为b的每一位都相同，当一个很大的数*11111…的时候

相当于每一位上的数字错位1111…次，然后相加

在这里插入图片描述

可以看到，结果上的每一位都是以b的大小为一个区间，并且在原数字上的区间和

因此可以先把原数字*（b /11111）按位存入一个前缀和数组中，

然后将答案按照b的大小设定一个区间，依次存入答案数组

Solved：

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N=1e6+10;
int a[N],sum[N];
int n,m;void solve()
{memset(sum,0,sizeof(sum));string A,B;cin>>A>>B;int a=0,b=0;reverse(A.begin(),A.end());vector<int> res;for(int i=0;i<A.size();i++){b=(A[i]-'0')*(B[0]-'0');res.push_back((b+a)%10);a=(b+a)/10;}while(a){res.push_back(a%10);a/=10;}int len=res.size();for(int i=0;i<len;i++){sum[i+1]=sum[i]+res[i];}string ans; int q=0;for(int i=1;i<=len+B.size();i++){int l=max((int)0,(int)(i-B.size()));int r=min(i,len);q+=sum[r]-sum[l];ans.push_back(q%10+'0');q/=10; }while(q){ans.push_back(q%10+'0');q/=10;}while(ans.size()>1&&ans.back()=='0'){ans.pop_back();}reverse(ans.begin(),ans.end());cout<<ans<<endl;
}signed main()
{std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();} return 0;
}