https://codeforces.com/gym/102452

J. Junior Mathematician

 

题意：定义 f(x)=∑i=1k−1∑j=i+1kd(x,i)⋅d(x,j)f(x)=\sum_{i=1}^{k-1}\sum_{j=i+1}^{k} d(x,i) \cdot d(x,j)，其中 d(x,i)d(x,i) 为数 xx 第 ii 为上的数字。给定 L,R,m,(10≤L≤R<105 000,2≤m≤60)L,R,m,(10 \le L \le R < 10^{5\,000},2\le m\le 60) ，问 [L,R][L,R] 中有几个数 xx 满足 x≡f(x)(modm)x \equiv f(x) \pmod{m}。

数位dp

套路，要判断两个数是否相等，不需要分别记录这两个数，而只需要记录两数之差。

dp[pos][ans][pre][lim]dp[pos][ans][pre][lim] 表示到第 pospos 位，f(x)−x=ansf(x)-x=ans，∑i=1posd(x,i)=pre\sum_{i=1}^{pos}d(x,i)=pre，是否达到上限，时的方案数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, l, r) for (int i = r, i##end = l; i >= i##end; --i)
bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
#define here if (dbg) printf("Passing [%s] in Line %d\n", __FUNCTION__, __LINE__);
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> P;
#define ll long long
typedef unsigned long long ull;

const int maxn = 5010;
const int N = maxn;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const LD pi = acos(-1.0);
const LD eps = 1e-13;

#define Assert(x) if (!(x)) cout << 1 / 0;

int fac[5010], T, m, f[5010][62][62], l;
char s[maxn], t[maxn], *a;

int dp(int pos, int ans, int pre, int flag)
{
    if(pos == 0)  return ans == 0;
    if(flag && f[pos][ans][pre] != -1)  return f[pos][ans][pre];
    int x = flag ? 9 : a[l-pos] - '0', tmp = ((pre - fac[pos - 1])  + m) % m, res = 0;
    for(int i = 0; i <= x; i++)
    {
        res += dp(pos - 1, (ans + i * tmp) % m, (pre + i) % m, flag || i < a[l-pos] - '0');
        res %= mod;
    }
    if(flag)  f[pos][ans][pre] = res;
    return res;
}

int cal(char* s)
{
    l = strlen(s);
    a = s;
    return dp(l, 0, 0, 0);
}

int check(char *s)
{
    int pre = s[0] - '0', ans = s[0] - '0', res = 0;
    for(int i = 1; s[i]; i++)
    {
        res += pre * (s[i] - '0');
        pre += s[i] - '0';
        ans = ans * 10 + s[i] - '0';
        res %= m;
        pre %= m;
        ans %= m;
    }
    return (res - ans) % m == 0;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s %s %d", s, t, &m);
        int len = strlen(t);
        fac[0] = 1;
        for(int i = 1; i <= len; i++)
            fac[i] = 10 * fac[i - 1] % m;

        for(int i = 1; i <= len; i++)
            for(int k1 = 0; k1 <= m; k1++)
                for(int k2 = 0; k2 <= m; k2++)
                    f[i][k1][k2] = -1;
        int res = (cal(t) - cal(s) + check(s)) % mod;
        printf("%d\n", (res + mod) % mod);
    }
}

 

E. Erasing Numbers

 

题意：给定一个 nn 的排列 1≤n≤50001\le n\le 5000 且 nn 是奇数，每次操作选三个相邻的数，只保留中位数。问对于每个数，能否最终只剩下它。

对于数 xx，把小于它的看作 0，大于它的看作 1。

对于整个数列的中位数，必定可以满足条件：每次选择 0 1 相邻的地方，无论第三个数是什么，必定是删去一个0，一个1，则始终有01个数相同且始终存在01相邻的位置，所以始终可以操作并使得最终只剩这个数。

则变成判断能否使得01个数相同，通过选择000或111可以改变01个数，所以遍历模拟，要注意连续的一段长度为奇或偶情况不同，且断开后仍可能用上一段剩余的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, l, r) for (int i = r, i##end = l; i >= i##end; --i)
bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
#define here if (dbg) printf("Passing [%s] in Line %d\n", __FUNCTION__, __LINE__);
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> P;
#define ll long long
typedef unsigned long long ull;

const int maxn = 500010;
const int N = maxn;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const LD pi = acos(-1.0);
const LD eps = 1e-13;

int T;
int n;
int a[N];
int cal(int l, int r, int f, int x) {
	int cx = 0, ans = 0;
	for (int i = l; i <= r; i++) {
		if ((f && a[i] > x) || (!f && a[i] < x))cx++;
		else {
			if (cx >= 3) {
				if (cx & 1)ans += cx - 1, cx = 1;
				else ans += cx - 2, cx = 2;
			}
			cx = max(0, cx - 1);
		}
	}
	if (cx >= 3) {
		if (cx & 1)ans += cx - 1, cx = 1;
		else ans += cx - 2, cx = 2;
	}
	return ans;
}
bool ck(int k) {
	int x = a[k] - 1, y = n - a[k];
	int cnt = 0;
	if (x == y)return true;
	if (x < y) {
		if (x >= y - cal(1, k - 1, 1, a[k]) - cal(k + 1, n, 1, a[k]))return true;
		else return false;
	}
	else {
		if (y >= x - cal(1, k - 1, 0, a[k]) - cal(k + 1, n, 0, a[k]))return true;
		else return false;
	}
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++) {
			if (ck(i))printf("1");
			else printf("0");
		}
		puts("");
	}
	return 0;
}

 

I. Incoming Asteroids

 

题意：有 nn 个站点，mm 次操作，两种操作：新来一个人，选择 1≤k≤31\le k\le 3 个站点，且这个人的时长必须达到 yy；所有选择了第 xx 个站点的人的时长增加 yy。问每次第二种操作后，有几个人达到目标。

奇怪的套路

对每个站点维护一个小根的优先队列，把人的时长平分成 kk 份，分别压入他选择的站点的优先队列中。对于每次第二种操作，找到队列首的人，如果经过这次增加后，他分给这个站点的时长被满足了，则这个人重新计算分给各个站点的时长。

每次重新计算时，人所需要的时长至少变为原先的 k−1k\frac{k-1}{k}，则经过 O(log⁡kk−1y)O(\log_{\frac{k}{k-1}}y) 次后，他的目标就达到了，每次重新计算需要向 kk 个站点的优先队列中push，则总的复杂度为 O(m⋅log⁡32y⋅log⁡2m)O(m\cdot \log_{\frac{3}{2}}y\cdot \log_{2}m).

在具体实现时，对于第二种操作，显然不能遍历队列里每个人更新他还需要的时长，但是也不能直接只给这个站点计算被增加的时长再看是否满足人，因为不同人选择站点的时间点不同。所以要统一所有人选择这个站点的时间点：在把一个人的需求压入队列前先加上这个站点已经被第二种操作增加的总时长。

在把时长平分成 kk 份时要上取整，否则会收敛地很慢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, l, r) for (int i = r, i##end = l; i >= i##end; --i)
bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
#define here if (dbg) printf("Passing [%s] in Line %d\n", __FUNCTION__, __LINE__);
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> P;
#define ll long long
typedef unsigned long long ull;

const int maxn = 500010;
const int N = maxn;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const LD pi = acos(-1.0);
const LD eps = 1e-13;

int n, m, p, last;
int v[N], nd[N], tnd[N], vis[N];
vector<int>vc[N], ans;
typedef pair<int, int>pii;
priority_queue<pii, vector<pii>, greater<pii> >q[N];
int main() {
	scanf("%d%d", &n, &m);
	while (m--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			int y, k;
			scanf("%d%d", &y, &k);
			y ^= last;
			p++;
			nd[p] = y;
			tnd[p] = y;
			for (int i = 1; i <= k; i++) {
				int x;
				scanf("%d", &x);
				x ^= last;
				vc[p].push_back(x);
				q[x].push({ v[x] + (nd[p] + k - 1) / k, p });
				tnd[p] += v[x];
			}
		}
		else {
			int x, y;
			scanf("%d%d", &x, &y);
			x ^= last, y ^= last;
			ans.clear();
			v[x] += y;
			while (!q[x].empty() && q[x].top().first <= v[x]) {
				int u = q[x].top().second; q[x].pop();
				if (vis[u])continue;
				nd[u] = tnd[u];
				for (int t : vc[u]) {
					nd[u] -= v[t];
				}
				if (nd[u] <= 0) {
					vis[u] = 1;
					ans.push_back(u);
				}
				else {
					tnd[u] = nd[u];
					int k = (int)vc[u].size();
					for (int t : vc[u]) {
						q[t].push({ v[t] + (nd[u] + k - 1) / k, u });
						tnd[u] += v[t];
					}
				}
			}
			sort(ans.begin(), ans.end());
			last = (int)ans.size();
			printf("%d", last);
			for (int u : ans)printf(" %d", u); puts("");
		}
	}
	return 0;
}