开个坑记录一下刷USACO的Training的记录
可能会随时弃坑
只有代码和做法简述
可能没有做法简述
[USACO1.1]你的飞碟在这儿Your Ride Is He…
模拟，细节已忘
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s1[],s2[];
int main()
{
int ss1=,ss2=;
scanf("%s",&s1);
scanf("%s",&s2);
int len1=strlen(s1),len2=strlen(s2);
for(int i=;i<len1;i++)
ss1*=s1[i]-;
for(int i=;i<len2;i++)
ss2*=s2[i]-;
int l1=ss1%,l2=ss2%;
if(l1==l2)
cout<<"GO"<<endl;
else
cout<<"STAY"<<endl;
return ;
}
[USACO1.1]贪婪的送礼者Greedy Gift Givers
模拟，用map减少代码量
#include <iostream>
#include <string>
#include <cstdio>
#include <map> using namespace std ; string s[ ] , ch , s1 ;
int n ;
map<string,int> mp ; int main() {
cin >> n ;
for( int i = ; i <= n ; i ++ ) cin >> s[ i ] , mp[ s[ i ] ] = ;
for( int i = ; i <= n ; i ++ ) {
int val , m ;
cin >> ch >> val >> m ;
if( m != ) val /= m ;
mp[ ch ] -= val * m ;
for( int i = ; i <= m ; i ++ ) {
cin >> s1 ;
mp[ s1 ] += val ;
}
}
for( int i = ; i <= n ; i ++ ) {
cout << s[ i ] << " " << mp[ s[ i ] ] << endl ;
}
}
[USACO1.1]黑色星期五Friday the Thirteenth
恶心模拟，用数学方法算一下规律，然后模拟即可
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int year,month,i,n,last=;
int dayOfMonth[]={,,,,,,,,,,,};
int result[]={};
cin>>n;
for(year=;year<+n;++year){
if(year%==||(year%!=&&year%==)) dayOfMonth[]=;
for(month=;month<;++month){
last=(last+dayOfMonth[month])%;
result[last]++;
}
dayOfMonth[]=;
}
for(i=;i<;++i) cout<<result[(i+)%]<<' ';
cout<<result[]<<endl;
return ;
}
[USACO1.1]坏掉的项链Broken Necklace
暴力模拟，细节已忘
#include <cstdio>
using namespace std;
int n,ans=-;char a[];
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
void find(int x){
char c=a[x];
int sum=;
for(int i=x;i;i--){
if(a[i]==c)sum++;
else if(a[i]=='w')sum++;
else break;
}
c=a[x+];
for(int i=x+;i<=*n;i++){
if(a[i]==c)sum++;
else if(a[i]=='w')sum++;
else break;
}
ans=max(ans,sum);
}
int main(){
scanf("%d%s",&n,a+);
for(int i=;i<=n;i++){
a[i+n]=a[i];a[i+n+n]=a[i];
}
for(int i=n;i<=*n;i++){
if(a[i]==a[i+])continue;
if(a[i]=='w'){
a[i]='r';
find(i);
a[i]='b';
find(i);
a[i]='w';
}
find(i);
}
ans=min(ans,n);
if(ans==-)ans=n;
printf("%d\n",ans);
return ;
}
[USACO1.2]命名那个数字 Name That Number
看不懂。这题有毒，用的题解的check
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <map> using namespace std ; char ft[][]={{},{},"ABC","DEF","GHI","JKL","MNO","PRS","TUV","WXY"};
string s[ ] ;
int n ; int main() {
while( cin >> s[ n ] ) n ++ ;
string ch = s[ ] ;
n -- ;
sort( s + , s + n + ) ;
bool check = ;
for( int i = ; i <= n ; i ++ ) {
bool ok = ( s[ i ].length() == ch.length() ) ;
for( int j = ; j < s[ i ].length() ; j ++ ) {
char c=s[ i ][ j ] ;
ok = ok & (c==ft[ch[j]-''][] || c==ft[ch[j]-''][] || c==ft[ch[j]-''][]);
}
if( ok ) {
cout << s[ i ] << endl ;
check = ;
}
}
if( check ) cout << "NONE\n" ;
return ;
}
[USACO1.2]挤牛奶Milking Cows
差分一下然后按题目模拟，纯模拟可过，应该是数据水吧
#include <bits/stdc++.h> using namespace std ; #define ll long long
#define N 1000010 int n ;
int c[ N ] ; int main() {
scanf( "%d" , &n ) ;
int s = 0x3f3f3f3f , t = ;
for( int i = , l , r ; i <= n ; i ++ ) {
scanf( "%d%d" , &l , &r ) ;
c[ l ] ++ ; c[ r ] -- ;
s = min( s , l ) ;
t = max( t , r - ) ;
}
int ans[ ] = { };
int ch = , now = s ;
t ++ ;
for( int i = s ; i <= t ; i ++ ) {
c[ i ] = c[ i - ] + c[ i ] ;
int x = c[ i ] != ;
if( x != ch || i == t ) {
ans[ ch ] = max( ans[ ch ] , i - now ) ;
now = i ;
ch ^= ;
}
}
printf( "%d %d\n" , ans[ ] , ans[ ] ) ;
return ;
}
[USACO1.2]方块转换 Transformations
恶心模拟题，不写
于是挑了一个下午的自习写掉了这题...
这道题告诉我们在代码大量重复的情况下要善用define......
反正define一下for，然后旋转和翻转打个子程序，代码量也就1kb左右..不这么干我觉得代码量能到3kb
#include <bits/stdc++.h> using namespace std ; #define FOR( i , a , b ) for( int i = a ; i <= b ; i ++ )
#define copy( a , b ) memcpy( a , b , sizeof( a ) ) char c[ ][ ] , a[ ][ ] , ans[ ][ ] , t[ ][ ] ;
int n ; void turn() {
copy( t , c ) ;
FOR( i , , n ) FOR( j , , n ) c[ i ][ n - j + ] = t[ j ][ i ] ;
} bool check() {
FOR( i , , n ) FOR( j , , n ) if( c[ i ][ j ] != ans[ i ][ j ] ) return ;
return ;
} void turn2() {
copy( t , c ) ;
FOR( i , , n ) FOR( j , , n ) c[ i ][ n - j + ] = t[ i ][ j ] ;
} int main() {
scanf( "%d" , &n ) ;
FOR( i , , n ) scanf( "%s" , a[ i ] + ) ;
FOR( i , , n ) scanf( "%s" , ans[ i ] + ) ;
copy( c , a ) ; turn() ;
if( check() ) { return puts( "" ) , ; }
copy( c , a ) ; FOR( i , , ) { turn() ; }
if( check() ) { return puts( "" ) , ; }
copy( c , a ) ; FOR( i , , ) { turn() ; }
if( check() ) { return puts( "" ) , ; }
copy( c , a ) ; turn2() ;
if( check() ) { return puts( "" ) , ; }
copy( c , a ) ; turn2() ;
FOR( i , , ) { turn() ; if( check() ) { return puts( "" ) , ; } }
copy( c , a ) ;
if( check() ) { return puts( "" ) , ; }
return puts( "" ) , ;
}
[USACO1.2]回文平方数 Palindromic Squares
坑点就是输出的时候，当前数输出要是B进制数
然后就是进制转换的模拟了
#include <bits/stdc++.h> using namespace std ; int n , s ;
int l , t ;
int a[ ] , c[ ] ; bool check( int x , int k ) {
l = , t = x ;
while( t ) {
a[ ++ l ] = t % k ;
t /= k ;
}
for( int i = , j = l ; i <= l / ; i ++ , j -- ) {
if( a[ i ] != a[ j ] ) return ;
}
return ;
} int main() {
scanf( "%d" , &n ) ;
for( int i = ; i <= ; i ++ ) {
if( check( i * i , n ) ) {
int t = i , len = ;
while( t ) {
c[ ++ len ] = t % n ;
t /= n ;
}
for( int i = len ; i ; i -- ) {
if( c[ i ] >= ) putchar( c[ i ] - + 'A' ) ;
else printf( "%d" , c[ i ] ) ;
}
putchar( ' ' ) ;
for( int i = l ; i ; i -- ) {
if( a[ i ] >= ) putchar( a[ i ] - + 'A' ) ;
else printf( "%d" , a[ i ] ) ;
}
puts( "" ) ;
}
}
return ;
}
[USACO1.2]双重回文数 Dual Palindromes
和上一题差不多。
觉得这题更简单点...
#include <bits/stdc++.h> using namespace std ; int n , s ;
int a[ ] ; bool check( int x , int k ) {
int l = , t = x ;
while( t ) {
a[ ++ l ] = t % k ;
t /= k ;
}
for( int i = , j = l ; i <= l / ; i ++ , j -- ) {
if( a[ i ] != a[ j ] ) return ;
}
return ;
} int main() {
scanf( "%d%d" , &n , &s ) ;
for( int tot = , i = s + ; tot < n ; i ++ ) {
int cnt = ;
for( int j = ; j <= && cnt < ; j ++ ) {
if( check( i , j ) ) cnt ++ ;
}
if( cnt >= ) {
printf( "%d\n" , i ) ;
tot ++ ;
}
}
return ;
}
[USACO1.3]混合牛奶 Mixing Milk
随便贪心一下的样子
太久了忘记了
可能码风会很丑
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll int
#define maxn 5010
#define inf 1<<30
#define mt(x,y) memset(x,y,sizeof(x))
#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y
#define abs(x) x>0?x:-x
#define mod 10000007
inline void read(ll &x){x=;ll f=;char c=getchar();while(c<''||c>''){if(c=='-')f=-f;c=getchar();}while(c>=''&&c<=''){x=x*+c-'';c=getchar();}x*=f;}
using namespace std;
/************************************************************************/
//struct edge{ll u,w,v;}e[maxn];
struct node{ll a,b;}a[maxn];
ll n,m,ans=;
/************************************************************************************************************************************/
//inline void add(ll u,ll v,ll w){e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}
//inline void prime(ll x){mt(prime,1);prime[0]=0;prime[1]=0;for(ll i=2;i<=x;i++){if(prime[i])for(ll j=i+i;j<=x;j+=i)prime[j]=0;}}
//inline ll power(ll a,ll b){ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans;}
//inline ll log(ll x){ll p=1,ans=0;while(p<=x){ans++;p<<=1;}return ans;}
inline bool cmp(node a,node b){return a.a<b.a;}
/************************************************************************************************************************************/
int main(){
read(n);read(m);
for(ll i=;i<=m;i++){
read(a[i].a);read(a[i].b);
}
sort(a+,a+m+,cmp);
for(ll i=;i<=m;i++){
if(a[i].b<n){
n-=a[i].b;
ans+=a[i].a*a[i].b;
}else {
ans+=n*a[i].a;
break;
}
}
printf("%d",ans);
return ;
}
[USACO1.3]修理牛棚 Barn Repair
因为最多只能断$m$个点，所以把每个牛棚之间的差值求出来，然后从大到小断掉$m$个点就好
#include <bits/stdc++.h> using namespace std ; #define ll long long
#define N 55010 int n , m , s ;
int a[ N ] , c[ N ] ; bool cmp( int a , int b ) {
return a > b ;
} int main() {
scanf( "%d%d%d" , &m , &s , &n ) ;
for( int i = ; i <= n ; i ++ ) scanf( "%d" , &a[ i ] ) ;
sort( a + , a + n + ) ;
for( int i = ; i <= n ; i ++ ) c[ i - ] = a[ i ] - a[ i - ] ;
sort( c + , c + n + , cmp ) ;
int ans = a[ n ] - a[ ] + ;
for( int i = ; i < m && i < n ; i ++ ) {
ans -= c[ i ] - ;
}
printf( "%d\n" , ans ) ;
}
[USACO1.3]牛式 Prime Cryptarithm
模拟一下竖式运算就行了...
但是好恶心啊...
#include <bits/stdc++.h> using namespace std ; #define N 200010 int n ;
int a[ N ] ;
bool vis[ N ] ;
int ans = ; bool check_1( int x ) {
int w[ ] , l = ;
while( x ) {
w[ ++ l ] = x % ;
x /= ;
}
for( int i = ; i <= l ; i ++ ) {
if( !vis[ w[ i ] ] ) return ;
}
return ;
} void check( int x , int y ) {
if( check_1( x ) ) return ;
if( check_1( y ) ) return ;
int w_1 = y % , w_2 = y / ;
if( w_1 * x >= || w_2 * x >= ) return ;
if( x * y >= ) return ;
if( check_1( w_1 * x ) ) return ;
if( check_1( w_2 * x ) ) return ;
if( check_1( x * y ) ) return ;
ans ++ ;
} int main() {
scanf( "%d" , &n ) ;
for(int i = ; i <= n ; i ++ ) {
scanf( "%d" , &a[ i ] ) ;
vis[ a[ i ] ] = ;
}
for( int i = ; i <= ; i ++ ) {
for( int j = ; j <= ; j ++ ) {
check( i , j ) ;
}
}
printf( "%d\n" , ans ) ;
return ;
}
[USACO1.3]虫洞wormhole
用$dfs$枚举配对方案
然后再用$dfs$判一下这种方案能不能走出环
然后注意要把坐标排序一下，不然可能会出现重复方案
#include <bits/stdc++.h> using namespace std ; #define N 5010 int n ;
struct node {
int x , y ;
} a[ N ] ;
int b[ N ] ; bool cmp( node a , node b ) {
if( a.y == b.y ) return a.x < b.x ;
return a.y < b.y ;
} bool find( int num , int now , int s , int p ) {
if( num != && now == s && p == ) return ;
if( !p ) {
if( a[ now ].y == a[ now + ].y ) return find( num + , now + , s , ) ;
else return ;
}
if( p ) return find( num + , b[ now ] , s , ) ;
} bool check() {
for( int j = ; j <= n ; j ++ ) {
if( find( , j , j , ) ) return ;
}
return ;
} int ans = ; void dfs( int x ) {
if( x == n + ) {
if( check() ) ans ++ ;
return ;
}
if( b[ x ] == ) {
for( int i = x + ; i <= n ; i ++ ) {
if( b[ i ] == ) {
b[ i ] = x ; b[ x ] = i ;
dfs( x + ) ;
b[ i ] = ; b[ x ] = ;
}
}
}
if( b[ x ] != ) dfs( x + ) ;
} int main() {
scanf( "%d" , &n ) ;
for( int i = ; i <= n ; i ++ ) {
scanf( "%d%d" , &a[ i ].x , &a[ i ].y ) ;
}
sort( a + , a + n + , cmp ) ;
dfs( ) ;
printf( "%d\n" , ans ) ;
return ;
}
[USACO1.3]滑雪课程设计Ski Course Design
枚举最后的最低高度，然后按题意算出每个山峰的贡献就好
对于每个最低高度取个$min$
#include <bits/stdc++.h> using namespace std ; #define N 5010 int n ;
int a[ N ] ; int main() {
scanf( "%d" , &n ) ;
for( int i = ; i <= n ; i ++ ) scanf( "%d" , &a[ i ] ) ;
sort( a + , a + n + ) ;
int ans = ;
for( int cnt = ; cnt < ; cnt ++ ) {
int sum = ;
for( int i = ; i <= n ; i ++ ) {
if( a[ i ] < cnt ) sum += ( cnt - a[ i ] ) * ( cnt - a[ i ] ) ;
else {
if( a[ i ] > cnt + ) {
sum += ( a[ i ] - ( cnt + ) ) * ( a[ i ] - ( cnt + ) ) ;
}
}
}
ans = min( ans , sum ) ;
}
printf( "%d\n" , ans ) ;
}
[USACO1.3]号码锁 Combination Lock
直接枚举...
然后两个号码分开来匹配就好了
注意是环形所以要多判一下
#include <bits/stdc++.h> using namespace std ; #define N 5010 int n ;
int a[ ] , b[ ] , c[ ] ;
int ans = ; int check() {
int sum = ;
for( int i = ; i < ; i ++ ) {
if( abs( a[ i ] - c[ i ] ) <= ) {
sum ++ ;
} else {
int x = min( a[ i ] , c[ i ] ) , y = max( a[ i ] , c[ i ] ) ;
if( n - y + x <= ) sum ++ ;
}
}
if( sum == ) return ;
sum = ;
for( int i = ; i < ; i ++ ) {
if( abs( b[ i ] - c[ i ] ) <= ) {
sum ++ ;
} else {
int x = min( b[ i ] , c[ i ] ) , y = max( b[ i ] , c[ i ] ) ;
if( n - y + x <= ) sum ++ ;
}
}
if( sum == ) return ;
return ;
} int main() {
scanf( "%d" , &n ) ;
for( int i = ; i < ; i ++ ) scanf( "%d" , &a[ i ] ) ;
for( int i = ; i < ; i ++ ) scanf( "%d" , &b[ i ] ) ;
for( int i = ; i <= n ; i ++ ) {
for( int j = ; j <= n ; j ++ ) {
for( int k = ; k <= n ; k ++ ) {
c[ ] = i ; c[ ] = j ; c[ ] = k ;
ans += check() ;
}
}
}
printf( "%d\n" , ans ) ;
}
[USACO1.4]等差数列 Arithmetic Progressions
一开始打了一个立方的暴力，拿了个55..
然后在题解的点醒下猛然发现可以直接枚举最后两个数，公差就出来了
枚举最后两个数可以剪掉一些枝，就是当最后一个数减掉n*公差小于0就直接跳掉了
#include <bits/stdc++.h> using namespace std ; #define N 1000100 int n , m ;
int a[ N ] , b[ N ] ;
struct node {
int x , y ;
} ans[ N ] ; bool cmp1( int a , int b ) {
return a > b ;
} bool cmp2( node a , node b ) {
if( a.y == b.y ) return a.x < b.x ;
return a.y < b.y ;
} int main() {
scanf( "%d%d" , &n , &m ) ;
int tot = ;
for( int i = ; i <= m ; i ++ ) {
for( int j = ; j <= m ; j ++ ) {
if( !b[ i * i + j * j ] ) a[ ++ tot ] = i * i + j * j ;
b[ i * i + j * j ] = ;
}
}
int cnt = ;
sort( a + , a + tot + , cmp1 ) ;
for( int i = ; i <= tot - n + ; i ++ ) {
for( int j = i + ; j <= tot - n + ; j ++ ) {
int c = a[ i ] - a[ j ] , now = a[ j ] , t = n - , flag = ;
if( now - t * c < ) continue ;
while( t ) {
t -- ;
now -= c ;
if( !b[ now ] ) { flag = ; break ; }
}
if( !flag ) continue ;
ans[ ++ cnt ].x = now , ans[ cnt ].y = c ;
}
}
if( !cnt ) return puts("NONE") , ;
sort( ans + , ans + cnt + , cmp2 ) ;
for( int i = ; i <= cnt ; i ++ ) {
printf( "%d %d\n" , ans[ i ].x , ans[ i ].y ) ;
}
return ;
}
[USACO1.4]母亲的牛奶 Mother's Milk
就是爆搜出每个状态。不过感觉$dfs$不是很好打就打了$bfs$
然后可以给每个状态编个号，可以大量简化代码
#include <bits/stdc++.h> using namespace std ; int a , b , c ;
int ans[ ] ;
int vis[ ][ ][ ] ;
int q[ ][ ] ; int main() {
scanf( "%d%d%d" , &a , &b , &c ) ;
vis[ ][ ][ c ] = ;
int l = , r = ;
q[ l ][ ] = , q[ l ][ ] = , q[ l ][ ] = c ;
ans[ c ] = ;
while( l != r ) {
for( int i = ; i < ; i ++ ) {
int xa = q[ l ][ ] , xb = q[ l ][ ] , xc = q[ l ][ ] ;
int w , now1 = i / , now2 = i % ;
// now1 从now1桶倒出
// now2 倒进now2桶
// 0,1,2 对应 a,b,c
if( now1 == now2 ) continue ;
if( now1 == ) { // 从1桶倒出
w = xa ;
if( now2 == ) { xb = min( q[ l ][ ] + w , b ) ; xa = max( xa - ( b - q[ l ][ ] ) , ) ; }
if( now2 == ) { xc = min( q[ l ][ ] + w , c ) ; xa = max( xa - ( c - q[ l ][ ] ) , ) ; }
}
if( now1 == ) { // 从2桶倒出
w = xb ;
if( now2 == ) { xa = min( q[ l ][ ] + w , a ) ; xb = max( xb - ( a - q[ l ][ ] ) , ) ; }
if( now2 == ) { xc = min( q[ l ][ ] + w , c ) ; xb = max( xb - ( c - q[ l ][ ] ) , ) ; }
}
if( now1 == ) {
w = xc ;
if( now2 == ) { xa = min( q[ l ][ ] + w , a ) ; xc = max( xc - ( a - q[ l ][ ] ) , ) ; }
if( now2 == ) { xb = min( q[ l ][ ] + w , b ) ; xc = max( xc - ( b - q[ l ][ ] ) , ) ; }
}
if( vis[ xa ][ xb ][ xc ] || !w ) continue ;
vis[ xa ][ xb ][ xc ] = ;
if( xa == ) ans[ xc ] = ;
q[ r ][ ] = xa , q[ r ][ ] = xb , q[ r ][ ] = xc ;
r ++ ;
if( r == ) r = ;
}
l ++ ;
if( l == ) l = ;
}
for( int i = ; i <= ; i ++ ) {
if( ans[ i ] ) printf( "%d " , i ) ;
}
return ;
}
[USACO1.5]数字三角形 Number Triangles
dp入门题
#include <iostream>
#include <cstring>
using namespace std;
int f[][],a[][];
int n;
int main(){
cin>>n;
memset(f,,sizeof(f));
memset(a,,sizeof(a));
for(int i=;i<=n;i++){
for(int j=;j<=i;j++){
cin>>a[i][j];
}
}
f[][]=a[][];
for(int i=;i<=n;i++){
for(int j=;j<=i;j++){
if(j==)f[i][j]=f[i-][j]+a[i][j];
else if(j==i)f[i][j]=f[i-][j-]+a[i][j];
else f[i][j]=max(f[i-][j],f[i-][j-])+a[i][j];
}
}
int ans=;
for(int i=;i<=n;i++){
ans=max(ans,f[n][i]);
}
cout<<ans<<endl;
return ;
}
[USACO1.5]回文质数 Prime Palindromes
其实这题正解应该是$dfs$构造出回文数来然后判断素数什么的
但是懒得写啊
所以就投机取巧一下
因为是回文素数，所以可以先判是否回文（在这题里面判断回文最大复杂度也就$O(16)$），不是就跳掉
用$O(\sqrt{n})$的时间判掉是不是素数
然后开个$O2$卡卡也就过去了
然而洛谷人才真的多
可以判掉上界，因为$1e8$里面的回文素数最大是$9989899$
所以可以直接大于这个数的上界砍掉
那么不开$O2$也能稳稳过掉了
#include <bits/stdc++.h> using namespace std ; int a , b ;
int num[ ] ; bool is_prime( int x ) {
int m = sqrt( x ) ;
for( int i = ; i <= m ; i ++ ) {
if( x % i == ) return ;
}
return ;
} bool check( int x ) {
int l = ;
while( x ) {
num[ ++ l ] = x % ;
x /= ;
}
for( int i = , j = l ; i <= l / ; i ++ , j -- ) {
if( num[ i ] != num[ j ] ) return ;
}
return ;
} int main() {
scanf( "%d%d" , &a , &b ) ;
if( a % == ) a ++ ;
if( b >= (int)1e8 ) b = ;
for( int i = a ; i <= b ; i += ) {
if( check( i ) && is_prime( i ) ) printf( "%d\n" , i ) ;
}
}
[USACO1.5]特殊的质数肋骨 Superprime Rib
这题随便搜一下就好了...
就是最高位不能是1和9注意判掉就行
#include <bits/stdc++.h> using namespace std ; int n ;
int ans[ ] ;
int num[ ] ;
int p[] = { , , , , , , } ; bool is_prime( int x ) {
int m = sqrt( x ) ;
for( int i = ; i <= m ; i ++ ) {
if( x % i == ) return ;
}
return ;
} bool check( int x ) {
int ans = , l = ;
for( int i = x ; i ; i -- ) {
ans += num[ i ] * l ;
l *= ;
}
if( is_prime( ans ) ) return ;
return ;
} int cnt = ; void print() {
int sum = , l = ;
for( int i = n ; i ; i -- ) {
sum += l * num[ i ] ;
l *= ;
}
ans[ ++ cnt ] = sum ;
} void dfs( int x ) {
if( x == n + ) {
print() ;
return ;
}
for( int i = ; i <= ; i ++ ) {
if( x == && ( i == || i == ) ) continue ;
num[ x ] = p[ i ] ;
if( x != && !check( x ) ) continue ;
dfs( x + ) ;
num[ x ] = ;
}
} int main() {
scanf( "%d" , &n ) ;
dfs( ) ;
sort( ans + , ans + cnt + ) ;
for( int i = ; i <= cnt ; i ++ ) printf( "%d\n" , ans[ i ] ) ;
}
城堡 The Castle
它让我考虑弃掉$usaco-training$了...
我$debug$了一天...，写了$4kb+$
就是搜索
第一二问随便写。我一开始直接写了一个联通块的染色
然后发现不能用邻接表不然没法求$3,4$问,于是重新码
然后搞3,4问差不多2,3h。。对着题解debug出来的
先处理墙在上面的情况，然后再处理墙在旁边的情况，注意顺序不能乱...
我就不知道他为什么不要直接弄个$SPJ$，或者是干脆不要方案啊......
这$4kb+$代码全都是血和泪...
#include <bits/stdc++.h>
using namespace std ;
const int dx[] = { , - , , } ;
const int dy[] = { - , , , } ;
int ans[ ] = { , , , } ;
int Ans = ;
struct node {
int u , d , l , r ;
} t[ ][ ] ;
int a[ ][ ] ;
int n , m ;
int tot = ;
int belong[ ][ ] ;
int num[ ] ;
bool check( int x , int y ) {
if( x < || x > n || y < || y > m ) return ;
if( belong[ x ][ y ] ) return ;
return ;
}
void dfs( int x , int y , int c ) {
belong[ x ][ y ] = c ;
num[ c ] ++ ;
for( int i = ; i < ; i ++ ) {
if( ! ( a[ x ][ y ] & ( << i ) ) ){
int nx = x + dx[ i ] , ny = y + dy[ i ] ;
if( check( nx , ny ) ) dfs( nx , ny , c ) ;
}
}
}
bool check_1( int x , int y ) {
if( num[ belong[ x ][ y ] ] + num[ belong[ x ][ y - ] ] > ans[ ] )
return ;
if( num[ belong[ x ][ y ] ] + num[ belong[ x ][ y - ] ] == ans[ ] && y - < ans[ ] )
return ;
if( num[ belong[ x ][ y ] ] + num[ belong[ x ][ y - ] ] == ans[ ] && y - == ans[ ] && x > ans[ ] )
return ;
return ;
}
bool check_2( int x , int y ) {
if( num[ belong[ x ][ y ] ] + num[ belong[ x - ][ y ] ] > ans[ ] )
return ;
if( num[ belong[ x ][ y ] ] + num[ belong[ x - ][ y ] ] == ans[ ] && y < ans[ ] )
return ;
if( num[ belong[ x ][ y ] ] + num[ belong[ x - ][ y ] ] == ans[ ] && y == ans[ ] && x > ans[ ] )
return ;
return ;
}
int main() {
scanf( "%d%d" , &m , &n ) ;
for( int i = ; i <= n ; i ++ ) {
for( int j = ; j <= m ; j ++ ) {
scanf( "%d" , &a[ i ][ j ] ) ;
int t1 = a[ i ][ j ] ;
if( t1 - >= ) t[ i ][ j ].d = , t1 -= ;
if( t1 - >= ) t[ i ][ j ].r = , t1 -= ;
if( t1 - >= ) t[ i ][ j ].u = , t1 -= ;
if( t1 - >= ) t[ i ][ j ].l = , t1 -= ;
}
}
for( int i = ; i <= n ; i ++ ) {
for( int j = ; j <= m ; j ++ ) {
if( belong[ i ][ j ] ) continue ;
dfs( i , j , ++ tot ) ;
}
}
for( int i = ; i <= tot ; i ++ ) Ans = max( Ans , num[ i ] ) ;
printf( "%d\n%d\n" , tot , Ans ) ;
for( int i = ; i <= n ; i ++ ) {
for( int j = ; j <= m ; j ++ ) {
if( t[ i ][ j ].l && belong[ i ][ j ] != belong[ i ][ j - ] ) {
if( check_1( i , j ) ) {
ans[ ] = num[ belong[ i ][ j ] ] + num[ belong[ i ][ j - ] ] ;
ans[ ] = i ; ans[ ] = j - ;
ans[ ] = 'E' ;
}
}
if( t[ i ][ j ].u && belong[ i ][ j ] != belong[ i - ][ j ] ) {
if( check_2( i , j ) ) {
ans[ ] = num[ belong[ i ][ j ] ] + num[ belong[ i - ][ j ] ] ;
ans[ ] = i ; ans[ ] = j ;
ans[ ] = 'N' ;
}
}
}
}
printf( "%d\n%d %d %c\n" , ans[ ] , ans[ ] , ans[ ] , ans[ ] ) ;
}顺序的分数 Ordered Fractions
这题随便做...
枚举分子和分母，判一下$gcd$
然后转成小数排序输出就可以了
分母不能为0
#include <bits/stdc++.h> using namespace std ; int n , cnt = ;
struct node {
double val ;
int x , y ;
} fac[ ] ; int gcd( int a , int b ) {
if( b == ) return a ;
return gcd( b , a % b ) ;
} bool cmp( node a , node b ) {
return a.val < b.val ;
} int main() {
scanf( "%d" , &n ) ;
for( int i = ; i <= n ; i ++ ) {
for( int j = ; j <= i ; j ++ ) {
if( gcd( j , i ) == ) {
fac[ ++ cnt ].x = j ;
fac[ cnt ].y = i ;
fac[ cnt ].val = (double)fac[ cnt ].x / (double)fac[ cnt ].y ;
}
}
}
sort( fac + , fac + cnt + , cmp ) ;
for( int i = ; i <= cnt ; i ++ ) {
printf( "%d/%d\n" , fac[ i ].x , fac[ i ].y ) ;
}
return ;
}
三值的排序 Sorting a Three-Valued Sequence
这题有点思维..
考虑最后得到的序列
一定是$1112223333$这样子的
那么就可以把最终序列划分成三段
对于出现在1,2段的3，显然只要一次交换就能换到第三段那里
然后对于1出现在2的情况，2出现在1的情况，也是要交换的，不过对于这两种情况只需要取个$max$就好了，因为两者是可以互相抵消的
#include <bits/stdc++.h> using namespace std ; int n ;
int a[ ] ;
int cnt[ ] , num[ ] ; int main() {
scanf( "%d" , &n ) ;
for( int i = ; i <= n ; i ++ )
scanf( "%d" , &a[ i ] ) , cnt[ a[ i ] ] ++ ;
for( int i = ; i <= cnt[ ] + cnt[ ] ; i ++ ) {
if( a[ i ] == ) num[ ] ++ ;
else if( a[ i ] == && i <= cnt[ ] ) num[ ] ++ ;
else if( a[ i ] == && i > cnt[ ] ) num[ ] ++ ;
}
printf( "%d\n" , num[ ] + max( num[ ] , num[ ] ) ) ;
}
健康的荷斯坦奶牛 Healthy Holsteins
数据范围很小，所以直接爆搜所有状态即可
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstdlib> using namespace std ; #define N 30 int v , n ;
int t[ N ] ;
int a[ N ][ N ] ;
int num[ N ] ;
int now[ N ] ;
int ans = , Ans[ N ] ; void dfs( int x , int p ) {
bool flag = ;
now[ p ] = x ;
for( int i = ; i <= v ; i ++ ) {
num[ i ] += a[ x ][ i ] ;
if( num[ i ] < t[ i ] ) flag = ;
}
if( flag ) {
if( p < ans ) {
ans = p ;
for( int i = ; i <= p ; i ++ ) {
Ans[ i ] = now[ i ] ;
}
}
return ;
}
for( int i = x + ; i <= n ; i ++ ) {
dfs( i , p + ) ;
for( int k = ; k <= v ; k ++ ) {
num[ k ] -= a[ i ][ k ] ;
}
}
} int main() {
scanf( "%d" , &v ) ;
for( int i = ; i <= v ; i ++ ) scanf( "%d" , &t[ i ] ) ;
scanf( "%d" , &n ) ;
for( int i = ; i <= n ; i ++ ) {
for( int j = ; j <= v ; j ++ ) {
scanf( "%d" , &a[ i ][ j ] ) ;
}
}
for( int i = ; i <= n ; i ++ ) {
memset( now , , sizeof( now ) ) ;
memset( num , , sizeof( num ) ) ;
dfs( i , ) ;
}
printf( "%d " , ans ) ;
for( int i = ; i <= ans ; i ++ ) printf( "%d " , Ans[ i ] ) ;
puts( "" ) ;
return ;
}
海明码 Hamming Codes
可以有前导零，所以直接从1开始枚举就好了...而0一定在答案里面
对于是否符合要求，直接暴力判断
#include <bits/stdc++.h> using namespace std ; int n , b , d ;
int ans[ ] ; int main() {
scanf( "%d%d%d" , &n , &b , &d ) ;
int tot = ;
ans[ ] = ;
for( int i = ; tot < n ; i ++ ) {
bool flag = ;
for( int j = ; j <= tot ; j ++ ) {
int sum = ;
for( int k = ; k >= ; k -- ) {
if( ( ( ans[ j ] >> k ) & ) ^ ( ( i >> k ) & ) )
sum ++ ;
}
if( sum < d ) { flag = ; break ; }
}
if( flag == ) {
ans[ ++ tot ] = i ;
}
}
for( int i = ; i <= n ; i ++ ) {
printf( "%d " , ans[ i ] ) ;
if( !( i % ) ) putchar( '\n' ) ;
}
return ;
}
序言页码 Preface Numbering
打表题...感觉没啥意义，所以就直接抄了$lmh$大爷的表就跳下一题了
#include <bits/stdc++.h>
using namespace std ;
const char *A[]={" ", "I ", "II ", "III ", "IV ", "V ", "VI ", "VII ", "VIII ", "IX "};
const char *B[]={" ", "X ", "XX ", "XXX ", "XL ", "L ", "LX ", "LXX ", "LXXX ", "XC "};
const char *C[]={" ", "C ", "CC ", "CCC ", "CD ", "D ", "DC ", "DCC ", "DCCC ", "CM "};
const char *D[]={" ", "M ", "MM ", "MMM "};
const char *S="IVXLCDM ";
int n ;
int c[ ] ;
int main() {
scanf( "%d" , &n ) ;
for( int i = ; i <= n ; i ++ ) {
int tmp = i ;
for( int j = ; A[ tmp % ][ j ] ^ ' ' ; j ++ ) c[ A[ tmp % ][ j ] ] ++ ;
tmp /= ;
for( int j = ; B[ tmp % ][ j ] ^ ' ' ; j ++ ) c[ B[ tmp % ][ j ] ] ++ ;
tmp /= ;
for( int j = ; C[ tmp % ][ j ] ^ ' ' ; j ++ ) c[ C[ tmp % ][ j ] ] ++ ;
tmp /= ;
for( int j = ; D[ tmp % ][ j ] ^ ' ' ; j ++ ) c[ D[ tmp % ][ j ] ] ++ ;
tmp /= ;
}
for( int i = ; S[ i ] ^ ' ' ; i ++ ) if( c[ S[ i ] ] ) printf( "%c %d\n" , S[ i ] , c[ S[ i ] ] ) ;
}循环数 Runaround Numbers
直接从$m$向后枚举，感觉效率过不去但是实际上过得去...
#include <bits/stdc++.h> using namespace std ; int m ;
int a[ ] , len , t[ ] ;
int vis[ ] ; bool check() {
int now = ;
for( int i = ; i <= len ; i ++ ) {
if( vis[ a[ now ] ] || a[ now ] == ) return ;
vis[ a[ now ] ] ++ ;
now = ( now + a[ now ] - ) % len + ;
}
if( now != ) return ;
return ;
} int main() {
scanf( "%d" , &m ) ;
while( ) {
int x = ++m ;
len = ;
while( x ) {
t[ ++ len ] = x % ;
x /= ;
}
for( int i = ; i <= len ; i ++ ) a[ i ] = t[ len - i + ] ;
memset( vis , , sizeof( vis ) ) ;
if( check() ) return printf( "%d" , m ) , ;
}
}
派对灯 Party Lamps
有点恶心，貌似是分类讨论然后模拟
后面再补
最长前缀 Longest Prefix
因为给的那几个用来匹配模式串的串很小，所以直接暴力dp暴力check即可
#include <bits/stdc++.h> #define ll long long
#define inf 0x3f3f3f3f
#define il inline #define in1(a) a=read()
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
#define out(a) printf( "%d" , a )
#define outn(a) out(a),putchar('\n') #define I_int int
inline I_int read() { I_int x = , f = ; char c = getchar() ;
while( c < '' || c > '' ) {
if( c == '-' ) f = - ;
c = getchar() ;
}
while( c >= '' && c <= '' ) {
x = (x << ) + (x << ) + c - ;
c = getchar() ;
}
return x * f ;
}
#undef I_int using namespace std ; #define N 1000100 struct node {
int len ;
char ch[ ] ;
} a[ N ] ;
int n , m , f[ N ] ;
char s[ N ] , ch[ N ] ; int main() {
scanf( "%s" , ch+ ) ;
while( ch[ ] != '.' ) {
a[ ++ n ].len = strlen( ch+ ) ;
for( int i = , len = strlen( ch+ ) ; i <= len ; i ++ ) {
a[ n ].ch[ i ] = ch[ i ] ;
}
scanf( "%s" , ch+ ) ;
}
int m = ;
while( scanf( "%s" , ch+ ) == ) {
int len = strlen( ch+ ) ;
for( int i = ; i <= len ; i ++ ) {
s[ i + m ] = ch[ i ] ;
}
m += len ;
}
f[ ] = ;
for( int i = ; i <= m ; i ++ ) {
for( int j = ; j <= n ; j ++ ) {
if( i + a[ j ].len <= m && f[ i ] ) {
bool flag = ;
for( int k = i + ; k <= a[ j ].len + i ; k ++ ) {
if( s[ k ] != a[ j ].ch[ k - i ] ) { flag = ; break ; }
}
if( flag ) continue ;
f[ i + a[ j ].len ] = ;
}
}
}
for( int i = m ; i >= ; i -- ) {
if( f[ i ] ) return outn( i ) , ;
}
}
奶牛家谱 Cow Pedigrees
关于这道题，做法很多..
我写了一个比较麻烦的做法，复杂度也很低$O(n^4)$
$f[i][j][k]$表示前$i$层放了$j$个节点，下一层要放$k$个节点的最优解
转移的方案可以利用组合数来算下一层能放的不同方案
但是不知道为什么我推杨辉三角出锅，于是使用了一下题解对组合数的求法。其实就是用组合数的另一个公式来推）
采用这种方法的话完全可以删掉C数组。我只是懒得删....
转移懒得再打一遍了。详见代码
#include <bits/stdc++.h> using namespace std ; #define N 510
#define mod 9901 int c[ N ][ N ] ;
int n , m ;
int f[ N ][ N ][ N ] ;
//前i层，前j个节点，这层放了k个节点 int power( int a , int b ) {
int ans = , base = a ;
while( b ) {
if( b& ) ans = ans * base % mod ;
base = base * base % mod ;
b >>= ;
}
return ans % mod ;
} int fac[N],ifac[N]; int main() {
scanf( "%d%d" , &n , &m ) ; fac[]=;
for( int i = ; i <= ; i ++ ) fac[i]=fac[i-]*i%mod;
for( int i = ; i <= ; i ++ ) ifac[ i ] = power( fac[ i ] , mod - ) % mod ;
for( int i = ; i <= ; i ++ )
for( int j = i ; j <= ; j ++ )
c[ i ][ j ] = fac[ j ] * ifac[ i ] % mod * ifac[ j - i ] % mod ; f[][][]=; f[][][]=;
for( int t = ; t <= m- ; t ++ ) {
for( int i = ; i < n ; i += ) { //当前层节点数
for( int j = (t<<1ll)- ; j < n ; j += ) { // 总点数
for( int k = ; k <= (i<<1ll) ; k+= ) { // 下一层放l个点
if( j + k > n ) break ;
f[t+][j+k][k]=(f[t+][j+k][k]+f[t][j][i]*c[k/][i]%mod)%mod;
}
}
}
} int ans = ;
for( int i = ; i <= ; i += )
ans = ( ans + f[ m ][ n ][ i ] ) % mod ;
printf( "%d\n" , ans ) ;
}
[USACO5.3]校园网Network of Schools
忽然写到这题就想起来我这坑弃了好久...
补一下坑
把图缩成个有向无环图之后，对于第一问显然只需要给0入度的点提供。然后第二问求要加多少条边这个缩点后的图能变成一个环，其实就是0出度和0入度取个max。注意对于缩点完后只有1个点的情况，第二问的答案是0
#include <cstring>
#include <algorithm>
#include <cstdio> #define ll long long
#define inf 0x3f3f3f3f
#define il inline namespace io { #define in(a) a=read()
#define out(a) write(a)
#define outn(a) out(a),putchar('\n') #define I_int int
inline I_int read() {
I_int x = , f = ; char c = getchar() ;
while( c < '' || c > '' ) { if( c == '-' ) f = - ; c = getchar() ; }
while( c >= '' && c <= '' ) { x = x * + c - '' ; c = getchar() ; }
return x * f ;
}
char F[ ] ;
inline void write( I_int x ) {
if( x == ) { putchar( '' ) ; return ; }
I_int tmp = x > ? x : -x ;
if( x < ) putchar( '-' ) ;
int cnt = ;
while( tmp > ) {
F[ cnt ++ ] = tmp % + '' ;
tmp /= ;
}
while( cnt > ) putchar( F[ -- cnt ] ) ;
}
#undef I_int }
using namespace io ; using namespace std ; #define N 100010 int n , in[N] , out[N] ;
int head[N] , cnt ;
struct edge {
int to , nxt;
} e[N<<];
int dfn[N] , low[N] , vis[N] , st[N] , bl[N] , tim , num , top; void ins(int u , int v) {
e[++cnt] = (edge) {v , head[u]} ;
head[u] = cnt ;
} void tarjan(int u) {
dfn[u] = low[u] = ++ tim ;
vis[u] = ; st[++top] = u ;
for(int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].to ;
if(!dfn[v]) {
tarjan(v) ;
low[u] = std::min(low[u] , low[v]) ;
} else if(vis[v]) low[u] = std::min(low[u] , dfn[v]) ;
}
if(dfn[u] == low[u]) {
int x ; num ++ ;
do {
x = st[top --] ;
vis[x] = ;
bl[x] = num ;
}while(x != u) ;
}
} int main() {
n = read() ;
for(int i = ; i <= n ; i ++) {
int x = read() ;
while(x != ) {
ins(i , x) ;
x = read() ;
}
}
for(int i = ; i <= n ; i ++) {
if(!dfn[i]) tarjan(i) ;
}
for(int u = ; u <= n ; u ++) {
for(int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].to ;
if(bl[u] != bl[v]) in[bl[v]] ++ , out[bl[u]] ++ ;
}
}
int ans1 = , ans2 = ;
for(int i = ; i <= num ; i ++) {
if(!in[i]) ans1 ++ ;
if(!out[i]) ans2 ++ ;
}
if(num == ) outn() , outn() ;
else outn(ans1) , outn(std::max(ans1 , ans2)) ;
return ;
}