Educational Codeforces Round 99 (Rated for Div. 2)

ACM算法日常

发布于 2020-12-15 09:49:34

3200

发布于 2020-12-15 09:49:34

文章被收录于专栏：ACM算法日常

A. Strange Functions

定义

g(x)=x

末尾有几个0，问在1到n范围内

g(x)

有多少种不同的取值。

1\le n\le 10^{100}

「思路」

显然末尾最少有0个0，假设数字长度为

len

，最多就有len-1个0，那么答案就是len。

单组时间复杂度：

O(len)

#include <bits/stdc++.h>
#define rep(i, s, t) for(register int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(register int i = (s), LIM=(t); i >= LIM; --i)
using namespace std;
const int MXN = 2e5 + 5;
int n;
char ar[MXN];
void work() {
    scanf("%s", ar);
    n = strlen(ar);
    printf("%d\n", n);
}
int main() {
    //ios::sync_with_stdio(false);cin.tie(0);
    int tim;
    cin >> tim;
    for(int cas = 1; cas <= tim; ++ cas) work();
    return 0;
}

B. Jumps

在一维数轴中，初始时位于0，

pos=0

，第

次移动有两种选择：

向后移动距离1，

pos=pos-1

；

向前移动距离k，

pos=pos+k

。

问最多移动次数移动到位置

。

1\le t\le 10^3,1\le n\le10^6

「思路」

首先对于每次移动都选择向前移动

步，接下来有三种情况：

当前

pos=n

，答案是当前走的次数。

当前

pos=n+1

，答案是当前走的次数加1。

当前

pos\gt n+1

，答案是当前走的次数。

那么为什么当

pos=n+1

的时候，需要再走一步呢？

因为你将某一步变成向后移动距离1的话，最远也只能移动到位置

pos-2

，所以当前走的次数内不可能走到

。

单组时间复杂度：

O(\sqrt n)

#include <bits/stdc++.h>
#define rep(i, s, t) for(register int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(register int i = (s), LIM=(t); i >= LIM; --i)
using namespace std;
const int MXN = 2e5 + 5;
int n;
void work() {
    cin >> n;
    int ans = 0, sum = 0;
    for(int i = 1; i <= n; ++i) {
        sum += i;
        if(sum == n) {
            ans = i;
            break;
        }else if(sum == n + 1) {
            ans = i + 1;
            break;
        }else if(sum > n) {
            ans = i;
            break;
        }
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int tim;
    cin >> tim;
    for(int cas = 1; cas <= tim; ++ cas) work();
    return 0;
}

C. Ping-pong

Alice

和玩

Bob

乒乓球游戏，

Alice

先手。

初始

Alice

有

点耐力值，

Bob

有

点耐力值，发球和接球会损失一点耐力值，没有耐力值就不能接球和发球。

谁无法回击对方打过来的球这回合谁就输了，每个回合赢了的人可以接着下一回合发球。

他们都采用最佳策略，即首先尽可能让自己赢得多，其次让对方赢得少。

输出最后双方赢的回合数。

1\le t\le 10^4,1\le x,y\le 10^6

「思路」

后手的某一种最佳策略是让先手先一直赢，那么一直是先手发球。

当先手发完球耐力值变成0的时候，后手选择回击球，因为此时先手无法反击。那么先手就少赢一轮，且后手每一轮都能赢。

但是不管怎么样，后手一定要保证自己的耐力值比先手后变成0。

因为每个人都是最主要的是让自己赢得多，所以很多时候会选择暂时让球。

所以最后答案是

x-1,y

。

单组时间复杂度：

O(1)

#include <bits/stdc++.h>
#define rep(i, s, t) for(register int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(register int i = (s), LIM=(t); i >= LIM; --i)
using namespace std;
const int MXN = 2e5 + 5;
int n, m;
void work() {
    cin >> n >> m;
    cout << n - 1 << " " << m << "\n";
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int tim;
    cin >> tim;
    for(int cas = 1; cas <= tim; ++ cas) work();
    return 0;
}

D. Sequence and Swaps

给你一个长度为

的数组和一个整数

，每次操作你可以任意选择一个大于

的元素

a[i]

，交换他们的值，问最少次数使得这个数组单调不递减。

1\le t\le 500,1\le n\le 500,0\le x,a_i\le 500

「思路」

因为

只能和比

大的数字交换值，那么

肯定会越来越大。如果有多个需要交换的地方，一定最先交换前的地方，因为

会变大，且我要保证数组单调不递减呀。

首先记录

las

为最后一个下标满足

a[las]\lt a[las-1]

。那么我必须要从头开始遍历直到

las-1

为止，所有能和

交换的地方就一定要交换。

最后判断序列是否合法，如果合法输出交换次数，否则输出-1。

单组时间复杂度：

O(n)

#include <bits/stdc++.h>
#define rep(i, s, t) for(register int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(register int i = (s), LIM=(t); i >= LIM; --i)
using namespace std;
const int mod = 998244353;
const int MXN = 1e3 + 5;
int n, m;
int ar[MXN];
void work() {
    cin >> n >> m;
    int cnt = 0, las = -1;
    rep(i, 1, n + 1) cin >> ar[i];
    rep(i, 2, n + 1) {
        if(ar[i] < ar[i - 1]) {
            las = i;
        }
    }
    rep(i, 1, las) {
        if(ar[i] > m) {
            ++ cnt;
            swap(ar[i], m);
        }
    }
    rep(i, 2, n + 1) {
        if(ar[i] < ar[i - 1]) {
            cnt = -1;
            break;
        }
    }
    cout << cnt << "\n";
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int tim = 1;
    cin >> tim;
    for(int cas = 1; cas <= tim; ++ cas) work();
    return 0;
}

E. Four Points

给你二维坐标系上四个整点，每次操作可以将某个整点移动到和它4相邻的一个位置。问最少操作次数使得这四个点组成一个正方形。正方形边长可以为0。

1\le t\le 10^4,0\le x,y\le 10^9

「思路」

首先这四个点对应在正方形上点的顺序一共只有4!种可能性，可以用next_permutation来枚举这个对应顺序。

接下来是这个正方形的边长，他的边长肯定是四个点之间横坐标差的绝对值和纵坐标差的绝对值中的一个，共有

种取值可能性。

假设左下的点为

a[0]

，右下的点为

a[1]

，右上的点为

a[2]

，左上的点为

a[3]

。

枚举边长为

，我们先将四个点做操作：

a[1].x -= d, a[2].x -= d, a[2].y -= d, a[3].y -= d

。

那么此情况的答案就是将四个点移动到同一个点的最小操作次数。

经典问题，横纵坐标分开考虑，显然是移动到中位数位置即可。

单组时间复杂度：

O(4!*12*4)

#include <bits/stdc++.h>
#define rep(i, s, t) for(register int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(register int i = (s), LIM=(t); i >= LIM; --i)
using namespace std;
int n, m;
class node {
    public:
    int x, y;
}p[4];
void work() {
    vector<int> d(4, 0);
    vector<int> vlen;
    vector<node> a;
    rep(i, 0, 4) {
        d[i] = i;
        cin >> p[i].x >> p[i].y;
        rep(j, 0, i) {
            vlen.emplace_back(abs(p[i].x - p[j].x));
            vlen.emplace_back(abs(p[i].y - p[j].y));
        }
    }
    int64_t ans = 1e18;
    do {
        a.clear();
        rep(i, 0, 4) a.emplace_back(p[d[i]]);
        for(int d: vlen) {
            a[1].x -= d, a[2].x -= d, a[2].y -= d, a[3].y -= d;
            int64_t cnt = 0;
            vector<int> vx, vy;
            rep(i, 0, 4) vx.emplace_back(a[i].x), vy.emplace_back(a[i].y);
            sort(vx.begin(), vx.end());
            sort(vy.begin(), vy.end());
            rep(i, 0, 4) cnt += abs(vx[i] - vx[1]), cnt += abs(vy[i] - vy[1]);
            ans = min(ans, cnt);
            a[1].x += d, a[2].x += d, a[2].y += d, a[3].y += d;
        }
    }while(next_permutation(d.begin(), d.end()));
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int tim = 1;
    cin >> tim;
    for(int cas = 1; cas <= tim; ++ cas) work();
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-12-02，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度