Codeforces Round 1467 题目大意 & 解题报告

Codeforces Round #695 (Div. 2)

许久不打变得更菜了…

A. Wizard of Orz

0 大意

给定 $n$ 个板子,每个板子上有一个相同的数字 $x ( 0 \leq x \leq 9 )$

随机选择一个数字 $y(1 \leq y \leq n)$,令板子 $i$ 上的数字变成 $ x + |y – i| \pmod 10$

1 Code

显然,输出 $98\{987654321\}$ 的前 $n$ 位即可

#include <cstdio>

int main() {
	int T;
	scanf( "%d", &T );
	while( T -- ) {
		int n;
		scanf( "%d", &n );
		if( n == 1 ) 
			printf( "9" );
		else {
			printf( "98" );
			int cur = 9;
			for( int i = 3; i <= n; i ++ ) {
				printf( "%d", cur );
				cur ++;
				if( cur >= 10 ) 
					cur = 0;
			}
		}
		printf( "\n" );
	}
}
Continue reading “Codeforces Round 1467 题目大意 & 解题报告”

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

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

A Juggling Letters

题目大意

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

思路

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

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

Codeforces Contest #1325 解题报告 & 题目大意

A EhAb AnD gCd

题目大意

给定一个整数 $x(2\leq x \leq 10^9)$

求 $a,b$ 满足 $\gcd(a,b) + \operatorname{lcm}(a,b) = x$

多组解输出任意一个

Code

这有啥说的,随便找个质因数让后输出 $p, x$ 就可以

// Woshiluo Luo<[email protected]>
// 2020/03/14 22:36:48

#include <cmath>
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

int t, x;

int main() {
    scanf( "%d", &t );
    while( t -- ) {
        scanf( "%d", &x );
        int sq = std::sqrt(x) + 1;
        for( int i = 1; i <= sq; i ++ ) {
            if( x % i == 0 ) {
                int tmp = ( x / i ) - 1;
                if( tmp == 0 )
                    continue;
                printf( "%d %d\n", i, tmp * i );
                break;
            }
        }
    }
}

B CopyCopyCopyCopyCopy

题目大意

给你一个长度为 $n$ 的数列 $a$, 现在你可以复制无数个 $a$ 接到原来的数列后面

问这样接完后,最长严格上升子序列的长度

Code

因为可以接无限次,所以直接输出数字个数就可以了

// Woshiluo Luo<[email protected]>
// 2020/03/14 22:42:47
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e5 + 1e4;

int t;
int n;
int a[N];

int main() {
    scanf( "%d", &t );
    while( t -- ) {
        scanf( "%d", &n );
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%d", &a[i] );
        }
        std::sort( a + 1, a + n + 1 );
        int cnt = 0, la = 0;
        for( int i = 1; i <= n; i ++ ) {
            if( i == 1 || a[i] != la ) {
                la = a[i];
                cnt ++;
            }
        }
        printf( "%d\n", cnt );
    }
}

C Ehab and Path-etic MEXs

题目大意

给一棵节点数为 $n$ 的树

现在你要给每条边一个边权,要求:

  • 边权为一个整数 $v(0\leq v \leq n – 2)$
  • 每条边的边权不能和别的边的相同

现在定义 $MEX(u,v)$ 为 $u,v$ 之间的最短简单路径上没有出现的边权中的最小值

请给出一种边权方案,最小化 $\max{MEX(u,v)}$

思路

考虑每条边会被算进去多少次,记为每条边的贡献

贡献越大给越大的边就可以了

实际上可以更加简化,因为无论如何一定有一个 $MEX \geq 2$

所以我们尽可能避免 $0,1,2$ 出现在一条边上即可

随便找一个度数 $\geq 2$ 的点,把这三个数字放上去即可

如果没有这种点,那么怎么摆都会有一条 $MEX=n-1$ 的路径

Code

// Woshiluo Luo<[email protected]>  
// 2020/03/14 22:52:18
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e5 + 1e4;

// Edge Start
struct edge {
    int to, next, val;
} e[ N << 1 ];
int ehead[N], ecnt;
inline void add_edge( int now, int to, int val ) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    e[ecnt].val = val;
    ehead[now] = ecnt;
}
// Edge End

struct node { long long val; int id; } max[N];
bool cmp( node _a, node _b ) { return _a.val < _b.val; }

int n, x, y;
int son[N], val[N];

void dfs( int now, int la ) {
    son[now] = 1;
    for( int i = ehead[now]; i; i = e[i].next ) {
        if( e[i].to == la )
            continue;
        dfs( e[i].to, now );
        son[now] += son[ e[i].to ];
        max[ e[i].val ].val = ( 1LL * son[ e[i].to ] * ( n - son[ e[i].to ] ) );
    }
}

int main() {
#ifdef woshiluo
    freopen( "c.in", "r", stdin );
    freopen( "c.out", "w", stdout );
#endif
    scanf( "%d", &n );
    for( int i = 1, u, v; i < n; i ++ ) {
        max[i].id = i;
        scanf( "%d%d", &u, &v );
        add_edge( u, v, i );
        add_edge( v, u, i );
    }

    dfs( 1, 0 );

    std::sort( max + 1, max + n, cmp );

    for( int i = 1; i < n; i ++ ) {
        val[ max[i].id ] = i - 1;
    }

    for( int i = 1; i < n; i ++ ) {
        printf( "%d\n", val[i] );
    }
}

D Ehab the Xorcist

给定两个整数 $u,v$ 求最短的数列 $a$ 满足

  • $$ \sum a = v $$
  • xor 和为 $u$

多解输出任意一个

无解输出 $-1$

题目大意

这题感觉的 C 简单啊

满足 $xor$ 容易,满足 $v$ 的话需要难度

考虑最后 $xor$ 的结果受每个二进制位的和的奇偶性影响

因此可以确定每一位的奇偶性

然后随便搞一下满足 $v$ 就可以了

Code

// Woshiluo Luo<[email protected]>
// 2020/03/14 23:39:20
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

unsigned long long u, v;
int bit_u[110], bit_less[110], bit_cnt[110];
std::vector<unsigned long long> ans;

inline void noans() {
    printf( "-1\n" );
    exit(0);
}

void to_bit( unsigned long long a, int bit[] ) {
    int cnt = 0;
    while( a ) {
        bit[ ++ cnt ] = a & 1;
        a >>= 1;
    }
}

int main() {
    scanf( "%llu%llu", &u, &v );
    if( v < u )
        noans();

    to_bit( v - u, bit_less );
    to_bit( u, bit_u );

    for( int i = 1; i <= 100; i ++ ) {
        bit_cnt[i] = bit_u[i];
    }
    int p = 64;
    int cnt = 0;
    while( p ) {
        bit_cnt[p] += ( cnt - ( cnt & 1 ) );
        cnt = cnt & 1;
        if( bit_less[p] )
            cnt ++;
        p --; cnt <<= 1;
    }

    if( cnt != 0 )
        noans();

    bool flag = true;
    while( flag ) {
        flag = false;
        unsigned long long out = 0;
        unsigned long long p = 1;
        for( int i = 1; i <= 64; i ++, p <<= 1 ) {
            if( bit_cnt[i] ) {
                out = out | p;
                bit_cnt[i] --;
                flag = true;
            }
        }
        if( flag )
            ans.push_back(out);
    }

    cnt = ans.size();
    printf( "%d\n", cnt );
    for( int i = 0; i < cnt; i ++ ) {
        printf( "%llu ", ans[i] );
    }

}

E Ehab’s REAL Number Theory Problem

题目大意

给你一个长度为 $n$ 的数列,保证数列中每个数字有不超过 $7$ 个因数

请求出最短的子序列,使子序列成绩为完全平方数

思路

这题比 F 题难吧…

首先由 保证数列中每个数字有不超过 $7$ 个因数 得每个数不会有超过两个 $1$ 和其本身以外的质因数

然后我们可以先把每个数里的完全平方数因子先除掉,因为这些不会对答案造成影响

这样下来每个数的因子只有 1 和其本身以及两个质因数(前提是这个数不是质数)

然后建图,如果这个数是质数,将其和 $1$ 连接,如过不是将其的两个质因数连接

剩下就是求最小环

Code

// Woshiluo Luo<[email protected]>
// 2020/03/15 22:08:53

#include <cmath>
#include <cstdio>
#include <cstring>

#include <queue>
#include <vector>
#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e6 + 1e4;
const int M = 1100;
const int INF = 0x3f3f3f3f;

int n, ans = INF;
int dis[N], fa[N];
bool marked[N], pool[N];

// Edge Start
struct edge {
    int cur, to, next;
} e[ N << 1 ];
int ehead[N], ecnt = 1;
inline void add_edge( int now, int to ) {
    ecnt ++;
    e[ecnt].cur = now;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// Edge End

int bfs( int st ) {
    memset( dis, INF, sizeof(dis) );
    memset( fa, 0, sizeof(fa) );
    std::queue<int> q;
    q.push(st); dis[st] = 0;
    while( !q.empty() ) {
        int cur = q.front(); q.pop();
        for( int i = ehead[cur]; i; i = e[i].next ) {
            if( e[i].to == fa[cur] )
                continue;

            if( dis[ e[i].to ] >= INF ) {
                fa[ e[i].to ] = cur;
                dis[ e[i].to ] = dis[cur] + 1;
                q.push( e[i].to );
            }
            else {
                return dis[cur] + dis[ e[i].to ] + 1;
            }
        }
    }
    return INF;
}

int main() {
    scanf( "%d", &n );
    for( int i = 1, x; i <= n; i ++ ) {
        scanf( "%d", &x );
        std::vector<int> a;
        int cnt = std::sqrt(x) + 1;
        while(cnt > 1) {
            int cnt_pow = cnt * cnt;
            while( x % cnt_pow == 0 )
                x /= cnt_pow;
            cnt --;
        }
        if( x == 1 )
            chk_Min( ans, 1 );
        if( pool[x] )
            chk_Min( ans, 2 );
        pool[x] = true;
        int tmp = std::sqrt(x);
        for( int j = 2; j <= tmp; j ++ ) {
            if( x % j == 0 ) {
                a.push_back(j);
                a.push_back( x / j );
                break;
            }
        }
        if( a.size() == 0 ) {
            add_edge( 1, x );
            add_edge( x, 1 );
        }
        else if( a.size() != 0 ) {
            add_edge( a[0], a[1] );
            add_edge( a[1], a[0] );
        }
    }

    if( ans != INF ) {
        printf( "%d\n", ans );
        return 0;
    }

    for( int i = 1; i <= 1000; i ++ ) {
        if( ehead[i] )
            chk_Min( ans, bfs(i) );
    }

    if( ans >= INF )
        ans = -1;

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

F Ehab’s Last Theorem

题目大意

给定一个 $n$ 个节点的图

令 $glo=\lceil\sqrt{n}\rceil$

你要么找到一个长度和 $glo$ 相等的环

要么找到一个比 $glo$ 小的独立集

Code

先试图找环,找不到肯定有独立集

// Woshiluo Luo<[email protected]>  
// 2020/03/15 15:49:32
#include <cstdio>
#include <cstring>

#include <stack>
#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e5 + 1e4;
const int M = 2e5 + 1e4;

int n, m, need;

int dep[N];
bool vis[N];
std::stack<int> st;

// Edge Start
struct edge { int to, next; } e[ M << 1 ];
int ehead[N], ecnt;
inline void add_edge( int now, int to ) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// Edge End


void dfs( int now ) {
    st.push(now);
    dep[now] = st.size();
    for( int i = ehead[now]; i; i = e[i].next ) {
        if( dep[ e[i].to ] == 0 )
            dfs( e[i].to );
        else if( dep[now] - dep[ e[i].to ] + 1 >= need ) {
            int size = dep[now] - dep[ e[i].to ] + 1;
            printf( "%d\n%d\n", 2, size );
            for( int i = 1; i <= size; i ++ ) {
                printf( "%d ", st.top() );
                st.pop();
            }
            exit(0);
        }
    }
    if( !vis[now] ) {
        for( int i = ehead[now]; i; i = e[i].next ) {
            vis[ e[i].to ] = true;
        }
    }
    st.pop();
}

int main() {
#ifdef woshiluo
    freopen( "f.in", "r", stdin );
    freopen( "f.out", "w", stdout );
#endif
    scanf( "%d%d", &n, &m );
    while( need * need < n )
        need ++;

    while( m -- ) {
        int u, v;
        scanf( "%d%d", &u, &v );
        add_edge( u, v ); add_edge( v, u );
    }

    dfs(1);

    printf( "%d\n", 1 );
    int cnt = 0;
    for( int i = 1; i <= n; i ++ ) {
        if( vis[i] == false ) {
            printf( "%d ", i );
            cnt ++;
        }
        if( cnt == need )
            break;
    }
}

Codeforces Contest #1312 解题报告 & 部分翻译

比赛链接:Educational Codeforces Round 83 (Rated for Div. 2)

A Two Regular Polygons

1 题目大意

给你两个正多边形,一个 $n$ 条边 $A$ ,一个 $m$ 条边 $B$

问 $B$ 有没有可能被 $A$ 包含且所有顶点都与 $A$ 的某一个节点重合

有输出 YES ,否则输出 NO

2 Code

判 $n \bmod m = 0$ 就可以了

#include <cstdio>

int T;
int n, m;

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d%d", &n, &m );
        printf( "%s\n", ( n % m == 0 )? "YES": "NO" );
    }
}

B Bogosort

1 题目大意

给你一个长度为 $n$ 的序列 $a$, 你可以将 $a$ 重新排序,使其满足 $j – a_j \neq i – a_i$

输出任何一个即可

保证有解

$n \leq 100$

2 思路

$$
\begin{aligned}
j – a_j & \neq i – a_i \\
j – i & \neq a_j – a_i
\end{aligned}
$$

直接从大到小输出

3 Code

// Woshiluo Luo<[email protected]>  
// 2020/03/09 22:40:32 
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 110;

int T;
int n;
int a[N];

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d", &n );
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%d", &a[i] );
        }
        std::sort( a + 1, a + n + 1 );
        for( int i = n; i >= 1; i -- ) {
            printf( "%d ", a[i] );
        }
        printf( "\n" );
    }
}

C Adding Powers

1 题目大意

给你两个长度为 $n$ 的数列 $a,v$

其中 $a$ 通过输入提供,$v$ 初始所有值为 $0$

接下来,对于第 $i$ 次操作(从 $0$ 计数),你可以

  • 选择任意一个 $v_i$ 增加 $k^i$
  • 什么都不做

问你是否通过多次操作后,使 $v$ 变成 $a$

能输出 YES ,否则输出 NO

2 思路

首先对于每个数字 $a$, 考虑其是否可以变成多个 $k^i$ 的和(不能有重复的 $i$)

能的话算出来,看看有没有和之前重复的,有就不可能

不能的话直接没有可能

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/09 22:58:45
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 110;

int T;
int n;
long long k;
bool vis[N];
long long a[N];

inline void wrong() {
    printf( "NO\n" );
}

inline void right() {
    printf( "YES\n" );
}

void calc() {
    for( int i = 1; i <= n; i ++ ) {
        if( a[i] == 0 ) {
            continue;
        }
        long long cur = a[i];
        int cnt = 1;
        while( cur ) {
            int tmp = cur % k;
            if( tmp > 1 ) {
                wrong();
                return ;
            }
            if( tmp == 1 ) {
                if( vis[cnt] == false )
                    vis[cnt] = true;
                else {
                    wrong();
                    return ;
                }
            }
            cur /= k;
            cnt ++;
        }
    }
    right();
}

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        memset( vis, 0, sizeof(vis) );

        scanf( "%d%lld", &n, &k );
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%lld", &a[i] );
        }

        calc();
    }
}

D Count the Arrays

1 题目大意

你需要寻找这样的数列个数

  • 有 $n$ 个元素
  • 每个数字都是 $1$ 到 $m$ 之间的整数
  • 只有恰好一对数字相等
  • 数列先严格递增,再严格递减

个数对 $998244353$ 取模后输出

$2 \leq n \leq m \leq 2 \times 10^5$

2 思路

式子题,看 Code 去

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/09 23:21:18
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 2e5 + 1e4;
const int mod = 998244353;

inline int add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline void add_eq( int &a, int b ) { a = ( a + b ) % mod; }
inline void mul_eq( int &a, int b ) { a = ( 1LL * a * b ) % mod; }

int ksm( int a, int p ) {
    int res = 1;
    while(p) {
        if( p & 1 )
            res = mul( res, a );
        a = mul( a, a );
        p >>= 1;
    }
    return res;
}

inline int get_inv( int a ) { return ksm( a, mod - 2 ); }

int n, m, sum, ans;
int fact[N], inv[N];

void init() {
    fact[1] = 1;
    for( int i = 2; i <= m; i ++ ) {
        fact[i] = mul( fact[ i - 1 ], i );
    }
    inv[m] = get_inv( fact[m] );
    for( int i = m - 1; i >= 1; i -- ) {
        inv[i] = mul( inv[ i + 1 ], i + 1 );
    }
    inv[0] = 1;
    fact[0] = 1;
}

// Get C^a_b
inline int C( int a, int b ) {
    if( a <= 0 )
        return 1;
    if( b <= 0 )
        return 1;
    return mul( mul( fact[b], inv[ b - a ] ), inv[a] );
}

int main() {
#ifdef woshiluo
    freopen( "d.in", "r", stdin );
    freopen( "d.out", "w", stdout );
#endif
    scanf( "%d%d", &n, &m );
    init();

    for( int i = n - 1; i <= m; i ++ ) {
        add_eq( sum, mul( C( n - 3, i - 2 ), mul( m - i + 1, n - 2 ) ) );
    }

    for( int i = 2; i < n; i ++ ) {
        add_eq( ans, mul( sum, C( i - 2, n - 3 ) ) );
    }

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

E Array Shrinking

1 题目大意

这好像是个原题

给你一个长度为 $n$ 的数列 $a$

如果 $a_i = a_{i + 1}$, 那么这两个数可以合并成 $a_i + 1$

问最小数列长度

$1 \leq a_i \leq 1000, 1 \leq n \leq 500$

2 思路

区间 dp

设 $f_{i,j}$ 为 $i$ 到 $j$ 最小长度

$merged_{i,j}$ 为 $i$ 到 $j$ 合并出来的数字

然后就是标准板子了

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/10 15:50:48
#include <cstdio>
#include <cstring>

#include <algorithm>

const int N = 510;

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

int n;
int a[N];
int f[N][N], merged[N][N];

int main() {
#ifdef woshiluo
    freopen( "e.in", "r", stdin );
    freopen( "e.out", "w", stdout );
#endif
    scanf( "%d", &n );
    for( int i = 1; i <= n; i ++ ) {
        scanf( "%d", &a[i] );
        f[i][i] = 1;
        merged[i][i] = a[i];
    }
    for( int len = 2; len <= n; len ++ ) {
        for( int left = 1, rig = len; rig <= n; left ++, rig ++ ) {
            f[left][rig] = rig - left + 1;
            for( int mid = left; mid < rig; mid ++ ) {
                int &f_left = f[left][mid], &f_rig = f[ mid + 1 ][rig],
                &merge_left = merged[left][mid], &merge_rig = merged[ mid + 1 ][rig];
                chk_Min( f[left][rig], f_left + f_rig );
                if( f_left == 1 && f_rig == 1 && merge_left == merge_rig ) {
                    f[left][rig] = 1;
                    merged[left][rig] = merge_left + 1;
                }
            }
        }
    }
    printf( "%d\n", f[1][n] );
}

Codeforces Round #530 (Div. 2) 解题报告

A

题目大意: 有一个高h重w的雪球从山上滚下来,每下降一米,重量+=高度,中间会碰到两个石头,碰到后雪球减去石头的重量,问到达高度为 0 是重量为多少

小于0则看做0

模拟题……

#include <cstdio>
int w,h;
int u1,u2,d1,d2;
int main(){
    scanf("%d%d%d%d%d%d",&w,&h,&u1,&d1,&u2,&d2);
    while(h){
        w+=h;
        if(h==d1) w-=u1;
        if(h==d2) w-=u2;
        if(w<0) w=0;
        h--;
    }
    printf("%d",w);
}

B

现在需要画$n$个正方形,问最少需要几个单位线段可以保证画出来的$n$个正方形的每条边都可以通过已有线段平行得到

贪心就对了

#include <cstdio>
#include <cmath>
int n,tmp,ans;
int main(){
    scanf("%d",&n);
    tmp=std::sqrt(n);
    if(n%tmp==0){
        printf("%d",tmp+(n/tmp));
        return 0;
    }
    else {
        ans=tmp+(n/tmp);
        printf("%d",ans+1);
    }
}

C

给你一个字符串,如果一个字母后跟的是*表示这个字母可以被删除,保留或重复多次,如果跟的是?表示这个字母可以被删除或者保留,如果都不是,则表明其必须留在原位置

贪心题目,比较原字符串长度与要求的长度,然后分段讨论

#include <cstdio>
#include <cstring>
int k,len,zlen,sfcnt,tmp;
bool sf,cd;
char s[1000];
int main(){
    scanf("%s",s+1);
    scanf("%d",&k);
    len=strlen(s+1);
    for(int i=1;i<=len;i++){
        if(s[i]>='a'&&s[i]<='z')
            zlen++;
        if(s[i]=='?') sfcnt++;
        if(s[i]=='*') {cd=true;sfcnt++;}
    }
    if(zlen>k){
        if(sfcnt<zlen-k){
            printf("Impossible");
            return 0;
        }
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            if(s[i+1]=='?'||s[i+1]=='*'){
                if(zlen>k) {zlen--;sfcnt--;}
                else printf("%c",s[i]);
            }
            else printf("%c",s[i]);
        }
    }
    else if(zlen==k){
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            else printf("%c",s[i]);
        }
    }
    else if(zlen<k){
        if(!cd){
            printf("Impossible");
            return 0;
        }
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            else if(s[i+1]=='*'){
                printf("%c",s[i]);
                while(1){
                   if(zlen>=k) break;
                   printf("%c",s[i]);
                   zlen++;
                }
            }
            else printf("%c",s[i]);
        }
    }
}

D

现在已知树的形态与奇数深度点到根的长度(最短路径所经过的边的边权和)

因为交叉未知……所以直接贪心!!!

#include <cstdio>
#include <cstdlib>
inline int Min(int a,int b){return a<b?a:b;}
const int N=1e5+2e4;
const int INF=2147483640;
int n,v;
long long sum=0;
int s[N],a[N],son[N];
// edge start
struct edge{
    int to,next;
}e[N<<1];
int ehead[N],ecnt;
inline void add_edge(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
void dfs(int now,int val){
    if(s[now]<=-1){
        int tmp=INF;
        for(int i=ehead[now];i;i=e[i].next){
            tmp=Min(s[e[i].to],tmp);
        }
        if(tmp==INF) return ;
        tmp-=val;a[now]=tmp;
        for(int i=ehead[now];i;i=e[i].next){
            s[e[i].to]-=val+a[now];
        }
        for(int i=ehead[now];i;i=e[i].next){
            dfs(e[i].to,val+a[now]);
        }
        return ;
    }
    a[now]=s[now];
    for(int i=ehead[now];i;i=e[i].next){
        dfs(e[i].to,val+a[now]);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        scanf("%d",&v);
        add_edge(v,i);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        if(s[i]!=-1&&s[i]<s[1]){
            printf("-1");
            return 0;
        }
    }
    dfs(1,0);
    sum=0;
    for(int i=1;i<=n;i++){
        if(a[i]<0){
            printf("-1");
            return 0;
        }
        sum+=a[i];
    }
    printf("%lld",sum);
}
]]>