算是填个坑吧 ， QwQ
Day 1
第一题很水，就是考代码能力 ，直接贴代码。
#include <iostream>
#include <cstdlib>
#include <cstdio>
<< , maxn = ;
using namespace std ;
int n , jv[maxn][maxn] ;
inline void Init( )
{
freopen( "magic.in" , "r" , stdin ) ;
freopen( "magic.out" , "w" , stdout ) ;
}
int read( )
{
, ret = ;
; ch = getchar( ) ; }
+ ch - ' , ch = getchar( ) ;
return ret * k ;
}
void sov( )
{
, y = (+n)>> ;
jv[x][y] = ;
; i <= n*n ; ++i )
{
&& y != n )
{
jv[n][y+] = i ;
x = n ; ++y ;
continue ;
}
)
{
jv[x-][] = i ;
--x ; y = ;
continue ;
}
&& y == n )
{
jv[x+][y] = i ;
++x ; continue ;
}
else
{
][y+] )
{
jv[x-][y+] = i ;
--x ; ++y ;
continue ;
}
jv[x+][y] = i ;
++x ; continue ;
}
}
}
void output( )
{
; x <= n ; ++x )
{
; y <= n ; ++y )
printf( "%d " , jv[x][y] ) ;
printf( "\n" ) ;
}
}
int main( )
{
Init( ) ;
n = read( ) ;
sov( ) ;
output( ) ;
fclose( stdin ) ;
fclose( stdout ) ;
;
}
第二题
就是求一个有向图的最小正环 ， 但分析后就知道每个点只有一个出度 ，所以图中只存在简单环 ，
于是我在考场上用并查集做的 。
#include <iostream>
#include <cstdlib>
#include <cstdio>
<< , maxn = + ;
using namespace std ;
] ; //father and dis
inline void Init( )
{
freopen( "message.in" , "r" , stdin ) ;
freopen( "message.out" , "w" , stdout ) ;
}
int read( )
{
, ret = ;
; ch = getchar( ) ; }
+ ch - ' , ch = getchar( ) ;
return ret * k ;
}
int find( int x )
{
] == x ) return x ;
] ;
fa[x][] = find( fa[x][] ) ;
fa[x][] += fa[fu][] ;
] ;
}
void sov( )
{
; x <= n ; ++x ) fa[x][] = x ;
int y , root1 , root2 , ans = inf ;
; x <= n ; ++x )
{
y = read( ) ;
root1 = find( x ) , root2 = find( y ) ;
if( root1 != root2 )
{
fa[root1][] = root2 ;
fa[root1][] += + fa[y][] ;
}
else
ans = min( ans , fa[x][] + fa[y][] + ) ;
}
printf( "%d\n" , ans ) ;
}
int main( )
{
Init( ) ;
n = read( ) ;
sov( ) ;
fclose( stdin ) ;
fclose( stdout ) ;
;
}
后面是先拓扑去不是环里的点，在找最小的环（对每个点打标记，打个标记的点不用遍历。）
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
<< , maxn = + ;
using namespace std ;
queue < int > Q ;
struct id
{
int nxt , in ; bool vis ;
} node[maxn] ;
;
inline void Init( )
{
freopen( "message.in" , "r" , stdin ) ;
freopen( "message.out" , "w" , stdout ) ;
}
int read( )
{
, ret = ;
; ch = getchar( ) ; }
+ ch - ' , ch = getchar( ) ;
return ret * k ;
}
void input( )
{
n = read( ) ;
; x <= n ; ++x )
node[x].nxt = read( ) , node[node[x].nxt].in++ ;
}
void sov( )
{
; x <= n ; ++x ) if( !node[x].in ) { Q.push( x ) ; node[x].vis = true ; }
while( !Q.empty( ) )
{
int u = Q.front( ) ; Q.pop( ) ;
int v = node[u].nxt ;
) { Q.push( v ) ; node[v].vis = true ; }
} ans = inf ;
; x <= n ; ++x )
{
, j = node[x].nxt ;
if( !node[x].vis )
{
while( j != x )
{
cnt++ ;
node[j].vis = true ;
j = node[j].nxt ;
}
ans = min( ans , cnt ) ;
}
}
printf( "%d\n" , ans ) ;
}
int main( )
{
Init( ) ;
input( ) ;
sov( ) ;
fclose( stdin ) ;
fclose( stdout ) ;
;
}
当然可以用tajan但我tajan最多只改到90分，就暴栈了QwQ ，不过改成bfs还是可以过，但我没写过 。
第三题就是搜索+剪枝，最开始我以为顺子越长越好，其实并不是QwQ，所以就只有45分 ， 然后我就改成枚举了一下顺子的长度，然后就过了。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fo(a,b,c) for(int a=(b);a<=(c);a++)
<< ;
using namespace std ;
] , c[] , ans ;
inline void Init( )
{
freopen( "landlords.in" , "r" , stdin ) ;
freopen( "landlords.out" , "w" , stdout ) ;
}
int read( )
{
, ret = ;
; ch = getchar( ) ; }
+ ch - ' , ch = getchar( ) ;
return ret * k ;
}
void input( )
{
int a , b ;
fo( i , , n )
{
a = read( ) , b = read( ) ;
) a = ; else if( a ) a-- ;
s[a] ++ ;
}
}
int quer( )
{
memset( c , , sizeof( c ) ) ;
fo( i , , ) c[s[i]] ++ ;
// cout<<c[1]<<" "<<c[2]<<" "<<c[3]<<" "<<c[4]<<endl;
;
] && c[]> ) c[]-- , c[] -= , tot ++ ;
] && c[] > ) c[] -- , c[] -= , tot ++ ;
] && c[] ) c[]-- , c[] -- , tot ++ ;
] && c[] ) c[]-- , c[]-- , tot ++ ;
] && c[] ) c[]-- , c[]-- , tot++ ;
] + c[] + c[] + c[] ;
}
void dfs( int now )
{
if( now >= ans ) return ;
int tmp = quer( ) ;
if( tmp + now < ans ) ans = now + tmp ;
fo( i , , )
{
int j = i ;
) ++j ;
)
{
fo( j2 , i+ , j- )
{
fo( k , i , j2 ) s[k] -= ;
dfs( now + ) ;
fo( k , i , j2 ) s[k] += ;
}
}
}
fo( i , , )
{
int j = i ;
) ++j ;
)
{
fo( j2 , i+ , j- )
{
fo( k , i , j2 ) s[k] -= ;
dfs( now + ) ;
fo( k , i , j2 ) s[k] += ;
}
}
}
fo( i , , )
{
int j = i ;
) ++j ;
)
fo( j2 , i+ , j- )
{
fo( k , i , j2 ) --s[k] ;
dfs( now + ) ;
fo( k , i , j2 ) ++s[k] ;
}
}
return ;
}
int main( )
{
Init( ) ;
t = read( ) , n = read( );
while( t-- )
{
memset( s , , sizeof(s) ) ;
// memset( c , 0 , sizeof(c) ) ;
ans = inf ;
input( ) ;
dfs( ) ;
printf( "%d\n" , ans ) ;
}
fclose( stdin ) ;
fclose( stdout ) ;
;
}
day2
第一题比较简单，就是一个二分嘛 ，虽然昨年没写出来qwq（昨年用堆贪心）
#include <iostream>
#include <cstdlib>
#include <cstdio>
<< , maxn = + ;
using namespace std ;
int l , n , m , a[maxn] ;
inline void Init( )
{
freopen( "stone.in" , "r" , stdin ) ;
freopen( "stone.out" , "w" , stdout ) ;
}
int read( )
{
, ret = ;
; ch = getchar( ) ; }
+ ch - ' , ch = getchar( ) ;
return ret * k ;
}
void input( )
{
l = read( ) , n = read( ) , m = read( ) ;
; x <= n ; ++x ) a[x] = read( ) ;
a[n+] = l , ++n ;
}
bool check( int len )
{
, ans = ;
; x <= n ; ++x )
{
if( a[x] - last < len ) ans++ ;
else last = a[x] ;
if( ans > m ) return false ;
}
return true ;
}
void sov( )
{
, rr = l ;
while( ll <= rr )
{
;
;
;
}
printf( ) ;
}
int main( )
{
Init( ) ;
input( ) ;
sov( ) ;
fclose( stdin ) ;
fclose( stdout ) ;
;
}
第二题的话，就是方程式比较难推，QwQ我考场上写的记搜，结果空间复杂度算错 ，本来还是可以骗一点分的 ，
就是个dp，方程式其实还是比较好推，就是要想到一个前缀优化，然后滚一滚就可以过 。
#include <iostream>
#include <cstdlib>
#include <cstdio>
;
using namespace std ;
int n , m , k ;
] , b[] ;
][][][] ;
int main( )
{
scanf( "%d%d%d" , &n , &m , &k ) ;
scanf( , b+ ) ;
f[][][][] = , f[][][][] = ;
; i <= n ; ++i )
{
; j <= min( i , m) ; ++j )
{
; l <= k ; ++l )
{
,last=(i-)&;
if( a[i] == b[j] )
{
f[j][l][][now] = ( f[j-][l-][][last] + f[j-][l-][][last] ) % mod + f[j-][l][][last] ;
f[j][l][][now] %= mod ;
f[j][l][][now] = ( f[j][l][][last] + f[j][l][][last] ) % mod ;
}
else
{
f[j][l][][now] = (f[j][l][][last]+f[j][l][][last])%mod ;
f[j][l][][now] = ;
}
// cout<<j<<" "<<l<<" "<<now<<" "<<f[j][l][1][now]<<" "<<f[j][l][0][now]<<endl;
}
}
}
printf( ][n&]+f[m][k][][n&])%mod ) ;
;
}