Codeforces Round #666 (Div. 2) 题目大意 & 解题报告

by woshiluo

即 Codeforces Round 1397
比赛链接: https://codeforces.com/contest/1397

A Juggling Letters

题目大意

给你 $n$ 个字符串，问能不能打乱成相等的三个字符串

思路

因为可以随意打乱，所以统计每个字母个数，只要每个字母的个数模 $n$ 余 $0$ 即可

Code

// Woshiluo<[email protected]>
// 2020/08/30 22:37:13
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>

template <class T>
T Max( T a, T b ) { return a > b? a: b; }
template <class T>
T Min( T a, T b ) { return a < b? a: b; }
template <class T>
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T>
void chk_Min( T &a, T b ) { if( b < a ) a = b; }

int T;
int n;
char a[1100];
int sum[200];

int main() {
        scanf( "%d", &T );
        while( T -- ) {
                memset( sum, 0, sizeof(sum) );
                scanf( "%d", &n );
                for( int i = 1; i <= n; i ++ ) {
                        scanf( "%s", a );
                        int len = strlen(a);
                        for( int i = 0; i < len; i ++ ) {
                                sum[ a[i] ] ++;
                        }
                }
                bool flag = true;
                for( int i = 'a'; i <= 'z'; i ++ ) {
                        if( sum[i] % n != 0 ) {
                                flag = false;
                        }
                }
                printf( "%s\n", flag? "YES": "NO" );
        }
}

B Power Sequence

题目大意

给定 $a$ 序列，可以随便打乱

每次可以花费一代价，将某个数字 $+1$ 或 $-1$

问最少多少代价，可以把使得 $a$ 序列满足 $a_i=c^i$

思路

当时 FST 了

思路上是对的，小部分跑暴力，大部分的可以直接当 $c=1$

Code

// Woshiluo<[email protected]>
// 2020/08/30 22:43:38
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>

template <class T>
T Max( T a, T b ) { return a > b? a: b; }
template <class T>
T Min( T a, T b ) { return a < b? a: b; }
template <class T>
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T>
void chk_Min( T &a, T b ) { if( b < a ) a = b; }
template <class T>
T aabs( T a ) { return a < 0? -a: a; }

const int N = 1e5 + 1e4;

int n;
long long a[N];

int main() {
#ifdef woshiluo
        freopen( "b.in", "r", stdin );
        freopen( "b.out", "w", stdout );
#endif
        scanf( "%d", &n );
        for( int i = 1; i <= n; i ++ ) {
                scanf( "%lld", &a[i] );
        }
        bool flag = true;
        const long long MAX = 1e18;
        long long ans = (long long)(1e18);
        std::sort( a + 1, a + n + 1 );

        for( int c = 1; c <= 100000; c ++ ) {
                long long tmp = 1, res = 0;
                for( int i = 1; i <= n; i ++ ) {
                        if( tmp >= MAX ) {
                                flag = false;
                                break;
                        }
                        res += aabs( tmp - a[i] );
                        tmp *= 1LL * c;
                }
                if( flag ) {
                        ans = Min( ans, res );
                }
        }
        printf( "%lld\n", ans );
}

C Multiples of Length

题目大意

给定一个序列，允许你做三次操作，使得序列全部变成 $0$

每次操作选择一段长度为 $k$ 的序列，将其中每一个可以增加 $k*a(a \in Z 且 a \in [-10^{18},10^{18}])$

输出任意方案

思路

$ax + by = \gcd(a,b)$ 显然是有解的

也就是只要我们令 $\gcd(a,b) = 1$ 也就是 $a,b$ 互质，对于任意 $ax + by = c (a,b,c \in Z)$ 都可以有解

那简单， $(1, n)$ 和 $(n, n – 1)$ 显然是互质的嘛

Code

// Woshiluo<[email protected]>
// 2020/08/30 23:21:14
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>

template <class T>
T Max( T a, T b ) { return a > b? a: b; }
template <class T>
T Min( T a, T b ) { return a < b? a: b; }
template <class T>
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T>
void chk_Min( T &a, T b ) { if( b < a ) a = b; }

const int N = 1e5 + 1e4;

long long n;
long long a[N];
long long fir[N], sec[N];

long long ex_gcd(long long a, long long b, long long& x, long long& y) {
        if (b == 0) {
                x = 1;
                y = 0;
                return a;
        }
        long long d = ex_gcd(b, a % b, x, y);
        long long temp = x;
        x = y;
        y = temp - a / b * y;
        return d;
}

int main() {
        scanf( "%lld", &n );
        for( int i = 1; i <= n; i ++ ) {
                scanf( "%lld", &a[i] );
        }
        long long t1 = 0, t2 = 0;
        ex_gcd( n, 1, t1, t2 );
        fir[1] = t1 * a[1];
        sec[1] = t2 * a[1];
        long long b = n - 1;
        for( int i = 2; i <= n; i ++ ) {
                long long t1 = 0, t2 = 0;
                ex_gcd( n, b, t1, t2 );
                fir[i] = t1 * a[i];
                sec[i] = t2 * a[i];
        }
        printf( "%d %lld\n", 1, n );
        for( int i = 1; i <= n; i ++ ) {
                printf( "%lld ", -fir[i] * n );
        }
        printf( "\n%d %d\n", 1, 1 );
        printf( "%lld", -sec[1] );
        if( n == 1 ) {
                printf( "\n1 1\n0" );
                return 0;
        }
        printf( "\n%d %lld\n", 2, n );
        for( int i = 2; i <= n; i ++ ) {
                printf( "%lld ", -sec[i] * b );
        }
}

D Stoned Game

题目大意

$n$ 堆石子，$2$ 个人轮流取一个石子，不能取上一个人取得堆子

第一个无石子可取的人，算输

若每个人用最优方案，谁能嬴

思路

只能取一个石子，所以并不是很博奕论

所以每个人都取当前的最大的那堆，就行了

Code

// Woshiluo<[email protected]>
// 2020/08/31 00:16:02
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <queue>
#include <algorithm>

template <class T>
T Max( T a, T b ) { return a > b? a: b; }
template <class T>
T Min( T a, T b ) { return a < b? a: b; }
template <class T>
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T>
void chk_Min( T &a, T b ) { if( b < a ) a = b; }

const int N = 110;

int T;
int n;

struct node {
        int id, val;
        bool operator< ( const node &b ) const { return val < b.val; }
};

int main() {
#ifdef woshiluo
        freopen( "d.in", "r", stdin );
        freopen( "d.out", "w", stdout );
#endif
        scanf( "%d", &T );
        while( T -- ) {
                std::priority_queue<node> q;
                scanf( "%d", &n );
                for( int i = 1, tmp; i <= n; i ++ ) {
                        scanf( "%d", &tmp );
                        q.push((node){ i, tmp });
                }
                int lst = 0;
                bool fir = true;
                while( !q.empty() ) {
                        node top = q.top(); q.pop();
                        if( top.id == lst ) {
                                if( q.empty() )
                                        break;
                                node top2 = q.top(); q.pop();
                                top2.val --; lst = top2.id; fir ^= 1;
                                if( top2.val != 0 )
                                        q.push(top2);
                                q.push(top);
                        }
                        else {
                                top.val --; lst = top.id; fir ^= 1;
                                if( top.val != 0 )
                                        q.push(top);
                        }
                }
                printf( "%s\n", fir? "HL": "T" );
        }
}

E Monster Invaders

题目大意

这题面巨长

一个游戏，$n$ 关，每关 $n$ 个小怪，$1$ 个 boss

小怪 1 格血，boss 一个

三种武器

  • 手枪，费用 $r_1$, 对特定人减一格血
  • 散弹枪，费用 $r_2$，对所有人减一格血
  • AWP，费用 $r_3$，杀死特定人

从当前关到相邻关卡，费用为 $d$

在所有小兵死亡之前，不能使用 手枪/AWP 来攻击 Boss

一旦攻击 Boss，必须前往相邻关卡

求杀死所有 Boss 所需的最少时间

思路

首先可以发现，杀死这一关的 Boss 有两种方法

  1. 挨个杀死小兵，最后一枪给 Boss 送死
  2. 对每个人减一格血，去别的地方再回来给 Boss 来一枪

然后就是大力 dp 了

  • $f_{i,0}$ 是当前不需要往回走
  • $f_{i,1}$ 是当时需要往回走

注意到 $f_{i,1}$ 是同一条路需要走三次（过去，回来，再过去）

但是有一种情况，你可以走到最后，回来，但是不需要再回去了

这种情况特判就可以了

Code

// Woshiluo<[email protected]>
// 2020/09/01 00:31:59
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>

template <class T>
T Max( T a, T b ) { return a > b? a: b; }
template <class T>
T Min( T a, T b ) { return a < b? a: b; }
template <class T>
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T>
void chk_Min( T &a, T b ) { if( b < a ) a = b; }

const int N = 1e6 + 1e5;

long long n, r1, r2, r3, d;
long long a[N], b[N], c[N];
long long f[N][3];
// b[] / 0 => kill all in once
// c[] / 1 => kill all in twice

int main() {
#ifdef woshiluo
        freopen( "e.in", "r", stdin );
        freopen( "e.out", "w", stdout );
#endif
        scanf( "%lld%lld%lld%lld%lld", &n, &r1, &r2, &r3, &d );
        long long min_3 = Min( r1, Min( r2, r3 ) );
        for( long long i = 1; i <= n; i ++)  {
                scanf( "%lld", &a[i] );
                b[i] = a[i] * Min( r1, r3 ) + r3;
                c[i] = Min( r2 + min_3, Min( r1, r3 ) * a[i] + Min( r1, r2 ) * 2LL );
        }
        f[0][1] = f[0][2] = (long long)(1e18);
        for( long long i = 1; i <= n; i ++ ) {
                f[i][0] = Min( f[ i - 1 ][0] + b[i], f[ i - 1 ][1] + Min( b[i], c[i] ) ) + d;
                f[i][1] = Min( f[ i - 1 ][0] + c[i], f[ i - 1 ][1] + Min( b[i], c[i] ) ) + 3LL * d;
                f[i][2] = Min( f[ i - 1 ][0] + c[i], f[ i - 1 ][2] + Min( b[i], c[i] ) ) + 2LL * d;
        }

        printf( "%lld\n", Min( f[n - 1][2] + b[n],
                                Min( f[n][0] - d, f[ n - 1 ][0] + c[n] + 2LL * d ) ) );
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

message
account_circle
Please input name.
email
Please input email address.
links

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。