微擎 网站开发工具,网网站制作开发,个人网站模板免费下载,安卓app在线开发2021 CSP-S 题解廊桥分配括号序列回文交通规划配合#x1f449;CSP-S游记 食用更佳哦~
【雷】#xff1a;只是在民间数据过了#xff0c;不保证一定正确。仅供参考#xff01;#xff01;#xff01; 【雷】#xff1a;只是在民间数据过了#xff0c;不保证一定正确。…
2021 CSP-S 题解廊桥分配括号序列回文交通规划配合CSP-S游记 食用更佳哦~
【雷】只是在民间数据过了不保证一定正确。仅供参考 【雷】只是在民间数据过了不保证一定正确。仅供参考 【雷】只是在民间数据过了不保证一定正确。仅供参考
廊桥分配
problem
题目链接 solution
显然暴力就是枚举国内的廊桥数量然后模拟一遍O(n2)O(n^2)O(n2)。
正解就是加速这个过程。
设 f1[i]:f_1[i]:f1[i]: 国内有 iii 个廊桥能承载的飞机数量fi[i]:f_i[i]:fi[i]: 国外的。
最后就是 max{f1[i]f2[n−i]}\max\Big\{f_1[i]f_2[n-i]\Big\}max{f1[i]f2[n−i]}
考虑将 nnn 个廊桥看成 nnn 个桶对于国内飞机尽量地往前停否则就再开一个廊桥停这个飞机用前缀和就能求得 f1[i]/f2[i]f_1[i]/f_2[i]f1[i]/f2[i]。
可以通过 set\text{set}set 维护迅速找到每架飞机着陆前空的廊桥。 code
#include set
#include cstdio
#include iostream
using namespace std;
#define maxn 100005
set pair int, int s;
int f1[maxn], f2[maxn];
int n, m1, m2;void calc( int m, int *f ) {s.clear();for( int i 1, x, y;i m;i ) {scanf( %d %d, x, y );s.insert( { x, y } );}for( int i 1;i m;i ) {auto it s.begin();while( it ! s.end() ) {f[i] ;int k it - second;s.erase( it );it s.lower_bound( { k 1, 0 } );}f[i] f[i - 1];}
}int main() {scanf( %d %d %d, n, m1, m2 );calc( m1, f1 );calc( m2, f2 );int ans 0;for( int i 0;i n;i )ans max( ans, f1[i] f2[n - i] );printf( %d\n, ans );return 0;
}括号序列
problem
题目链接 solution
这道题难就难在 **()** 是不合法的。
为了知道左右的信息我们选择区间 dpdpdp。
设 g[l,r]:[l,r]g[l,r]:[l,r]g[l,r]:[l,r] 能否全为 ∗*∗
设 f[l,r]:[l,r]f[l,r]:[l,r]f[l,r]:[l,r] 强制 l−rl-rl−r 括号匹配的方案数
设 dp[l,r]:[l,r]dp[l,r]:[l,r]dp[l,r]:[l,r] 为超级完美序列的方案数不要求 l−rl-rl−r 一定匹配
转移很简单就是将合法的规则翻译成方程式即可。
(***(...)) 枚举左边连续一段 ∗*∗((...)***) 枚举右边连续一段 ∗*∗((...)) 直接嵌套一个匹配括号对()**() l−rl-rl−r 与不同的括号匹配中间要么为 ∅\empty∅ 要么为连续的 ∗*∗
主要是 dp−fdp-fdp−f 之间相互转移ggg 是预处理做的。
这就是妥妥的 O(n4)O(n^4)O(n4) 的转移。
正解就是在这个基础上进行了前缀和/后缀和的优化。 code-65’
#include cstdio
#define maxn 505
#define int long long
#define mod 1000000007
int n, m;
char s[maxn];
int f[maxn][maxn], dp[maxn][maxn];
bool g[maxn][maxn];signed main() {scanf( %lld %lld %s, n, m, s 1 );for( int i 1;i n;i ) {if( s[i] * or s[i] ? ) g[i][i] 1;g[i][i - 1] 1;}for( int len 2;len m;len )for( int i 1;i len - 1 n;i ) {int j i len - 1;if( s[i] * or s[i] ? ) g[i][j] | g[i 1][j];if( s[j] * or s[j] ? ) g[i][j] | g[i][j - 1];}for( int i 1;i n;i )if( s[i] ) or s[i] * or s[i 1] ( or s[i 1] * ) continue;else f[i][i 1] dp[i][i 1] 1;for( int len 3;len n;len ) for( int i 1;i len - 1 n;i ) {int j i len - 1;if( s[i] ) or s[i] * or s[j] ( or s[j] * ) continue;f[i][j] ( f[i][j] dp[i 1][j - 1] ) % mod;if( j - 1 - ( i 1 ) 1 m ) f[i][j] ( f[i][j] g[i 1][j - 1] ) % mod;for( int k i 2;k j - 1;k ) if( k - 1 - ( i 1 ) 1 m ) break;else f[i][j] ( f[i][j] g[i 1][k - 1] * dp[k][j - 1] ) % mod;for( int k j - 2;k i 1;k -- )if( ( j - 1 ) - ( k 1 ) 1 m ) break;else f[i][j] ( f[i][j] g[k 1][j - 1] * dp[i 1][k] ) % mod;for( int k i 1;k j - 1;k ) for( int t 0;t m;t )if( k t 1 j ) break;else dp[i][j] ( dp[i][j] f[i][k] * dp[k t 1][j] * g[k 1][k t] ) % mod;dp[i][j] ( dp[i][j] f[i][j] ) % mod;}printf( %lld\n, dp[1][n] );return 0;
}code-100‘
#include cstdio
#include iostream
using namespace std;
#define int long long
#define mod 1000000007
#define maxn 505
int f[maxn][maxn], g[maxn][maxn], h[maxn][maxn];
char s[maxn];
int n, m;bool is( int x, char c ) {if( x 1 or x n ) return 0;else return s[x] ? or s[x] c;
}signed main() {scanf( %lld %lld %s, n, m, s 1 );for( int i 2;i n;i ) f[i][i - 1] 1;for( int l n;l;l -- )for( int r l;r n;r ) {if( is( l, ( ) and is( r, ) ) ) {f[l][r] f[l 1][r - 1];for( int i l 2;i min( l m 1, r ) and is( i - 1, * );i )f[l][r] ( f[l][r] f[i][r - 1] ) % mod;for( int i r - 2;i max( l 1, r - m - 1 ) and is( i 1, * );i -- )f[l][r] ( f[l][r] f[l 1][i] ) % mod;}h[l][r] g[l][r] f[l][r];for( int i r - 1;i r - m and is( i 1, * );i -- ) g[l][r] ( g[l][r] h[l][i] ) % mod;for( int i l;i r;i ) f[l][r] ( f[l][r] g[l][i] * f[i 1][r] ) % mod;}printf( %lld\n, f[1][n] );return 0;
}回文
problem
题目链接 solution
这道题比前面的题可能还要简单一点。
会发现每次选择最左端或者最右端的数字连续选择对应在中间的序列也必须是连续的。
i.e.
1....213....3 选最左边的 111接着选最右边的 333bbb 序列里面就是 13...为了最后的回文最后几次操作必须是选 333 后立马选 111。
那会不会是 1...123....3 这种呢123 貌似可以不相邻成为两端。
显然不可能先选的 13... 之后才选择 222 那么回文就必须先选 222再选 31而 222 都被 111 和 333 堵死了。
所以这就是一个贪心模拟的过程。
优先从左边选择开始模拟。 code
#include cstdio
#define maxn 1000005
int T, n, flag;
int a[maxn], ans[maxn];
int pos[2][maxn];void print() {int l 1, r n 1;for( int i 1;i ( n 1 );i )if( ans[i] l ) printf( L ), l ;else printf( R ), r --;printf( \n );
}void solve( int l, int r, int L, int R ) {for( int i 2;i n;i ) {if( l L ) {if( pos[1][a[l]] L - 1 ) { ans[i] l , ans[(n 1 | 1) - i] -- L; continue; }if( pos[1][a[l]] R 1 ) { ans[i] l , ans[(n 1 | 1) - i] R; continue; }}if( r R ) {if( pos[0][a[r]] L - 1 ) { ans[i] r --, ans[(n 1 | 1) - i] -- L; continue; }if( pos[0][a[r]] R 1 ) { ans[i] r --, ans[(n 1 | 1) - i] R; continue; }}flag 0;return;}
}int main() {scanf( %d, T );while( T -- ) {scanf( %d, n );for( int i 1;i n;i ) pos[0][i] pos[1][i] 0;for( int i 1;i ( n 1 );i ) {scanf( %d, a[i] );if( ! pos[0][a[i]] ) pos[0][a[i]] i;else pos[1][a[i]] i;}flag 1;ans[1] 1, ans[n 1] pos[1][a[1]];solve( 2, n 1, pos[1][a[1]], pos[1][a[1]] );if( flag ) { print(); continue; }flag 1;ans[1] n 1, ans[n 1] pos[0][a[n 1]];solve( 1, (n 1) - 1, pos[0][a[n 1]], pos[0][a[n 1]] );if( flag ) { print(); continue; }printf( -1\n );}return 0;
}交通规划
problem
题目链接 solution
只能黑白染色然后端点颜色不同的边就会计算贡献。
如果想到了就是非常明显的网络流。
这种平面图般的网络流是很经典的有最短路优化——BZOJ上有一题网络流的经典“狼抓兔子”。
就算不会最短路优化也是可以暴力上网络流硬跑前 60′6060′ 的部分分。 code-60‘
#include queue
#include cstdio
#include cstring
#include iostream
using namespace std;
#define inf 1e18
#define maxn 505
#define Maxn 260000
#define maxm 1200000
#define int long long
queue int q;
struct node { int to, nxt, flow; }E[maxm];
int n, m, T, cnt, N, s, t, k;
int head[Maxn], cur[Maxn], dis[Maxn];
int a[maxn][maxn], b[maxn][maxn];void addedge( int u, int v, int flow ) {E[cnt] { v, head[u], flow };head[u] cnt ;E[cnt] { u, head[v], flow };head[v] cnt ;
}bool bfs() {memset( dis, 0, sizeof( dis ) );dis[s] 1, q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i cur[u] head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dis[v] and E[i].flow ) {dis[v] dis[u] 1;q.push( v );}}}return dis[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dis[v] dis[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, inf );return ans;
}int id( int i, int j ) { return ( i - 1 ) * m j; }signed main() {scanf( %lld %lld %lld, n, m, T );for( int i 1;i n;i ) for( int j 1;j m;j ) scanf( %lld, a[i][j] );for( int i 1;i n;i ) for( int j 1;j m;j ) scanf( %lld, b[i][j] );while( T -- ) {cnt 0, memset( head, -1, sizeof( head ) );scanf( %lld, k );N n * m, s N k 1, t s 1;for( int i 1;i n;i ) for( int j 1;j m;j ) addedge( id(i, j), id(i 1, j), a[i][j] );for( int i 1;i n;i ) for( int j 1;j m;j ) addedge( id(i, j), id(i, j 1), b[i][j] );for( int i 1;i N;i ) addedge( s, i, 0 ), addedge( i, t, 0 );for( int i 1, w, x, c;i k;i ) {scanf( %lld %lld %lld, w, x, c ); N; int pos;if( x m ) pos id( 1, x );else if( x n m ) pos id( x - m, m );else if( x n m * 2 ) pos id(n, 2 * m n - x 1);else pos id( 2 * ( m n ) - x 1, 1 );addedge( N, pos, w );if( c ) addedge( s, N, w );else addedge( N, t, w );}printf( %lld\n, dinic() );}return 0;
}
