• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

SMU2017年校赛 题解

开发技术 开发技术 4小时前 2次浏览

比赛链接

A.星图

l[i],r[i],u[i],d[i]分别代表第(i)行或(列)从某个方向看过去的第一个黑洞所在位置

然后判断对应的黑洞是否在当前点的后面

#include <bits/stdc++.h>
using namespace std;


const int N = 1005;
int n , m , q , l[N] , r[N] , d[N] , u[N] ;
char mp[N][N];

inline int read()
{
    int x = 0 , ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x;
}

int main()
{
    n = read() , m = read() , q = read();
    memset( u , 0x3f3f3f3f , sizeof(u) ) , memset( l , 0x3f3f3f3f , sizeof( l ) );
    for( int i = 1 , f ; i <= n ; i ++ )
    {
        f = 1 ;
        scanf( "%s" , mp[i] + 1 );
        for( int j = 1 ; j <= m ; j ++ )
        {
            if( mp[i][j] == '#' )
            {
                if(f) f = 0 , l[i] = j;
                r[i] = j;
                d[j] = i;
            }
        }
    }

    for( int j = 1 ; j <= m ; j ++ )
    {
        for( int i = 1 ; i <= n ; i ++ )
        {
            if( mp[i][j] == '#' )
            {
                u[j] = i;
                break;
            }
        }
    }

    int x , y ;
    char dir;
    for( int i = 1 ; i <= q ; i ++ )
    {
        x = read() , y = read() , scanf( "%c" , &dir );
        if( dir == 'L' ) puts( l[x] > y ? "YES" : "NO" );
        else if( dir == 'R' ) puts( r[x] < y ? "YES" : "NO" );
        else if( dir == 'D' ) puts( d[y] < x ? "YES" : "NO" );
        else puts( u[y] > x ? "YES" : "NO" );
    }
    return 0;
}

B.好数

若存在大于等于两个数,则必有一数与第一个数不相同

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;
    for( auto it : s )
    {
        if( it != s[0] )
        {
            cout << "NO";
            exit(0);
        }
    }
    cout << "YESn";
}

C.装进肚子

贪心,早上甜蜜值减去晚上甜蜜值,越大越适合早上吃

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n , k ;
long long ans;
struct Node
{
    int x , y;
    friend bool operator < ( Node a , Node b ) { return a.x - a.y > b.x - b.y; }
} a[N];

int read()
{
    int x = 0 , ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x;
}

int main()
{
    n = read() , k = read();
    for( int i = 1 ; i <= n ; i ++ ) a[i].x = read();
    for( int i = 1 ; i <= n ; i ++ ) a[i].y = read();
    sort( a + 1 , a + 1 + n );
    for( int i = 1 ; i <= k ; i ++ ) ans += a[i].x;
    for( int i = k + 1 ; i <= n ; i ++ ) ans += a[i].y;
    cout << ans << endl;
}

D.ZZZZone爱吃糖

前缀和

#include <bits/stdc++.h>
using namespace std;

long long n , a[10005] , m , ans;

int main()
{
    cin >> n;
    for( int i = 1 ; i <= n ; i ++ ) cin >> a[i] , a[i] += a[ i - 1 ];
    cin >> m;
    for( int i = 1 , l , r ; i <= m ; i ++ )
    {
        cin >> l >> r;
        ans += max( 0LL , a[r] - a[ l - 1 ] );
    }
    cout << ans << endl;
    return 0;
}

E.开心的涂刷

总方案数(m^n),任意相邻格子不同的方案数(mtimes(m-1)^{n-1})

作差

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod = 1000000007;
ll n , m ;

ll ksm( ll x , ll y )
{
    ll res = 1;
    while( y )
    {
        if( y & 1 ) res = ( res * x ) % mod;
        y >>= 1;
        x = ( x * x ) % mod;
    }
    return res;
}

int main()
{
    cin >> n >> m ;
    m %= mod;
    cout << ( ksm( m , n ) - m * ksm( m - 1 , n - 1 ) % mod + mod ) % mod << endl;
    return 0;
}

F.兼职数靶

打个表就行

#include<bits/stdc++.h>
using namespace std;

int n , cnt;
int point[20][20] = {   {1,1,1,1,1,1,1,1,1,1,1,1,1},
                    {1,2,2,2,2,2,2,2,2,2,2,2,1},
                    {1,2,2,2,2,2,2,2,2,2,2,2,1},
                    {1,2,2,3,3,3,3,3,3,3,2,2,1},
                    {1,2,2,3,3,3,3,3,3,3,2,2,1},
                    {1,2,2,3,3,4,4,4,3,3,2,2,1},
                    {1,2,2,3,3,4,4,4,3,3,2,2,1},
                    {1,2,2,3,3,4,4,4,3,3,2,2,1},
                    {1,2,2,3,3,3,3,3,3,3,2,2,1},
                    {1,2,2,3,3,3,3,3,3,3,2,2,1},
                    {1,2,2,2,2,2,2,2,2,2,2,2,1},
                    {1,2,2,2,2,2,2,2,2,2,2,2,1},
                    {1,1,1,1,1,1,1,1,1,1,1,1,1} };

bool get()
{
    char ch = getchar();
    while( ch != '.' && ch != '#' ) ch = getchar();
    return ( ch == '#' ? 1 : 0 );
}

int main()
{
    for( ; ; )
    {
        cin >> n;
        if( n == 0 ) exit(0);
        cnt = 0;
        for( int i = 1 ; i <= 13 ; i ++ )
        {
            for( int j = 1 ; j <= 13 ; j ++ )
            if( get() ) cnt += point[ i - 1 ][ j - 1 ];
        }
        printf( "%.2lfn" , 1.0 * cnt / n );
    }
    return 0;
}

G.卡牌游戏

只记录AliceBob多赢了几局即可

#include <bits/stdc++.h>
using namespace std;


int n , t;
string a , b;
int main()
{
    cin >> n;
    for( int i = 1 ; i <= n ; i ++ )
    {
        cin >> a >> b;
        if( ( a == "Jin" && b == "Mu" ) || ( a == "Mu" && b == "Tu" ) || ( a == "Tu" && b == "Shui" ) || ( a == "Shui" && b == "Huo" ) || ( a == "Huo" && b == "Jin" ) ) t ++;
        if( ( b == "Jin" && a == "Mu" ) || ( b == "Mu" && a == "Tu" ) || ( b == "Tu" && a == "Shui" ) || ( b == "Shui" && a == "Huo" ) || ( b == "Huo" && a == "Jin" ) ) t --;
    }
    if( t > 0 ) cout << "Alicen";
    else if( t < 0 ) cout << "Bobn";
    else cout << "Drawn";
    return 0;
}

H.Hungry!

签到题输入(n)输出(n)gu...和一句话,正式赛大家应该都是被英文劝退了吧

#include<bits/stdc++.h>
using namespace std;


int m;
string s;
unordered_map< char , char > h;

int main()
{
    while(cin>>m)
    {
        for( int i = 1 ; i <= m ; i ++ ) cout << "gu...";
        cout<< "nThe story is so boring. And I am so hungry!n";
    }
}

I.快饿死的XzzF

动态规划,记忆化搜索也行吧

#include <bits/stdc++.h>
using namespace std;

int n ;
long long f[25][2];

int main()
{
    cin >> n;
    f[1][0] = f[1][1] = 1;
    for( int i = 2 ; i <= n ; i ++ ) f[i][1] = f[i-1][0] + f[i-1][1] , f[i][0] = f[i-1][1];
    cout << f[n][0] + f[n][1] << endl;
    return 0;
}

J.小猪佩奇练打字

做个简单的哈希即可

#include<bits/stdc++.h>
using namespace std;


int m;
string s;
unordered_map< char , char > h;

int main()
{
    cin >> s;
    for( char i = 'a' ; i <= 'z' ; i ++ ) h[i] = i;
    cin >> m;
    for( char x , y ; m ; m -- )
    {
        cin >> x >> y;
        swap( h[x] , h[y] );
    }
    for( auto i : s ) cout << h[i];
    return 0;
}

K.免费WIFI

贪心的选择即可

似乎有优先队列做法,我每次sort暴力跑也过了

#include<bits/stdc++.h>
#define l first
#define r second
using namespace std;


long long q[10005] , n , cnt = 1 , m;
pair< long , long > t[10005];

int main()
{
    cin >> n >> m;
    for( int i = 1 ; i <= n ; i ++ ) cin >> t[i].l >> t[i].r;
    sort( t + 1 , t + 1 + n );
    for( int i = 1 , f ; i <= n ; i ++ )
    {
        f = 0;
        for( int j = 1 ; j <= cnt && !f ; j ++ ) if( t[i].l > q[j] ) q[j] = t[i].r , f = 1;
        if( !f ) q[ ++ cnt ] = t[i].r;
        sort( q + 1 , q + 1 + cnt );
    }
    cout << cnt / m + ( cnt % m ? 1 : 0 ) << endl;
    return 0;
}

程序员灯塔
转载请注明原文链接:SMU2017年校赛 题解
喜欢 (0)