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

发布于 # algorithm

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

A Two Regular Polygons

1 题目大意

给你两个正多边形，一个 nn 条边 AA ，一个 mm 条边 BB

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

有输出 YES ，否则输出 NO

2 Code

判 n mod m=0n \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 题目大意

给你一个长度为 nn 的序列 aa, 你可以将 aa 重新排序，使其满足 j−aj≠i−aij - a_j \neq i - a_i

输出任何一个即可

保证有解

n≤100n \leq 100

2 思路

j−aj≠i−aij−i≠aj−ai\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 题目大意

给你两个长度为 nn 的数列 a,va,v

其中 aa 通过输入提供，vv 初始所有值为 00

接下来，对于第 ii 次操作（从 00 计数），你可以

  • 选择任意一个 viv_i 增加 kik^i
  • 什么都不做

问你是否通过多次操作后，使 vv 变成 aa

能输出 YES ，否则输出 NO

2 思路

首先对于每个数字 aa, 考虑其是否可以变成多个 kik^i 的和（不能有重复的 ii）

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

不能的话直接没有可能

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 题目大意

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

  • 有 nn 个元素
  • 每个数字都是 11 到 mm 之间的整数
  • 只有恰好一对数字相等
  • 数列先严格递增，再严格递减

个数对 998244353998244353 取模后输出

2≤n≤m≤2×1052 \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 题目大意

这好像是个原题

给你一个长度为 nn 的数列 aa

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

问最小数列长度

1≤ai≤1000,1≤n≤5001 \leq a_i \leq 1000, 1 \leq n \leq 500

2 思路

区间 dp

设 fi,jf_{i,j} 为 ii 到 jj 最小长度

mergedi,jmerged_{i,j} 为 ii 到 jj 合并出来的数字

然后就是标准板子了

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] );
}

AGC 034 F RNG and XOR

发布于 # algorithm

题目连接: https://atcoder.jp/contests/agc034/tasks/agc034_f

道理我都懂，可是不看题解不到啊……

\newcommand \xor{\mathbin{\mathbf{xor}}}

1 题意

给定一个数字 nn

对于 0⋯2n−10 \cdots 2^n - 1 中每个数字都有一个 aia_i

现在有一个数 XX, 一开始为 00

每一次操作会随机选择一个数字 ii （其中 0≤i≤2n−10 \leq i \leq 2^n - 1，选中 ii 的概率为 ai∑a\frac{a_i}{\sum a}）

然后令 X=X⊕iX = X \oplus i

问使 X=iX=i 的期望次数

2 思路

先令 pi=ai∑ap_i=\frac{a_i}{\sum a}

令 fif_i 表示从 ii 到 00 的期望次数，这和从 00 到 ii 显然是一样的

接着有一个非常显然的式子

fi=fi\xorj×pj+1(i≠0)fi−1=fi\xorj×pj(i≠0)\begin{aligned} f_i &= f_{i \xor j} \times p_j + 1 ( i \neq 0 )\\ f_i - 1 &= f_{i \xor j } \times p_j ( i \neq 0 ) \end{aligned}

然后我们就可以得到这个式子

(f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \oplus (p_0, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\ \= ( x, f_1 - 1, f_2 - 1, \cdots, f_{2^{n-1}} - 1, f_{2^n-1} - 1 )

但是 xx 是未知的

注意到 ∑p=1\sum p = 1 所以左边右边的和是相等的

所以

x=∑i=02n−1fi−∑i=12n−1fi−1=f0+2n−1\begin{aligned} x &= \sum_{i=0}^{2^n-1} f_i - \sum_{i=1}^{2^n-1} f_i - 1 \\ &= f_0 + 2^n - 1 \end{aligned} (f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \oplus (p_0, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\ \= ( f_0 + 2^n - 1, f_1 - 1, f_2 - 1, \cdots, f_{2^{n-1}} - 1, f_{2^n-1} -1 )

我们需要的使其中两个式子没有未知数

注意到如果使 p0=p0−1p_0 = p_0 - 1

那么右边每一个数都会减去 fif_i

即

(f0,f1,f2,⋯ ,f2n−1,f2n−1)⊕(p0−1,p1,p2,…,p2n−1,p2n)=(2n−1,−1,−1,⋯ ,−1,−1)(f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \oplus (p_0 - 1, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\ = ( 2^n - 1, - 1, - 1, \cdots, -1, -1 )

于是就可以放进 FWT 里直接做

然后你就发现这东西跑出来是错的……

为什么呢

令

P=(p0−1,p1,p2,…,p2n−1,p2n)A=(2n−1,−1,−1,⋯ ,−1,−1)\begin{aligned} \mathbf{P} & = (p_0 - 1, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\ \mathbf{A} & = ( 2^n - 1, - 1, - 1, \cdots, -1, -1 ) \end{aligned}

因为 P\mathbf{P} 和 A\mathbf{A} FWT 后第一位都是 00

没有办法倒推出来 f0f_0

但是可以发现 ff 的值是可以平移的

即

fi+k=∑i=02n−1pj(fi⊕j+k)+1=∑i=02n−1fi⊕j×pj+k+1f_i + k = \sum_{i=0}^{2^n-1} p_j(f_{i \oplus j} + k) + 1 = \sum_{i=0}^{2^n-1} f_{i \oplus j} \times p_j + k + 1

那么我们又知道 fi=0f_i = 0

所以将 ff 每一位都减去 f0f_0 即可

3 Code

#include <cstdio>

const int N = 1 << 20;
const int mod = 998244353;

int n;
int a[N], b[N], p[N], sum;

inline i
nt 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 inv( int a ) { return ksm( a, mod - 2 ); }

void XOR( int *f, int len, int x = 1 ) {
    for( int o = 2, k = 1; o <= len; o <<= 1, k <<= 1 ) {
        for( int i = 0; i < len; i += o ) {
            for( int j = 0; j < k; j ++ ) {
                add_eq( f[ i + j ], f[ i + j + k ] );
                f[ i + j + k ] = add( f[ i + j ], add( - f[ i + j + k ], - f[ i + j + k ] ) );
                mul_eq( f[ i + j ], x ); mul_eq( f[ i + j + k ], x );
            }
        }
    }
}

int main() {
#ifdef woshiluo
    freopen( "F.in", "r", stdin );
    freopen( "F.out", "w", stdout );
#endif
    scanf( "%d", &n );
    n = 1 << n;
    for( int i = 0; i < n; i ++ ) {
        scanf( "%d", &a[i] );
        sum += a[i];
        b[i] = mod - 1;
    }
    sum = inv(sum);
    for( int i = 0; i < n; i ++ ) {
        p[i] = mul( a[i], sum );
    }

    b[0] = n - 1; p[0] -= 1;
    XOR( b, n ); XOR( p, n );
    for( int i = 0; i < n; i ++ ){
        mul_eq( b[i], inv( p[i] ) );
    }
    XOR( b, n, inv(2) );
    for( int i = 0; i < n; i ++ ) {
        printf( "%d\n", ( ( add( b[i], -b[0] ) + mod ) % mod ) );
    }
}

将 Bilibili 缓存转换成视频

发布于 # share

0 环境 & 提示

  • 电脑
    • PHP
    • Bash
  • 手机
    • Bilibili 国内版 5.54.0

这样子转换出来还是有水印的，请不要在未经 UP 主同意的情况下传播或用在非法行为

1 过程

因为要备份手机，就想着能不能把 Bilbili 的缓存转换成普通视频留在电脑上

然后看了一下下载目录，里面有一个 video.m4s 和 audio.m4s

拿 mpv 一打开，发现刚好一个是视频一个是音频...

剩下的事情就是拿 ffmpeg 合并一下的事情...

随便胡个脚本就行了

2 脚本

covert.sh
# Author: Woshiluo<[email protected]>
#!/bin/bash

work_dir=`pwd`;
fa_php=`pwd`"/fa.php";
part_php=`pwd`"/part.php";

echo $part_php;
mkdir -p "$work_dir/output"

function covert() {
	cp "$fa_php" ./
	cp "$part_php" ./
	fa=`php fa.php`
	part=`php part.php`
	echo "[INFO] Coverting $fa $part..."
	rm fa.php part.php
	mkdir -p "$work_dir/output/$fa"
	for file in `ls`; do
		if [ -d $file ]; then
			cd $file
			ffmpeg -i video.m4s -i audio.m4s -c copy "$work_dir/output/$fa/$part.mkv" -y >/dev/null 2>&1
			cd ..
		fi
	done
	echo "[INFO] Done!"
}

for file in `ls`; do
	if [ -d $file ] && [ $file != "output" ]; then
		cd ./$file
		for video in `ls`; do
			if [ -d $video ]; then
				cd ./$video
				covert
				cd ..
			fi
		done
		cd ..
	fi
done
fa.php
<?php

$_file = file_get_contents( "./entry.json" );

$desc = json_decode( $_file );

echo $desc -> title;
part.php
<?php

$_file = file_get_contents( "./entry.json" );

$desc = json_decode( $_file );

echo $desc -> page_data -> part;

随便胡的脚本

把这三个文件放到 Bilibili 的下载目录下，然后执行 covert.sh 就行了

执行过后转换过的文件会在 output 目录下

Atcoder ARC 103 F Distance Sums

发布于 # algorithm

0 写在之前

这几天写的题目并不算少

然而这道题是唯一一个看过去傻了的题目...

应该以前听过，题面看着眼熟

可是死活不会做...

1 思路

基本上可以明确是到构造题

这里依赖两个性质：

树的中心的 DD 值是最小的

D(fa) = D(x) - n + 2 \times size\[i\]

这个就是标准的树和树的重心的性质

可以推出来如果以重心做根，那么 DD 越大越在下面

所以尝试生成一颗以重心为根的树就行了

然后我发现我不会判否

结果发现最后生成出来树判断一次就行了...

2 实现

读入 DD 排序

从大到小依此根据上面的式子找父亲

最后判断一下是否正确就可以了

3 Code

// User: woshiluo
// Email: [email protected]
// Problem link: https://atcoder.jp/contests/arc103/tasks/arc103_d
// Comment:
// Why the problem id is 'F', but the link is 'arc103_d'
// Interesting

#include <cstdio>
#include <cstdlib>

#include <map>
#include <algorithm>

const int N = 1e5 + 1e3;

int n;
int size[N], father[N];

struct node{
	int id;
	long long d;
} a[N];

std::map<long long, int> mp;

void wrong() {
	printf( "-1\n" );
	exit(0);
}
bool cmp( node _a, node _b ) { return _a.d < _b.d; }

int main() {
#ifdef woshiluo
	freopen( "F.in", "r", stdin );
	freopen( "F.out", "w", stdout );
#endif
	scanf( "%d", &n );
	for( int i = 1; i <= n; i ++ ) {
		scanf( "%lld", &a[i].d );
		a[i].id = i;
		size[i] = 1;
		mp[ a[i].d ] = i;
	}
	std::sort( a + 1, a + n + 1, cmp );
	int rt_d, rt;
	rt = a[1].id; rt_d = a[1].d;
	for( int i = n; i > 1; i -- ) {
		int fa = mp[ a[i].d + 2LL * size[ a[i].id ] - n ];
		if( fa == 0 ) {
			wrong();
			return 0;
		}
		size[fa] += size[ a[i].id ];
		father[ a[i].id ] = fa;
	}
	for( int i = 1; i <= n; i ++ ) {
		if( i == rt )
			continue;
		 rt_d -= size[i];
	}
	if( rt_d != 0 )
		wrong();

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

HDU 4507 恨7不成妻

发布于 # algorithm

思路

裸的要死的数位 DP 题目

一眼看过去，平方和，有点懵

但是维护平方和也是老套路了

维护 sumsum, cntcnt, powsumpow_sum 就可以了

代码

代码写的着急，会有一些不太好看

#include <cstdio>

const int mod = 1e9 + 7;

inline int add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline int power( int a ) { return mul( a, a ); }

int T, max_len;
long long left, rig;
int _count[110][2][10][10][10], _sum[110][2][10][10][10], _pow[110][2][10][10][10];
int max_count[110][2][10][10][10], max_sum[110][2][10][10][10], max_pow[110][2][10][10][10];
bool _vis[110][2][10][10][10];
int a[110];

inline int length( int cur, int len ) {
	int res = cur;
	while( len > 0 ) {
		res = mul( 10, res );
		len --;
	}
	return res;
}

struct node {
	int len, cur, seven, rem, base_rem;
	bool max;
	int& count() {
		if( max )
			return max_count[len][seven][rem][cur][base_rem];
		return _count[len][seven][rem][cur][base_rem];
	}
	int& sum() {
		if( max )
			return max_sum[len][seven][rem][cur][base_rem];
		return _sum[len][seven][rem][cur][base_rem];
	}
	int& pow() {
		if( max )
			return max_pow[len][seven][rem][cur][base_rem];
		return _pow[len][seven][rem][cur][base_rem];
	}
	bool& vis() {
		return _vis[len][seven][rem][cur][base_rem];
	}
	void print() {
//		printf( "%d %d %d %d %d %d\n", len, cur, seven, rem, base_rem, max );
//		printf( "%d %d %d\n", count(), sum(), pow() );
	}
};

int dfs( node cur ) {
	if( ( ! cur.max ) && cur.vis() )
		return cur.pow();
	if( cur.len == 0 ) {
		if( cur.seven || cur.rem == 0 || cur.base_rem == 0 ) {
			cur.count() = cur.sum() = cur.pow() = 0;
			return cur.pow();
		}
		cur.count() = 1; cur.sum() = cur.cur; cur.pow() = power( cur.cur );
		return cur.pow();
	}
	int &cur_count = cur.count();
	int &cur_sum = cur.sum();
	int &cur_pow = cur.pow();
	if( cur.max )
		cur_count = cur_sum = cur_pow = 0;
	for( int i = 0; i <= ( cur.max? a[cur.len]: 9 ); i ++ ) {
		node nxt = cur;
		nxt.len -= 1; nxt.seven = ( cur.seven || ( i == 7 ) ); nxt.cur = i; nxt.max = ( cur.max && i == a[cur.len] );
		nxt.rem = ( cur.rem * 10 + i ) % 7; nxt.base_rem = ( cur.base_rem + i ) % 7;
		dfs( nxt );
		cur_count = add( cur_count, nxt.count() );
		cur_sum = add( cur_sum, add( mul( length( cur.cur, cur.len ), nxt.count() ), nxt.sum() ) );
		cur_pow = add( cur_pow, add( nxt.pow(), add( mul( nxt.count(), power( length( cur.cur, cur.len ) ) ),
						mul( mul( 2, length( cur.cur, cur.len ) ), nxt.sum() ) ) ) );
	}
	if( cur.max == false )
		cur.vis() = true;
	cur.print();
	return cur_pow;
}

int sum( long long _a ) {
	if( _a == 0 )
		return 0;
	if( _a < 0 )
		return 0;
	max_len = 0;
	while( _a ) {
		a[ ++ max_len ] = _a % 10;
		_a /= 10;
	}
//	printf( "ans: %d\n", dfs( (node){ max_len, 0, 0, 0, 0, true } ) );
	return dfs( (node){ max_len, 0, 0, 0, 0, true } );
}

int main() {
#ifdef woshiluo
	freopen( "hdu.4507.in", "r", stdin );
	freopen( "hdu.4507.out", "w", stdout );
#endif
	scanf( "%d", &T );
	while( T -- ) {
		scanf( "%lld%lld", &left, &rig );
		if( left == 0 )
			printf( "%d\n", ( sum(rig) + mod ) % mod );
		else
			printf( "%d\n", ( add( sum(rig), - sum( left - 1 ) ) + mod ) % mod );
	}
}

Woshiluo's NoteBook

「Jump up HIGH!!」