四川省建设人才网站2018,视频会议软件,网页设计自己做网页素材,桂林旅游网页设计文章目录A - Dial UpB - SquaresC - LIS to Original SequenceD - Unique SubsequenceE - SnackF - Tree Degree Subset Sum网址链接A - Dial Up
签到题
特判一下有没有0/1在目标串中出现而没在原串出现
除了第一次0/1数字互换时#xff0c;需要从a1a_1a1左右找距离最近的…
文章目录A - Dial UpB - SquaresC - LIS to Original SequenceD - Unique SubsequenceE - SnackF - Tree Degree Subset Sum网址链接A - Dial Up
签到题
特判一下有没有0/1在目标串中出现而没在原串出现
除了第一次0/1数字互换时需要从a1a_1a1左右找距离最近的不同数字
后面互换就是左/右转一次
#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
简单题
x2−yz2(x,y∈[1,n])x^2-yz^2\quad \Big(x,y\in[1,n]\Big)x2−yz2(x,y∈[1,n])
(xz)(x−z)y(xz)(x-z)y(xz)(x−z)y
observation : xz x-z 同奇偶且xz x-z
则有 x−z∈[1,n]x-z\in[1,\sqrt{n}]x−z∈[1,n]
考虑枚举ix−zix-zix−z计算出xzxzxz的范围[1,⌊ni⌋]\big[1,\lfloor\frac{n}{i}\rfloor\big][1,⌊in⌋]
然后计算在范围内与iii同奇偶的个数
时间复杂度O(n)O(\sqrt n)O(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 : a1a_1a1一定填在序列第一位 如果a11a_11a11填序列第一位是肯定的 如果a11a_11a11假设不填第一个那么需要一个小于a1a_1a1的数填在前面才会是最佳字典序 但填在a1a_1a1前面就会和a1,...,aka_1,...,a_ka1,...,ak构成更长的最长上升子序列不满足条件假设不成立
observation2 : 如果a1≠1a_1≠1a11则a2a_2a2一定填111是最优的
第一位都已经固定了为了使答案字典序最小肯定先放111构成1,a2,...,ak1,a_2,...,a_k1,a2,...,ak的相同长度LIS\rm LISLIS
observation3 : 除去a1a_1a1和111出现了新的子问题构造一个长度为n−2n-2n−2的序列LIS\rm LISLIS为a2,...,aka_2,...,a_ka2,...,ak
所以可以一位一位的递归构造实际上遍历一遍即可构造
#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
DPDPDP简单题
observation : x......x****x****后面以xxx开头的任意子序列都不会成为答案
所以可以设计dpi:dp_i:dpi: 从后往前到i时以iii开始的答案lstAi:lst_{A_i}:lstAi: AiA_iAi上一次的位置
dpi∑ji1lstAidpjdp_i\sum_{ji1}^{lst_{A_i}}dp_jdpi∑ji1lstAidpj 并且dplstAidp_{lst_{A_i}}dplstAi要清零
最后答案就是∑idplsti\sum_i dp_{lst_i}∑idplsti
区间求和单点修改可以用树状数组维护
#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
困难题
一眼网络流
超级源点SSS超级汇点TTT蛇Li,i∈[1,n]L_i,i\in[1,n]Li,i∈[1,n]人Rj,j∈[1,m]R_j,j\in[1,m]Rj,j∈[1,m]∀i,i∈[1,n]S→Li\forall_{i,i\in[1,n]} S\rightarrow L_i∀i,i∈[1,n]S→Li流量AiA_iAi∀i,i∈[1,n];j,j∈[1,m]Li→Rj\forall_{i,i\in[1,n];j,j\in[1,m]}L_i\rightarrow R_j∀i,i∈[1,n];j,j∈[1,m]Li→Rj流量BjB_jBj∀j,j∈[1,m]Rj→T\forall_{j,j\in[1,m]}R_j\rightarrow T∀j,j∈[1,m]Rj→T流量CjC_jCj
求图的最大流即可
但是n,mn,mn,m级别根本不能支持网络流的算法
需要找一种可以不真的跑网络流的算法求最大流
转换一下最大流等于最小割
将蛇LiL_iLi分成X,YX,YX,Y两个部分XXX与超级源点在一个集合YYY与超级汇点在一个集合
则每个人RjR_jRj就可以独立决定自己是在SSS集合还是TTT集合
在SSS集合就要断掉和TTT的边花费CjC_jCj在TTT集合就要断掉和XXX集合的所有边花费集合大小的∣X∣⋅Bj|X|·B_j∣X∣⋅Bj选择两者中的较小值
重要的是XXX的划分因此先决定XXX的划分
按AiA_iAi的降序从LiL_iLi中选择用作XXX的定点
尝试所有的XXX从0−N0-N0−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
困难题
令did_idi表示iii点的度数−1-1−1则度数范围为[0,n−2][0,n-2][0,n−2]
定义fif_ifi : 度数和为iii时最小选取顶点的集合个数gig_igi : 度数和为iii时最大选取顶点的集合个数 引理∀fi≤y≤gi\forall_{f_i\le y\le g_i}∀fi≤y≤gi一定都有一种顶点选取方式满足度数和为yyy 假设这个引理是正确的
利用与abc-215 colorful candies 2的同样的思想
不同度数的个数最多有n\sqrt nn
设计DPDPDP转移出fif_ifiggg可以由fff推出
fimin{fi−sumdcnt}f_i\min\{f_{i-sumd}cnt\}fimin{fi−sumdcnt}
可以用log\rm loglog倍增一段相同度数个数
最后gig_igi就相当于总个数减去度数和为s−is-is−i的最小选取顶点的集合个数fs−if_{s-i}fs−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;
}
