河南萌新联赛2024第（三）场：河南大学 BCEFJL
B 正则表达式思路:直接scanf按格式输入a,b,c,d,然后判断四个数是不是都符合0~255即可
AC代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,cnt=0;
cin>>t;
while(t--){
int a,b,c,d;
scanf("%d.%d.%d.%d",&a,&b,&c,&d);
if(a>=0 && a<=255 &&
b>=0 && b<=255 &&
c>=0 && c<=255 &&
d>=0 && d<=255) cnt++;
}
cout<<cnt<<endl;
return 0;
} C Circle
思路:设圆的个数为n,n==0时,ans=1; n>0时,ans=n*(n-1)+2
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
signed main(){
int t,cnt=0;
cin>>t;
vector<int> arr(t);
for(int i=0;i<=t;i++) cin>>arr;
for(auto xx:arr){
if(xx==0) cout<<1<<" ";
else cout<<xx*xx-xx+2<<" ";
}
return 0;
} J keillempkill学姐の卷积
思路:四个循环嵌套模拟即可
AC代码:
#include<bits/stdc++.h>
using namespace std;
int a;
int b;
int n,m;
#define int long long
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a;
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++) cin>>b;
}
int xx = m-n+1;
for(int i=1;i<=xx;i++){
for(int j=1;j<=xx;j++){
int ans = 0;
for(int ix=1;ix<=n;ix++){
for(int iy=1;iy<=n;iy++){
ans += a*b;
}
}
cout<<ans<<" ";
}
cout<<endl;
}
return 0;
} L SSH
思路:数据量不大,合理存储之后直接搜刮就好,公钥和私钥用map来存,用户和其拥有的私钥开一个由string和vector构成的结构体来储存,ip地点下就是map<string,结构体>
AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
map<string,string> key;
struct user{
string name;
vector<string> ma;
};
map<string,vector<user> > wang;
int main(){
cin>>m>>n>>q;
for(int i=0;i<m;i++){
string aa,bb;
cin>>aa>>bb;
key=aa;
}
for(int i=0;i<n;i++){
string ww; int x;
cin>>ww>>x;
//user u;
while(x--){
user uu;
string na; int c;
cin>>na>>c;
uu.name=na;
while(c--){
string cc;
cin>>cc;
uu.ma.push_back(cc);
}
wang.push_back(uu);
}
}
// cout<<endl<<" ### "<<endl;
// for(auto xx:key) cout<<xx.first<<" "<<xx.second<<endl;
// cout<<endl;
// for(auto xx:wang){
// cout<<xx.first<<" ";
// for(auto aa:wang){
// cout<<aa.name<<" ";
// for(auto bb:aa.ma) cout<<bb<<" ";
// }cout<<endl;
// }
// cout<<endl;
while(q--){
string naa,iip,kee;
cin>>naa>>iip>>kee;
kee = key;
bool flag = false;
for(auto xx:wang){
if(xx.name==naa){
for(auto aa:xx.ma){
if(aa==kee){
flag = true;
break;
}
}
}
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
} F 累加器
思路:起首将输入的数转化成二进制用一个字符串存起来,我们按位来分析。 起首,二进制下的末尾有n次累加就会变革n次,若末尾最初为0,则末尾的前一位会变革n/2次,反之则会变革(n+1)/2次(相当于末尾最初就变革了一次) 据此可以推出每一位都满意这个推算,不断加给ans即可
AC代码:
#include<bits/stdc++.h>
using namespace std;
int t,a,b;
int main(){
cin>>t;
while(t--){
cin>>a>>b;
int aa=a;
string s = "00000000000000000000000000";
int cnt = 1;
while(aa){
if(aa%2) s='1';
aa/=2;
cnt++;
}
//cout<<s<<endl;
int ans = 0;
ans += b;
int cnn = 2;
while(b){
if(s=='1') b++;
b/=2;
ans += b;
cnn++;
}
cout<<ans<<endl;
}
return 0;
} E 区间
这题是赛后补的,之前没学过线段树,借这个题也是学了半天线段树,解法就是用线段树求区间连续最大子段和
这题来写具体一点
初始化数组:
由于最开始都是白色的,所以数组初始化全为1,接着就是用build()建立
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
w=1;
}
build(1,1,n); 建立:
node是树的每个节点包罗的信息:(注意线段树一般都要开4*N以避免越界题目 )
l,r表示左右端点 sum0,sum1表示该段中0的数量和1的数量
lmx1,rmx1表示从左端点向右和从右端点向左连续最长仅1子段的长度(lmx0,rmx0反之)
lazy是lazy标记
build()函数建立的过程是从上到下不断二分区间的过程,用到了递归,取mid时采用位运算效率更高,lazy标记最开始都初始化为0
struct node{
int l,r;
int sum1,sum0;
int lmx1,rmx1;
int rmx0,lmx0;
int lazy;
}tr;
void build(int p,int l,int r){
tr={l,r,w,w^1,w,w,w^1,0};
if(l==r) return ;
int mid=l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(p);
} 换色操作:
这里的swap操作仅限于01数组,若是非01数组,则要按照dp的头脑取max
这里的代码也适用于区间修改,只是按题目中来就是单点修改了,0换成1 1换成0 的事
void update1(int p,int l,int r){
if(l<=tr.l && r>=tr.r){
swap(tr.sum1,tr.sum0);
swap(tr.lmx1,tr.lmx0);
swap(tr.rmx1,tr.rmx0);
tr.lazy++;
return;
}
pushdown(p);
int mid=tr.l+tr.r>>1;
if(l<=mid) update1(lc,l,r);
if(r>mid) update1(rc,l,r);
pushup(p);
} 向上向下更新:
先根据lazy标记的信息向下更新,之后再向上更新
void pushup(int p){
tr.sum1=max(max(tr.sum1,tr.sum1),tr.rmx1+tr.lmx1);
tr.sum0=max(max(tr.sum0,tr.sum0),tr.rmx0+tr.lmx0);
tr.lmx1=tr.lmx1;
tr.rmx1=tr.rmx1;
tr.lmx0=tr.lmx0;
tr.rmx0=tr.rmx0;
if(tr.r-tr.l+1==tr.lmx1) tr.lmx1+=tr.lmx1;
if(tr.r-tr.l+1==tr.rmx1) tr.rmx1+=tr.rmx1;
if(tr.r-tr.l+1==tr.lmx0) tr.lmx0+=tr.lmx0;
if(tr.r-tr.l+1==tr.rmx0) tr.rmx0+=tr.rmx0;
}
void pushdown(int p){
int ta=tr.lazy;
if(ta&1)
{
swap(tr.sum0,tr.sum1);
swap(tr.lmx0,tr.lmx1);
swap(tr.rmx0,tr.rmx1);
swap(tr.lmx1,tr.lmx0);
swap(tr.sum0,tr.sum1);
swap(tr.rmx1,tr.rmx0);
tr.lazy+=ta;
tr.lazy+=ta;
tr.lazy=0;
}
}
询问部分:
从最顶端开始,然后逐级取mid,分右端点<=mid. 左端点>mid mid在左右端点中间 三种情况处理
node query(int p,int l,int r){
if(l<=tr.l && tr.r<=r) return tr;
pushdown(p);
int mid=tr.l+tr.r>>1;
node x,y,ans;
if(r<=mid) ans = query(lc,l,r);
else if(l>mid) ans = query(rc,l,r);
else{
x = query(lc,l,mid);
y = query(rc,mid+1,r);
ans.sum1 = max({x.sum1,y.sum1,x.rmx1+y.lmx1});
ans.sum0 = max({x.sum0,y.sum0,x.rmx0+y.lmx0});
ans.lmx1=x.lmx1;
ans.lmx0=x.lmx0;
ans.rmx0=y.rmx0;
ans.rmx1=y.rmx1;
if(x.r-x.l+1==x.lmx1) ans.lmx1+=y.lmx1;
if(x.r-x.l+1==x.lmx0) ans.lmx0+=y.lmx0;
if(y.r-y.l+1==y.rmx1) ans.rmx1+=x.rmx1;
if(y.r-y.l+1==y.rmx0) ans.rmx0+=x.rmx0;
}
return ans;
} AC代码:
#include<bits/stdc++.h>#define int long long#define lc p<<1#define rc p<<1|1#define endl '\n'using namespace std;const int N = 5e5+100,M = 1e1;const int INF = 4e18;const int mod=1<<20;typedef pair<int,int> PII;int w;struct node{ int l,r; int sum1,sum0; int lmx1,rmx1; int rmx0,lmx0; int lazy;}tr;void pushup(int p){ tr.sum1=max(max(tr.sum1,tr.sum1),tr.rmx1+tr.lmx1) ; tr.sum0=max(max(tr.sum0,tr.sum0),tr.rmx0+tr.lmx0); tr.lmx1=tr.lmx1; tr.rmx1=tr.rmx1; tr.lmx0=tr.lmx0; tr.rmx0=tr.rmx0; if(tr.r-tr.l+1==tr.lmx1) tr.lmx1+=tr.lmx1; if(tr.r-tr.l+1==tr.rmx1) tr.rmx1+=tr.rmx1; if(tr.r-tr.l+1==tr.lmx0) tr.lmx0+=tr.lmx0; if(tr.r-tr.l+1==tr.rmx0) tr.rmx0+=tr.rmx0;}void pushdown(int p){ int ta=tr.lazy; if(ta&1) { swap(tr.sum0,tr.sum1); swap(tr.lmx0,tr.lmx1); swap(tr.rmx0,tr.rmx1); swap(tr.lmx1,tr.lmx0); swap(tr.sum0,tr.sum1); swap(tr.rmx1,tr.rmx0); tr.lazy+=ta; tr.lazy+=ta; tr.lazy=0; }}void build(int p,int l,int r){ tr={l,r,w,w^1,w,w,w^1,0}; if(l==r) return ; int mid=l+r>>1; build(lc,l,mid); build(rc,mid+1,r); pushup(p);}void update1(int p,int l,int r){
if(l<=tr.l && r>=tr.r){
swap(tr.sum1,tr.sum0);
swap(tr.lmx1,tr.lmx0);
swap(tr.rmx1,tr.rmx0);
tr.lazy++;
return;
}
pushdown(p);
int mid=tr.l+tr.r>>1;
if(l<=mid) update1(lc,l,r);
if(r>mid) update1(rc,l,r);
pushup(p);
}node query(int p,int l,int r){
if(l<=tr.l && tr.r<=r) return tr;
pushdown(p);
int mid=tr.l+tr.r>>1;
node x,y,ans;
if(r<=mid) ans = query(lc,l,r);
else if(l>mid) ans = query(rc,l,r);
else{
x = query(lc,l,mid);
y = query(rc,mid+1,r);
ans.sum1 = max({x.sum1,y.sum1,x.rmx1+y.lmx1});
ans.sum0 = max({x.sum0,y.sum0,x.rmx0+y.lmx0});
ans.lmx1=x.lmx1;
ans.lmx0=x.lmx0;
ans.rmx0=y.rmx0;
ans.rmx1=y.rmx1;
if(x.r-x.l+1==x.lmx1) ans.lmx1+=y.lmx1;
if(x.r-x.l+1==x.lmx0) ans.lmx0+=y.lmx0;
if(y.r-y.l+1==y.rmx1) ans.rmx1+=x.rmx1;
if(y.r-y.l+1==y.rmx0) ans.rmx0+=x.rmx0;
}
return ans;
}void solve(){ int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
w=1;
}
build(1,1,n); while(q--){ int op; int l,r; cin>>op; if(op==1){ int x; cin>>x; update1(1,x,x); } else{ cin>>l>>r; node ans; ans = query(1,l,r); cout<<ans.sum1<<endl; } }}signed main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T=1; while(T--){ solve(); } return 0;}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]