专栏文章

题解：P14585 [LNCPC 2025] Entering the unknown

MMyShiroko
P14585题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min1hpl3
此快照首次捕获于
2025/12/01 19:02
3 个月前
此快照最后确认于
2025/12/01 19:02
3 个月前
查看原文

P14585 [LNCPC 2025] Entering the unknown 题解

赛时差 5 min 调出来qwq。
设下标为 ii 的数的“数字”（即为题面中的最大出现数字）为 bib_i。
原数组为 aia_i。
这样问题就转化成了求 ∑l=1n∑r=ln[max⁡i=lrb[i]∣∑i=lra[i]]\sum_{l = 1}^n \sum_{r = l}^n [\max_{i = l}^r b[i] \mid \sum_{i = l}^r a[i]]。
然后随便敲个 st 表就可以打 O(n2)O(n ^ 2) 暴力了（哈哈哈，我在 ICPC 赛制上打部分分）。
考虑优化，我们注意到，bb 数组的取值仅为 [0,9][0,9]。
考虑由此入手，发现最大值具有可加性。
所以我们从大到小枚举可行的区间最大值。现在，我们要求区间和整除现在枚举的极大值的区间个数。
发现直接做不好做，考虑容斥。
发现我们可以 O(n)O(n) 做一段数中，有多少个区间的和整除某个值。
设现在枚举的最大值为 mxmx。
现在我们求出所有的所有区间和整除 mxmx 的区间，再减去区间和整除 mxmx 并且区间 max⁡b\max b 不等于 mxmx 的区间个数就行。
至于怎么 O(n)O(n) 做这个东西呢？
只需要维护每个数的前缀和模 mxmx 意义下余数的出现次数即可。
形式化地说：
设点 ii 的前缀和为 sumisum_i。
则一个合法区间 [l,r][l,r] 等价于 sumr≡suml−1(modmx)sum_r \equiv sum_{l - 1} \pmod {mx}。
特殊的 sum0sum_0 为 00。
发现我们需要的只是 ∑i=0r−1[sumr≡sumi(modmx)]\sum{i = 0}^{r - 1} [sum_r \equiv sum_i \pmod {mx}]。
我们对于每一种余数记录出现次数即可。
特殊的，cnt0cnt_0 初始化为 00。
每次枚举 mxmx 后，将 bb 数组为 mxmx 的所有点删除即可。
每次我们枚举所有的未删除连通块即可。
时间复杂度为 O(∑n)O(\sum n)。
跑的飞快！！！
最后感谢 Pursuing_OIer提供思路！
CPP
#include <iostream>
#include <stdio.h>
#include <bitset>
#include <algorithm>
#include <string.h>
#include <cmath>
#define int long long 
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 1e5 + 3;
constexpr int mod = 1e9 + 7;
constexpr int INF = 0x7f7f7f7f7f7f7f7f;

int T;
int n;
int ans;
int top;
int a[N];
int mx[N];
int cnt[11];

struct miku
{
	int l,r;
}stk[N];

bitset<N> vis;

inline int get_max(int x)
{
	int res = 0;
	while(x) res = max(res,x % 10),x /= 10;
	return res;
}

inline int work(int op)
{
	int res = 0;
	for(int i = 1,sum;i <= top;i ++)
	{
		sum = 0;
		for(int j = 0;j < op;j ++) cnt[j] = 0;
		cnt[0] = 1;
		for(int j = stk[i].l;j <= stk[i].r;j ++)
		{
			sum += a[j];
			res += cnt[sum % op];
			cnt[sum % op] ++;
		}
	}
	top = 0;
	for(int i = 1;i <= n;i ++) if(mx[i] == op) vis[i] = 1;
	for(int l = 1,r;l <= n;l ++)
	{
		if(vis[l]) continue;
		r = l;
		while(!vis[r + 1] && r < n) r ++;
		stk[++ top] = {l,r};
		l = r;
	}
	for(int i = 1,sum;i <= top;i ++)
	{
		sum = 0;
		for(int j = 0;j < op;j ++) cnt[j] = 0;
		cnt[0] = 1;
		for(int j = stk[i].l;j <= stk[i].r;j ++)
		{
			sum += a[j];
			res -= cnt[sum % op];
			cnt[sum % op] ++;
		}
	}
	return res;
}

inline void solve()
{
	vis.reset();
	top = ans = 0;
	cin >> n;
	for(int i = 1;i <= n;i ++)
	{
		cin >> a[i];
		mx[i] = get_max(a[i]);
	}
	stk[++ top] = {1,n};
	for(int i = 9;i >= 1;i --) ans += work(i);
	cout << ans << '\n';
}

signed main()
{
	#ifndef ONLINE_JUDGE
		freopen("data.in","r",stdin);freopen("data.out","w",stdout);
	#endif
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> T;
	while(T --) solve();
	Blue_Archive;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...