3.30 月赛

链接：https://ac.nowcoder.com/acm/contest/34980/

A. 思维？

比较简单，可以发现在三位以外，五位以内就可以凑出来17，那么当 n >= 4 是一定 yes 的，超出的位数只可能是 偶数 或者 奇数，只要使得计算 17 所用的位数分别为 偶数个 和 奇数个 就可以了，剩下的 两两相减得到 1， 再相乘就行。

B. 高精度， dp

用python会很方便，不过需要提前处理好 i-j 所表示的数

f[i][j]表示前 i 位 用了 j 个加号所得到的结果

转移方程为 f[i][j] = min(f[i][j], f[k][j-1] + val[k+1][j])

还有一个需要优化的是，如果直接枚举 中间点k，时间复杂度是 n^3 的，这样一定会超时

但考虑一下，如果要想结果最小，那肯定是要把整个段平均分开的，所以这个切割的长度最佳时应该是 n / m + 1，python内应为 n // m + 1，表示先地板除，再加一，这样就是 n^2 的了

import sys
from math import inf

n, m = map(int, sys.stdin.readline().split())
s = " " + sys.stdin.readline().strip()

val = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(n + 1):
    if i != 0:
        val[i][i] = int(s[i])
    for j in range(i + 1, n + 1):
        val[i][j] = val[i][j - 1] * 10 + int(s[j])

mi = [[] for _ in range(m + 1)]
for i in range(m + 1):
    mi[i].append(0)

len = n // m + 1
dp = [[inf] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = val[0][i]
dp[0] = [0] * (m + 1)

for i in range(1, n + 1):
    for j in range(1, m + 1):
        for k in range(max(0, i - len), i):
            dp[i][j] = min(dp[i][j], dp[k][j - 1] + val[k + 1][i])

print(dp[n][m])

E. 前缀积，逆元

记 Ai 为前 i 项之积，要想找到符合这样要求的序列 [ i, j ]

则一定满足 Ai * Aj_1 mod MOD = x

那么只需要找到有多少个 Aj的逆 mod MOD = x * Ai_1 就好了

只要从左到右遍历一遍区间，统计一下 Ai , Ai+1, ... , Aj 对应的逆元，然后从右到左再重新遍历一遍，累加答案即可 

但还有一个问题就是如果 a[i] = 0，这样会导致一些错误，那其实这个时候只需要分区间来执行上述操作就好了

还有问题就是如果 x == 0，那这时候只需要用 所有的子区间个数 - 区间内没有一个元素为 0 的区间数即可

 #include<bits/stdc++.h>

const int MAXN = 5e5 + 10;
const int MOD = 998244353;
using namespace std;
typedef long long LL;

LL n, x;
LL a[MAXN];
map<LL, int> mp;
LL pro = 1;
LL ans;
int poi[MAXN], cnt;

LL exgcd(int a,int b,LL &x,LL &y)
{
	if(!b)
	{
		x = 1;
		y = 0;
		return a;	
	}	
	LL d = exgcd(b,a%b,y,x);
	y -= (a / b) * x;
	return d;
}

LL inv(int a,int b)
{
	LL x,y;
	if(exgcd(a,b,x,y) != 1) return -1;
	return (x % MOD + MOD) % MOD;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> x;
	for(int i = 1;i <= n;i++) 
	{
		cin >> a[i];
		a[i] %= MOD;
		if(!a[i]) poi[++cnt] = i;

	}
	poi[cnt+1] = n + 1;	
	if(!x){
		for(int i = 0;i <= cnt;i++){
			LL len = 1LL * poi[i+1] - 1 - (poi[i]+1) + 1;
//			cout << len << '\n';
			ans += len * (len + 1) / 2;
		}		
		cout << 1LL * n * (n + 1) / 2 - ans << '\n';
		return 0;
	}
	
//	cout << inv(2, MOD) << '\n';
//	cout << inv(6, MOD)

	for(int i = 0;i <= cnt;i++){
		mp.clear();
		mp[1]++;
		pro = 1;
		for(int j = poi[i] + 1; j < poi[i+1];j++){
			pro = pro * a[j] % MOD;
			mp[inv(pro, MOD) % MOD]++;
		}
		for(int j = poi[i+1]-1;j > poi[i];j--){
			mp[inv(pro, MOD) % MOD]--;
			ans += mp[x*inv(pro, MOD)%MOD];
			pro = pro * inv(a[j], MOD) % MOD;			
		}
	}
	cout << ans << '\n';
	return 0;
}

I.

硬币问题，比较简单，只要分别处理出来对于给定的硬币，二人分别所需的最少数目就可以

J. 二分，前缀和，最长不上升子序列 nlogn 做法

比较关键的地方在于 check 函数，要如何确认对于一个值，能否将区间划分为 k 段，使得每一段的平均值大于等于该值

贪心肯定是不行的，局部最优解不一定是全局最优解，对于一个特别大的数，无论是将它分配到一个尽可能小的区间还是尽可能大的区间都可能是错误的。

这时候考虑前缀和

定义前缀和为 summ[i] = summ[i-1] + a[i] - ave

那么对于一个合法的 ave， 应该有 summ[0] = 0, summ[n] >= 0

那么要将区间划分为 k 段，那么对于每一个区间的右边界 R， 应当有 summ[0] <= summ[R1] <= summ[R2] <= ... <= summ[n]

那么这样只需要求解一下长度为 n 的最长上升子序列就好了，需要注意的是一定要以 summ[0] = 0 开头。

可以先把 summ 中所有大于等于 0 的项筛出来， 然后再求解

这里只贴贴一个 nlogn的求解最长不降子序列的代码

还有一道比较类似的题，也是让区间的均值最大。

https://www.acwing.com/problem/content/104/

#include<bits/stdc++.h>

const int MAXN = 1e5 + 10;
using namespace std;

int n;
int a[MAXN], b[MAXN];
int poi[MAXN];
int len;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	vector<int> f(n+1, 1e5+1);
	f[0] = 0;
	for(int i = 1;i <= n;i++) {
		if(a[i] > f[len]) f[++len] = a[i];
		else {
			auto p = lower_bound(f.begin(), f.end(), poi[b[i]]) - f.begin();
			f[p] = a[i];			
		}

	} 
	cout << len << '\n';
	return 0;
}