文章目录

• A - Dial Up
• B - Squares
• C - LIS to Original Sequence
• D - Unique Subsequence
• E - Snack
• F - Tree Degree Subset Sum

网址链接

A - Dial Up

签到题

特判一下有没有0/1在目标串中出现而没在原串出现

除了第一次0/1数字互换时，需要从$a_1$左右找距离最近的不同数字

后面互换就是左/右转一次

#include <cstdio> #include <iostream> using namespace std; #define maxn 200005 int n, m; bool s0, s1, t0, t1; int s[maxn], t[maxn];int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ ) {scanf( "%d", &s[i] );if( s[i] ) s1 = 1;else s0 = 1;}for( int i = 1;i <= m;i ++ ) {scanf( "%d", &t[i] );if( t[i] ) t1 = 1;else t0 = 1;}if( ( t1 and ! s1 ) or ( t0 and ! s0 ) )return ! printf( "-1\n" );int l = 0, r = 0;for( int i = n;i;i -- )if( s[i] == s[1] ) l ++;else { l ++; break; }for( int i = 1;i <= n;i ++ )if( s[i] == s[1] ) r ++;else break;int c = min( l, r ), now = s[1], ans = 0;bool flag = 0;for( int i = 1;i <= m;i ++ ) {if( now ^ t[i] ) {if( flag ) now ^= 1, ans ++;else now ^= 1, ans += c;flag = 1;}ans ++;}printf( "%d\n", ans );return 0; }

B - Squares

简单题

$x^2-y=z^2(x,y\in [1,n])$

$(x+z)(x-z)=y$

observation : x+z x-z 同奇偶，且x+z $>$ x-z

则有 $x-z\in [1,\sqrt{n}]$

考虑枚举$i=x-z$，计算出$x+z$的范围$[1,\lfloor \frac{n}{i}\rfloor ]$

然后计算在范围内与$i$同奇偶的个数

时间复杂度$O(\sqrt{n})$

#include <cstdio> #include <iostream> using namespace std; #define int long long #define mod 998244353 int n, ans;signed main() {scanf( "%lld", &n );for( int i = 1;i * i <= n;i ++ ) {int l = i, r = n / i;if( ( i & 1 ) ^ ( l ^ 1 ) ) l ++;if( ( i & 1 ) ^ ( r ^ 1 ) ) r ++;if( l <= r ) ans = ( ans + ( r - l ) / 2 + 1 ) % mod;}printf( "%lld\n", ans );return 0; }

C - LIS to Original Sequence

简单构造题

observation1 : $a_1$一定填在序列第一位

• 如果$a_1=1$，填序列第一位是肯定的

• 如果$a_1>1$，假设不填第一个，那么需要一个小于$a_1$的数填在前面，才会是最佳字典序

  但填在$a_1$前面，就会和$a_1,...,a_k$构成更长的最长上升子序列，不满足条件，假设不成立

observation2 : 如果$a_1\ne 1$，则$a_2$一定填$1$是最优的

• 第一位都已经固定了，为了使答案字典序最小，肯定先放$1$，构成$1,a_2,...,a_k$的相同长度$\mathrm{L}\mathrm{I}\mathrm{S}$

observation3 : 除去$a_1$和$1$，出现了新的子问题，构造一个长度为$n-2$的序列，$\mathrm{L}\mathrm{I}\mathrm{S}$为$a_2,...,a_k$

所以可以一位一位的递归构造，实际上遍历一遍即可构造

#include <cstdio> #define maxn 200005 int a[maxn]; bool vis[maxn]; int n, k;int main() {scanf( "%d %d", &n, &k );for( int i = 1;i <= k;i ++ ) scanf( "%d", &a[i] );for( int i = 1, j = 1;i < k;i ++ ) {printf( "%d ", a[i] );vis[a[i]] = 1;while( j < a[i] and vis[j] ) j ++;if( ! vis[j] ) printf( "%d ", j ), vis[j] = 1;}for( int i = n;i;i -- )if( ! vis[i] ) printf( "%d ", i );return 0; }

D - Unique Subsequence

$DP$简单题

observation : x......x****，x****后面以$x$开头的任意子序列都不会成为答案

所以可以设计$d{p}_i:$ 从后往前到i时以$i$开始的答案，$ls{t}_{A_i}:$ $A_i$上一次的位置

$d{p}_i={\sum }_{j=i+1}^{ls{t}_{A_i}}d{p}_j$ 并且$d{p}_{ls{t}_{A_i}}$要清零

最后答案就是${\sum }_{i}d{p}_{ls{t}_i}$

区间求和，单点修改可以用树状数组维护

#include <cstdio> #define mod 998244353 #define int long long #define maxn 200005 int n; int f[maxn], t[maxn], lst[maxn], A[maxn];int lowbit( int i ) { return i & -i; }void add( int i, int val ) {for( ;i <= n;i += lowbit( i ) ) t[i] = ( t[i] + val + mod ) % mod; }int query( int i ) {int ans = 0;for( ;i;i -= lowbit( i ) ) ans = ( ans + t[i] ) % mod;return ans; }signed main() {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &A[i] );for( int i = n;i;i -- ) {if( ! lst[A[i]] ) f[i] = ( query( n ) + 1 ) % mod;else f[i] = query( lst[A[i]] );if( lst[A[i]] ) add( lst[A[i]], -f[lst[A[i]]] );add( i, f[i] );lst[A[i]] = i; }int ans = 0;for( int i = 1;i <= n;i ++ ) ans = ( ans + f[lst[i]] ) % mod;printf( "%lld\n", ans );return 0; }

E - Snack

困难题

一眼网络流

• 超级源点$S$，超级汇点$T$，蛇$L_i,i\in [1,n]$，人$R_j,j\in [1,m]$
• ${\forall }_{i,i\in [1,n]}S\to L_i$，流量$A_i$
• ${\forall }_{i,i\in [1,n];j,j\in [1,m]}{L}_i\to R_j$，流量$B_j$
• ${\forall }_{j,j\in [1,m]}{R}_j\to T$，流量$C_j$

求图的最大流即可

但是$n,m$级别根本不能支持网络流的算法

需要找一种可以不真的跑网络流的算法求最大流

转换一下，最大流等于最小割

将蛇$L_i$分成$X,Y$两个部分，$X$与超级源点在一个集合，$Y$与超级汇点在一个集合

则每个人$R_j$就可以独立决定自己是在$S$集合还是$T$集合

• 在$S$集合，就要断掉和$T$的边，花费$C_j$
• 在$T$集合，就要断掉和$X$集合的所有边，花费集合大小的$|X|\cdot B_j$
• 选择两者中的较小值

重要的是$X$的划分，因此先决定$X$的划分

按$A_i$的降序从$L_i$中选择用作$X$的定点

尝试所有的$X$，从$0-N$

#include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define int long long #define maxn 200005 vector < int > G[maxn]; int n, m, sumB, sumC; int A[maxn], B[maxn], C[maxn], sumA[maxn];signed main() {scanf( "%lld %lld", &n, &m );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &A[i] );for( int i = 1;i <= m;i ++ ) scanf( "%lld", &B[i] );for( int i = 1;i <= m;i ++ ) scanf( "%lld", &C[i] );sort( A + 1, A + n + 1 );for( int i = 1;i <= m;i ++ ) sumB += B[i];for( int i = 1;i <= n;i ++ ) sumA[i] = sumA[i - 1] + A[i];for( int i = 1;i <= m;i ++ ) G[min( n, C[i] / B[i] )].push_back( i );int ans = 1e18;for( int i = 0;i <= n;i ++ ) {ans = min( ans, sumA[n - i] + i * sumB + sumC );for( auto j : G[i] ) sumB -= B[j], sumC += C[j];}printf( "%lld\n", ans );return 0; }

F - Tree Degree Subset Sum

困难题

令$d_i$表示$i$点的度数$-1$，则度数范围为$[0,n-2]$

定义$f_i$ : 度数和为$i$时最小选取顶点的集合个数，$g_i$ : 度数和为$i$时最大选取顶点的集合个数

引理：${\forall }_{f_i\le y\le g_i}$，一定都有一种顶点选取方式满足度数和为$y$

假设这个引理是正确的

利用与abc-215 colorful candies 2的同样的思想

不同度数的个数最多有$\sqrt{n}$

设计$DP$转移出$f_i$，$g$可以由$f$推出

$f_i=\min \{f_{i-sumd}+cnt\}$

可以用$\mathrm{l}\mathrm{o}\mathrm{g}$倍增一段相同度数个数

最后$g_i$就相当于总个数减去度数和为$s-i$的最小选取顶点的集合个数$f_{s-i}$

#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; #define maxn 200005 #define int long long struct node { int sumd, cnt;node(){}node( int Sumd, int Cnt ) {sumd = Sumd, cnt = Cnt;} }; vector < node > g; int n; int d[maxn], f[maxn];signed main() {scanf( "%lld", &n );memset( d, -1, sizeof( d ) );for( int i = 1, u, v;i < n;i ++ ) {scanf( "%lld %lld", &u, &v );d[u] ++, d[v] ++;}sort( d + 1, d + n + 1 );for( int i = 1, j = 1;i <= n;i = j ) {while( j <= n and d[i] == d[j] ) j ++;int cnt = j - i;for( int k = 1;k <= cnt;k <<= 1 ) {g.push_back( node( d[i] * k, k ) );cnt -= k;}if( cnt ) g.push_back( node( d[i] * cnt, cnt ) );}memset( f, 0x3f, sizeof( f ) );f[0] = 0; int sum = 0;for( auto now : g ) {sum += now.sumd;for( int i = sum;i >= now.sumd;i -- )f[i] = min( f[i], f[i - now.sumd] + now.cnt );}int ans = 0;for( int i = 0;i <= sum;i ++ )ans += max( ( n - f[sum - i] ) - f[i] + 1, 0ll );printf( "%lld\n", ans );return 0; }

总结

以上是生活随笔为你收集整理的[AtCoder Regular Contest 125] A-F全题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。