A. Points on the line

题意

给定一条直线上\(n\)个点，要求去掉最少的点，使得直线上相距最远的两个点的距离\(\leq d\).

思路

枚举长度为\(d\)的区间。

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long LL;

int a[110];

int main() {

    int n, d;

    scanf("%d%d", &n, &d);

    F(i, 0, n) {

        int x;

        scanf("%d", &x);

        ++a[x];

    }

    F2(i, 1, 100) a[i] += a[i-1];

    int ans = min(a[100]-a[d], a[99-d]);

    F(i, 1, 100-d) {

        int l = i, r = i+d;

        ans = min(ans, a[l-1]+a[100]-a[r]);

    }

    printf("%d\n", ans);

    return 0;

}

B. Our Tanya is Crying Out Loud

题意

初始数为\(n\)，两种操作：

减一：代价为\(A\)
除以\(k\)：代价为\(B\)且仅当整除时可进行此操作

求最小代价使\(n\)变为\(1\).

思路

一旦某一次除法的代价\(\gt\)减法的(等效)代价，则直接减到\(1\)，否则进行除法操作。

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long LL;

int main() {

    LL n,k,a,b;

    scanf("%I64d%I64d%I64d%I64d",&n,&k,&a,&b);

    LL ans = 0;

    bool flag = false;

    while (n!=1) {

        if (n%k) {

            ans += n%k*a;

            n = n/k*k;

        }

        if (n/k*(k-1)*a <= b) {

            ans += (n-1)*a;

            break;

        }

        ans += b;

        n /= k;

    }

    printf("%I64d\n", ans);

    return 0;

}

C. Phone Numbers

题意

在字符集\(\sum\)范围内，求长度为\(k\)的，比给定字符串\(s\)大的，最小的字符串。

思路

记\(len=|s|\)，

若\(len<k\)，在\(s\)之后补\(k-len\)个最小的字符
若\(len>k\)，首先将之后的多余部分截断，再将前面的部分加一（操作与数字+1同理）。

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

#define maxn 100010

using namespace std;

typedef long long LL;

char s[maxn];

int mp[256], ch[30], a[maxn];

bool vis[256];

int main() {

    int n, k, tot=0;

    scanf("%d%d", &n,&k);

    scanf("%s",s);

    int len = strlen(s);

    F(i, 0, len) {

        if (tot==26) break;

        if (!vis[s[i]]) {

            ch[tot++] = s[i];

            vis[s[i]] = true;

        }

    }

    sort(ch, ch+tot);

    F(i, 0, tot) mp[ch[i]] = i;

    if (k>len) {

        while (len<k) s[len++] = ch[0];

        s[len] = '\0';

        puts(s);

        return 0;

    }

    s[k] = '\0';

    F(i, 0, k) a[i] = mp[s[i]];

    int i = k-1;

    while (true) {

        ++a[i];

        if (a[i]<tot) break;

        a[i--] = 0;

    }

    F(i, 0, k) s[i] = ch[a[i]];

    puts(s);

    return 0;

}

D. Alena And The Heater

题意

给定数组\(a\)，按一定的规则可以生成数组\(b\). 规则如下：

\(b_1=b_2=b_3=b_4=0.\)

For all \(5\leq i\leq n\):

--- \(b_i=0\) if \(a_i,a_{i-1},a_{i-2},a_{i-3},a_{i-4}\gt r\) and \(b_{i-1},b_{i-2},b_{i-3},b_{i-4}=1\)

--- \(b_i=1\) if \(a_i,a_{i-1},a_{i-2},a_{i-3},a_{i-4}\lt l\) and \(b_{i-1},b_{i-2},b_{i-3},b_{i-4}=0\)

--- \(b_i=b_{i-1}\) otherwise

思路

只需确定每个转折点，对于其及其前面共\(5\)个数字，由\(1\)变为\(0\)则取最小值使\(r\)比它小，由\(0\)变为\(1\)则取最大值使\(l\)比它大。

至于中间则无需考虑，因为题目保证有解，而要不发生变化，即条件不成立，则只要\(l\)尽量小，\(r\)尽量大即可。

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

#define inf 1000000000

#define maxn 100010

using namespace std;

char s[maxn];

int a[maxn];

typedef long long LL;

int minn(int p) { int ret = a[p]; F(i, p+1, p+5) ret = min(ret, a[i]); return ret; }

int maxx(int p) { int ret = a[p]; F(i, p+1, p+5) ret = max(ret, a[i]); return ret; }

int main() {

    int n;

    scanf("%d", &n);

    F(i, 0, n) scanf("%d", &a[i]);

    scanf("%s", s);

    bool flag = false;

    int r = inf, l = -inf;

    F(i, 0, n) {

        if (s[i]-'0'!=flag) {

            if (flag) r = min(r, minn(i-4)-1);

            else l = max(l, maxx(i-4)+1);

            flag = !flag;

        }

    }

    printf("%d %d\n", l, r);

    return 0;

}

E. Cashback

题意

给定一个数组，将其分割成若干段，将每一段的\(value\)求和，要求得最小值。

\(value\)定义如下：

对于长度为\(k\)的数组\(b\)，其\(value\)为除了\(\lfloor\frac{k}{c}\rfloor\)小元素以外的元素的和。

例如：[3,1,6,5,2], c=2，其value为3+6+5=14.

思路

首先一个显然的事实是：假设不分段而作为一个整体能去除掉\(m\)个元素，那分段去除掉的元素个数必然\(\leq m\).

然而又有另一个显然的事实：不分段去掉\(m\)个元素之和\(sum1\)，与分段去掉\(m\)个元素\(sum2\)相比，显然\(sum1\leq sum2\). 因为不分段的话去掉的是一整段的\(m\)个最小，而分段的话去掉的是\(m\)段中每段中的最小。

综合上面两个事实，应该尽量多分段，又要保证每一段分的有价值，即，最理想的情况就是每\(c\)个元素分一段。

于是\(dp\)如下：

\(dp[i] = min(dp[i-1]+a[i], dp[i-c]+sum[i-c+1..i]-min[i-c+1..i])\)

至于最小值，直接用ST表进行RMQ即可，比赛时用的是单调队列维护的...。

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

#define maxn 100010

using namespace std;

typedef long long LL;

LL a[maxn], sum[maxn], dp[maxn];

int st[maxn];

int main() {

    int n, c;

    scanf("%d%d", &n, &c);

    F2(i, 1, n) {

        scanf("%I64d", &a[i]);

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

    }

    if (c==1) { printf("%d\n", 0); return 0; }

    dp[1] = a[1];

    int l=0, r=0; st[r++] = 1;

    F2(i, 2, n) {

        LL minn = dp[i-1]+a[i];

        while (r>l && a[st[r-1]]>=a[i]) --r;

        st[r++] = i;

        if (i-c>=0) {

            while (r>l && st[l]<=i-c) ++l;

            minn = min(minn, dp[i-c]+sum[i]-sum[i-c]-a[st[l]]);

        }

        dp[i] = minn;

    }

    printf("%I64d\n", dp[n]);

    return 0;

}

巴特西

Codeforces Round #466

A. Points on the line

题意

思路

Code

B. Our Tanya is Crying Out Loud

题意

思路

Code

C. Phone Numbers

题意

思路

Code

D. Alena And The Heater

题意

思路

Code

E. Cashback

题意

思路

Code

最新文章

热门文章