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

B. 正则表达式

题目：

https://ac.nowcoder.com/acm/contest/87865/B
给出n个地址，每个地址的形式为x.x.x.x，找四个x都满足x>=0&&x<=255的个数

思路：

首先定义四个数组和一个字符，然后按题目所给的形式输入，判断四个数组若都满足条件，ans++，最后输出ans。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1100;
int a[N],b[N],c[N],d[N];
char s;
signed main()
{IOSint n,ans=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>s>>b[i]>>s>>c[i]>>s>>d[i];if(a[i]>=0&&a[i]<=255&&b[i]>=0&&b[i]<=255&&c[i]>=0&&c[i]<=255&&d[i]>=0&&d[i]<=255)ans++;}cout<<ans<<'\n';
}

C. Circle

题目：

https://ac.nowcoder.com/acm/contest/87865/C
给出一个整数n，求n个圆可以分割的最大区域数

思路：

找规律，一开始看着样例直接写的pow(2,n)，想简单了，又花了一下4，5个的情况，发现0,1的时候是pow(2,n)，当n>1时，满足n*n-(n-2)。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
signed main()
{IOSint t;cin>>t;while(t--){int n;cin>>n;if(n<2)cout<<pow(2,n)<<" ";else{cout<<n*n-(n-2)<<" ";}}
}

D. 开心消消乐（Right Version）

题目：

https://ac.nowcoder.com/acm/contest/87865/D
给定一个n个数的数列，可执行若干次操作，每次操作选定两个数𝑙,𝑟(1≤𝑙≤𝑟≤𝑛)l,r(1≤l≤r≤n)，使得∀𝑖∈[𝑙,𝑟],𝑎i=ai⨁al。要求l一直递减。求让这个序列全部转换为0的最小操作次数。

思路：

​ 这个题比赛的时候过的人挺少，直接没看，后来别人给我说这道题特别简单，看了一眼真的特别简单，立马写出来。
因为题目已经限制l一直递减了，所以只需要定义一个数组，令a[0]=-1，从a[1]开始，如果a[i]!=a[i-1]，就让ans++，最后得出的ans就是答案。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e6+20;
int a[N];
signed main()
{IOSint n,ans=0;a[0]=-1;cin>>n;for(int i=1;i<=n;i++){ cin>>a[i];if(a[i]!=a[i-1]){if(a[i]!=0)ans++;}}cout<<ans<<'\n';}

F.累加器

题目：

https://ac.nowcoder.com/acm/contest/87865/F
给出一个数n，每次加1，观察二进制下位数有几位变化，在加了k次1后总共变化了多少。

思路1：

1.跟第一次萌新联赛的题相似，1是每两次出现1次，2是每4次出现1次，依次类推n是每pow(2,n)出现1次。
2.累加，令e=1;sum=sum+x/e;e*=2;当x<e的时候截止
3.再利用前缀和，用x+y次加1二进制下的改变量减去x次加1的改变量。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e6;int solve(int x)
{int e=1,sum=0;while(x>=e){sum=sum+x/e;e*=2;}return sum;
}signed main()
{IOSint t;cin>>t;while(t--){int x,y;cin>>x>>y;int ss=solve(x+y)-solve(x);cout<<ss<<'\n';}
}

思路2：

用异或写：
1.首先累加位数的改变量，用bitset定义p,q,s，然后令p=1，进入循环，令q=i，然后s=q^p，异或的性质是相同为0，不同为1，统计异或后1的个数，后面令p=q。不断循环累加异或后1的个数。存在数组a中
2.利用前缀和，a[y+x]-a[x]得出最后答案。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<bitset>
int a[2000010];
bitset<64>p,q,s;int x,y,w=0;void solve()
{cin>>x>>y;cout<<a[y+x]-a[x]<<endl;
}signed main()
{IOSint t=1;cin>>t;p=1;for(int i=1;i<=2000010;i++){q=i;s=p^q;w+=s.count();a[i]=w;p=q;}while(t--){solve();}return 0; 
}

J.keillempkill学姐の卷积

题目：

https://ac.nowcoder.com/acm/contest/87865/J
给一个nn的矩阵和一个mm的矩阵(1≤n≤m≤20)，卷积操作得出最后结果。
卷积操作是：比如nn比较小，就在mm的矩阵中从头开始先找出与nn数量相同的矩阵，对应位置分别相乘再相加，然后再让列加1，直到覆盖完全部的列，再把行加1，直到把整个mm的矩阵覆盖完全。最后输出一个(m-n+1)*(m-n+1)的矩阵。

思路：

1.首先看for循环吧nn和mm的矩阵输入
2.开for循环，i<=n;j<=n，x=0,y=0；累加ans+=a[i][j]*b[i+x][j+y];当in&&jn的时候就把此时的ans值存入数组里，如果此时的j+y!=0，就让y++，否则x++，并且此时让y重置回0，当i+xm&&j+ym时说明m*m的矩阵已经全被覆盖，结束循环。
3.输出储存的ans的值，当**(i+1)%(m-n+1)==0**时，输出换行。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int a[30][30],b[30][30],tt[1000];
signed main()
{IOSint n,m,ans=0,x=0,y=0,s=0;cin>>n>>m;int t=m-n+1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)cin>>b[i][j];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ans+=a[i][j]*b[i+x][j+y];//cout<<ans<<'\n';if(i==n&&j==n){//cout<<"0"<<'\n';tt[s++]=ans;if(i+x==m&&j+y==m){//tt[s++]=ans;break;}if(j+y!=m)y++;else{x++;y=0;}i=0,j=0;ans=0;//cout<<x<<" "<<y<<'\n';}}}//cout<<s<<'\n';//cout<<"-1"<<'\n';for(int i=0;i<s;i++){cout<<tt[i]<<" ";if((i+1)%t==0)cout<<'\n';}
}

L.SSH

题目：

https://ac.nowcoder.com/acm/contest/87865/L
1.输入m,n,q，m是密钥对，包含一个公钥和一个私钥；n是主机；q代表q次查询
2.输入m行，每行两个字符串代表一个公钥和一个私钥。
3.n组数据，包含一个字符串代表id，和一个整数k代表用户数量，然后是k行，每行一个字符串用户名，一个整数t表示公钥数量，t个字符串表示公钥
4.接下来q行，表示q次查询，每行一个字符串表示用户名，一个字符串表示用户id，一个字符串表示私钥。

思路：

首先用一个map来存公钥，然后再用两个map里面套vector来分别存用户名和私钥，然后利用for循环找是否有满足条件的（细节见代码注释），按要求输出。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+20;
signed main()
{IOSint m,n,q;cin>>m>>n>>q;map<string,string> a;for(int i=1;i<=m;i++){string s1,s2;cin>>s1>>s2;a[s2]=s1;}map<string,vector<string> > s;map<string,vector<string> > b;for(int i=1;i<=n;i++){string t;int k;cin>>t>>k;for(int j=1;j<=k;j++){string user;cin>>user;s[t].push_back(user);int tt;cin>>tt;for(int cnt=1;cnt<=tt;cnt++){string ss;cin>>ss;b[user].push_back(ss);}}}for(int i=1;i<=q;i++){string s1,s2,s3;cin>>s1>>s2>>s3;int flag=0;for(auto t : s[s2])//将该ip对应的用户名赋给t{if(t==s1)//如果该ip对应的用户名中包含s1{flag=1;break;}}if(flag==0)cout<<"No"<<'\n';else{string ans=a[s3];//所要查询私钥对应的公钥int f=0;for(auto t : b[s1])//将该ip该用户有的公钥赋给t{if(t==ans)//如果该ip该用户有的公钥中有所要查询私钥对应的公钥{f=1;break;}}if(f==0)cout<<"No"<<'\n';elsecout<<"Yes"<<'\n';}}
}