NYIST_SW_ACM 第二次常规月赛解题报告

ACM 阅读量

失败的月赛

A. CRY翩翩起舞

一道超级难的证明的签到题（求偏导）？？
实际上大胆猜结论就能过。

题意

给你 $ n $ 个点，让你找到一个点使这个点到所有点的平方距离 (欧几里得距离) 和最小。

题解

场上卡死，不知道怎么解，场下看了题解不知道怎么证明。用了模拟退火，三分套三分的板子，都过不去。不知道为啥求了费马点，也过不去，可能精度？
用这个公式 $ \LARGE x = \frac{\sum_{i = 1}^{n}x_i}{n}\ $ $\LARGE y = \frac{\sum_{i = 1}^{n}y_i}{n}$，求得一个 $ x, y $，然后套欧几里得公式即可。我也不知道为啥。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1E5+7;
typedef long long ll;
struct Point{
    double x,y;
}DATA[MAXN],p;

double dis(Point a,Point b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int main() {
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> DATA[i].x >> DATA[i].y;
        p.x += DATA[i].x;
        p.y += DATA[i].y;
    }
    p.x /= n;
    p.y /= n;
    double ans;
    for(int i = 1;i <= n;i++){
        ans += dis(p,DATA[i]);
    }
    printf("%.2f\n",ans);
    return 0;
}

B. CRY痛哭流涕

待补

C. CRY推命题

题意

给你一堆命题的关系，用矩阵的 $i，j$ 表示。$0$ 代表不确定 $i,j$ 的关系 ，$1$ 代表 $i \to j$，$-1$ 代表 $i$ 无法推出 $j$ 。问最少需要确定几个 $0$ 的关系才能确定 $ 1 \to n\ $ ，否则输出 $-1$.

题解

正解应该是 $O(n)$ 的 $ 01BFS $，但是数据难造，$O(n*logn))$的最短路也可过。
对与这张图，我们对关系为 $1$ 的 $i \to j$ 建花费为$0$ 的边， 对关系为 $0$ 的 $i \to j$ 建造花费为 $1$ 的边，剩余的都设为 $INF$。跑整张图的最短路即可。

代码

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
#include <bits/stdc++.h>
const int MAXN = 2e5 + 5;
const int INF = 0x3f3f3f3f;
using namespace std;
vector<pair<int, int> > edge[MAXN];
bool vis[MAXN];
int dist[MAXN];

void dijkstra(int n) {
    memset(dist, INF, sizeof(dist));
    memset(vis, false, sizeof(vis));
    priority_queue<pair<int, int> > que;
    que.push(make_pair(0, 1));
    dist[1] = 0;
    while (!que.empty()) {
        int u = que.top().second;
        que.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < edge[u].size(); i++) {
            int v = edge[u][i].first;
            if (dist[v] > dist[u] + edge[u][i].second) {
                dist[v] = dist[u] + edge[u][i].second;
                que.push(make_pair(-dist[v], v));
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            edge[i].clear();
            for (int j = 1; j <= n; j++) {
                int op;
                cin >> op;
                if (i == j)
                    continue;
                if (op == 0) {
                    edge[i].push_back(make_pair(j, 1));
                } else if (op == 1) {
                    edge[i].push_back(make_pair(j, 0));
                }
            }
        }
        dijkstra(n);
        cout << dist[n] << endl;
    }
}

D. CRY的住宿计划

题意

找到一个 $0$ 的位置，使这个 $0$ 的位置到其他 $K$ 个 $0$ 的位置切比雪夫距离最大值最小

两点 $(x_1,y_1)\ (x_2,y_2)$ 的切比雪夫距离为 $max(abs(x_1-x_2),abs(y_1-y_2))$ ，其中 $abs()$为绝对值函数。

题解

暴力枚举每个点，二分切比雪夫距离，用二维前缀和快速查询当前矩形中 $0$ 的个数 时间复杂度 $O(n^{2}\ast logn)$
还有一中 $O(n^{2} + logn ^ {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
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1E5+7;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
int n,m,k;
int dp[1005][1005];
char Map[1005][1005];

bool judge(int x,int y,int mid){
    int a = max(1,x - mid),b = max(1,y - mid);
    int c = min(n,x + mid),d = min(m,y + mid);
    int num = dp[c][d] - dp[c][b-1] - dp[a-1][d] + dp[a-1][b-1];
    return num >= k + 1;
}

int solve(int x,int y){
    int L = 0,R = max(n , m);
    int ans = INF;
    while(L <= R){
        int mid = (L + R) >> 1;
        if(judge(x,y,mid)){
            R = mid - 1;
            ans = mid;
        } else {
            L = mid + 1;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;

    for(int i = 1;i <= n;i++){
        scanf("%s",Map[i]+1);
    }

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + ((Map[i][j] - '0')^1);
        }
    }
    
    int ans = INF;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
        	if(Map[i][j] == '0')
            	ans = min(ans,solve(i,j));
        }
    }
    cout << ans << endl;
    return 0;
}

E. CRY的心里阴影

待补

F.CRY的最大公约数

题意

$T$ 组数据，$n$ 次操作，每次给定一个数，如果这个数不在当前序列内则把这个数加入这个序列，否则把这个数从序列中删去，求当前序列的最大公约数

题解

直接权值线段树，离散化数据，每次更新一个链，查询 $O(1)$ 即可

代码

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4E5 + 7;
typedef long long ll;
int a[MAXN];
int n;
vector<int> V;
struct Node {
    int l, r;
    int mid() { return (l + r) >> 1; }
    int gcd;
} tree[MAXN << 2];
int getid(int x) { return lower_bound(V.begin(), V.end(), x) - V.begin() + 1; }

void PushUp(int rt) {
    if (tree[rt << 1].gcd == -1 && tree[rt << 1 | 1].gcd == -1)
        tree[rt].gcd = -1;
    else if (tree[rt << 1 | 1].gcd == -1)
        tree[rt].gcd = tree[rt << 1].gcd;
    else if (tree[rt << 1].gcd == -1)
        tree[rt].gcd = tree[rt << 1 | 1].gcd;
    else
        tree[rt].gcd = __gcd(tree[rt << 1].gcd, tree[rt << 1 | 1].gcd);
    return;
}

void Build(int l, int r, int rt) {
    tree[rt].l = l, tree[rt].r = r;
    tree[rt].gcd = -1;
    if (l == r)
        return;
    int mid = tree[rt].mid();
    Build(l, mid, rt << 1);
    Build(mid + 1, r, rt << 1 | 1);
}

void Update(int pos, int val, int rt) {
    if (tree[rt].l == tree[rt].r && tree[rt].l == pos) {
        if (tree[rt].gcd == -1)
            tree[rt].gcd = val;
        else
            tree[rt].gcd = -1;
        return;
    }
    int mid = tree[rt].mid();
    if (pos <= mid)
        Update(pos, val, rt << 1);
    else
        Update(pos, val, rt << 1 | 1);
    PushUp(rt);
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        V.clear();
        Build(1, n, 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            V.push_back(a[i]);
        }
        sort(V.begin(), V.end()), V.erase(unique(V.begin(), V.end()));
        for (int i = 1; i <= n; i++) {
            int pos = getid(a[i]);
            Update(pos, a[i], 1);
            cout << tree[1].gcd << endl;
        }
    }
    return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2018 - 2020 Never Give Up! All Rights Reserved.

访客数 : | 访问量 :