Luogu USACO Training 刷水记录

开个坑记录一下刷USACO的Training的记录

可能会随时弃坑

只有代码和做法简述

可能没有做法简述

[USACO1.1]你的飞碟在这儿Your Ride Is He…

模拟，细节已忘

#include<iostream>  
#include<cstdio>
#include<cstring>
using namespace std;  
char s1[100],s2[100];
int main()  
{  
    int ss1=1,ss2=1;  
    scanf("%s",&s1);
    scanf("%s",&s2);
    int len1=strlen(s1),len2=strlen(s2);
    for(int i=0;i<len1;i++)  
      ss1*=s1[i]-64;
    for(int i=0;i<len2;i++)  
      ss2*=s2[i]-64;  
    int l1=ss1%47,l2=ss2%47;
    if(l1==l2) 
      cout<<"GO"<<endl;  
    else 
      cout<<"STAY"<<endl;
    return 0;  
}

View Code

[USACO1.1]贪婪的送礼者Greedy Gift Givers

模拟，用map减少代码量

#include <iostream>
#include <string>
#include <cstdio>
#include <map>

using namespace std ;

string s[ 100 ] , ch , s1 ; 
int n ;
map<string,int> mp ;

int main() {
    cin >> n ;
    for( int i = 1 ; i <= n ; i ++ ) cin >> s[ i ] , mp[ s[ i ] ] = 0 ;
    for( int i = 1 ; i <= n ; i ++ ) {
        int val , m  ;
        cin >> ch >> val >> m ;
        if( m != 0 ) val /= m ;
        mp[ ch ] -= val * m ;
        for( int i = 1 ; i <= m ; i ++ ) {
            cin >> s1 ;
            mp[ s1 ] +=  val ;
        }
    }
    for( int i = 1 ; i <= n ; i ++ ) {
        cout << s[ i ] << " " << mp[ s[ i ] ] << endl ;
    }
}

View Code

[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=3;   
    int dayOfMonth[12]={31,31,28,31,30,31,30,31,31,30,31,30};
    int result[7]={0};          
    cin>>n;
    for(year=1900;year<1900+n;++year){
        if(year%400==0||(year%100!=0&&year%4==0)) dayOfMonth[2]=29; 
        for(month=0;month<12;++month){
            last=(last+dayOfMonth[month])%7;
            result[last]++;
        }
        dayOfMonth[2]=28;
    }
    for(i=0;i<6;++i) cout<<result[(i+6)%7]<<' '; 
    cout<<result[5]<<endl;
    return 0;
}

View Code

[USACO1.1]坏掉的项链Broken Necklace

暴力模拟，细节已忘

#include <cstdio>
using namespace std;
int n,ans=-1;char a[1500];
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=0;
    for(int i=x;i;i--){
        if(a[i]==c)sum++;
        else if(a[i]=='w')sum++;
        else break;
    }
    c=a[x+1];
    for(int i=x+1;i<=3*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+1);
    for(int i=1;i<=n;i++){
        a[i+n]=a[i];a[i+n+n]=a[i];
    }
    for(int i=n;i<=2*n;i++){
        if(a[i]==a[i+1])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==-1)ans=n;
    printf("%d\n",ans);
    return 0;
}

View Code

[USACO1.2]命名那个数字 Name That Number

看不懂。这题有毒，用的题解的check

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std ;

char ft[10][4]={{},{},"ABC","DEF","GHI","JKL","MNO","PRS","TUV","WXY"};
string s[ 10000 ] ; 
int n ;

int main() {
    while( cin >> s[ n ] ) n ++ ;
    string ch = s[ 0 ] ;
    n -- ;
    sort( s + 1 , s + n + 1 ) ;
    bool check = 1 ;
    for( int i = 1 ; i <= n ; i ++ ) {
        bool ok = ( s[ i ].length() == ch.length() ) ;
        for( int j = 0 ; j < s[ i ].length() ; j ++ ) {
            char c=s[ i ][ j ] ;
            ok = ok & (c==ft[ch[j]-'0'][0] || c==ft[ch[j]-'0'][1] || c==ft[ch[j]-'0'][2]);
        }
        if( ok ) {
            cout << s[ i ] << endl ;
            check = 0 ;
        }
    }
    if( check ) cout << "NONE\n" ;
    return 0 ;
}

View Code

[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 = 0 ;
    for( int i = 1 , l , r ; i <= n ; i ++ ) {
        scanf( "%d%d" , &l , &r ) ;
        c[ l ] ++ ; c[ r ] -- ;
        s = min( s , l ) ;
        t = max( t , r - 1 ) ;
    }
    int ans[ 2 ] = { 0 };
    int ch = 1 , now = s ;
    t ++ ; 
    for( int i = s ; i <= t ; i ++ ) {
        c[ i ] = c[ i - 1 ] + c[ i ] ;
        int x = c[ i ] != 0 ;
        if( x != ch || i == t ) {
            ans[ ch ] = max( ans[ ch ] , i - now ) ;
            now = i ;
            ch ^= 1 ;
        }
    }
    printf( "%d %d\n" , ans[ 1 ] , ans[ 0 ] ) ;
    return 0 ;
}

View Code

[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[ 20 ][ 20 ] , a[ 20 ][ 20 ] , ans[ 20 ][ 20 ] , t[ 20 ][ 20 ] ;
int n ;

void turn() {
    copy( t , c ) ;
    FOR( i , 1 , n ) FOR( j , 1 , n ) c[ i ][ n - j + 1 ] = t[ j ][ i ] ;
}

bool check() {
    FOR( i , 1 , n ) FOR( j , 1 , n ) if( c[ i ][ j ] != ans[ i ][ j ] ) return 0 ;
    return 1 ;
}

void turn2() {
    copy( t , c ) ;
    FOR( i , 1 , n ) FOR( j , 1 , n ) c[ i ][ n - j + 1 ] = t[ i ][ j ] ;
}

int main() {
    scanf( "%d" , &n ) ;
    FOR( i , 1 , n ) scanf( "%s" , a[ i ] + 1 ) ;
    FOR( i , 1 , n ) scanf( "%s" , ans[ i ] + 1 ) ;
    copy( c , a ) ; turn() ;
    if( check() ) { return puts( "1" ) , 0 ; } 
    copy( c , a ) ; FOR( i , 1 , 2 ) { turn() ; }
    if( check() ) { return puts( "2" ) , 0 ; }
    copy( c , a ) ; FOR( i , 1 , 3 ) { turn() ; }
    if( check() ) { return puts( "3" ) , 0 ; } 
    copy( c , a ) ; turn2() ; 
    if( check() ) { return puts( "4" ) , 0 ; }
    copy( c , a ) ; turn2() ;
    FOR( i , 1 , 3 ) { turn() ; if( check() ) { return puts( "5" ) , 0 ; } }
    copy( c , a ) ;
    if( check() ) { return puts( "6" ) , 0 ; } 
    return puts( "7" ) , 0 ;
}

View Code

[USACO1.2]回文平方数 Palindromic Squares

坑点就是输出的时候，当前数输出要是B进制数

然后就是进制转换的模拟了

#include <bits/stdc++.h>

using namespace std ;

int n , s ;
int l , t ;
int a[ 10000000 ] , c[ 1000000 ] ;

bool check( int x , int k ) {
    l = 0 , t = x ;
    while( t ) {
        a[ ++ l ] = t % k ;
        t /= k ;
    }
    for( int i = 1 , j = l ; i <= l / 2 ; i ++ , j -- ) {
        if( a[ i ] != a[ j ] ) return 0 ;
    }
    return 1 ;
}

int main() {
    scanf( "%d" , &n ) ;
    for( int i = 1 ; i <= 300 ; i ++ ) {
        if( check( i * i , n ) ) {
            int t = i , len = 0 ;
            while( t ) {
                c[ ++ len ] = t % n ;
                t /= n ;
            }
            for( int i = len ; i ; i -- ) {
                if( c[ i ] >= 10 ) putchar( c[ i ] - 10 + 'A' ) ;
                else printf( "%d" , c[ i ] ) ;
            }
            putchar( ' ' ) ;
            for( int i = l ; i ; i -- ) {
                if( a[ i ] >= 10 ) putchar( a[ i ] - 10 + 'A' ) ;
                else printf( "%d" , a[ i ] ) ;
            }
            puts( "" ) ;
        }
    }
    return 0 ;
}

View Code

[USACO1.2]双重回文数 Dual Palindromes

和上一题差不多。

觉得这题更简单点...

#include <bits/stdc++.h>

using namespace std ;

int n , s ;
int a[ 10000000 ] ;

bool check( int x , int k ) {
    int l = 0 , t = x ;
    while( t ) {
        a[ ++ l ] = t % k ;
        t /= k ;
    }
    for( int i = 1 , j = l ; i <= l / 2 ; i ++ , j -- ) {
        if( a[ i ] != a[ j ] ) return 0 ;
    }
    return 1 ;
}

int main() {
    scanf( "%d%d" , &n , &s ) ;
    for( int tot = 0 , i = s + 1 ; tot < n ; i ++ ) {
        int cnt = 0 ;
        for( int j = 2 ; j <= 10 && cnt < 2 ; j ++ ) {
            if( check( i , j ) ) cnt ++ ;
        }
        if( cnt >= 2 ) {
            printf( "%d\n" , i ) ;
            tot ++ ;
        }
    }
    return 0 ;
}

View Code

[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=0;ll f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';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=0;
/************************************************************************************************************************************/
//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=1;i<=m;i++){
        read(a[i].a);read(a[i].b);
    }
    sort(a+1,a+m+1,cmp);
    for(ll i=1;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 0;
}

View Code

[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 = 1 ; i <= n ; i ++ ) scanf( "%d" , &a[ i ] ) ;
    sort( a + 1 , a + n + 1 ) ;
    for( int i = 2 ; i <= n ; i ++ ) c[ i - 1 ] = a[ i ] - a[ i - 1 ] ;
    sort( c + 1 , c + n + 1 , cmp ) ;
    int ans = a[ n ] - a[ 1 ] + 1 ;
    for( int i = 1 ; i < m && i < n ; i ++ ) {
        ans -= c[ i ] - 1 ;
    }
    printf( "%d\n" , ans ) ;
}

View Code

[USACO1.3]牛式 Prime Cryptarithm

模拟一下竖式运算就行了...

但是好恶心啊...

#include <bits/stdc++.h>

using namespace std ;

#define N 200010

int n ;
int a[ N ] ;
bool vis[ N ] ;
int ans = 0 ;

bool check_1( int x ) {
    int w[ 100 ] , l = 0 ;
    while( x ) {
        w[ ++ l ] = x % 10 ;
        x /= 10 ;
    }
    for( int i = 1 ; i <= l ; i ++ ) {
        if( !vis[ w[ i ] ] ) return 1 ;
    }
    return 0 ;
}

void check( int x , int y ) {
    if( check_1( x ) ) return ;
    if( check_1( y ) ) return ;
    int w_1 = y % 10 , w_2 = y / 10 ;
    if( w_1 * x >= 1000 || w_2 * x >= 1000 ) return ;
    if( x * y >= 10000 ) 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 = 1 ; i <= n ; i ++ ) {
        scanf( "%d" , &a[ i ] ) ;
        vis[ a[ i ] ] = 1 ;
    }
    for( int i = 100 ; i <= 999 ; i ++ ) {
        for( int j = 10 ; j <= 99 ; j ++ ) {
            check( i , j ) ;
        }
    }
    printf( "%d\n" , ans ) ;
    return 0 ;
}

View Code

[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 != 1 && now == s && p == 1 ) return 1 ;
    if( !p ) {
        if( a[ now ].y == a[ now + 1 ].y ) return find( num + 1 , now + 1 , s , 1 ) ;
        else return 0 ;
    }
    if( p ) return find( num + 1 , b[ now ] , s , 0 ) ;
}

bool check() {
    for( int j = 1 ; j <= n ; j ++ ) {
        if( find( 1 , j , j , 1 ) ) return 1 ; 
    }
    return 0 ;
}

int ans = 0 ;

void dfs( int x ) {
    if( x == n + 1 ) {
        if( check() ) ans ++ ;
        return ;
    }
    if( b[ x ] == 0 ) {
        for( int i = x + 1 ; i <= n ; i ++ ) {
            if( b[ i ] == 0 ) {
                b[ i ] = x ; b[ x ] = i ;
                dfs( x + 1 ) ;
                b[ i ] = 0 ; b[ x ] = 0 ;
            }
        }
    }
    if( b[ x ] != 0 ) dfs( x + 1 ) ;
}

int main() {
    scanf( "%d" , &n ) ;
    for( int i = 1 ; i <= n ; i ++ ) {
        scanf( "%d%d" , &a[ i ].x , &a[ i ].y ) ;
    }
    sort( a + 1 , a + n + 1 , cmp ) ;
    dfs( 1 ) ;
    printf( "%d\n" , ans ) ;
    return 0 ; 
}

View Code

[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 = 1 ; i <= n ; i ++ ) scanf( "%d" , &a[ i ] ) ;
    sort( a + 1 , a + n + 1 ) ;
    int ans = 10000000 ;
    for( int cnt = 0 ; cnt < 84 ; cnt ++ ) {
        int sum = 0 ;
        for( int i = 1 ; i <= n ; i ++ ) {
            if( a[ i ] < cnt ) sum += ( cnt - a[ i ] ) * ( cnt - a[ i ] ) ;
            else {
                if( a[ i ] > cnt + 17 ) {
                    sum += ( a[ i ] - ( cnt + 17 ) ) * ( a[ i ] - ( cnt + 17 ) ) ;
                }
            } 
        }
        ans = min( ans , sum ) ;
    }
    printf( "%d\n" , ans ) ;
}

View Code

[USACO1.3]号码锁 Combination Lock

直接枚举...

然后两个号码分开来匹配就好了

注意是环形所以要多判一下

#include <bits/stdc++.h>

using namespace std ;

#define N 5010

int n ;
int a[ 3 ] , b[ 3 ] , c[ 3 ] ;
int ans = 0 ;

int check() {
    int sum = 0 ;
    for( int i = 0 ; i < 3 ; i ++ ) {
        if( abs( a[ i ] - c[ i ] ) <= 2 ) {
            sum ++ ;
        } else {
            int x = min( a[ i ] , c[ i ] ) , y = max( a[ i ] , c[ i ] ) ;
            if( n - y + x <= 2 ) sum ++ ;
        }
    }
    if( sum == 3 ) return 1 ;
    sum = 0 ;
    for( int i = 0 ; i < 3 ; i ++ ) {
        if( abs( b[ i ] - c[ i ] ) <= 2 ) {
            sum ++ ;
        } else {
            int x = min( b[ i ] , c[ i ] ) , y = max( b[ i ] , c[ i ] ) ;
            if( n - y + x <= 2 ) sum ++ ;
        }
    }
    if( sum == 3 ) return 1 ;
    return 0 ;
}

int main() {
    scanf( "%d" , &n ) ;
    for( int i = 0 ; i < 3 ; i ++ ) scanf( "%d" , &a[ i ] ) ;
    for( int i = 0 ; i < 3 ; i ++ ) scanf( "%d" , &b[ i ] ) ;
    for( int i = 1 ; i <= n ; i ++ ) {
        for( int j = 1 ; j <= n ; j ++ ) {
            for( int k = 1 ; k <= n ; k ++ ) {
                c[ 0 ] = i ; c[ 1 ] = j ; c[ 2 ] = k ;
                ans += check() ;
            }
        }
    }
    printf( "%d\n" , ans ) ;
}

View Code

[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 = 0 ;
    for( int i = 0 ; i <= m ; i ++ ) {
        for( int j = 0 ; j <= m ; j ++ ) {
            if( !b[ i * i + j * j ] ) a[ ++ tot ] = i * i + j * j ;
            b[ i * i + j * j ] = 1 ;
        }
    }
    int cnt = 0 ;
    sort( a + 1 , a + tot + 1 , cmp1 ) ;
    for( int i = 1 ; i <= tot - n + 1  ; i ++ ) {
        for( int j = i + 1 ; j <= tot - n + 2 ; j ++ ) {
            int c = a[ i ] - a[ j ] , now = a[ j ] , t = n - 2 , flag = 1 ;
            if( now - t * c < 0 ) continue ;
            while( t ) {
                t -- ;
                now -= c ;
                if( !b[ now ] ) { flag = 0 ; break ; }
            } 
            if( !flag ) continue ;
            ans[ ++ cnt ].x = now , ans[ cnt ].y = c ;
        }
    }
    if( !cnt ) return puts("NONE") , 0 ;
    sort( ans + 1 , ans + cnt + 1 , cmp2 ) ;
    for( int i = 1 ; i <= cnt ; i ++ ) {
        printf( "%d %d\n" , ans[ i ].x , ans[ i ].y ) ;
    }
    return 0 ;
}

View Code

[USACO1.4]母亲的牛奶 Mother's Milk

就是爆搜出每个状态。不过感觉$dfs$不是很好打就打了$bfs$

然后可以给每个状态编个号，可以大量简化代码

#include <bits/stdc++.h>

using namespace std ;


int a , b , c ;
int ans[ 100 ] ;
int vis[ 30 ][ 30 ][ 30 ] ;
int q[ 100010 ][ 3 ] ;

int main() {
    scanf( "%d%d%d" , &a , &b , &c ) ;
    vis[ 0 ][ 0 ][ c ] = 1 ;
    int l = 1 , r = 2 ;
    q[ l ][ 0 ] = 0 , q[ l ][ 1 ] = 0 , q[ l ][ 2 ] = c ;
    ans[ c ] = 1 ;
    while( l != r ) {
        for( int i = 0 ; i < 9 ; i ++ ) {
            int xa = q[ l ][ 0 ] , xb = q[ l ][ 1 ] , xc = q[ l ][ 2 ] ;
            int w , now1 = i / 3 , now2 = i % 3 ;
            // now1 从now1桶倒出 
            // now2 倒进now2桶 
            // 0,1,2 对应 a,b,c 
            if( now1 == now2 ) continue ;
            if( now1 == 0 ) { // 从1桶倒出 
                w = xa ;
                if( now2 == 1 ) { xb = min( q[ l ][ 1 ] + w , b ) ; xa = max( xa - ( b - q[ l ][ 1 ] ) , 0 ) ; }
                if( now2 == 2 ) { xc = min( q[ l ][ 2 ] + w , c ) ; xa = max( xa - ( c - q[ l ][ 2 ] ) , 0 ) ; }
            }
            if( now1 == 1 ) { // 从2桶倒出 
                w = xb ;
                if( now2 == 0 ) { xa = min( q[ l ][ 0 ] + w , a ) ; xb = max( xb - ( a - q[ l ][ 0 ] ) , 0 ) ; }
                if( now2 == 2 ) { xc = min( q[ l ][ 2 ] + w , c ) ; xb = max( xb - ( c - q[ l ][ 2 ] ) , 0 ) ; }
            }
            if( now1 == 2 ) {
                w = xc ;
                if( now2 == 0 ) { xa = min( q[ l ][ 0 ] + w , a ) ; xc = max( xc - ( a - q[ l ][ 0 ] ) , 0 ) ; }
                if( now2 == 1 ) { xb = min( q[ l ][ 1 ] + w , b ) ; xc = max( xc - ( b - q[ l ][ 1 ] ) , 0 ) ; }
            }
            if( vis[ xa ][ xb ][ xc ] || !w ) continue ; 
            vis[ xa ][ xb ][ xc ] = 1 ;
            if( xa == 0 ) ans[ xc ] = 1 ;
            q[ r ][ 0 ] = xa , q[ r ][ 1 ] = xb , q[ r ][ 2 ] = xc ;
            r ++ ;
            if( r == 100000 ) r = 1 ;
        }
        l ++ ;
        if( l == 100000 ) l = 1 ;
    }
    for( int i = 0 ; i <= 20 ; i ++ ) {
        if( ans[ i ] ) printf( "%d " , i ) ;
    }
    return 0 ;
}

View Code

[USACO1.5]数字三角形 Number Triangles

dp入门题

#include <iostream>
#include <cstring>
using namespace std;
int f[1010][1010],a[1010][1010];
int n;
int main(){
    cin>>n;
    memset(f,0,sizeof(f));
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(j==1)f[i][j]=f[i-1][j]+a[i][j];
            else if(j==i)f[i][j]=f[i-1][j-1]+a[i][j];
            else f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,f[n][i]);
    }
    cout<<ans<<endl;
    return 0;
}

View Code

[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[ 100 ] ;

bool is_prime( int x ) {
    int m = sqrt( x ) ;
    for( int i = 2 ; i <= m ; i ++ ) {
        if( x % i == 0 ) return 0 ;
    }
    return 1 ;
}

bool check( int x ) {
    int l = 0 ;
    while( x ) {
        num[ ++ l ] = x % 10 ;
        x /= 10 ;
    }
    for( int i = 1 , j = l ; i <= l / 2 ; i ++ , j -- ) {
        if( num[ i ] != num[ j ] ) return 0 ;
    }
    return 1 ;
}

int main() {
    scanf( "%d%d" , &a , &b ) ;
    if( a % 2 == 0 ) a ++ ; 
    if( b >= (int)1e8 ) b = 9999999 ;
    for( int i = a ; i <= b ; i += 2 ) {
        if( check( i ) && is_prime( i ) ) printf( "%d\n" , i ) ;
    }
}

View Code

[USACO1.5]特殊的质数肋骨 Superprime Rib

这题随便搜一下就好了...

就是最高位不能是1和9注意判掉就行

#include <bits/stdc++.h>

using namespace std ;

int n ;
int ans[ 100000 ] ;
int num[ 100 ] ;
int p[] = { 0 , 1 , 2 , 3 , 5 , 7 , 9 } ;

bool is_prime( int x ) {
    int m = sqrt( x ) ;
    for( int i = 2 ; i <= m ; i ++ ) {
        if( x % i == 0 ) return 0 ;
    }
    return 1 ;
}

bool check( int x ) {
    int ans = 0 , l = 1 ;
    for( int i = x ; i ; i -- ) {
        ans += num[ i ] * l ;
        l *= 10 ;
    }
    if( is_prime( ans ) ) return 1 ;
    return 0 ;
}

int cnt = 0 ;

void print() {
    int sum = 0 , l = 1 ;
    for( int i = n ; i ; i -- ) {
        sum += l * num[ i ] ;
        l *= 10 ;
    }
    ans[ ++ cnt ] = sum ;
}

void dfs( int x ) {
    if( x == n + 1 ) {
        print() ;
        return ;
    }
    for( int i = 1 ; i <= 6 ; i ++ ) {
        if( x == 1 && ( i == 1 || i == 6 ) ) continue ; 
        num[ x ] = p[ i ] ;
        if( x != 1 && !check( x ) ) continue ;
        dfs( x + 1 ) ;
        num[ x ] = 0 ; 
    }
}

int main() {
    scanf( "%d" , &n ) ;
    dfs( 1 ) ;
    sort( ans + 1 , ans + cnt + 1 ) ;
    for( int i = 1 ; i <= cnt ; i ++ ) printf( "%d\n" , ans[ i ] ) ;
}

View Code

城堡 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[] = { 0 , -1 , 0 , 1 } ;
const int dy[] = { -1 , 0 , 1 , 0 } ;

int ans[ 4 ] = { 0 , 0 , 0 , 0 } ;
int Ans = 0 ;

struct node {
    int u , d , l , r ;
} t[ 100 ][ 100 ] ;
int a[ 100 ][ 100 ] ;
int n , m ;
int tot = 0 ;
int belong[ 100 ][ 100 ] ;
int num[ 5000 ] ;

bool check( int x , int y ) {
    if( x < 1 || x > n || y < 1 || y > m ) return 0 ;
    if( belong[ x ][ y ] ) return 0 ;
    return 1 ;
}

void dfs( int x , int y , int c ) {
    belong[ x ][ y ] = c ;
    num[ c ] ++ ;
    for( int i = 0 ; i < 4 ; i ++ ) {
        if( ! ( a[ x ][ y ] & ( 1 << 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 - 1 ] ] > ans[ 0 ] )
         return 1 ;
    if( num[ belong[ x ][ y ] ] + num[ belong[ x ][ y - 1 ] ] == ans[ 0 ] && y - 1 < ans[ 2 ] )
        return 1 ;
    if( num[ belong[ x ][ y ] ] + num[ belong[ x ][ y - 1 ] ] == ans[ 0 ] && y - 1 == ans[ 2 ] && x > ans[ 1 ] )
        return 1 ;
    return 0 ;
}

bool check_2( int x , int y ) {
    if( num[ belong[ x ][ y ] ] + num[ belong[ x - 1 ][ y ] ] > ans[ 0 ] ) 
        return 1 ;
    if( num[ belong[ x ][ y ] ] + num[ belong[ x - 1 ][ y ] ] == ans[ 0 ] && y < ans[ 2 ] )
        return 1 ;
    if( num[ belong[ x ][ y ] ] + num[ belong[ x - 1 ][ y ] ] == ans[ 0 ] && y == ans[ 2 ] && x > ans[ 1 ] )
        return 1 ;
    return 0 ;
}

int main() {
    scanf( "%d%d" , &m , &n ) ;
    for( int i = 1 ; i <= n ; i ++ ) {
        for( int j = 1 ; j <= m ; j ++ ) {
            scanf( "%d" , &a[ i ][ j ] ) ;
            int t1 = a[ i ][ j ] ;
            if( t1 - 8 >= 0 ) t[ i ][ j ].d = 1 , t1 -= 8 ;
            if( t1 - 4 >= 0 ) t[ i ][ j ].r = 1 , t1 -= 4 ;
            if( t1 - 2 >= 0 ) t[ i ][ j ].u = 1 , t1 -= 2 ;
            if( t1 - 1 >= 0 ) t[ i ][ j ].l = 1 , t1 -= 1 ;
        }
    }
    for( int i = 1 ; i <= n ; i ++ ) {
        for( int j = 1 ; j <= m ; j ++ ) {
            if( belong[ i ][ j ] ) continue ;
            dfs( i , j , ++ tot ) ;
        }
    }
    for( int i = 1 ; i <= tot ; i ++ ) Ans = max( Ans , num[ i ] ) ;
    printf( "%d\n%d\n" , tot , Ans ) ;
    for( int i = 1 ; i <= n ; i ++ ) {
        for( int j = 1 ; j <= m ; j ++ ) {
            if( t[ i ][ j ].l && belong[ i ][ j ] != belong[ i ][ j - 1 ] ) {
                if( check_1( i , j ) ) {
                    ans[ 0 ] = num[ belong[ i ][ j ] ] + num[ belong[ i ][ j - 1 ] ] ;
                    ans[ 1 ] = i ; ans[ 2 ] = j - 1 ;
                    ans[ 3 ] = 'E' ;
                }
            }
            if( t[ i ][ j ].u && belong[ i ][ j ] != belong[ i - 1 ][ j ]  ) {
                if( check_2( i , j ) ) {
                    ans[ 0 ] = num[ belong[ i ][ j ] ] + num[ belong[ i - 1 ][ j ] ] ;
                    ans[ 1 ] = i ; ans[ 2 ] = j ;
                    ans[ 3 ] = 'N' ;
                }
            } 
        }
    }
    printf( "%d\n%d %d %c\n" , ans[ 0 ] , ans[ 1 ] , ans[ 2 ] , ans[ 3 ] ) ;
}

View Code

顺序的分数 Ordered Fractions

这题随便做...

枚举分子和分母，判一下$gcd$

然后转成小数排序输出就可以了

分母不能为0

#include <bits/stdc++.h>

using namespace std ;


int n , cnt = 0 ;
struct node {
    double val ;
    int x , y ;
} fac[ 10000 ] ;

int gcd( int a , int b ) {
    if( b == 0 ) 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 = 1 ; i <= n ; i ++ ) {
        for( int j = 0 ; j <= i ; j ++ ) {
            if( gcd( j , i ) == 1 ) {
                fac[ ++ cnt ].x = j ;
                fac[ cnt ].y = i ;
                fac[ cnt ].val = (double)fac[ cnt ].x / (double)fac[ cnt ].y ;
            }
        }
    }
    sort( fac + 1 , fac + cnt + 1 , cmp ) ;
    for( int i = 1 ; i <= cnt ; i ++ ) {
        printf( "%d/%d\n" , fac[ i ].x , fac[ i ].y ) ;
    }
    return 0 ;
}

View Code

三值的排序 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[ 1010 ] ;
int cnt[ 4 ] , num[ 4 ] ;

int main() {
    scanf( "%d" , &n ) ;
    for( int i = 1 ; i <= n ; i ++ ) 
        scanf( "%d" , &a[ i ] ) , cnt[ a[ i ] ] ++ ; 
    for( int i = 1 ; i <= cnt[ 1 ] + cnt[ 2 ] ; i ++ ) {
        if( a[ i ] == 3 ) num[ 3 ] ++ ;
        else if( a[ i ] == 2 && i <= cnt[ 1 ] ) num[ 2 ] ++ ;
        else if( a[ i ] == 1 && i > cnt[ 1 ] ) num[ 1 ] ++ ;
    }
    printf( "%d\n" , num[ 3 ] + max( num[ 2 ] , num[ 1 ] ) ) ;
}

View Code

健康的荷斯坦奶牛 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 = 100000 , Ans[ N ] ;

void dfs( int x , int p ) {
    bool flag = 1 ;
    now[ p ] = x ;
    for( int i = 1 ; i <= v ; i ++ ) {
        num[ i ] += a[ x ][ i ] ;
        if( num[ i ] < t[ i ] ) flag = 0 ;
    }
    if( flag ) {
        if( p < ans ) {
            ans = p ; 
            for( int i = 1 ; i <= p ; i ++ ) {
                Ans[ i ] = now[ i ] ;
            }
        }
        return ;
    }
    for( int i = x + 1 ; i <= n ; i ++ ) {
        dfs( i , p + 1 ) ;
        for( int k = 1 ; k <= v ; k ++ ) {
            num[ k ] -= a[ i ][ k ] ;
        }
    }
}
 
int main() {
    scanf( "%d" , &v ) ;
    for( int i = 1 ; i <= v ; i ++ ) scanf( "%d" , &t[ i ] ) ;
    scanf( "%d" , &n ) ;
    for( int i = 1 ; i <= n ; i ++ ) {
        for( int j = 1 ; j <= v ; j ++ ) {
            scanf( "%d" , &a[ i ][ j ] ) ;
        }
    }
    for( int i = 1 ; i <= n ; i ++ ) {
        memset( now , 0 , sizeof( now ) ) ;
        memset( num , 0 , sizeof( num ) ) ;
        dfs( i , 1 ) ;
    }
    printf( "%d " , ans ) ;
    for( int i = 1 ; i <= ans ; i ++ ) printf( "%d " , Ans[ i ] ) ;
    puts( "" ) ;
    return 0 ;
}

View Code

海明码 Hamming Codes

可以有前导零，所以直接从1开始枚举就好了...而0一定在答案里面

对于是否符合要求，直接暴力判断

#include <bits/stdc++.h>

using namespace std ;

int n , b , d ;
int ans[ 1000 ] ;

int main() {
    scanf( "%d%d%d" , &n , &b , &d ) ;
    int tot = 1 ;
    ans[ 1 ] = 0 ;
    for( int i = 1 ; tot < n ; i ++ ) {
        bool flag = 1 ;
        for( int j = 1 ; j <= tot ; j ++ ) {
            int sum = 0 ;
            for( int k = 30 ; k >= 0 ; k -- ) {
                if( ( ( ans[ j ] >> k ) & 1 ) ^ ( ( i >> k ) & 1 ) ) 
                    sum ++ ;
            }
            if( sum < d ) { flag = 0 ; break ; }
        }
        if( flag == 1 ) {
            ans[ ++ tot ] = i ;
        }
    }
    for( int i = 1 ; i <= n ; i ++ ) {
        printf( "%d " , ans[ i ] ) ;
        if( !( i % 10 ) ) putchar( '\n' ) ;
    }
    return 0 ;
}

View Code

序言页码 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[ 256 ] ;

int main() {
    scanf( "%d" , &n ) ;
    for( int i = 1 ; i <= n ; i ++ ) {
        int tmp = i ;
        for( int j = 0 ; A[ tmp % 10 ][ j ] ^ ' ' ; j ++ ) c[ A[ tmp % 10 ][ j ] ] ++ ;
        tmp /= 10 ;
        for( int j = 0 ; B[ tmp % 10 ][ j ] ^ ' ' ; j ++ ) c[ B[ tmp % 10 ][ j ] ] ++ ;
        tmp /= 10 ;
        for( int j = 0 ; C[ tmp % 10 ][ j ] ^ ' ' ; j ++ ) c[ C[ tmp % 10 ][ j ] ] ++ ;
        tmp /= 10 ;
        for( int j = 0 ; D[ tmp % 10 ][ j ] ^ ' ' ; j ++ ) c[ D[ tmp % 10 ][ j ] ] ++ ; 
        tmp /= 10 ;
    }
    for( int i = 0 ; S[ i ] ^ ' ' ; i ++ ) if( c[ S[ i ] ] ) printf( "%c %d\n" , S[ i ] , c[ S[ i ] ] ) ;
}

View Code

循环数 Runaround Numbers

直接从$m$向后枚举，感觉效率过不去但是实际上过得去...

#include <bits/stdc++.h>

using namespace std ;

int m ;
int a[ 100 ] , len , t[ 100 ] ;
int vis[ 100 ] ;

bool check() {
    int now = 1 ;
    for( int i = 1 ; i <= len ; i ++ ) {
        if( vis[ a[ now ] ] || a[ now ] == 0 ) return 0 ;
        vis[ a[ now ] ] ++ ;
        now = ( now + a[ now ] - 1 ) % len + 1 ;
    }
    if( now != 1 ) return 0 ;
    return 1 ;
}

int main() {
    scanf( "%d" , &m ) ;
    while( 1 ) {
        int x = ++m ;
        len = 0 ;
        while( x ) {
            t[ ++ len ] = x % 10 ; 
            x /= 10 ; 
        }
        for( int i = 1 ; i <= len ; i ++ ) a[ i ] = t[ len - i + 1 ] ;
        memset( vis , 0 , sizeof( vis ) ) ;
        if( check() ) return printf( "%d" , m ) , 0 ;
    }
}

View Code

派对灯 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 = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) {
        if( c == '-' ) f = -1 ;
        c = getchar() ;
    }
    while( c >= '0' && c <= '9' ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    return x * f ;
}
#undef I_int

using namespace std ;

#define N 1000100

struct node {
    int len ;
    char ch[ 200 ] ;
} a[ N ] ; 
int n , m , f[ N ] ; 
char s[ N ] , ch[ N ] ;

int main() {
    scanf( "%s" , ch+1 ) ;
    while( ch[ 1 ] != '.' ) {
        a[ ++ n ].len = strlen( ch+1 ) ;
        for( int i = 1 , len = strlen( ch+1 ) ; i <= len ; i ++ ) {
            a[ n ].ch[ i ] = ch[ i ] ;
        }
        scanf( "%s" , ch+1 ) ;
    }
    int m = 0 ;
    while( scanf( "%s" , ch+1 ) == 1 ) {
        int len = strlen( ch+1 ) ;
        for( int i = 1 ; i <= len ; i ++ ) {
            s[ i + m ] = ch[ i ] ;
        }
        m += len ;
    }
    f[ 0 ] = 1 ;
    for( int i = 0 ; i <= m ; i ++ ) {
        for( int j = 1 ; j <= n ; j ++ ) {
            if( i + a[ j ].len <= m && f[ i ] ) {
                bool flag = 0 ;
                for( int k = i + 1 ; k <= a[ j ].len + i ; k ++ ) {
                    if( s[ k ] != a[ j ].ch[ k - i ] ) { flag = 1 ; break ; }
                }
                if( flag ) continue ;
                f[ i + a[ j ].len ] = 1 ;
            } 
        }
    }
    for( int i = m ; i >= 0 ; i -- ) {
        if( f[ i ] ) return outn( i ) , 0 ;
    }
}

View Code

奶牛家谱 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 = 1 , base = a ;
    while( b ) {
        if( b&1 ) ans = ans * base % mod ;
        base = base * base % mod ;
        b >>= 1 ;
    }
    return ans % mod ;
}

int fac[N],ifac[N];

int main() {
    scanf( "%d%d" , &n , &m ) ;
    
    fac[0]=1;
    for( int i = 1 ; i <= 300 ; i ++ ) fac[i]=fac[i-1]*i%mod;
    for( int i = 0 ; i <= 300 ; i ++ ) ifac[ i ] = power( fac[ i ] , mod - 2 ) % mod ;
    for( int i = 1 ; i <= 300 ; i ++ ) 
        for( int j = i ; j <= 300 ; j ++ ) 
            c[ i ][ j ] = fac[ j ] * ifac[ i ] % mod * ifac[ j - i ] % mod ;

    f[1][1][1]=1; f[2][3][2]=1;
    for( int t = 2 ; t <= m-1 ; t ++ ) {
        for( int i = 2 ; i < n ; i +=2 ) { //当前层节点数 
            for( int j = (t<<1ll)-1 ; j < n ; j += 2 ) { // 总点数 
                for( int k = 2 ; k <= (i<<1ll) ; k+=2 ) { // 下一层放l个点 
                    if( j + k > n ) break ;
                    f[t+1][j+k][k]=(f[t+1][j+k][k]+f[t][j][i]*c[k/2][i]%mod)%mod;
                }
            }
        }
    }
    
    int ans = 0 ;
    for( int i = 2 ; i <= 200 ; i += 2 ) 
            ans = ( ans + f[ m ][ n ][ i ] ) % mod ;
    printf( "%d\n" , ans ) ;
}

View Code

[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 = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) 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<<1];
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] = 1 ; 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] = 0 ;
            bl[x] = num ;
        }while(x != u) ;
    }
}

int main() {
    n = read() ;
    for(int i = 1 ; i <= n ; i ++) {
        int x = read() ;
        while(x != 0) {
            ins(i , x) ;
            x = read() ;
        }
    }
    for(int i = 1 ; i <= n ; i ++) {
        if(!dfn[i]) tarjan(i) ;
    }
    for(int u = 1 ; 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 = 0 , ans2 = 0 ;
    for(int i = 1 ; i <= num ; i ++) {
        if(!in[i]) ans1 ++ ;
        if(!out[i]) ans2 ++ ;
    }
    if(num == 1) outn(1) , outn(0) ;
    else outn(ans1) , outn(std::max(ans1 , ans2)) ;
    return 0 ;
}

View Code