福州建站模板搭建,可以做公众号的网站吗,网站前后端分离怎么做,三亚网络网站建设Caddi Programming Contest 2021(AtCoder Beginner Contest 193)
A - Discount
打折浮点数除即可
B - Play Snuke
枚举判断符合要求的求最小值即可
C - Unexpressed O(n)O(\sqrt{n})O(n)枚举aaa#xff0c;暴力翻倍#xff08;最小的222最多乘323232次就会超过nnn的上…Caddi Programming Contest 2021(AtCoder Beginner Contest 193)
A - Discount
打折浮点数除即可
B - Play Snuke
枚举判断符合要求的求最小值即可
C - Unexpressed
O(n)O(\sqrt{n})O(n)枚举aaa暴力翻倍最小的222最多乘323232次就会超过nnn的上限
mapmapmap存该数有没有被aba^bab覆盖到数量不会太多不用担心MLEMLEMLE
D - Poker
暴力枚举计算情况。注意两个串选择同一数字时的小细节即可
#include cstdio
#include cmath
#define int long long
#define maxn 20
int n;
char s[maxn], t[maxn];
int tot[maxn], cnt_s[maxn], cnt_t[maxn];int calc( int x ) {return x * ( x - 1 );
}signed main() {scanf( %lld %s %s, n, s 1, t 1 );for( int i 1;i 4;i )tot[s[i] - 0] , tot[t[i] - 0] ;int cnt 0;for( int i 1;i 9;i ) {if( tot[i] n ) continue;for( int j 1;j 9;j ) {if( ( tot[j] n ) || ( i j tot[i] 1 n ) ) continue;int sum_s 0, sum_t 0;s[5] i 0, t[5] j 0;for( int k 1;k 5;k )cnt_s[s[k] - 0] , cnt_t[t[k] - 0] ;for( int k 1;k 9;k ) {sum_s k * pow( 10, cnt_s[k] );sum_t k * pow( 10, cnt_t[k] );}if( sum_s sum_t ) {if( i j )cnt ( n - tot[i] ) * ( n - tot[i] - 1 );elsecnt ( n - tot[i] ) * ( n - tot[j] );}for( int k 1;k 9;k )cnt_s[k] cnt_t[k] 0;}}printf( %.10f\n, cnt * 1.0 / ( calc( 9 * n - 8 ) ) );return 0;
}E - Oversleeping
发现每段差都在500以内暴力枚举相遇点
k1∗(2X2Y)Xik2∗(PQ)Pj⇔k1∗(2X2Y)−k2∗(PQ)P−Xj−ik_1*(2X2Y)Xik_2*(PQ)Pj \Leftrightarrow k_1*(2X2Y)-k_2*(PQ)P-Xj-ik1∗(2X2Y)Xik2∗(PQ)Pj⇔k1∗(2X2Y)−k2∗(PQ)P−Xj−i
即扩欧k1′(2X2Y)k2′(PQ)gcd(2X2Y,PQ)k_1(2X2Y)k_2(PQ)gcd(2X2Y,PQ)k1′(2X2Y)k2′(PQ)gcd(2X2Y,PQ)
有解必须满足gcd(2X2Y,PQ)∣P−Xj−igcd(2X2Y,PQ)|P-Xj-igcd(2X2Y,PQ)∣P−Xj−i
扩欧求出的解不一定是非负最优解扩倍(乘对方的倍数)成非负再取模变最优
#include cstdio
#include iostream
using namespace std;
#define int __int128
int T, X, Y, P, Q;void read( int x ) {x 0; char s getchar();while( s 0 || s 9 ) s getchar();while( 0 s s 9 ) {x ( x 1 ) ( x 3 ) ( s ^ 48 );s getchar();}
}void exgcd( int a, int b, int d, int x, int y ) {if( ! b ) d a, x 1, y 0;else {exgcd( b, a % b, d, y, x );y - x * ( a / b );}
}void print( int x ) {if( x 9 ) print( x / 10 );putchar( ( x % 10 ) 0 );
}signed main() {read( T );while( T -- ) {read( X ), read( Y ), read( P ), read( Q );int d, x, y, ans 1e32;exgcd( X * 2 Y * 2, P Q, d, x, y );for( int i 0;i Y;i )for( int j 0;j Q;j ) {int c P j - X - i;if( c % d ) continue;int k1 c / d * x;int k2 c / d * ( - y );int mod1 ( P Q ) / d, mod2 ( X * 2 Y * 2 ) / d;if( k1 0 ) {int t ( - k1 mod1 - 1 ) / mod1;k1 mod1 * t, k2 mod2 * t;}if( k2 0 ) {int t ( - k2 mod2 - 1 ) / mod2;k1 mod1 * t, k2 mod2 * t;}k1 % mod1;ans min( ans, k1 * ( X * 2 Y * 2 ) X i );}if( ans 1e32 ) printf( infinity\n );else print( ans ), putchar( \n );}return 0;
}F - Zebraness
一般的这种相邻之间计算贡献都可以转换成最小割问题考虑整体边数减去最小失去
如果相邻两个点是一样的颜色则失去111
但是这样根本无法在网络流上进行切割
所以考虑奇偶分开天然分裂相邻块
翻转奇数块颜色进行连边固定颜色的最大可以流出444至于不确定的就根据相邻边选择
按颜色分给超级源点和超级汇点大约是在O(n3)O(n^3)O(n3)
#include queue
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 105
#define inf 0x7f7f7f7f
struct node {int v, nxt, flow;
}edge[maxn * maxn * 30];
int n, cnt, s, t;
char ch[maxn][maxn];
int head[maxn * maxn], cur[maxn * maxn], dis[maxn * maxn];
queue int q;void addEdge( int u, int v, int c ) {edge[cnt].v v;edge[cnt].nxt head[u];edge[cnt].flow c;head[u] cnt ;edge[cnt].v u;edge[cnt].nxt head[v];edge[cnt].flow 0;head[v] cnt ;
}int id( int i, int j ) {return ( i - 1 ) * n j;
}bool bfs() {memset( dis, 0, sizeof( dis ) );memcpy( cur, head, sizeof( head ) );dis[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i edge[i].nxt ) {int v edge[i].v;if( ! dis[v] edge[i].flow ) {dis[v] dis[u] 1;q.push( v );}}}return dis[t];
}int dfs( int u, int cap ) {if( u t || ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i edge[i].nxt ) {int v edge[i].v; cur[u] i;if( dis[v] dis[u] 1 ) {int w dfs( v, min( cap, edge[i].flow ) );if( ! w ) continue;cap - w;flow w;edge[i].flow - w;edge[i ^ 1].flow w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, inf );return ans;
}int main() {memset( head, -1, sizeof( head ) );scanf( %d, n );for( int i 1;i n;i )scanf( %s, ch[i] 1 );for( int i 1;i n;i )for( int j 1;j n;j )if( ! ( ( i j ) 1 ) || ch[i][j] ? ) continue;else ch[i][j] B W - ch[i][j];s 0, t n * n 1;for( int i 1;i n;i )for( int j 1;j n;j ) {if( ch[i][j] B ) addEdge( s, id( i, j ), 4 );if( ch[i][j] W ) addEdge( id( i, j ), t, 4 );}for( int i 1;i n;i )for( int j 1;j n;j ) {addEdge( id( i, j ), id( i, j 1 ), 1 );addEdge( id( i, j 1 ), id( i, j ), 1 );}for( int i 1;i n;i )for( int j 1;j n;j ) {addEdge( id( i, j ), id( i 1, j ), 1 );addEdge( id( i 1, j ), id( i, j ), 1 );}printf( %d\n, 2 * n * ( n - 1 ) - dinic() );return 0;
}
