T1 数字 Number
1 记录
考场上疯狂肝这道题目，结果少个特判
2 Solution
很明显，$n$ 只有三种情况
- $n$ 就是结尾
- 中间有一段是一个数字，这个情况 $O(\log^3(n))$ 枚举即可
- 中间切一刀，左边是一个不完整的数字，右边也是一个不完整的数字，枚举中间即可
所以直接暴力即可
所以这是一道毒瘤模拟题目
3 Source
#include <cstdio>
#include <cmath>
inline int _ws( long long now ) {
if( now == 0 )
return 0;
return ( (int)std::log10(now) ) + 1;
}
int t;
long long n, ans;
long long pow_10[20] = { 1, 1 };
long long check( int st, int ed, long long val ) {
long long res = val;
long long ed_val, tmp = val - 1;
while( st && tmp >= 0 ) {
if( st < _ws( tmp ) ) {
tmp %= pow_10[st];
if( _ws( tmp ) < st )
return false;
}
res = ( tmp * pow_10[ _ws(res) ] ) + res;
st -= _ws( tmp );
tmp --;
}
if( st )
return false;
tmp = val + 1;
while( ed && tmp >= 0 ) {
if( ed < _ws( tmp ) ) {
ed_val = tmp;
tmp /= pow_10[ _ws( tmp ) - ed ];
}
else
ed_val = tmp;
if( tmp <= 0 )
return false;
res = ( res * pow_10[ _ws( tmp ) ] ) + tmp;
ed -= _ws( tmp );
tmp ++;
}
if( res == n )
return ed_val;
else
return false;
}
int main() {
freopen( "number.in", "r", stdin );
freopen( "number.out", "w", stdout );
scanf( "%d", &t );
for( int i = 1; i <= 18; i ++ )
pow_10[i] = pow_10[ i - 1 ] * 10LL;
while( t -- ) {
scanf( "%lld", &n );
ans = n;
int ws = _ws( n );
for( int st = 0; st <= ws; st ++ ) {
for( int len = 1; len <= ws - st; len ++ ) {
if( long long tmp = check( st, ws - st - len, ( n % pow_10[ ws - st ] ) / pow_10[ ws - st - len ] ) ) {
ans = ans < tmp? ans: tmp;
}
}
}
for( int ed_p = 1; ed_p < ws; ed_p ++ ) {
long long fir = n / pow_10[ ws - ed_p ], sec = n % pow_10[ ws - ed_p ], res;
if( _ws( sec ) < ws - ed_p )
continue;
fir ++;
if( _ws( fir ) > ed_p ) {
fir %= pow_10[ ed_p ];
}
res = ( sec * pow_10[ ed_p ] ) + fir;
for( int pin = 1; pin <= ed_p; pin ++ ) {
sec /= 10;
if( sec == 0 )
break;
long long tmp = ( sec * pow_10[ ed_p ] ) + fir;
if( ( ( ( tmp - 1 ) % pow_10[ ed_p ] ) * pow_10[ ws - ed_p ] + tmp / pow_10[ _ws(tmp) - ( ws - ed_p ) ] ) == n )
res = res < tmp? res: tmp;
}
ans = ans < res? ans: res;
}
printf( "%lld\n", ans );
}
fclose( stdin );
fclose( stdout );
}T2 Maja
1 记录
全去肝 T1 去了
2 Solution
很容易得到，路径一定是在某一个地方开始，朝另一个点左右横跳
并且左右横跳的的距离不会超过 2
即设 $f[k][i][j]$ 表示 $k$ 步 走到 $(i,j)$ 的最大结果
在做到 $f[j][i][j]$ 的时候顺便维护全局最大值即可
$k$ 最大是 $\min( \frac{k}{2}, n \times m)$
滚动 $k$ 即可
3 Source
#include <cstdio>
#include <cstring>
#include <algorithm>
template <typename T> T Max( T a, T b ) { return a > b? a: b; }
template <typename T> T Min( T a, T b ) { return a < b? a: b; }
const int N = 110;
int n, m, A, B, k, a[N][N], max[N][N];
long long f[2][N][N], ans;
int dx[4] = { 0, 0, +1, -1 };
int dy[4] = { +1, -1, 0, 0 };
int main() {
freopen( "maja.in", "r", stdin );
freopen( "maja.out", "w", stdout );
scanf( "%d%d%d%d%d", &n, &m, &A, &B, &k );
for( int i = 1; i <= n; i ++ ) {
for( int j = 1; j <= m; j ++ ) {
scanf( "%d", &a[i][j] );
}
}
for( int i = 1; i <= n; i ++ ) {
for( int j = 1; j <= m; j ++ ) {
int res = 0;
if( i != n )
res = Max( res, a[ i + 1 ][j] );
if( i != 1 )
res = Max( res, a[ i - 1 ][j] );
if( j != m )
res = Max( res, a[i][ j + 1 ] );
if( j != 1 )
res = Max( res, a[i][ j - 1 ] );
max[i][j] = res;
}
}
memset( f, -1, sizeof( f ) );
int cur = 0, next = 1;
int max_k = Min( k >> 1, n * m );
f[next][A][B] = a[A][B];
for( int o = 0; o < max_k; o ++ ) {
std::swap( cur, next );
for( int i = 1; i <= n; i ++ ) {
for( int j = 1; j <= m; j ++ ) {
if( f[cur][i][j] == -1 )
continue;
for( int z = 0; z < 4; z ++ ) {
int tx = i + dx[z];
int ty = j + dy[z];
if( tx < 1 || tx > n || ty < 1 || ty > m )
continue;
f[next][tx][ty] = Max( f[next][tx][ty], f[cur][i][j] + a[tx][ty] );
int tmp = ( ( k - ( o << 1 ) ) >> 1 );
ans = Max( ans, ( f[cur][i][j] * 2 ) + ( 1LL * max[i][j] * tmp ) + ( 1LL * a[i][j] * ( tmp - 1 ) ) );
// printf( "%d %d %d %lld\n", o, i, j, ans );
}
}
}
}
printf( "%lld\n", ans );
fclose( stdin );
fclose( stdout );
}T3 djq的朋友圈 Friends
1 记录
考场上完全没有看懂题目的说
下来看了好久才看懂
2 Solution
这个数据范围不是状压就是爆搜的感觉
结果他不仅仅是个状压，还很神仙
考虑将于 $1$ 节点直接连接的称为 $A$ 类点，相连但是并不直接的是 $B$ 类点
设 $dp[i]$ ，其中 $i$ 是状压状态，表示取了哪些 $A$ 类点
复杂度 $O(2^A \times A)$
看起来一切都好
然后发现出题人搞我们，这个方法并不能 AC
反向思考，我们也可以枚举$B$
这样一来，复杂度就是 $ O( 2^{\min(A,B)} \times A ) $
3 Source
#include <cstdio>
#include <cstring>
const int N = 50;
const int INF = 0x3f3f3f3f;
template <typename T> T lowbit( T now ) { return now & ( - now ); }
template <typename T> T full_bit ( T a ) { return ( 1LL << a ) - 1LL; }
int get_1( long long now ) {
int res = 0;
while( lowbit(now) )
res ++, now -= lowbit(now);
return res;
}
inline int Max( int a, int b ) { return a > b? a: b; }
int n, m, ans, a_cnt, b_cnt, dp[ 1 << 23 ];
int f[N][N], id[N];
long long hf[N], ok[N];
int main() {
freopen( "friends.in", "r", stdin );
freopen( "friends.out", "w", stdout );
memset( f, -1, sizeof(f) );
memset( id, -1, sizeof(id) );
scanf( "%d%d", &n, &m );
for( int i = 1, u, v, w; i <= m; i ++ ) {
scanf( "%d%d%d", &u, &v, &w );
f[u][v] = f[v][u] = w;
}
for( int i = 2; i <= n ; i ++ ) {
if( f[1][i] == -1 )
continue;
id[i] = ++ a_cnt;
ans += ( f[1][i] == 0 );
for( int j = 2; j <= n; j++ ) {
if( f[1][j] == -1 && f[i][j] != -1 ) {
if( id[j] == -1 )
id[j] = ++ b_cnt;
hf[ id[i] ] |= 1LL << ( id[j] - 1LL );
ok[ id[i] ] |= ( (long long)( f[1][i] == f[i][j] ) ) << ( id[j] - 1LL );
}
}
}
if( a_cnt <= 20 ) {
for( int i = 0; i <= full_bit( a_cnt ); i ++ )
dp[i] = -INF;
dp[0] = 0;
for( int i = 0; i <= full_bit( a_cnt ); i ++ ) {
if( dp[i] < 0 )
continue;
long long now = 0;
for( int j = 1; j <= a_cnt; j ++ )
if( ( i >> ( j - 1 ) ) & 1 )
now |= hf[j];
for( int j = 1; j <= a_cnt; j ++ ) {
if( ( i >> ( j - 1 ) ) & 1 )
continue;
int next = i | ( 1 << ( j - 1 ) );
dp[next] = Max( dp[next], dp[i] + get_1( ok[j] & ( ~now ) ) );
}
}
printf( "%d\n", dp[ full_bit( a_cnt ) ] + ans );
return 0;
}
for( int i = 0; i <= full_bit( b_cnt ); i ++ )
dp[i] = -INF;
dp[0] = 0;
for( int i = 0; i <= full_bit( b_cnt ); i ++ ) {
if( dp[i] < 0 )
continue;
for( int j = 1; j <= a_cnt; j ++ ) {
if( ( i | hf[j] ) == i )
continue;
int next = i | hf[j];
dp[next] = Max( dp[next], dp[i] + get_1( ok[j] & ( ~ i ) ) );
}
}
printf( "%d", ans + dp[ full_bit( b_cnt ) ] );
fclose( stdin );
fclose( stdout );
}