By

牛客周赛Round 91

背单词+牛客周赛

A-while

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read();
const int N=1e3;
int main(){
	string s,str="while";
	int ans=0;
	cin>>s;
	for(int i=0;i<5;i++){
		if(s[i]!=str[i]) ans++;
	}
	cout<<ans;
	return 0;
}
int read(){
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}

B-token

前缀和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read();
const int N=1e3;
ll n,m,ans=-1,a[100010];
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++){
		m+=a[i];
		if(i-10>0) m-=a[i-10];
		ans=max(ans,m);
	}
	cout<<ans;
	return 0;
}
int read(){
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}

C-小苯的逆序对和

思维

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read();
const int N=1e3;
ll n,m1,m2,ans=-1,a[200010];
int main(){
	int t;t=read();
	while(t--){
		ans=0,m1=0,m2=1e9;
		n=read();
		for(int i=1;i<=n;i++) a[i]=read();
		for(int i=1;i<=n;i++){
			m1=max(a[i],m1);
			if(a[i]<m1) ans=max(m1+a[i],ans);
		}
		cout<<ans<<"\n";
	}
	return 0;
}
int read(){
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}

D-数组4.0

求联通分量个数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read();
const int N=1e3;
int n;
int main(){
	int t;t=read();
	while(t--){
		unordered_map<int,int> mp;
		n=read();
		for(int i=1;i<=n;i++){
			int x=read();
			mp[x]++;
		}
		unordered_set<int> st;
		int ans=0;
		for(auto x:mp){
			if(st.find(x.first)==st.end()){
				queue<int> q;
				q.push(x.first);;
				st.insert(x.first);
				vector<int> vt;
				while(!q.empty()){
					int u=q.front();q.pop();
					vt.push_back(u);
					for(int i=u-1;i<=u+1;i++){
						if(mp.find(i)!=mp.end()&&st.find(i)==st.end()){
							st.insert(i);
							q.push(i);
						}
					}
				}
				if(vt.size()>=2) ans++;
				else ans+=mp[vt[0]];
			}
		}
		cout<<ans-1<<"\n";
	}
	return 0;
}

int read(){
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}

求连续自然数的段数

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;cin>>t;
	while(t--){
		int n,x;
		cin>>n;
		vector<int> v;
		for(int i=1;i<=n;i++)
			cin>>x,v.push_back(x);
		sort(v.begin(),v.end());
		int cnt=0,l=0,r=-1,t=0;
		for(int i=0;i<v.size();i++){
			if(v[i]>r+1){//大于1了
				if(l==r) cnt+=t;//上一个数和上一个不等于v[i]的数相等
				else cnt++;//不等
				l=v[i];//l是上一个不等于v[i]的数
				t=0;
			}
			r=v[i];//r是上一个数
			t++;
		}
		if(l==r) cnt+=t;
		else cnt++;
		cout<<cnt-2<<"\n";
	}
	return 0;
}

E-小苯的矩阵反转

题意是仅选择两行 或两列 或一行一列 其中两行可以重复 这时候就相当于什么也不做 我们只要关注所有行的1的个数的种类 和所有列的1的个数的种类 然后讨论这四种情况最后形成的图案

  • 什么也不做: 个数为0的行数为n
  • 选择两行: 个数为0的行数为n-2, 个数为m的行数为2
  • 选择两列: 个数为0的列数为m-2, 个数为n的行数为2
  • 选择一行一列: 个数为1的行数为n-1, 个数为m-1的行数为1, 个数为1的列数为m-1, 个数为n-1的列数为1
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;

int ax[1005], ay[1005];

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n,m;
    cin>>n>>m;
    char ch;
    memset(ax, 0, sizeof(int)*(n+1));
    memset(ay, 0, sizeof(int)*(m+1));
    for (int i=1; i<=n; i++)
      for (int j=1; j<=m; j++)
        cin>>ch, ax[i] += ch == '1', ay[j] += ch == '1';
    unordered_map<int, int> mpx, mpy;
    for (int i=1; i<=n; i++)
      mpx[ax[i]]++;
    for (int i=1; i<=m; i++)
      mpy[ay[i]]++;
    if (mpx[0] == n
        || mpx[0] == n-2 && mpx[m] == 2
        || mpy[0] == m-2 && mpy[n] == 2
        || mpx[1] == n-1 && mpx[m-1] == 1 && mpy[1] == m-1 && mpy[n-1] == 1)
      cout<<"YES"<<'\n';
    else
      cout<<"NO"<<'\n';
  }
  
  return 0;
}

F-小苯的因子查询

假设一个数 num ,有 odd 个奇质因数和 even 个偶质因数。那么根据

  • 奇 * 偶 = 偶
  • 奇 * 奇 = 奇

想得到奇因数，那不能选择 even ，总共 1/(even+1) 概率能得到奇因数。

偶质因数只有 2 ，fac[i] 代表 i 的阶乘含有质因数 2 的数目，若想求 fac[i+1] ，只要求 i+1 有多少个 2 的质因数即可，概率就是 1/dp[i+1]，再结合费马小定理求逆元即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+1,mod=998244353;
int fac[N];
ll fp(ll a,ll b){
	ll res=1;
	a%=mod;
	while(b>0){
		if(b&1) res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
int main(){
	fac[0]=0;
	for(int i=1;i<=N-1;i++){
		fac[i]=fac[i-1]+__builtin_ctz(i);//加上每个i的2的个数
	}
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		cout<<fp(fac[n]+1,mod-2)<<" ";
	}
	return 0;
}