牛客小白月赛97题解

A. 三角形

将所有边的长度存到桶里，最后判断桶里是否有大于等于 3 的数。

B. 好数组

判断数组中是否有0，有0就不是好数组，否则就是好数组。

C. 前缀平方和序列

考虑构造出序列的前缀和序列，前缀和序列确定，这个序列也确定了。

所以问题就成为了有多少个长度为 n 的递增序列，每个元素都在 1 到 x 之间。

即从 1 到 x 中选出 n 个平方数的方案。

求解组合数可以用杨辉三角。

D. 走一个大整数迷宫

注意到 模 始终等于 ，所以 的值与 没有关系。

然后考虑使用 ， 表示起点到 计数器模 的值为 的最短时间。

cpp代码：

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int N=12;
const int M=10011;
int a[N][N];
int b[N][N];
int mod;
int dist[N][N][M];
bool st[N][N][M];
int main(){
	ios;
	int  n,m,p;
	cin>>n>>m>>p;
	if(p==2){
		cout<<n+m-2<<endl;
		return 0;
	}
	mod=p-1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			a[i][j]%=mod;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>b[i][j];
		}
	}
	queue<array<int,3>>q;
	q.push({1,1,a[1][1]});
	int dir[4][2]={1,0,0,1,-1,0,0,-1};
	st[1][1][a[1][1]]=1;
	while(q.size()){
		auto [x,y,z]=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int xx=x+dir[i][0];
			int yy=y+dir[i][1];
			if(xx<=n&&xx>0&&yy<=m&&yy>0&&st[xx][yy][(z+a[xx][yy])%mod]==0){
				int zz=(z+a[xx][yy])%mod;
				dist[xx][yy][zz]=dist[x][y][z]+1;
				st[xx][yy][zz]=1;
				q.push({xx,yy,zz});
			}
		}
	}
	
	if(st[n][m][0]==0)cout<<-1<<endl;
	else cout<<dist[n][m][0]<<endl;
    return 0;
}

E. 前缀和前缀最大值

对于一个序列 ，考虑如何快速计算它的 类价值。

考虑 类价值最小的方案，是从小到大排序序列 。

然后进行 次，将序列 的最后一个数字移动到最前面。

会发现这样操作序列 的 类价值是单调不减的，并且每次只移动一个数，增量只可能是 或者 。

所以可以得出一个结论， 类价值是连续的。

所以只要求出序列 的 类价值的上界 和下界 ，就可以得出 类价值为 。

类价值的上界就是序列 从大到小排序。

然后考虑如何处理多次询问。

上界很好算，就是区间正数个数。

然后考虑下界。

由于发现序列 的值域很小，所以询问的一个区间的正数的种数最多只有 种。

使用前缀和可以快速的求出这些数。

然后就可以使用上述方法求出上界。

cpp代码：

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int sum[100010][101];
int nesum[100010];
int main(){
	ios;
	int n;
	cin>>n;
	vector<int>a(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]<0)nesum[i]=nesum[i-1]-a[i];
		else nesum[i]=nesum[i-1];
		for(int j=1;j<=100;j++){
			sum[i][j]=sum[i-1][j]+(a[i]==j);
		}
	}
	int q;
	cin>>q;
	for(int c=1;c<=q;c++){
		int l,r;
		cin>>l>>r;
		int tmp=0;
		int t=nesum[r]-nesum[l-1];
		int res=0;
		int cnt=0;
		for(int i=1;i<=100;i++){
			int j=sum[r][i]-sum[l-1][i];
			if(j!=0){
				if(i*j+res>=t){
					cnt+=(t-res)/i;
					break;
				}
				else cnt+=j,res+=i*j;
			}
		}
		cout<<cnt+1<<endl;
	}
    return 0;
}

F .parent 树上启发式合并

询问的不同的字符串长度和不超过10000。

也就意味着不同的字符串长度只有150种左右。

然后将询问离线。

字符串哈希之后从左到右遍历所有这些长度的子串，同时进行记录这些子串的出现次数，假如这个出现次数的子串在被询问过，就记录答案，比如遍历到一个子串T，并且是第 次出现，恰好有一个询问是 ，那么就可以记录答案了。

这个过程使用unordered_map或者手写哈希表均可通过。

cpp代码：

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define vii vector<vector<int>>
#define ull unsigned long long
const int N = 10000;
vector<pair<ull, int>> S[N];
vector<pair<ull, int>> g[N];
vector<pair<ull, int>> cnt0[N];
int &find(vector<pair<ull, int>> f[], ull u) {
	int hu = u % N;
	for (auto &[i, j]: f[hu]) {
		if (i == u)return j;
	}
	f[hu].emplace_back(u, 0);
	return f[hu].back().se;
}
int count(vector<pair<ull, int>> f[], ull u) {
	int hu = u % N;
	for (auto &[i, j]: f[hu]) {
		if (i == u)return 1;
	}
	return 0;
}
int ans[100010];
ull hq[100010];
int que[100010];
ull p[100010];
ull h[100010];
const int B=131;
void init(const string& s){
	for (int i = 1; i <= s.size()-1; i++) h[i] = h[i - 1] * B + s[i];
}
ull get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }

int main(){
	ios;
	int n, q;
	cin >> n >> q;
	p[0]=1;
	for(int i=1;i<=100000;i++){
		p[i] = p[i - 1]*B;
	}
	string s;
	cin >> s;
	s = " " + s;
	vector<int> b;
	string t;
	for (int i = 1; i <= q; i++) {
		cin >> t >> que[i];
		t = ' ' + t;
		init(t);
		hq[i] = get(1, t.size() - 1);
		find(g, hq[i]  * p[que[i]]) = i;
		b.push_back(t.size() - 1);
		find(S, hq[i] ) = 1;
	}
	for (int i = 1; i <= q; i++) {
		ans[i] = -1;
	}
	std::sort(b.begin(), b.end());
	b.erase(std::unique(b.begin(), b.end()), b.end());
	init(s);
	for (auto len: b) {
		for (int i = len; i <= n; i++) {
			ull ha = get(i - len + 1, i);
			if (count(S, ha)) {
				find(cnt0, ha) += 1;
				if (count(g, ha * p[find(cnt0, ha)])) {
					ans[find(g, ha * p[find(cnt0, ha)])] = i;
				}
			}
		}
	}
	for (int i = 1; i <= q; i++)cout << ans[find(g, hq[i] * p[que[i]])] << endl;
	return 0;
}