C. Evolution Game

 

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
#include<bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> Pair;
 
const int maxn = 5e3+5;
Pair p[maxn];
int a[maxn], ans[maxn], n, w, mark;
 
 
int main()
{
    cin >> n >> w;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        p[i].first = a[i];
        p[i].second = i;
    }
    sort(p, p + n);
    for (int i = n - 1; i >= 0; --i) {
        for (int j = max(p[i].second - w, 0); j <= min(p[i].second + w, n - 1); ++j)
            if (a[j] > a[p[i].second]) ans[p[i].second] = max(ans[p[i].second], ans[j] + 1);
    }
    for (int i = 0; i < n; ++i) mark = max(mark, ans[i]);
    cout << mark << endl;
    return 0;
}

 

D. Bus Stop

 

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
#include<bits/stdc++.h>
using namespace std;
 
int T, n, data[2000010], ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--) {
        ans = 0;
        cin >> n;
        if (!n) {
            cout << 0 << endl;
            continue;
        }
        for (int i=0;i<n;i++) cin >> data[i];
        int l = 0, r = 0;
        while (r < n) {
            if (data[r] - data[l] <= 20) r++;
            else {
                ans++;
                l = r;
            }
        }
        ans++;
        cout << ans << endl;
    }
    return 0;
}

 

E. How Many Groups

 

题意：定义一个运算符 ‘~’ ，若 ∣x−y∣≤2|x-y|\leq 2 则xx ~ yy。现给出一组数字，将它们从小到大排列，若满足相邻两个数字 ∣x−y∣≤2|x-y|\leq 2，则可归为一组。最多可以修改2次，每次可任选1个元素+1或-1，每个元素最多被选中一次，求元素最多的那一组中的元素个数。

简单dp

设dp[i] [j] [k]表示到第 i 个数，且前一个数的值为 j，目前一共修改了 k 次，的最大元素个数。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
const int N = 1e6;
int T, n;
int a[maxn], dp[110][210][5];
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	} while ('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	} return x * f;
}
int main() {
	T = read();
	for (int tt = 1; tt <= T; tt++) {
		n = read();
		for (int i = 1; i <= n; i++)a[i] = read();
		sort(a + 1, a + n + 1);
		memset(dp, 0, sizeof(dp));
		dp[1][a[1]][0] = dp[1][a[1] - 1][1] = dp[1][a[1] + 1][1] = 1;
		for (int i = 2; i <= n; i++) {
			for (int k = 0; k <= 2; k++) {
				dp[i][a[i]][k] = max(dp[i][a[i]][k], max(dp[i-1][a[i]][k],max(dp[i - 1][a[i] - 2][k], dp[i - 1][a[i] - 1][k])) + 1);
				dp[i][a[i]][k] = max(dp[i][a[i]][k], max(dp[i - 1][a[i] + 1][k], dp[i - 1][a[i] + 2][k]) + 1);
				dp[i][a[i] - 1][k + 1] = max(dp[i][a[i] - 1][k + 1], max(dp[i-1][a[i]-1][k],max(dp[i - 1][a[i] - 2][k], dp[i - 1][a[i] - 3][k])) + 1);
				dp[i][a[i] - 1][k + 1] = max(dp[i][a[i] - 1][k + 1], max(dp[i - 1][a[i]][k], dp[i - 1][a[i] + 1][k]) + 1);
				dp[i][a[i] + 1][k + 1] = max(dp[i][a[i] + 1][k + 1], max(dp[i-1][a[i]+1][k],max(dp[i - 1][a[i]][k], dp[i - 1][a[i] - 1][k])) + 1);
				dp[i][a[i] + 1][k + 1] = max(dp[i][a[i] + 1][k + 1], max(dp[i - 1][a[i] + 2][k], dp[i - 1][a[i] + 3][k]) + 1);
			}
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = a[i] - 1; j <= a[i] + 1; j++)
				for (int k = 0; k <= 2; k++)ans = max(ans, dp[i][j][k]);
		}
		printf("Case %d: %d\n", tt, ans);
	}
	return 0;
}

 

F. Lucky Pascal Triangle

 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int tot = 22;
const LL mod = 1e9+7, inv = 500000004;
LL p[50], a[50], b[50], s[10], mark, q;
int T;
LL f(LL n)
{
    if (n <= 7) return 0;
    int i = upper_bound(p, p + tot, n) - p - 1;
    if (n == p[i]) return a[i];
    LL t1 = n % p[i], t2 = 2 * (p[i] % mod) - (n % p[i]) % mod + mod - 1;
    LL t3 = (((t1 % mod) * (t2 % mod)) % mod * inv) % mod;
    LL t4 = s[n / p[i]] * a[i] + s[max(n / p[i] - 1, 0ll)] * b[i] + (n / p[i] + 1) * f(n % p[i]);
    return ((t4 % mod + n / p[i] * t3) % mod ) % mod;
}
 
int main()
{
    p[0] = 1;
    for (int i = 1; i <= 7; ++i) s[i] = s[i - 1] + i;
    for (int i = 1; i < tot; ++i) p[i] = p[i - 1] * 7;
    for (int i = 1; i < tot; ++i) b[i] = (((p[i] % mod) * ((p[i] - 1) % mod)) % mod * inv) % mod;
    for (int i = 1; i < tot; ++i) a[i] = ((s[7] * a[i - 1]) % mod + (s[6] * b[i - 1]) % mod) % mod;
    cin >> T;
    for (int kase = 1; kase <= T; ++kase) {
        cin >> q;
        printf("Case %d: ", kase);
        cout << f(q + 1) << endl;
    }
    return 0;
}

 

G. Communication

 

找强连通分量的个数。

由于数据很小，并且当时不会Tarjan，就用了并查集+判环。

但是正解还是Tarjan。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 300;
int vis[300];
int cnt[300][300];
int T, n, m;
int par[maxn], rk[maxn];
void init(int n) {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		rk[i] = 0;
	}
}
int find(int x) {
	if (par[x] == x)return x;
	else return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rk[x] < rk[y])par[x] = y;
	else {
		par[y] = x;
		if (rk[x] == rk[y])rk[x]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
vector<int>G[maxn];
void dfs(int t, int u) {
	vis[u] = 1;
	cnt[t][u] = 1;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (vis[v])continue;
		dfs(t, v);
	}
}
int main() {
	scanf("%d", &T);
	while (T--) {
		memset(cnt, 0, sizeof(cnt));
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++)G[i].clear();
		init(n);
		for (int i = 0; i < m; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			G[u].push_back(v);
		}
		for (int i = 0; i < n; i++) {
			memset(vis, 0, sizeof(vis));
			dfs(i,i);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j)continue;
				if (cnt[i][j] && cnt[j][i])unite(i, j);
			}
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			if (par[i] == i)ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

H. As Rich as Crassus

 

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
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int T;
ll ans, m[10], r[10];
const ll n = 3;
 
ll ex_gcd(ll a, ll b, ll &x, ll &y)
{
    if (!b) {
        x = 1;y = 0;
        return a;
    }
    ll ret = ex_gcd(b, a%b, y, x);
    y -= a/b * x;
    return ret;
}
 
ll CRT(ll *m, ll*r, ll n)
{
    if (!n) return 0;
    ll M = m[0], R = r[0], x, y, d;
    for (int i=1;i<n;i++) {
        d = ex_gcd(M, m[i], x, y);
        if ((r[i] - R) % d) return -1;
        x = (r[i] - R) / d * x % (m[i]/d);
        R += x * M;
        M = M / d * m[i];
        R %= M;
    }
    return R >= 0 ? R : R + M;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> m[0] >> m[1] >> m[2];
        cin >> r[0] >> r[1] >> r[2];
        ans = CRT(m, r, n);
        ll res = pow((double)ans, 1.0/3.0);
        while (res * res * res < ans) res++;
        cout << res << endl;
    }
    return 0;
}

 

J. Floating-Point Hazard

 

微积分，近似计算。

设

f(x)=x3f(x)=\sqrt[3]{x}

则

f(x+Δx)−f(x)Δx=f′(x)\frac{f(x+\Delta x)-f(x)}{\Delta x}=f'(x)

f(x+Δx)−f(x)=f′(x)⋅Δxf(x+\Delta x)-f(x)=f'(x)\cdot \Delta x

其中

f′(x)=13x−23f'(x)=\frac{1}{3}x^{-\frac{2}{3}}

本题中 $$\Delta x=10^{-15}$$

注意 ∑\sum 是整数求和，∫abf(x)dx\int_{a}^{b} f(x) {\rm d}x 是对 f(x)⋅dxf(x)\cdot dx 的面积求和。本题要求的是前者。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int low, high;
int main()
{
    while (cin >> low >> high) {
        if (!low) break;
        double sum = 0;
        for (int i = low; i <= high; ++i) sum += pow(double(i), -2.0/3.0);
        printf("%.5E\n", sum * 1e-15 / 3.0);
    }
    return 0;
}

 

K. The Stream of Corning 2

 

题意：有两种操作：

  1. 在 t1 时刻插入一个数 v，这个数会在 t2 时刻消失。
  2. 查询 T 时刻第 K 大的数。

查询第 K 大的数，自然想到用权值线段树。

然而如果每次都遍历一遍找到那些仍然存在的数，则复杂度为 O(n2)O(n^2)。考虑用单调队列维护，以结束时间递增的方式存储所有数字，当进行查询操作时，从头开始若堆顶数字消失时间小于当前查询时间，则删除，直到堆顶数字消失时间大于等于当前查询时间。

由于每个数最多被删除一遍，而线段树删除操作为 log⁡n\log n，所以整体复杂度为 O(nlog⁡n)O(n\log n)。

比赛时也不知道怎么想到划分树去了，但划分树的修改需要重建树，单次重建为 O(nlog⁡n)O(n\log n)，也没有必要，因为划分树和主席树都用来查询区间第 K 大，用来查询全局第 K 大实在是没必要。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((l+r)>>1)
#define lch (rt<<1),l,mid
#define rch (rt<<1)|1,mid+1,r
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
const int N = 1e6;
int T, n;
int tr[maxn << 2];
void pushup(int rt) {
	tr[rt] = tr[rt << 1] + tr[(rt << 1) | 1];
}
void update(int x, int b, int rt, int l, int r) {
	if (l == r) {
		tr[rt] += b;
		return;
	}
	if (x <= mid)update(x, b, lch);
	else update(x, b, rch);
	pushup(rt);
}
int query(int rt, int l, int r, int k) {
	if (l == r)return l;
	if (tr[rt<<1] >= k)return query(lch, k);
	else return query(rch, k - tr[rt<<1]);
}
struct X
{
	int val, time;
};
struct cmp
{
	bool operator()(const X& a, const X&b) {
		return a.time > b.time;
	}
};
int main() {
	scanf("%d", &T);
	for (int tt = 1; tt <= T; tt++) {
		memset(tr, 0, sizeof(tr));
		printf("Case %d:\n", tt);
		priority_queue<X, vector<X>, cmp>q;
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			int op;
			scanf("%d", &op);
			if (op == 1) {
				int t1, v, t2;
				scanf("%d%d%d", &t1, &v, &t2);
				q.push(X{ v,t2 });
				update(v, 1, 1, 1, N);
			}
			else {
				int t, k;
				scanf("%d%d", &t, &k);
				while (!q.empty() && q.top().time < t) {
					update(q.top().val, -1, 1, 1, N);
					q.pop();
				}
				if (q.size() < k)printf("-1\n");
				else printf("%d\n", query(1, 1, N, k));
			}
		}
	}
	return 0;
}

 

L. Largest Allowed Area

 

二维前缀和+二分

题意：给出一个01矩阵，要求划出一个正方形区域，使得正方形中有且仅有一个1。求满足条件的最大的正方形的边长。

二维前缀和，可以求出每一个区域包含的1的个数。

1
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];

则以 (x1,y1)(x1,y1) 为左上角，(x2,y2)(x2,y2) 为右下角的矩形区域包含1的个数为：

1
ans(x1, y1, x2, y2)=a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][x2 - 1]

枚举正方形左上角，二分确定边长。

分三种情况：

  1. 若当前区域没有1，则需要扩大正方形，L=mid+1
  2. 当前区域有1个1，则需要扩大正方形，同时记录答案，L=mid+1, ans=max(ans,mid)
  3. 当前区域有多个1，则需要缩小正方形，R=mid-1

 

顺便记一下二分死循环的一些坑。

若要找到小于等于k的第一个数，则若mid<=kmid<=k，要L=midL=mid，反之R=mid−1R=mid-1.但此时若L=mid<=k,R=mid+1L=mid<=k,R=mid+1.则会使L=mid死循环，所以此时应改进mid取法。

mid = (L + R + 1) / 2

 

若要找到第一个大于等于k的数，则若mid>=kmid>=k，要R=midR=mid，反之L=mid+1L=mid+1.此时若取mid=(L+R+1)/2mid=(L+R+1)/2反而会使R=midR=mid死循环 。所以此时应使mid变回去。

mid = (L + R) / 2

 

还有一个对内存的小优化：

mid = (L + R + 1) / 2 --> mid = L + (R - L + 1) / 2

mid=( L + R) / 2 --> mid = L + (R - L) / 2

可防止精度溢出。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	} while ('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	} return x * f;
}
const int INF = 0x3f3f3f3f;
const int maxn = 1005;
const int N = 1e6;
int T, r, c;
int mz[maxn][maxn];
int check(int x, int y, int len) {
	return mz[x + len - 1][y + len - 1] - mz[x + len - 1][y-1] - mz[x-1][y + len - 1] + mz[x - 1][y - 1];
}
int main() {
	T = read();
	while (T--) {
		int ans = 0;
		r = read(); c = read();
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++)mz[i][j] = read();
		}
		for (int i = 1; i <= r; i++)
			for (int j = 1; j <= c; j++)
				mz[i][j] += mz[i - 1][j] + mz[i][j - 1] - mz[i - 1][j - 1];
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				int L = 1, R = min(r - i + 1, c - j + 1);
				while (L <= R) {
					int mid = (L + R) >> 1;
					int cnt = check(i, j, mid);
					if (cnt == 1)L = mid + 1, ans = max(ans, mid);
					else if (cnt == 0)L = mid + 1;
					else R = mid - 1;
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

本题还要加个快读，否则会T。