在一个队列中一次加入每一个字符，每次更新当前队列中的状态，当满足存在26个不同字符时，更新答案，删除队首。
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #define RG register using namespace std; char s[2000005]; int len, nex[2000005], flag[30]; int q[2000005]; int main ( ) { freopen ( "str.in", "r", stdin ); freopen ( "str.out", "w", stdout ); scanf ( "%s", s ); len = strlen ( s ); for ( RG int i = 0; i < len; i ++ ) flag[s[i]-'A'] = 1; int fl = 0; for ( RG int i = 0; i < 26; i ++ ) if ( !flag[i] ) { fl = 1; break; } if ( fl ) { printf ( "QwQ" ); return 0; } int num = 0, ans = 0x3f3f3f3f, h = 0, t = 0; memset ( flag, 0, sizeof ( flag ) ); for ( RG int i = 0; i < len; i ++ ) { q[++t] = s[i]-'A'; flag[s[i]-'A'] ++; if ( flag[s[i]-'A'] == 1 ) num ++; while ( t-h && num == 26 ) { ans = min ( ans, t-h ); int x = q[h+1]; h ++; flag[x] --; if ( !flag[x] ) num --; } } printf ( "%d", ans ); }
一开始想的分解质因数，再通过每个质因子的个数来判断是否成立，可是一开始就错了...以为1e9开方是1e3...
方法是先将x和y乘起来，因为题目有一个性质，他们的乘积一定是一个数的3次方，设这个数为k，因为x和y中每次游戏要不是有一个k1值，要不是有两个，所以x和y必然可以整除k。三个判断条件即可。【注意】二分求k值时不能让k大于1e6,三方爆long long。
#include<iostream> #include<cstdio> #include<cmath> #define ll long long using namespace std; ll x, y; int num1[400001], num2[400001]; int prime[400001], tot, isnot[400001]; void read ( ll &x ) { x = 0; char ch = getchar ( ); int t = 1; while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) t = -1; ch = getchar ( ); } while ( ch >= '0' && ch <= '9' ) { x = x * 10 + ch - '0'; ch = getchar ( ); } x = x * t; } inline int gcd ( int a, int b ) { return b == 0 ? a : gcd ( b, a % b ); } ll erfen ( ll qwq ) { ll l = 1, r = min ( sqrt ( qwq ), 1e6 ), res; while ( l <= r ) { ll mid = ( l + r ) >> 1; if ( mid * mid * mid <= qwq ) { l = mid + 1; res = mid; } else r = mid - 1; } return res; } int main ( ) { freopen ( "game.in", "r", stdin ); freopen ( "game.out", "w", stdout ); int T; scanf ( "%d", &T ); while ( T -- ) { int fl = 0; read ( x ); read ( y ); ll g = 1ll * x * y; ll qwq = erfen ( g ); if ( qwq * qwq * qwq != g ) fl = 1; if ( x % qwq != 0 || y % qwq != 0 ) fl = 1; if ( fl ) printf ( "No " ); else printf ( "Yes " ); } return 0; }
比较经典的一道题，分别把按行放木板和按列放木板给每一块泥地标号，可以连着放的号数一样。把每一个泥地的行号连向列号，跑最小割或者最大匹配即可。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std; int r, c; char a[55][55]; int num1[55][55], num2[55][55], cnt1, cnt2, s, t; int stot = 1, h[10005], tov[200005], nex[200005], f[200005], hh[10005]; void add ( int u, int v, int ff ) { tov[++stot] = v; f[stot] = ff; nex[stot] = h[u]; h[u] = stot; tov[++stot] = u; f[stot] = 0; nex[stot] = h[v]; h[v] = stot; } int dep[1005], vis[1005]; queue < int > q; bool bfs ( ) { memset ( dep, 0, sizeof ( dep ) ); memset ( vis, 0, sizeof ( vis ) ); q.push ( s ); vis[s] = 1; while ( !q.empty ( ) ) { int u = q.front ( ); q.pop ( ); for ( int i = h[u]; i; i = nex[i] ) { int v = tov[i]; if ( !vis[v] && f[i] ) { dep[v] = dep[u] + 1; vis[v] = 1; q.push ( v ); } } } return vis[t]; } int dfs ( int u, int delta ) { if ( u == t ) return delta; int res = 0; for ( int i = hh[u]; i && delta; i = nex[i] ) { int v = tov[i]; if ( dep[v] == dep[u] + 1 && f[i] ) { int dd = dfs ( v, min ( f[i], delta ) ); f[i] -= dd; f[i^1] += dd; delta -= dd; res += dd; hh[u] = i; } } return res; } void debug ( ) { for ( int i = 0; i < r; i ++ ) { for ( int j = 0; j < c; j ++ ) printf ( "%d ", num1[i][j] ); cout << endl; } cout << endl; for ( int i = 0; i < r; i ++ ) { for ( int j = 0; j < c; j ++ ) printf ( "%d ", num2[i][j] ); cout << endl; } } int main ( ) { freopen ( "cover.in", "r", stdin ); freopen ( "cover.out", "w", stdout ); scanf ( "%d%d", &r, &c ); for ( int i = 0; i < r; i ++ ) scanf ( "%s", a[i] ); for ( int i = 0; i < r; i ++ ) for ( int j = 0; j < c; j ++ ) { if ( j != 0 && a[i][j] == '*' && a[i][j-1] == '*' ) num1[i][j] = num1[i][j-1]; else if ( a[i][j] == '*' ){ cnt1 ++; num1[i][j] = cnt1; } if ( i != 0 && a[i][j] == '*' && a[i-1][j] == '*' ) num2[i][j] = num2[i-1][j]; else if ( a[i][j] == '*' ){ cnt2 ++; num2[i][j] = cnt2; } } //debug ( ); for ( int i = 0; i < r; i ++ ) for ( int j = 0; j < c; j ++ ) if ( a[i][j] == '*' ) { //printf ( "%d->%d+%d ", num1[i][j], num2[i][j], cnt1 ); add ( num1[i][j], num2[i][j] + cnt1, 1 ); } s = 0, t = cnt1+cnt2+1; for ( int i = 1; i <= cnt1; i ++ ) add ( s, i, 1 ); for ( int i = 1; i <= cnt2; i ++ ) add ( i + cnt1, t, 1 ); int ans = 0; while ( bfs ( ) ) { for ( int i = 0; i <= cnt1 + cnt2 + 1; i ++ ) hh[i] = h[i]; ans += dfs ( s, 0x3f3f3f3f ); } printf ( "%d", ans ); return 0; }