牛客小白月赛77

A 

题目描述

小Why有一个 2 行 2 列的方阵 A，每个格子上都有一个数字。

小Why可以执行以下的操作至多一次：

修改任意一个格子上的数字。

小Why想知道他能否使得这个方阵每行每列之和相等。

输入描述:

以下两行，每行两个元素，其中第 iii 行第 jjj 列的元素为 Ai,j​ (0≤Ai,j​≤9)。

输出描述:

如果小Why能够使得方阵 A 每行每列之和相等，那么输出 "YES" (不含引号)，否则输出 "NO" (不含引号)。

示例1

输入

9 7
7 7

输出

YES

示例2

输入

1 2
3 4

输出

NO

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
const int N=1e6+10;
typedef double db;
int a,b,c,d;
signed main()
{
	 cin>>a>>b>>c>>d;
	 int cnt=0;
	 if(a==d)cnt++;
	 if(b==c)cnt++;
	 if(cnt>=1){
	 	cout<<"YES";
	 }
	 else{
	 	cout<<"NO";
	 }
	
	return 0;
} 
 
//  a b c d   a+b=c+d=a+c=b+d   b=c a=d 

 B

题目描述

小Why有一个长度为 n 的全排列 a，定义px​ 表示元素 x 在 a 中的下标。

小Why先将上述 n 个元素映射为图 G 中的点，之后对于每个点 x ，都向 px​ 连一条边。在完成这些操作后，图 G 中一共出现了 m 个环（包括自环）。

现在小Why告诉你可以对 a 执行以下操作任意多次：

选择 a 中任意两个不同的元素，交换它们的位置。

小Why只打算告诉你 n 和 m，他想考考你至少需要多少次操作才能使得 a 单调递增。

输入描述:

第一行包含两个整数 n,m (1≤m≤n≤10^9)，表示图 G 中点的个数和环的个数。

输出描述:

输出一个整数，表示最少操作次数。

示例1

输入

2 1

输出

1

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
const int N=1e6+10;
typedef double db;
int n,m;
signed main()
{
	 cin>>n>>m;
	 
	 cout<<n-m;
	
	return 0;
} 
 
//  a b c d   a+b=c+d=a+c=b+d   b=c a=d 

 

 C

超市里一共有 n 个货架，m 个商品，一开始商品的位置是被打乱的，小Why需要将商品全部归位。
小Why在给货架编号后，实现了每个商品所在货架必然在其应在货架之前。
小Why决定手推购物车按编号顺序依次访问每个货架。在访问货架时，小Why可以执行以下两个操作任意多次：
 当购物车不为空时，将购物车中的一个商品放上货架。
 当货架不为空时，将货架上的一个商品放入购物车。
当小Why跑完一趟后，如果仍有商品没被归位，那么小Why会再次返回 1 号货架重复以上过程。
超市里的购物车同一时刻最多能放 k 个商品，且每个货架容量无限，请你告诉小Why至少需要跑多少趟才能将商品全部归位。

输入描述:

第一行包括三个整数 n,m,k (2≤n≤10^6,1≤m,k≤10^6)，表示货架个数，商品个数和购物车容量。

接下来 m 行，每行有两个整数 sti​,edi​(1≤sti​

输出描述:

输出一个整数，表示最少需要的趟数。

示例1

输入

3 3 1
1 2
1 3
2 3

输出

2

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
const int N=1e6+10;
typedef double db;
int n,m,k;
int a[N];
signed main()
{
	cin>>n>>m>>k;
	
	fp(i,1,m){
		int x,y;
		cin>>x>>y;
		a[x]++,a[y]--;
	}
	
	int mmax=0;
	
	fp(i,1,n)
	{
		a[i]+=a[i-1];
		mmax=max(mmax,a[i]);
	}
	
	cout<<(mmax-1)/k+1;
	
	return 0;
} 
 

 思路：可以抽象为差分   

对于一个商品假设一开始在1，然后要去4

那么他在1-3这个区间就一定会占据一个购物车位置，因为在这期间不可能将它放下来

这样就可以直接通过差分来维护在商品的“占据情况”。

D

题目描述

小Why拿到了一个密码长度为 m 的密码锁，这个密码锁可输入内容无限，并只对最后输入的 m 位字符进行检测，检测正确时密码锁会解锁一次，同时清空包含检测正确字符串在内的之前的所有字符。

小Why输入了一个长度为 n 的字符串 s 后，密码锁一共解锁了 k 次，请你告诉他有多少种密码是可能正确的。

输入描述:

第一行包含三个整数 n,m,k (1≤m∗k≤n≤106)，表示字符串 s 的长度，密码长度和解锁次数。第二行包含一个长度为 n 的字符串 s，保证字符串 s 中只含有 0∼9 的数字。

输出描述:

输出一个整数，表示有多少种密码是可能正确的。

示例1

输入

13 5 2
1231234123123

输出

2

 我复习了一波字符串哈希  这个算法我老早忘记了  以至于蓝桥杯差了这个就国三。哭死

字符串哈希模板：

#include<bits/stdc++.h>
using namespace std;
//#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
const int N=1e6+10;
typedef double db;
typedef unsigned long long ULL;
int n,m;
int l1,r1,l2,r2;
const int pp=131;
ULL h[N];
ULL p[N];
string s;
ULL gets(int a,int b)
{
	return h[b]-h[a-1]*p[b-a+1];
}
int main()
{
	cin>>n>>m;
	
	cin>>s;
	s=" "+s;
	
	p[0]=1;
	
	for(int i=1;i<=n;i++)
	{
		h[i]=h[i-1]*pp+s[i];
		p[i]=p[i-1]*pp;
	}
	
	for(int i=1;i<=m;i++){
		cin>>l1>>r1>>l2>>r2;
		if(gets(l1,r1)==gets(l2,r2)){
			cout<<"Yes"<<"\n";
		}
		else{
			cout<<"No"<<"\n";
		}
	}
	
	return 0;
} 
 

 

这道题也是字符串哈希  用map记录一下就行

#include<bits/stdc++.h>
using namespace std;
//#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
const int N=1e6+10;
typedef double db;
typedef unsigned long long ULL;
int n,m,k;
const int pp=131;
ULL h[N];
ULL p[N];
string s;
ULL gets(int a,int b)
{
	return h[b]-h[a-1]*p[b-a+1];
}
map<ULL,int>ma;
map<ULL,int>last;
int main()
{
	cin>>n>>m>>k;
	
	cin>>s;
	s=" "+s;
	
	p[0]=1;
	
	for(int i=1;i<=n;i++)
	{
		h[i]=h[i-1]*pp+s[i];
		p[i]=p[i-1]*pp;
	}
	
	for(int i=1;i<=n;i++){
		if(i>=m){
			ULL g=gets(i-m+1,i);
			if(!last.count(g)||last[g]<=i-m){
				ma[g]++;
				last[g]=i;
			}
		}
	}
	
	int sum=0;
	
	for(auto x:ma){
		if(x.second==k){
			sum++;
		}
	}
	
	cout<<sum<<"\n";
	return 0;
}