河南萌新联赛2024第（三）场：河南大学 BCEFJL

没腿的鸟  金牌会员 | 2024-8-2 15:23:46 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 656|帖子 656|积分 1968

 B   正则表达式

思路:直接scanf按格式输入a,b,c,d,然后判断四个数是不是都符合0~255即可
AC代码:
  1. #include<bits/stdc++.h>
  2. using namespace std;
  6. int main(){
  7.     int t,cnt=0;
  8.     cin>>t;
  9.     while(t--){
  10.         int a,b,c,d;
  11.         scanf("%d.%d.%d.%d",&a,&b,&c,&d);
  12.         if(a>=0 && a<=255 &&
  13.         b>=0 && b<=255 &&
  14.         c>=0 && c<=255 &&
  15.         d>=0 && d<=255) cnt++;
  16.     }
  17.     cout<<cnt<<endl;
  18.     return 0;
  19. }
复制代码
C   Circle

思路:设圆的个数为n,n==0时,ans=1; n>0时,ans=n*(n-1)+2
AC代码:
  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. #define int unsigned long long
  6. signed main(){
  7.     int t,cnt=0;
  8.     cin>>t;
  9.     vector<int> arr(t);
  10.     for(int i=0;i<=t;i++) cin>>arr[i];
  11.     for(auto xx:arr){
  12.         if(xx==0) cout<<1<<" ";
  13.         else cout<<xx*xx-xx+2<<" ";
  14.     }
  15.     return 0;
  16. }
复制代码
J   keillempkill学姐の卷积

思路:四个循环嵌套模拟即可
AC代码:
  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int a[22][22];
  5. int b[22][22];
  6. int n,m;
  8. #define int long long
  10. signed main(){
  11.     cin>>n>>m;
  12.     for(int i=1;i<=n;i++){
  13.         for(int j=1;j<=n;j++){
  14.             cin>>a[i][j];
  15.         }
  16.     }
  17.     for(int i=1;i<=m;i++){
  18.         for(int j=1;j<=m;j++) cin>>b[i][j];
  19.     }
  20.     int xx = m-n+1;
  21.     for(int i=1;i<=xx;i++){
  22.         for(int j=1;j<=xx;j++){
  23.             int ans = 0;
  24.             for(int ix=1;ix<=n;ix++){
  25.                 for(int iy=1;iy<=n;iy++){
  26.                     ans += a[ix][iy]*b[ix+i-1][iy+j-1];
  27.                 }
  28.             }
  29.             cout<<ans<<" ";
  30.         }
  31.         cout<<endl;
  32.     }
  33.     return 0;
  34. }
复制代码
L   SSH

思路:数据量不大,合理存储之后直接搜刮就好,公钥和私钥用map来存,用户和其拥有的私钥开一个由string和vector构成的结构体来储存,ip地点下就是map<string,结构体>
AC代码:
  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int n,m,q;
  5. map<string,string> key;
  7. struct user{
  8.     string name;
  9.     vector<string> ma;
  10. };
  12. map<string,vector<user> > wang;
  14. int main(){
  15.     cin>>m>>n>>q;
  16.     for(int i=0;i<m;i++){
  17.         string aa,bb;
  18.         cin>>aa>>bb;
  19.         key[bb]=aa;
  20.     }
  21.     for(int i=0;i<n;i++){
  22.         string ww; int x;
  23.         cin>>ww>>x;
  24.         //user u;
  25.         while(x--){
  26.             user uu;
  27.             string na; int c;
  28.             cin>>na>>c;
  29.             uu.name=na;
  30.             while(c--){
  31.                 string cc;
  32.                 cin>>cc;
  33.                 uu.ma.push_back(cc);
  34.             }
  35.             wang[ww].push_back(uu);
  36.         }
  37.     }
  39. // cout<<endl<<" ### "<<endl;
  40. // for(auto xx:key) cout<<xx.first<<" "<<xx.second<<endl;
  41. // cout<<endl;
  42. // for(auto xx:wang){
  43. //     cout<<xx.first<<" ";
  44. //     for(auto aa:wang[xx.first]){
  45. //         cout<<aa.name<<" ";
  46. //         for(auto bb:aa.ma) cout<<bb<<" ";
  47. //     }cout<<endl;   
  48. // }
  49. // cout<<endl;
  53.     while(q--){
  54.         string naa,iip,kee;
  55.         cin>>naa>>iip>>kee;
  56.         kee = key[kee];
  57.         bool flag = false;
  58.         for(auto xx:wang[iip]){
  59.             if(xx.name==naa){
  60.                 for(auto aa:xx.ma){
  61.                     if(aa==kee){
  62.                         flag = true;
  63.                         break;
  64.                     }
  65.                 }
  66.             }
  67.         }
  68.         if(flag) cout<<"Yes"<<endl;
  69.         else cout<<"No"<<endl;
  70.     }
  71.     return 0;
  72. }
复制代码
F   累加器

思路:起首将输入的数转化成二进制用一个字符串存起来,我们按位来分析。 起首,二进制下的末尾有n次累加就会变革n次,若末尾最初为0,则末尾的前一位会变革n/2次,反之则会变革(n+1)/2次(相当于末尾最初就变革了一次)   据此可以推出每一位都满意这个推算,不断加给ans即可
AC代码:
  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int t,a,b;
  6. int main(){
  7.     cin>>t;
  8.     while(t--){
  9.         cin>>a>>b;
  10.         int aa=a;
  11.         string s = "00000000000000000000000000";
  12.         int cnt = 1;
  13.         while(aa){
  14.             if(aa%2) s[cnt]='1';
  15.             aa/=2;
  16.             cnt++;
  17.         }
  18.         //cout<<s<<endl;
  19.         int ans = 0;
  20.         ans += b;
  21.         int cnn = 2;
  22.         while(b){
  23.             if(s[cnn-1]=='1') b++;
  24.             b/=2;
  25.             ans += b;
  26.             cnn++;
  27.         }
  28.         cout<<ans<<endl;
  29.     }
  30.     return 0;
  31. }
复制代码
E   区间

这题是赛后补的,之前没学过线段树,借这个题也是学了半天线段树,解法就是用线段树求区间连续最大子段和
这题来写具体一点
初始化数组:

由于最开始都是白色的,所以数组初始化全为1,接着就是用build()建立
  1.     int n,q;
  2.     cin>>n>>q;
  3.     for(int i=1;i<=n;i++){
  4.         w[i]=1;
  5.     }
  6.     build(1,1,n);
复制代码
建立:

node是树的每个节点包罗的信息注意线段树一般都要开4*N以避免越界题目 )
l,r表示左右端点         sum0,sum1表示该段中0的数量和1的数量
lmx1,rmx1表示从左端点向右和从右端点向左连续最长仅1子段的长度(lmx0,rmx0反之)
lazy是lazy标记
build()函数建立的过程是从上到下不断二分区间的过程,用到了递归,取mid时采用位运算效率更高,lazy标记最开始都初始化为0
  1. struct node{
  2.     int l,r;
  3.     int sum1,sum0;
  4.     int lmx1,rmx1;
  5.     int rmx0,lmx0;
  6.     int lazy;
  7. }tr[N*4];
  9. void build(int p,int l,int r){
  10.     tr[p]={l,r,w[l],w[l]^1,w[l],w[l],w[l]^1,0};
  11.     if(l==r) return ;
  12.     int mid=l+r>>1;
  13.     build(lc,l,mid);
  14.     build(rc,mid+1,r);
  15.     pushup(p);
  16. }
复制代码
换色操作:

这里的swap操作仅限于01数组,若是非01数组,则要按照dp的头脑取max
这里的代码也适用于区间修改,只是按题目中来就是单点修改了,0换成1 1换成0 的事
  1. void update1(int p,int l,int r){
  2.     if(l<=tr[p].l && r>=tr[p].r){
  3.         swap(tr[p].sum1,tr[p].sum0);
  4.         swap(tr[p].lmx1,tr[p].lmx0);
  5.         swap(tr[p].rmx1,tr[p].rmx0);
  6.         tr[p].lazy++;
  7.         return;
  8.     }
  9.     pushdown(p);
  10.     int mid=tr[p].l+tr[p].r>>1;
  11.     if(l<=mid) update1(lc,l,r);
  12.     if(r>mid) update1(rc,l,r);
  13.     pushup(p);
  14. }
复制代码
向上向下更新:

先根据lazy标记的信息向下更新,之后再向上更新
  1. void pushup(int p){
  2.     tr[p].sum1=max(max(tr[lc].sum1,tr[rc].sum1),tr[lc].rmx1+tr[rc].lmx1);
  3.     tr[p].sum0=max(max(tr[lc].sum0,tr[rc].sum0),tr[lc].rmx0+tr[rc].lmx0);
  4.     tr[p].lmx1=tr[lc].lmx1;
  5.     tr[p].rmx1=tr[rc].rmx1;
  6.     tr[p].lmx0=tr[lc].lmx0;
  7.     tr[p].rmx0=tr[rc].rmx0;
  8.     if(tr[lc].r-tr[lc].l+1==tr[lc].lmx1) tr[p].lmx1+=tr[rc].lmx1;
  9.     if(tr[rc].r-tr[rc].l+1==tr[rc].rmx1) tr[p].rmx1+=tr[lc].rmx1;
  10.     if(tr[lc].r-tr[lc].l+1==tr[lc].lmx0) tr[p].lmx0+=tr[rc].lmx0;
  11.     if(tr[rc].r-tr[rc].l+1==tr[rc].rmx0) tr[p].rmx0+=tr[lc].rmx0;
  12. }
  14. void pushdown(int p){
  15.     int ta=tr[p].lazy;
  16.     if(ta&1)
  17.     {
  18.         swap(tr[lc].sum0,tr[lc].sum1);
  19.         swap(tr[lc].lmx0,tr[lc].lmx1);
  20.         swap(tr[lc].rmx0,tr[lc].rmx1);
  22.         swap(tr[rc].lmx1,tr[rc].lmx0);
  23.         swap(tr[rc].sum0,tr[rc].sum1);
  24.         swap(tr[rc].rmx1,tr[rc].rmx0);
  26.         tr[lc].lazy+=ta;
  27.         tr[rc].lazy+=ta;
  28.         tr[p].lazy=0;
  29.     }
  30. }
复制代码

询问部分:

从最顶端开始,然后逐级取mid,分右端点<=mid.  左端点>mid  mid在左右端点中间 三种情况处理
  1. node query(int p,int l,int r){
  2.     if(l<=tr[p].l && tr[p].r<=r) return tr[p];
  3.     pushdown(p);
  4.     int mid=tr[p].l+tr[p].r>>1;
  5.     node x,y,ans;
  6.     if(r<=mid) ans = query(lc,l,r);
  7.     else if(l>mid) ans = query(rc,l,r);
  8.     else{
  9.         x = query(lc,l,mid);
  10.         y = query(rc,mid+1,r);
  11.         ans.sum1 = max({x.sum1,y.sum1,x.rmx1+y.lmx1});
  12.         ans.sum0 = max({x.sum0,y.sum0,x.rmx0+y.lmx0});
  13.         ans.lmx1=x.lmx1;
  14.         ans.lmx0=x.lmx0;
  15.         ans.rmx0=y.rmx0;
  16.         ans.rmx1=y.rmx1;
  17.         if(x.r-x.l+1==x.lmx1) ans.lmx1+=y.lmx1;
  18.         if(x.r-x.l+1==x.lmx0) ans.lmx0+=y.lmx0;
  19.         if(y.r-y.l+1==y.rmx1) ans.rmx1+=x.rmx1;
  20.         if(y.r-y.l+1==y.rmx0) ans.rmx0+=x.rmx0;
  21.     }
  22.     return ans;
  23. }
复制代码
AC代码:

  1. #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[N];struct node{    int l,r;    int sum1,sum0;    int lmx1,rmx1;    int rmx0,lmx0;    int lazy;}tr[N*4];void pushup(int p){    tr[p].sum1=max(max(tr[lc].sum1,tr[rc].sum1),tr[lc].rmx1+tr[rc].lmx1) ;    tr[p].sum0=max(max(tr[lc].sum0,tr[rc].sum0),tr[lc].rmx0+tr[rc].lmx0);    tr[p].lmx1=tr[lc].lmx1;    tr[p].rmx1=tr[rc].rmx1;    tr[p].lmx0=tr[lc].lmx0;    tr[p].rmx0=tr[rc].rmx0;    if(tr[lc].r-tr[lc].l+1==tr[lc].lmx1) tr[p].lmx1+=tr[rc].lmx1;    if(tr[rc].r-tr[rc].l+1==tr[rc].rmx1) tr[p].rmx1+=tr[lc].rmx1;    if(tr[lc].r-tr[lc].l+1==tr[lc].lmx0) tr[p].lmx0+=tr[rc].lmx0;    if(tr[rc].r-tr[rc].l+1==tr[rc].rmx0) tr[p].rmx0+=tr[lc].rmx0;}void pushdown(int p){    int ta=tr[p].lazy;    if(ta&1)    {        swap(tr[lc].sum0,tr[lc].sum1);        swap(tr[lc].lmx0,tr[lc].lmx1);        swap(tr[lc].rmx0,tr[lc].rmx1);         swap(tr[rc].lmx1,tr[rc].lmx0);        swap(tr[rc].sum0,tr[rc].sum1);        swap(tr[rc].rmx1,tr[rc].rmx0);         tr[lc].lazy+=ta;         tr[rc].lazy+=ta;        tr[p].lazy=0;    }}void build(int p,int l,int r){    tr[p]={l,r,w[l],w[l]^1,w[l],w[l],w[l]^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){
  2.     if(l<=tr[p].l && r>=tr[p].r){
  3.         swap(tr[p].sum1,tr[p].sum0);
  4.         swap(tr[p].lmx1,tr[p].lmx0);
  5.         swap(tr[p].rmx1,tr[p].rmx0);
  6.         tr[p].lazy++;
  7.         return;
  8.     }
  9.     pushdown(p);
  10.     int mid=tr[p].l+tr[p].r>>1;
  11.     if(l<=mid) update1(lc,l,r);
  12.     if(r>mid) update1(rc,l,r);
  13.     pushup(p);
  14. }node query(int p,int l,int r){
  15.     if(l<=tr[p].l && tr[p].r<=r) return tr[p];
  16.     pushdown(p);
  17.     int mid=tr[p].l+tr[p].r>>1;
  18.     node x,y,ans;
  19.     if(r<=mid) ans = query(lc,l,r);
  20.     else if(l>mid) ans = query(rc,l,r);
  21.     else{
  22.         x = query(lc,l,mid);
  23.         y = query(rc,mid+1,r);
  24.         ans.sum1 = max({x.sum1,y.sum1,x.rmx1+y.lmx1});
  25.         ans.sum0 = max({x.sum0,y.sum0,x.rmx0+y.lmx0});
  26.         ans.lmx1=x.lmx1;
  27.         ans.lmx0=x.lmx0;
  28.         ans.rmx0=y.rmx0;
  29.         ans.rmx1=y.rmx1;
  30.         if(x.r-x.l+1==x.lmx1) ans.lmx1+=y.lmx1;
  31.         if(x.r-x.l+1==x.lmx0) ans.lmx0+=y.lmx0;
  32.         if(y.r-y.l+1==y.rmx1) ans.rmx1+=x.rmx1;
  33.         if(y.r-y.l+1==y.rmx0) ans.rmx0+=x.rmx0;
  34.     }
  35.     return ans;
  36. }void solve(){    int n,q;
  37.     cin>>n>>q;
  38.     for(int i=1;i<=n;i++){
  39.         w[i]=1;
  40.     }
  41.     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企服之家，中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

没腿的鸟

金牌会员
这个人很懒什么都没写!

楼主热帖

标签云

挺好的 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表