Kyooma's Blog

2023杭电多校03

  • ~17.07K 字

题目来自: 2023“钉耙编程”中国大学生算法设计超级联赛（3）

Solved Rank A B C D E F G H I J K L
2 / 12 300 / 1200 - - - Ø O - - - Ø - O Ø
  • Ø 赛后通过
  • O 在比赛中通过
  • ! 尝试了但是失败了
  • - 没有尝试

D - Chaos Begin

SOLUTION

瞎搞，雷伤杯差点秒了

CODE
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q], *is=in, *it=in, c;
void read(ll &n){
	for(n = 0; (c = gc()) < '0' || c > '9';);
	for(;c <= '9' && c >= '0'; c = gc()) n = n * 10 + c - 48;
}

void read(int &n){
	for(n = 0; (c = gc()) < '0' || c > '9';);
	for(;c <= '9' && c >= '0'; c = gc()) n = n * 10 + c - 48;
}
pair <ll,ll> p[100005];
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
ll rng(ll l,ll r) {
	uniform_int_distribution <ll> uni (l,r);
	return uni(mt);
}
map <pair<ll,ll> ,ll> mp,ans;
ll n;
struct Point{
	ll x,y;
	Point(){
		
	}
	Point (ll _x,ll _y):x(_x),y(_y) {
		
	}
	Point operator + (const Point &b) const {
		return Point(x+b.x,y+b.y);
	}
	ll operator ^ (const Point &b) const {
		return x*b.y-y*b.x;
	}
	Point operator -(const Point &b) const {
		return Point(x-b.x,y-b.y);
	}
	bool operator != (const Point &b) const {
		return x!=b.x||y!=b.y;
	}
}P[60],fx,fff,QQ[60];
bool cmp(Point u,Point v) {
	ll du=u^fff,dv=v^fff;
	return du>dv;
}
void brute(){
	ans.clear();
	for (int i=1;i<=2*n;++i) {
		//read(P[i].x);read(P[i].y);
		cin >> P[i].x >> P[i].y;
	}
	for (int i=2;i<=2*n;++i) {
		QQ[i]=P[i]-P[1];
	}
	for (int i=2;i<=2*n;++i) {
		fx=QQ[i];
		fff=Point(fx.y,-fx.x);
		//cout << "fx.x=" <<fx.x << ",fx.y=" << fx.y << endl;
		sort(P+1,P+1+2*n,cmp);
		bool f=true;
		mp.clear();
		for (int j=1;j<=2*n;++j) {
			
			//cout << "x=" << P[j].x << ",y=" << P[j].y << endl;
			//cout << "dddd==" << (P[j]^fff) << endl;
			mp[make_pair(P[j].x,P[j].y)]++;
		}
		for (int j=1;j<=2*n;++j) {
			if (!mp[make_pair(P[j].x,P[j].y)]) continue;
			mp[make_pair(P[j].x,P[j].y)]--;
			Point aft=P[j]+fx;
			if (mp[make_pair(P[j].x,P[j].y)]) j--;
			if (!mp[make_pair(aft.x,aft.y)]) {
				
				f=false;
				break;
			}
			mp[make_pair(aft.x,aft.y)]--;
		}
		if (f) {
			ans[make_pair(fx.x,fx.y)]++;
			ans[make_pair(-fx.x,-fx.y)]++;
		}
	}
	cout << ans.size() << endl;
	for (auto it:ans) {
		cout << it.first.first << " " << it.first.second << endl;
	}
}
void solve(){
	mp.clear();
	ans.clear();
	for (int i=1;i<=2*n;++i) {
		cin >> p[i].first >> p[i].second;
		//read(p[i].first);read(p[i].second);
		mp[p[i]]++;
	}
	ll e=rng(1,2*n);
	//cout << "e=" << e << endl;
	for (int i=1;i<=2*n;++i) {
		if (i==e) continue;
		ll dx=p[i].first-p[e].first,dy=p[i].second-p[e].second;
		bool f=true;
		for (int j=1;j<=2*n;++j) {
			//cout << "j=" << j << endl;
			//cout << "x1=" << p[j].first+dx << endl;
			//cout << "y1=" << p[j].second+dy <<endl;
			//cout << "x2=" << p[j].first-dx << endl;
			//cout << "y2=" << p[j].second-dy <<endl;
			bool ff=false;
			if (mp[make_pair(p[j].first+dx,p[j].second+dy)]) ff=true;
			if (mp[make_pair(p[j].first-dx,p[j].second-dy)]) ff=true;
			if (!ff) {
				f=false;break;
			}
		}
		if (f) {
			ans[make_pair(dx,dy)]++;
			ans[make_pair(-dx,-dy)]++;
		}
	}
	cout << ans.size() << endl;
	for (auto it:ans) {
		cout << it.first.first << " " << it.first.second << endl;
	}
}

signed main(){
	int T = 1;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//read(T);
	cin >> T;
	while(T--) {
		cin >> n;
		if (n<=50) {
			brute();
		}else {
			solve();
		}
		
	}
	return 0;
}

E - Out of Control

SOLUTION

dp，lfy秒了

CODE
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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q], *is=in, *it=in, c;

void read(ll &n){
	for(n = 0; (c = gc()) < '0' || c > '9';);
	for(;c <= '9' && c >= '0'; c = gc()) n = n * 10 + c - 48;
}

void read(int &n){
	for(n = 0; (c = gc()) < '0' || c > '9';);
	for(;c <= '9' && c >= '0'; c = gc()) n = n * 10 + c - 48;
}
const int N=3e3+10;
const int p=1e9+7;
unordered_map<int,int>mp;
int a[N];
int dp[N][N];
void solve(){
	int n,i,j,x,y,ans=0;
	cin>>n;
	mp.clear();
	for(i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]++;
	}
	sort(a+1,a+n+1);
	int len=unique(a+1,a+n+1)-a-1;
	for(i=0;i<=len;i++){
		for(j=0;j<=n;j++) dp[i][j]=0;
	}
	int cnt=0;
	dp[0][0]=1;
	for(i=1;i<=len;i++){
		cnt+=mp[a[i]];
//		for(j=1;j<=cnt;j++){
//			dp[i][j]=(dp[i][j]+dp[i-1][j])%p;
//		}
		x=0;
		dp[i][0]=1;
		for(j=1;j<=cnt;j++){
			x=(x+dp[i-1][j-1])%p;
			dp[i][j]=((dp[i][j]+x)%p+dp[i-1][j])%p;
		}
	}
	for(i=1;i<=n;i++){
		ans=0;
//		for(j=1;j<=len;j++){
//			cout<<dp[j][i]<<" ";
//		}
//		cout<<'\n';
		cout<<dp[len][i]<<'\n';
	}
}

int main(){
	int T = 1;
//	read(T);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> T;
	while(T--) solve();
	return 0;
}

K - 8-bit Zoom

SOLUTION

签到题

CODE
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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q], *is=in, *it=in, c;

void read(ll &n){
	for(n = 0; (c = gc()) < '0' || c > '9';);
	for(;c <= '9' && c >= '0'; c = gc()) n = n * 10 + c - 48;
}

void read(int &n){
	for(n = 0; (c = gc()) < '0' || c > '9';);
	for(;c <= '9' && c >= '0'; c = gc()) n = n * 10 + c - 48;
}

const int N = 500;

char ch[N][N], res[N][N];

bool jud(int x, int y, int p){
	char chr = '.';
	for(int i = x; i < x + p; i++){
		for(int j = y; j < y + p; j++){
			if(chr == '.') chr = ch[i][j];
			else if(chr != ch[i][j]){
				return false;
			}
		}
	}
	return true;
}

void get(int x, int y, int q, char chr){
	for(int i = x; i < x + q; i++){
		for(int j = y; j < y + q; j++){
			res[i][j] = chr;
		}
	}
}

void solve(){
	int n, z;
	cin >> n >> z;
	int p = 1;
	if(z == 125 || z == 175) p = 4;
	else if(z == 150) p = 2;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin >> ch[i][j];
		}
	}
	if(n % p){
		cout << "error\n";
		return;
	}
	int q = z * p / 100;
	for(int i = 1, x = 1; i <= n; i += p, x += q){
		for(int j = 1, y = 1; j <= n; j += p, y += q){
			if(!jud(i, j, p)){
				cout << "error\n";
				return;		
			}
			get(x, y, q, ch[i][j]);
		}
	}
	n = n * z / 100;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cout << res[i][j];
		}
		cout << '\n';
	}
}

int main(){
	int T = 1;
//	read(T);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> T;
	while(T--) solve();
	return 0;
}

L - Noblesse Code

SOLUTION

对于一组 $(A, B)$，若 $A > B$，则它的父节点为 $(A \bmod B, B)$ ，反之类似。记作根节点为 $(a, a)$ 这样的点，并且由于根节点可以变成 $(a + a, a)$ 和 $(a, a + a)$，所以需要将根节点拆成两个点。

接下来对输入的 $n + m$ 个点每次求出它的父节点，并向它连边，这样就可以连出一颗树来。将前 $n$ 个点的点权记为 $1$，后 $m$ 个点的点权记为 $0$ ，这样每个点的答案就是它的字树点权和以及从它可以到达的几个兄弟节点的字树点权和。而兄弟节点之间一定是 $A$ 相同或者 $B$ 相同，那么按照不同的那一个数从大到小排序后求一遍前缀和即可。

CODE
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
119
120
121
122
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int N = 3e6 + 10, Log = 20, inf = 0x3f3f3f3f, M = 1e5 + 10;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

void read(int &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

struct Edge{
    int v;
    ll w;
    bool operator < (const Edge &p) const{
        return w > p.w;
    }
};

vector<Edge> e[N];
int tot, qry[M][2], a[N], du[N], ans[N];
map<pll, int> mp;

bool is_add;
int find_id(pll u){
    is_add = false;
    if(!mp.count(u)){
        is_add = true;
        mp[u] = ++tot;
        if(u.first == u.second) tot++;
    }
    return mp[u];
}

void dfs(int u){
    ans[u] = a[u];
    sort(e[u].begin(), e[u].end());
    int pre = 0;
    for(auto i : e[u]){
        int v = i.v;
        dfs(v);
        ans[u] += ans[v];
        pre += ans[v];
        ans[v] = pre;
    }
}

void solve() {
    int n, m;
    // cin >> n >> m;
    read(n);read(m);
    for(int i = 1; i <= n + m; i++){
        ll ai, bi, w;
        // cin >> ai >> bi;
        read(ai);read(bi);
        int u = find_id({ai, bi});
        if(i <= n) a[u] += 1;
        else{
            qry[i - n][0] = u;
            if(ai == bi) qry[i - n][1] = u + 1;
        }
        while(true){
            if(ai == bi || !is_add) break;
            if(ai < bi){
                w = bi;
                bi %= ai;
            }else{
                w = ai;
                ai %= bi;
            }
            int p = 0;
            if(!ai) ai = bi, p = 1;
            if(!bi) bi = ai;
            int fa = find_id({ai, bi}) + p;
            e[fa].push_back({u, w});
            // dbg(fa, u);
            du[u]++;
            u = fa;
        }
    }
    for(int i = 1; i <= tot; i++){
        if(!du[i]){
            dfs(i);
        }
    }
    for(int i = 1; i <= m; i++){
        cout << ans[qry[i][0]] + ans[qry[i][1]] << '\n';
        qry[i][0] = qry[i][1] = 0;
    }
    for(int i = 1; i <= tot; i++){
        e[i].clear();
        a[i] = ans[i] = du[i] = 0;
    }
    tot = 0;
    mp.clear();
}

int main() {
    int T = 1;
    // auto start = clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // cin >> T;
    read(T);
    while (T--) solve();
    // auto end = clock();
    // cout << "time:: " << 1. * (end - start) / CLOCKS_PER_SEC << '\n';
    return 0;
}

I - Operation Hope

SOLUTION

二分 + 2sat

首先二分答案 $x$，那么对于两个点 $u, v$，若存在 $|a_u - a_v| > x$ （$b, c$ 同理），那么 $u, v$ 就是一组互斥关系，需要建出$(u, \neg v)$ 和 $(v, \neg u)$ 两条边。对于判断2sat可行性，若使用tarjan跑scc，则需要建 $n^2$ 条边，显然是不允许的。

考虑Kosaraju算法找scc，该算法只需要遍历所有点，不需要遍历所有的边，而在此题中，若将排序后的数组依次放入双端队列，则对于某个点来说，和它相差最大的要么是队头，要么是队尾，而且基于Kosaraju算法，遍历过的点就可以直接从队列中移除，因此跑一次scc的时间复杂度是 $O(n)$。

总时间复杂度为 $O(nlog(w))$， $w$ 表示最大权值。

CODE
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10, Log = 20, inf = 0x3f3f3f3f, M = 3;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

void read(int &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

int a[N][3], n;

struct Queue{
    int q[N], l, r, p, base;
    Queue(){}
    Queue(int p_): p(p_){
        for(int i = 1; i <= n * 2; i++) q[i] = i;
        sort(q + 1, q + 1 + n * 2, [&](int &x, int &y){
            return a[x][p] < a[y][p];
        });
        init();
    }
    void init(int base_ = 0){
        l = 1;
        r = n * 2;
        base = base_;
    }
    int get(int val){
        if(l > r) return -1;
        if(a[q[l]][p] < val - base){
            return q[l++];
        }
        if(a[q[r]][p] > val + base){
            return q[r--];
        }
        return -1;
    }
}qe[M];

int color[N], stk[N], top, scc;
bool vis[N];

int re(int v){
    return v > n ? v - n : v + n;
}

void dfs1(int u){
    if(vis[u]) return;
    vis[u] = true;
    for(int i = 0; i < M; i++){
        while(true){
            int v = qe[i].get(a[u][i]);
            if(v <= 0) break;
            dfs1(re(v));
        }
    }
    stk[++top] = u;
}

void dfs2(int u){
    if(color[u]) return;
    color[u] = scc;
    int reu = re(u);
    for(int i = 0; i < M; i++){
        while(true){
            int v = qe[i].get(a[reu][i]);
            if(v <= 0) break;
            dfs2(v);
        }
    }
}

bool jud(int mid){
    for(int i = 0; i < M; i++){
        qe[i].init(mid);
    }
    for(int i = 1; i <= n * 2; i++){
        if(!vis[i]){
            dfs1(i);
        }
    }
    for(int i = 0; i < M; i++){
        qe[i].init(mid);
    }
    for(int i = 2 * n; i >= 1; i--){
        if(!color[stk[i]]){
            scc++;
            dfs2(stk[i]);
        }
    }
    bool ok = true;
    for(int i = 1; i <= n; i++){
        if(color[i] == color[i + n]) ok = false;
        vis[i] = color[i] = 0;
        vis[i + n] = color[i + n] = 0;
    }
    top = scc = 0;
    return ok;
}

void solve() {
    int mn = inf, mx = -inf;
    read(n);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < M; j++){
            read(a[i][j]);
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }
        for(int j = 0; j < M; j++){
            read(a[i + n][j]);
            mn = min(mn, a[i + n][j]);
            mx = max(mx, a[i + n][j]);
        }
    }
    for(int i = 0; i < M; i++){
        qe[i] = Queue(i);
    }
    int l = 0, r = mx - mn;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(jud(mid)){
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    cout << l << '\n';
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    read(T);
    while (T--) solve();
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可