NOIP2025模拟赛11

写在前面：

上次是什么时候写的来着？

哦，原来是这次。

哎呀呀一点意思也没有。

《麻雀》

山隔壁还是山
都有一个伴
相信海枯石烂
也许我笨蛋
飞太慢会落单
太快会受伤
日子不就都这样
天会晴就会暗
我早就习惯
一日为了三餐
不至于寒酸
为给你取暖我把翅膀折断
我遭遇那些苦难
你却不管
我飞翔在乌云之中
你看着我无动于衷
有多少次波涛汹涌
在我心中
你飞向了雪山之巅
我留在你回忆里面
你成仙我替你留守人间
麻雀也有明天
天会晴就会暗
我早就习惯
一日为了三餐
不至于寒酸
为给你取暖我把翅膀折断
我遭遇那些苦难
你却不管
我飞翔在乌云之中
你看着我无动于衷
有多少次波涛汹涌
在我心中
你飞向了雪山之巅
我留在你回忆里面
你成仙我替你留守人间
麻雀也有明天
我飞翔在乌云之中
你看着我无动于衷
有多少次波涛汹涌
在我心中
你飞向了雪山之巅
我留在你回忆里面
你成仙我替你留守人间
麻雀也有明天

真的有明天吗》

T1 白露澈明之泉

~~不知道，刚搜了一下好像是原始人里的。~~

Solve：

全世界都是 $95~pts$ ………

但是其实完全可以把全世界卡成 $0~pts$ ………

不知道，开场一秒钟想到贪心：

首先发现一定是先凑出来一整行的 $1$ 再用那个整行来搞不完整的列最优；

然后直接预处理记录每行每列都有几个 $1$ ，然后按 $1$ 的数量从大到小 $sort$ 一遍行，之后暴力 $check$ 每行，如果能直接被拼出来就 $break$ ，然后加上不完整的列数。

然后就会 $WA$ 一个点。

那很坏了。

因为一定有解，于是如果 $check$ 失败了的话，我们完全可以多搞一步来在那一列发明出一个 $1$ 。

然后加上就没了。

Code：

#include <bits/stdc++.h>
using namespace std;
const short _ = 3001;
short n, m, ans = 7777, shu[_], mxh, nw;
char c;
bool a[_][_];
struct hhh{
	short heng, num;
}h[_];
inline bool bbb(hhh x, hhh y){
	return x. heng > y. heng;
}
inline bool ok(short x){
	for(short i = 1; i <= n; i ++){
		if(a[i][x]){
			return 1;
		}
	}
	return 0;
}
inline short min(short x, short y){
	return x < y ? x : y;
}
int main(){
	freopen("fountain.in", "r", stdin), freopen("fountain.out", "w", stdout);
//	freopen("fountain11.in", "r", stdin);
	ios::sync_with_stdio(0), cin. tie(0), cout. tie(0);
	cin >> n;
	for(short i = 1; i <= n; i ++){
		for(short j = 1; j <= n; j ++){
			cin >> c;
			a[i][j] = c - '0';
			h[i]. heng += a[i][j];
			shu[j] += a[i][j];
		}
		h[i]. num = i;
		mxh = max(mxh, h[i]. heng);
	}
	if(mxh == n){//O(n)
		ans = 0;
		for(short i = 1; i <= n; i ++){
			if(shu[i] != n){
				ans ++;
			}
		}
		cout << ans;
		return 0;
	}
	sort(h + 1, h + n + 1, bbb);
	for(nw = 1; nw <= n; nw ++){//O(n^2)
		if(ok(h[nw]. num)){
			ans = min(ans, n - h[nw]. heng);
			break;
		}
		else{
			ans = min(ans, n - h[nw]. heng + 1);
		}
	}
	for(short i = 1; i <= n; i ++){//O(n)
		if(shu[i] != n){
			ans ++;
		}
	}
	cout << ans;
	return 0;
}

T2 在空无一物的时光深处

~~数数 $DP$ ？我去你吗的吧，我不会。~~

T3 最小字典序

赛时线段树狂假不止最终 $4pts$ 遗憾离场。

但是其实题解根本™用不上线段树。

根本就是一个 $DP$ + 倍增跳哈希。

首先设一个 $dp$ 数组每一位都存的是 $i$ ~ $n$ 按题意得的字典序最小的序列，然后每次转移枚举 $j∈(i,n]$ ，求 $$字典序的min ~(a_i!a_{i+1}|...|a_j, dp_{j + 1})$$ 可以发现 $a_i|a_{i+1}...|a_j$ 一定要等于 $a_i$ 才是最优的，于是就相当于是比较 $dp_{j+1}$ 们了。

但是空间会爆炸于是只记录 $dp_i$ 对应的序列里第 $2^j$ 个数在原数组里的位置 $plc_{i, j}$ ，在用 $hs_{i,j}$ 存下那一段的哈希值，于是空间 $n^2->n~logn$ 。

然后因为比较的次数太多，于是搞一个单调栈优化于是直接变成 $O(n)$ 的比较次数，每次比较就是直接跳处理好的倍增数组，求 $min$ 值的时候直接在单调栈里二分即可。

Code：

#include <bits/stdc++.h>
using namespace std;
const int _ = 200010;
unsigned long long mx, s[_], a[_], p[_], hs[_][33];
int n, t, plc[_], fa[_][33], top;
inline void add(long long x, long long q){
	fa[x][0] = q;
	hs[x][0] = a[x];
	for(int i = 1; i <= 20; i ++){
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
		hs[x][i] = hs[fa[x][i - 1]][i - 1] * p[1 << (i - 1)] + hs[x][i - 1];
	}
	return ;
}
inline bool shule(int x, int y){
	for(int i = 20; i >= 0; i --){
		if(hs[x][i] == hs[y][i] && fa[x][i] && fa[y][i]){ 
			x = fa[x][i];
			y = fa[y][i]; 
		}
	}
	return y != n + 1 && a[x] <= a[y];
}
int main(){
	freopen("min.in", "r", stdin), freopen("min.out", "w", stdout);
	ios::sync_with_stdio(0), cin. tie(0), cout. tie(0);
	p[0] = 1;
	for(int i = 1; i <= _ - 10; i ++){
		p[i] = p[i - 1] * 1331;
	}
cin >> t;
while(t --){
	cin >> n;
	for(int i = 0; i <= 30; i ++){
		plc[i] = n + 1;
	}
	top = n + 1;
	s[top] = n + 1;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		mx = max(mx, a[i]);
	}
	if(mx == 1){
		for(int i = 1; i <= n; i ++){
			if(! a[i]){
				cout << 0 << ' ';
			}
			else{
				cout << 1;
				break;
			}
		}
		cout << '\n';
		continue;
	}
	for(int i = n; i; i --){
		int mn = n + 1;
		for(int j = 0; j <= 30; j ++){
			if(a[i] >> j & 1){
				plc[j] = i;
			}
			else{
				mn = min(mn, plc[j]);
			}
		}
		add(i, s[upper_bound(s + top, s + n + 2, mn) - s - 1]);
		while(shule(i, s[top])){ 
			top ++; 
		}
		s[-- top] = i; 
	}
	long long x = 1;
	while(x != n + 1){ 
		cout << a[x] << ' '; 
		x = fa[x][0];
	}
	cout << '\n';
}
	return 0;
}

T4 swɒp

这道题对于我来说除了纠正了我可悲的英语发音外毫无意义因为我根本就是不会拿矩阵乘维护带 $min$ 和 $+$ 的 $DP$ 然后因为带修再拿线段树维护矩阵乘。

END.

posted @ 2025-11-19 20:08 养鸡大户肝硬化阅读(32) 评论(0) 收藏举报

刷新页面返回顶部

rain20100708

NOIP2025模拟赛11

写在前面：

《麻雀》

T1 白露澈明之泉

Solve：

Code：

T2 在空无一物的时光深处

T3 最小字典序

Code：

T4 swɒp

END.

公告