即 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" );
}
}
B Hills And Valleys
0 大意
给定一个长度为 $n$ 的序列，对于$\forall i (1 \leq i \leq n)$，如果满足 $ a_i < a_{i-1},a_i < a_{i+1} $ 或 $ a_i > a_{i-1}, a_i > a_{i+1} $ 则对答案贡献 $1$
现在，你可以随意修改仅 $1$ 个数字，求最小的贡献和
1 思路
对于 $i$, 我们令 $max = \max( a_{i+1}, a{i-1} ), min = \min( a_{i+1}, a{i-1} )$
则显然只有 $ a_i = \{ max – 1, max, max + 1, min – 1, min, min + 1\}$ 六种值可能有不同的结果，其他值的结果会和这六个中的某一个相同。
枚举即可
2 Code
#include <cstdio>
#include <vector>
const long long INF = ( 1LL << 60LL );
const long long N = 3e5 + 1e4;
long long n;
long long a[N];
bool chk( long long cur, long long left, long long rig ) {
if( cur < left && cur < rig )
return true;
if( cur > left && cur > rig )
return true;
return false;
}
bool is_vaild( long long cur ) {
return cur > 1 && cur < n;
}
long long calc( long long cur, long long val ) {
return ( is_vaild(cur) && chk( val, a[ cur - 1 ], a[ cur + 1 ] ) )
+ ( is_vaild( cur - 1 ) && chk( a[ cur - 1 ], a[ cur - 2 ], val ) )
+ ( is_vaild( cur + 1 ) && chk( a[ cur + 1 ], val, a[ cur + 2 ] ) ) ;
}
int main() {
#ifdef woshiluo
freopen( "b.in", "r", stdin );
freopen( "b.out", "w", stdout );
#endif
long long T;
scanf( "%lld", &T );
while( T -- ) {
long long ans = INF, raw = 0;
scanf( "%lld", &n );
// Readin
for( long long i = 1; i <= n; i ++ ) {
scanf( "%lld", &a[i] );
}
a[ n + 1 ] = 0;
for( long long i = 2; i < n; i ++ ) {
if( i != 1 && i != n )
raw += chk( a[i], a[ i - 1 ], a[ i + 1 ] );
}
// Calc
for( long long i = 1; i <= n; i ++ ) {
long long min = std::min( a[ i - 1 ], a[ i + 1 ] );
long long max = std::max( a[ i - 1 ], a[ i + 1 ] );
long long res = INF;
res = std::min( res, calc( i, min - 1 ) );
res = std::min( res, calc( i, min ) );
res = std::min( res, calc( i, min + 1 ) );
res = std::min( res, calc( i, max - 1 ) );
res = std::min( res, calc( i, max ) );
res = std::min( res, calc( i, max + 1 ) );
ans = std::min( ans, raw - ( calc( i, a[i] ) - res ) );
}
printf( "%lld\n", ans );
}
}C Three Bags
1 大意
三个集合，你可以从一个集合中取出一个数 $a$,从另一个集合中取出一个数字 $b$, 将 $a-b$ 放回第一个集合
求最后剩下的数字的最大值
2 思路
将这个减少的关系建成图之后，容易发现，答案无非是两种情况
- 两个集合的和减去另一个集合的和
- 所有数字减去两个不同集合的最小数字
那么都试一下就可以
3 Code
/// Woshiluo
/// Email: woshiluo.luo [at] outlook.com
/// Blog: https://blog.woshiluo.com
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
const long long LLF = 1e18;
const int INF = 0x3f3f3f3f;
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>
void chk_Min( T &a, T b ) { if( a > b ) a = b; }
template<class T>
void chk_Max( T &a, T b ) { if( a < b ) a = b; }
int n[3];
std::vector<long long> a[3];
int main() {
scanf( "%d%d%d", &n[0], &n[1], &n[2] );
long long min = LLF, tot = 0;
for( int j = 0; j < 3; j ++ ) {
long long sum = 0;
for( int i = 1; i <= n[j]; i ++ ) {
int tmp;
scanf( "%d", &tmp );
a[j].push_back(tmp);
sum += tmp;
}
tot += sum;
chk_Min(min, sum);
std::sort(a[j].begin(), a[j].end());
}
for( int i = 0; i < 3; i ++ ) {
for( int j = i + 1; j < 3; j ++ ) {
chk_Min( min, a[i][0] + a[j][0] );
}
}
printf( "%lld\n", tot - 2LL * min );
}D Sum of Paths
1 大意
机器人可以且仅可以向左或向右走，每个点有权值，机器人可以走 $k$ 步，起点任意，求机器人所有的可能的路径的权值的和
令路径的权值为其经过所有点的点权和（如果一个点经过了多次，则多次计算）
2 思路
显然每一个点对答案造成的贡献的次数是恒定的，求出这个次数即即可
3 Code
// Woshiluo
// Email: woshiluo.luo [at] outlook.com
// Blog: https://blog.woshiluo.com
#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>
void chk_Min( T &a, T b ) { if( a > b ) a = b; }
template<class T>
void chk_Max( T &a, T b ) { if( a < b ) a = b; }
const int N = 5100;
const int mod = 1e9 + 7;
struct ModInt {
int cur;
ModInt( int _cur = 0 ) { cur = (((_cur % mod) + mod) % mod); }
ModInt operator +( const ModInt &b ) const { return (cur + b.cur) % mod; }
ModInt operator *( const ModInt &b ) const { return (1LL * cur * b.cur) % mod; }
bool operator !=( const ModInt &b ) const { return cur != b.cur; }
void operator +=( const ModInt &b ) {
cur += b.cur;
if( cur >= mod )
cur -= mod;
}
void operator *=( const ModInt &b ) {
cur = ( 1LL * cur * b.cur ) % mod;
}
void output( char end = '\n' ) {
printf( "%d%c", ( cur + mod ) % mod, end );
}
};
int n, k, q;
ModInt f[N][N], a[N], p[N];
int main() {
#ifdef woshiluo
freopen( "d.in", "r", stdin );
freopen( "d.out", "w", stdout );
#endif
scanf( "%d%d%d", &n, &k, &q );
for( int i = 1; i <= n; i ++ ) {
int tmp;
scanf( "%d", &tmp );
a[i] = tmp;
f[0][i] = 1;
}
for( int i = 1; i <= k; i ++ ) {
int la = i - 1;
for( int j = 1; j <= n; j ++ ) {
f[i][j] = f[la][ j - 1 ] + f[la][ j + 1 ];
}
}
for( int i = 1; i <= n; i ++ ) {
for( int j = 0; j <= k; j ++ ) {
p[i] += f[j][i] * f[ k - j ][i];
}
}
ModInt ans = 0;
for( int i = 1; i <= n; i ++ ) {
ans += a[i] * p[i];
}
while( q -- ) {
int pos, val;
scanf( "%d%d", &pos, &val );
ans += a[pos] * p[pos] * -1;
a[pos] = val;
ans += a[pos] * p[pos];
ans.output();
}
}E Distinctive Roots in a Tree
1 题目大意
每个节点有一个给定的权值，如果一个根到所有节点的路径上的点的权值没有重复，，则我们称这个节点为好根，求好根个数
带修，只修改一个点
2 思路
容易发现，如果一个节点的权值已经出现过，那么只有两种状况
- 两个节点没有父子内，则两个节点的字数都不可能为好根
- 两个节点有父子关系，则只有两个节点之间的节点可以为好根
容易发现这个可以通过树上差分维护
3 Code
/// Woshiluo
/// Email: woshiluo.luo [at] outlook.com
/// Blog: https://blog.woshiluo.com
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#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>
void chk_Min( T &a, T b ) { if( a > b ) a = b; }
template<class T>
void chk_Max( T &a, T b ) { if( a < b ) a = b; }
const int N = 2e5 + 1e4;
// Edge Start
struct edge {
int to, next;
} e[ N << 1 ];
int ehead[N], ecnt;
inline void add_edge( int cur, int to ) {
ecnt ++;
e[ecnt].to = to;
e[ecnt].next = ehead[cur];
ehead[cur] = ecnt;
}
// Edge End
int n;
int a[N], sum[N];
inline void add( int from, int to, int val ) {
sum[from] += val;
sum[to + 1] -= val;
}
int dfn[N], size[N], la[N], idx;
bool vis[N];
void dfs( int cur, int fa ) {
idx ++; dfn[cur] = idx; size[cur] = 1;
vis[cur] = true;
bool flag = false;
if( la[ a[cur] ] ) {
flag = true;
if( vis[ la[ a[cur] ] ] == false ) {
int aot = la[ a[cur] ];
add( dfn[aot], dfn[aot] + size[aot] - 1, 1 );
}
}
la[ a[cur] ] = cur;
for( int i = ehead[cur]; i; i = e[i].next ) {
if( e[i].to == fa )
continue;
dfs( e[i].to, cur );
size[cur] += size[ e[i].to ];
if( la[ a[cur] ] != cur ) {
add( 1, n, 1 );
add( dfn[ e[i].to ], dfn[ e[i].to ] + size[ e[i].to ] - 1, -1 );
}
la[ a[cur] ] = cur;
}
if( flag )
add( dfn[cur], dfn[cur] + size[cur] - 1, 1 );
vis[cur] = false;
}
int main() {
#ifdef woshiluo
freopen( "e.in", "r", stdin );
freopen( "e.out", "w", stdout );
#endif
scanf( "%d", &n );
int cnt = 0;
std::map<int, int> mp;
for(int i = 1; i <= n; i ++) {
scanf( "%d", &a[i] );
if( mp.count(a[i]) )
a[i] = mp[ a[i] ];
else {
cnt ++;
mp[ a[i] ] = cnt;
a[i] = cnt;
}
}
for(int i = 1; i < n; i ++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
dfs(1, 0);
int ans = 0;
for( int i = 1; i <= n; i ++ ) {
sum[i] += sum[ i - 1 ];
if( sum[i] == 0 ) {
ans ++;
}
}
printf( "%d\n", ans );
}