2019杭电多校第六场

发表于 分类于 阅读次数： 本文字数： 9.1k 阅读时长 ≈ 8 分钟

过了6题，特别爽

1002. Nonsense Time

solved at 02:55

有一个\(1-n\)的排列\(p\), 一开始\(p\)所有位置全部无效，每次给出一个数\(k_i\)，意味着\(k_i\)这个位置的数开始有效，每次使一个数有效就输出当前有效序列的LIS长度，\((1<=n<=5e4)\)，保证数据是随机生成的 倒过来考虑，相当于从完整的序列中删去数字，如果删的数字不在LIS中那么显然结果不变，如果在LIS中就重新跑一边LIS

这里有一个结论（知乎搜的）：\(1-n\)的排列的LIS的期望长度是\(\theta(\sqrt n)\)级别的，所以只会跑\(\sqrt n\)次LIS, 总复杂度\(O(n\sqrt n \log(n))\)，时限长达14s, 肯定可以过

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
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;

int p[N], k[N], n, T, ans[N], now;
int dp[N], vis[N], valid[N], b[N], pre[N], pos[N];

void lis() {
	memset(vis, 0, sizeof(int) * (n + 5));
	now = 0;
	int m = 0;
	for(int i = 1; i <= n; ++i) {
		if(valid[i]) {
			dp[i] = lower_bound(b, b + m + 1, p[i]) - b;
			b[dp[i]] = p[i];
			m = max(m, dp[i]);
			pre[i] = pos[b[dp[i] - 1]];
		}
	}
	int pp = pos[b[m]];
	while(pp) {
		vis[pp] = 1;
		pp = pre[pp];
	}
	now = m;
}

int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i) {
			scanf("%d", &p[i]);
			valid[i] = 1;
			pos[p[i]] = i;
		}
		for(int i = 1; i <= n; ++i) {
			scanf("%d", &k[i]);
		}
		lis();
		for(int i = n; i; --i) {
			ans[i] = now;
			valid[k[i]] = 0;
			if(vis[k[i]] == 1) {
				lis();
			}
		}
		for(int i = 1; i <= n; ++i)
			printf("%d%c", ans[i], " \n"[i == n]);
	}
	return 0;
}

1005. Snowy Smile

solve at 00:32(+1)

差了三分钟痛失一血...

二维平面上有\(n\)个点，每个点有权值，你可以选择一个矩形，获得矩形区域内所有点的权值，求你能获得的最大值\((1<=n<=2000)\)

一看就是先离散化坐标然后枚举下边界再枚举上边界线段树维护最大子段和的套路，\(2000\)看上去就是个\(n^2\log(n)\)的复杂度

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
84
85
86
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2010;
int n, m, tx, ty, T;
int x[N], y[N], w[N], b[N];
vector<int> id[N];
LL ans;

struct tree {
    LL sum, rmx, lmx, mx;
    int tag;
}sgt[N << 2];

void pushup(int rt) {
    sgt[rt].sum = sgt[rt << 1].sum + sgt[rt << 1 | 1].sum;
    sgt[rt].mx = max(sgt[rt << 1].mx, sgt[rt << 1 | 1].mx);
    sgt[rt].lmx = max(sgt[rt << 1].lmx, sgt[rt << 1].sum + sgt[rt << 1 | 1].lmx);
    sgt[rt].rmx = max(sgt[rt << 1 | 1].rmx, sgt[rt << 1 | 1].sum + sgt[rt << 1].rmx);
    sgt[rt].mx = max(sgt[rt].mx, sgt[rt << 1].rmx + sgt[rt << 1 | 1].lmx);
}

void build(int rt, int l, int r) {
	sgt[rt].tag = 0;
    sgt[rt].sum = sgt[rt].lmx = sgt[rt].rmx = sgt[rt].mx = 0;
    if(l == r) {
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

void update(int rt, int l, int r, int pos, int val) {
	sgt[rt].tag = 1;
	if(l == r) {
		sgt[rt].mx += val;
        sgt[rt].sum = sgt[rt].lmx = sgt[rt].rmx = sgt[rt].mx;
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid)
		update(rt << 1, l, mid, pos, val);
	else
		update(rt << 1 | 1, mid + 1, r, pos, val);
	pushup(rt);
}

int main() {
	scanf("%d", &T);
	while(T--) {
		ans = 0;
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i) {
			scanf("%d%d%d", &x[i], &y[i], &w[i]);
			b[i] = x[i];
			id[i].clear();
		}
		sort(b + 1, b + n + 1);
		tx = unique(b + 1, b + n + 1) - b - 1;
		for(int i = 1; i <= n; ++i) {
			x[i] = lower_bound(b + 1, b + tx + 1, x[i]) - b;
		}
		for(int i = 1; i <= n; ++i) {
			b[i] = y[i];
		}
		sort(b + 1, b + n + 1);
		ty = unique(b + 1, b + n + 1) - b - 1;
		for(int i = 1; i <= n; ++i) {
			y[i] = lower_bound(b + 1, b + ty + 1, y[i]) - b;
			id[y[i]].push_back(i);
		}
		for(int i = 1; i <= ty; ++i) {
			build(1, 1, tx);
			for(int j = i; j <= ty; ++j) {
				for(auto f : id[j]) {
					update(1, 1, tx, x[f], w[f]);
				}
				ans = max(ans, sgt[1].mx);
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

1006. Faraway

solved at 02:20

二维平面上有一个不知道在哪里的集合点（知道横纵坐标范围在\([0, m]\)内，你有\(n\)个士兵，你知道这些士兵的坐标\(x_i, y_i\)以及士兵到集合点的曼哈顿距离模\(k_i\)的结果\(t_i\), 求可能的集合点数量\(1<=n<=10, 2<=k<=5, 1<=m<=1e9,0<=x_i,y_i<=m,0<=t_i<k_i\)

首先曼哈顿距离有一个绝对值，先考虑怎么去掉，每个士兵可以把平面分为四个区域，每个区域的绝对值符号都是固定的，\(n\)个点最多分成\((n+1)^2\)个区域，最多不过121, 对于每一个区域，考虑\(lcm(k) \ast lcm(k)\)的正方形里的点，其他的点都可以通过平移这些点得到，因为\(k\)是2-5, 因此\(lcm\)最多60, 只要枚举\(60 \ast 60\)的点\(O(n)\)判断是否合法就好了，总复杂度\(O(60^2n^3)\)，边界情况自行注意（我算的时候是左闭右开上闭下开，最后判右边和上面的线）

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;
const int N = 13;
using LL = long long;
LL ans;
int T, n, m, tot;
int x[N], y[N], k[N], t[N];
set<int> xx, yy;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a * b / gcd(a, b);}

bool judge(int xi, int yi) {
    for(int i = 1; i <= n; ++i) {
        if((abs(xi - x[i]) + abs(yi - y[i])) % k[i] != t[i])
            return false;
    }
    return true;
}

LL calc(int x1, int x2, int y1, int y2) {
    int cnt = 0;
    LL res = 0;
    for(int x = x1; x < x1 + tot; ++x) {
        for(int y = y1; y < y1 + tot; ++y) {
            cnt += judge(x, y);
        }
    }
    res += 1LL * cnt * ((x2 - x1) / tot) * ((y2 - y1) / tot);
    cnt = 0;
    int x3 = (x2 - x1) % tot;
    for(int x = x2 - x3; x < x2; ++x) {
        for(int y = y1; y < y1 + tot; ++y) {
            cnt += judge(x, y);
        }
    }
    res += 1LL * cnt * ((y2 - y1) / tot);
    int y3 = ((y2 - y1)) % tot;
    cnt = 0;
    for(int x = x1; x < x1 + tot; ++x) {
        for(int y = y2 - y3; y < y2; ++y)
            cnt += judge(x, y);
    }
    res += 1LL * cnt * ((x2 - x1) / tot);
    for(int x = x2 - x3; x < x2; ++x) {
        for(int y = y2 - y3; y < y2; ++y) {
            res += judge(x, y);
        }
    }
    return res;
}

LL calc_x(int x1, int x2) {
    int cnt = 0; LL res = 0;
    for(int x = x1; x < x1 + tot; ++x)
        cnt += judge(x, m);
    res += 1LL * cnt * ((x2 - x1) / tot);
    int x3 = (x2 - x1) % tot;
    for(int x = x2 - x3; x < x2; ++x) 
        res += judge(x, m);
    return res;
}

LL calc_y(int y1, int y2) {
    int cnt = 0; LL res = 0;
    for(int y = y1; y < y1 + tot; ++y)
        cnt += judge(m, y);
    res += 1LL * cnt * ((y2 - y1) / tot);
    int y3 = (y2 - y1) % tot;
    for(int y = y2 - y3; y < y2; ++y) 
        res += judge(m, y);
    return res;
 }

int main() {
    scanf("%d", &T);
    while(T--) {
        tot = 1; xx.clear(); yy.clear(); ans = 0;
        scanf("%d%d", &n, &m);
        xx.insert(0); xx.insert(m);
        yy.insert(0); yy.insert(m); 
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d%d%d", &x[i], &y[i], &k[i], &t[i]);
            xx.insert(x[i]);
            yy.insert(y[i]);
            tot = lcm(tot, k[i]);
        }
        auto p = xx.begin(), q = xx.begin();
        ++q;
        auto i = yy.begin(), j = yy.begin();
        ++j;
        for(; q != xx.end(); ++p, ++q) {
            for(; j != yy.end(); ++i, ++j) {
                ans += calc(*p, *q, *i, *j);
            }
            i = yy.begin(), j = yy.begin();
            ++j;
        }
        p = xx.begin(); q = xx.begin(); ++q;
        for(; q != xx.end(); ++p, ++q)
            ans += calc_x(*p, *q);
        i = yy.begin(); j = yy.begin(); ++j;
        for(; j != yy.end(); ++i, ++j)
            ans += calc_y(*i, *j);
        if(judge(m, m)) ans++;
        printf("%lld\n", ans);
    }
    return 0;
}

1008. TDL

solve at 01:10(+4)

定义\(f(n, m)\)为第\(m\)个比\(n\)大的与\(n\)互质的数

给你\(m\)和\(k = (f(n, m) - n)\, xor\, n\)，求最小的\(n\)\((1<=k<=1e18, 1<=m<=100)\)

注意到\(m\)非常小，直接在k上下范围内搜就行了(我们取得是2048,好像500就够了)

1011. 11Dimensions

solve at 04:53(+3)

你有一个长度小于\(5e4\)的整数\(n\)和一个数\(m\)，有些数位未知（以问号代替），已知\(n\)是\(m\)的整数倍，\(q\)次询问，每次给出一个数字\(k\)，求第\(k\)小的满足条件的\(n\ mod\ 1e9+7\)的结果\((1<=m<=20, 1<=q<=1e5)\)

队友做法是先\(dp[i][j]\)表示前\(i-1\)位已经填完了，\(i-n\)位的数模\(m\)等于\(j\)的方案数

然后询问离线排序dfs,按位依次枚举填的数是啥，显然每次处理的区间一定是连续的，复杂度不太会算，似乎是\(O(10nm+10(n + q)\log(q))\)?, 反正跑的还挺快的...

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
#define MAXN 1000000
#define LL long long
using namespace std;
const LL e18 = 1000000000000000001LL;
const int mod = 1000000007;
char str[50004];
LL dp[50004][22];
int n, m, Q;
vector<pair<LL, int>> query;
LL ans[100004];
int pow10_m[50004];
LL pow10_mod[50004];
void init()
{
    query.clear();
    for (int i = 0; i <= n + 1; ++i)
        memset(dp[i], 0, sizeof(dp[i]));
    dp[n][0] = 1;
    pow10_m[0] = 1;
    for (int i = 1; i <= n + 1; ++i)
    {
        pow10_m[i] = pow10_m[i - 1] * 10 % m;
    }
    for (int i = 1; i <= Q; ++i)
        ans[i] = -1;
}

void dfs(int curi, int l, int r, LL cans, int modm, LL curk)
{
    if (l > r)
        return;
    if (curi == n)
    {
        if (modm == 0)
        {
            for (int i = l; i <= r; ++i)
            {
                if(curk + 1 == query[i].first)
                    ans[query[i].second] = cans;
            }
        }
        return;
    }
    if (str[curi] != '?')
    {
        dfs(curi + 1, l, r,
            (cans + pow10_mod[n - curi - 1] * (str[curi] - '0')) % mod,
            (modm + pow10_m[n - curi - 1] * (str[curi] - '0')) % m,
            curk);
        return;
    }
    else
    {
        LL tot = curk, tt = curk;
        int ll = l, rr;
        for (int c = 0; c <= 9; ++c)
        {
            tot += dp[curi + 1][(m - ((modm + c * pow10_m[n - curi - 1]) % m)) % m];
            tot = min(e18, tot);
            LL curremain = (cans + pow10_mod[n - curi - 1] * c) % mod;
            rr = upper_bound(&query[l], &query[r + 1], pair<LL,int>(tot, 0x3f3f3f3f)) - (&query[0]);
            dfs(curi + 1, ll, rr - 1, curremain, (modm + c * pow10_m[n - curi - 1]) % m, tt);
            ll = rr;
            if(ll > r) break;
            tt = tot;
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    pow10_mod[0] = 1;
    for (int i = 1; i <= 50001; ++i)
    {
        pow10_mod[i] = pow10_mod[i - 1] * 10 % mod;
    }
    while (T--)
    {
        scanf("%d %d %d %s", &n, &m, &Q, str);
        init();
        for (int i = n - 1; i >= 0; --i)
        {
            if (str[i] != '?')
            {
                for (int r = 0; r < m; ++r)
                {
                    dp[i][(r + (str[i] - '0') * pow10_m[n - i - 1] % m) % m] =
                    min(dp[i][(r + (str[i] - '0') * pow10_m[n - i - 1]) % m] + dp[i + 1][r], e18);
                }
            }
            else
            {
                for (int r = 0; r < m; ++r)
                {
                    for (int c = 0; c <= 9; ++c)
                    {
                        dp[i][(r + c * pow10_m[n - i - 1]) % m] =
                        min(dp[i][(r + c * pow10_m[n - i - 1]) % m] + dp[i + 1][r], e18);
                    }
                }
            }
        }
        for (int id = 1; id <= Q; ++id)
        {
            LL x;
            scanf("%lld", &x);
            query.push_back(pair<LL,int>(x, id));
        }
        sort(query.begin(), query.end());
        dfs(0, 0, Q - 1, 0, 0, 0);
        for (int i = 1; i <= Q; ++i)
            printf("%lld\n", ans[i]);
    }
    return 0;
}

1012. Stay Real

solve at 00:43

队友签的到