C++博客-心如止水

UVa 10229 Modular Fibonacci

lee1r — Tue, 22 Nov 2011 14:57:00 GMT

Fibonacci数列一定会从F[0]、F[1]开始循环，这是JJ哥告诉我的……

于是，此题就很显然啦。
@import url(http://www.cppblog.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css);

以下是我的代码：

#include <vector>
#include <cstdio>
using namespace std;

int n, m;
vector<int> r[27];

void Init () {
    for ( m = 1; m < 20; m++ ) {
        int mod = ( 1 << m );
        int a = 0, b = 1, c = 1 % mod;
        r[m].push_back ( a );
        r[m].push_back ( b );
        r[m].push_back ( c );
        while ( b != 0 || c != 1 ) {
            a = b; b = c; c = ( a + b ) % mod;
            r[m].push_back ( c );
        }
        r[m].pop_back(); r[m].pop_back();
    }
}

int main () {
#ifndef ONLINE_JUDGE
    freopen ( "data.in", "r", stdin );
#endif
    Init ();
    while ( scanf ( "%d%d", &n, &m ) == 2 )
        if ( m ) printf ( "%d\n", r[m][n%r[m].size()] );
        else printf ( "%d\n", 0 );
    return 0;
}

lee1r 2011-11-22 22:57 发表评论

UVa 10128 Queue

lee1r — Sun, 06 Nov 2011 02:53:00 GMT

d[i][j][k]表示共i个人站队，从前面可以看到j个人，从后面可以看到k个人的方案个数。则d[i][j][k] = d[i-1][j][k] * (i-2) + d[i-1][j-1][k] + d[i-1][j][k-1] （假设新加入的一个人身高最小），边界条件是d[1][1][1] = 1。
以下是我的代码：

#include <iostream>
using namespace std;

typedef long long int64;

int64 d[17][17][17];

void Init () {
    d[1][1][1] = 1;
    for ( int i = 2; i <= 13; i++ )
        for ( int j = 1; j <= i; j++ )
            for ( int k = 1; k <= i; k++ )
                d[i][j][k] = d[i-1][j][k] * ( i - 2 ) + d[i-1][j-1][k] + d[i-1][j][k-1];
}

int main () {
    Init ();
    int T, n, p, r;
    cin >> T;
    while ( T-- ) {
        cin >> n >> p >> r;
        cout << d[n][p][r] << endl;
    }
    return 0;
}

lee1r 2011-11-06 10:53 发表评论

UVa 10269 Adventure of Super Mario

lee1r — Fri, 04 Nov 2011 01:25:00 GMT

先求任意两点之间不经过城堡的最短路。d[i][j]表示到达i点使用了j次鞋子的最短路长度。
以下是我的代码：

#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int kMaxn = 107;
const int kMaxm = kMaxn * kMaxn;
const int kInf = 0x7f7f7f7f;

int A, B, M, L, K, g[kMaxn][kMaxn];
int d[kMaxn][17];
bool inq[kMaxn][17];

struct State {
    State ( const int &_u, const int &_k ) : u ( _u ), k ( _k ) { }
    int u, k;
};

void Input () {
    memset ( g, 0x7f, sizeof ( g ) );
    scanf ( "%d%d%d%d%d", &A, &B, &M, &L, &K );
    while ( M-- ) {
        int u, v, w;
        scanf ( "%d%d%d", &u, &v, &w );
        g[u][v] = g[v][u] = w;
    }
}

void Solve () {
    for ( int k = 1; k <= A; k++ )
        for ( int i = 1; i <= A+B; i++ )
            for ( int j = 1; j <= A+B; j++ )
                if ( g[i][k] < kInf && g[k][j] < kInf && g[i][j] > g[i][k] + g[k][j] )
                    g[i][j] = g[i][k] + g[k][j];

    queue<State> q;
    memset ( d, 0x7f, sizeof ( d ) );
    memset ( inq, false, sizeof ( inq ) );
    d[A+B][0] = 0;
    q.push ( State ( A+B, 0 ) );
    while ( !q.empty() ) {
        int u = q.front().u, k = q.front().k;
        q.pop(); inq[u][k] = false;
        for ( int v = 1; v <= A + B; v++ ) {
            if ( k < K && g[u][v] <= L ) {
                if ( d[v][k+1] > d[u][k] ) {
                    d[v][k+1] = d[u][k];
                    if ( !inq[v][k+1] ) {
                        q.push ( State ( v, k+1 ) );
                        inq[v][k+1] = true;
                    }
                }
                if ( d[v][k] > d[u][k] + g[u][v] ) {
                    d[v][k] = d[u][k] + g[u][v];
                    if ( !inq[v][k] ) {
                        q.push ( State ( v, k ) );
                        inq[v][k] = true;
                    }
                }
            }
            else {
                if ( d[v][k] > d[u][k] + g[u][v] ) {
                    d[v][k] = d[u][k] + g[u][v];
                    if ( !inq[v][k] ) {
                        q.push ( State ( v, k ) );
                        inq[v][k] = true;
                    }
                }
            }
        }
    }
    int ans = kInf;
    for ( int i = 0; i <= K; i++ )
        ans = min ( ans, d[1][i] );
    printf ( "%d\n", ans );
}

int main () {
#ifndef ONLINE_JUDGE
    freopen ( "data.in", "r", stdin );
#endif
    int T;
    scanf ( "%d", &T );
    while ( T-- ) {
        Input ();
        Solve ();
    }
    return 0;
}

lee1r 2011-11-04 09:25 发表评论

UVa 128 Software CRC

lee1r — Wed, 28 Sep 2011 08:18:00 GMT

题目大意：给出一个256进制数，在这个数字后面增加2位，使得可以被34943整除。
以下是我的代码：

#include
#include
using namespace std;

typedef long long int64;

const int kMaxn = 1050;

int len;
int64 re, ans;
char s[kMaxn], output[7];

int main () {
#ifndef ONLINE_JUDGE
    freopen ( "data.in", "r", stdin );
#endif

    while ( gets ( s ) ) {
        len = strlen ( s );
        //printf ( "%d\n", len );
        if ( s[0] == '#' )
            break;

        re = 0;
        for ( int i = 0; i < len; i++ )
            re = ( re * 256 + s[i] ) % 34943;
        re = re * 256 * 256 % 34943;

        ans = ( re ? 34943 - re : 0 );

        //printf ( "%lld %lld\n", re, ans );

        sprintf ( output, "%04x\n", (int)ans );
        for ( int i = 0; i < 4; i++ )
            if ( output[i] >= 'a' && output[i] <= 'z' )
                output[i] = output[i] - 'a' + 'A';
        printf ( "%c%c %c%c\n", output[0], output[1], output[2], output[3] );
    }

    return 0;
}

lee1r 2011-09-28 16:18 发表评论

UVa 10820 Send a Table

lee1r — Tue, 20 Sep 2011 11:49:00 GMT

题目大意：N以内有多少对互质的数。
以下是我的代码：

#include
using namespace std;

const int kMaxn = 50000;

int phi[kMaxn+7], sum[kMaxn+7];

void Init ()
{
    phi[1] = 1;
    for ( int i = 2; i <= kMaxn; i++ )
        phi[i] = 0;
    for ( int i = 2; i <= kMaxn; i++ )
        if ( !phi[i] )
            for ( int j = i; j <= kMaxn; j+=i )
            {
                if ( !phi[j] )
                    phi[j] = j;
                phi[j] = phi[j] / i * ( i - 1 );
            }
    sum[1] = 1;
    for ( int i = 2; i <= kMaxn; i++ )
        sum[i] = sum[i-1] + ( phi[i] << 1 );
}

int main ()
{
    Init ();

    int n;
    while ( cin >> n && n )
        cout << sum[n] << endl;

    return 0;
}

lee1r 2011-09-20 19:49 发表评论

Ural 1049 Brave Balloonists

lee1r — Mon, 12 Sep 2011 01:53:00 GMT

求a[1] × a[2] × …… × a[10]的约数个数。
以下是我的代码：

#include <iostream>
#include <map>
#include <cstdio>
using namespace std;

typedef unsigned long long int64;

int64 a[17];
map<int64,int64> r;

void Input ()
{
    for ( int i = 1; i <= 10; i++ )
        cin >> a[i];
}

void Fac ( int64 x )
{
    while ( ( x & 1 ) == 0 )
    {
        x >>= 1;
        r[2]++;
    }
    for ( int i = 3; i * i <= x; i+= 2 )
        while ( x % i == 0 )
        {
            x/=i;
            r[i]++;
        }
    if ( x != 1 )
        r[x]++;
}

void Solve ()
{
    r.clear();
    for ( int i = 1; i <= 10; i++ )
        Fac ( a[i] );
    int ans = 1;
    for ( map<int64,int64>::iterator i = r.begin(); i != r.end(); i++ )
    {
        //cout << i->first << " " << i->second << endl;
        ans *= i->second + 1;
    }
    cout << ans % 10 << endl;
}

int main ()
{
    Input ();
    Solve ();

    return 0;
}

lee1r 2011-09-12 09:53 发表评论

UVa 465 Overflow

lee1r — Thu, 08 Sep 2011 02:42:00 GMT

需要注意两点：1、前导0要删除；2、a或者b溢出，c也不一定溢出，a或b为0的话结果为0。
以下是我的代码：

#include <iostream>
#include <sstream>
#include <string>
#include <cstdio>
using namespace std;
typedef long long int64;

const string kInf = "2147483647";

int cmp ( const string &a, const string &b )
{
    if ( a.size() > b.size() )
        return 1;
    else if ( a.size() < b.size() )
        return -1;
    else
    {
        for ( int i = 0; i < a.size(); i++ )
            if ( a[i] > b[i] )
                return 1;
            else if ( a[i] < b[i] )
                return -1;
        return 0;
    }
}

int main ()
{
#ifndef ONLINE_JUDGE
    freopen ( "data.in", "r", stdin );
#endif

    string a, t, b;

    while ( cin >> a >> t >> b )
    {
        cout << a << " " << t << " " << b << endl;
        while ( a.size() > 1 && a[0] == '0' )
            a.erase ( 0, 1 );
        //cout << a << endl;
        while ( b.size() > 1 && b[0] == '0' )
            b.erase ( 0, 1 );
        //cout << b << endl;
        bool over = false;
        if ( cmp ( a, kInf ) > 0 )
        {
            printf ( "first number too big\n" );
            over = true;
        }
        if ( cmp ( b, kInf ) > 0 )
        {
            printf ( "second number too big\n" );
            over = true;
        }
        if ( over )
        {
            if ( t == "+" || ( t == "*" && a != "0" && b != "0" ) )
                printf ( "result too big\n" );
            continue;
        }
        int64 aa, bb, cc;
        istringstream ( a ) >> aa;
        istringstream ( b ) >> bb;
        if ( t == "+" )
            cc = aa + bb;
        else
            cc = aa * bb;
        if ( cc > 0x7fffffff )
            printf ( "result too big\n" );
    }

    return 0;
}

lee1r 2011-09-08 10:42 发表评论

UVa 10310 Dog and Gopher

lee1r — Wed, 07 Sep 2011 16:11:00 GMT

超简单题。
以下是我的代码：

#include <cstdio>
#include <cmath>
using namespace std;

const double eps = 1e-8;

double d ( double x1, double y1, double x2, double y2 )
{
    return ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 );
}

int main ()
{
#ifndef ONLINE_JUDGE
    freopen ( "data.in", "r", stdin );
#endif

    int n;
    double x1, y1, x2, y2, x, y, ansx, ansy;
    bool found;

    while ( scanf( "%d%lf%lf%lf%lf", &n, &x1, &y1, &x2, &y2 ) == 5 )
    {
        found = false;
        for ( int i = 1; i <= n; i++ )
        {
            scanf ( "%lf%lf", &x, &y );
            if ( found )
                continue;
            if ( 4 * d ( x1, y1, x, y ) <= d ( x2, y2, x, y ) )
            {
                found = true;
                ansx = x;
                ansy = y;
            }
        }

        //printf ( "%f\n", (double)20000*20000*2 );

        if ( !found )
            printf ( "The gopher cannot escape.\n" );
        else
            printf ( "The gopher can escape through the hole at (%.3f,%.3f).\n", ansx, ansy );
    }

    return 0;
}

lee1r 2011-09-08 00:11 发表评论

UVa 10278 Fire Station

lee1r — Wed, 07 Sep 2011 16:08:00 GMT

题目大意就不说啦～
直接枚举新加入的结点即可。
以下是我的代码：

#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int kMaxn = 507;
const int kInf = 0x7f7f7f7f;

struct Edge
{
    int v, w;
};

int f, n, r[107];
int cnt, first[kMaxn], next[ kMaxn * 40 ];
Edge e[ kMaxn * 40 ];
int ans,value,d[107][kMaxn], near[kMaxn];

void Clear ()
{
    cnt=-1;
    memset ( first, -1, sizeof ( first ) );
}

void AddEdge ( int u, int v, int w )
{
    cnt++;
    e[cnt].v = v;
    e[cnt].w = w;
    next[cnt] = first[u];
    first[u] = cnt;
}

void Input ()
{
    scanf ( "%d%d", &f, &n );
    for ( int i = 1; i <= f; i++ )
        scanf ( "%d", &r[i] );
    //printf ( "%d\n", r[1] );
    getchar ();
    Clear ();
    string in;
    while ( getline ( cin, in ) && !in.empty() )
    {
        int u, v, w;
        istringstream ( in ) >> u >> v >> w;
        //printf ( "%d %d %d\n", u, v, w );
        AddEdge ( u, v, w );
        AddEdge ( v, u, w );
    }
}

void SPFA ( int start, int *dist )
{
    deque<int> q;
    bool inq[kMaxn];
    memset ( inq, false, sizeof ( inq ) );
    //memset ( dist, 0x7f, sizeof ( dist ) );
    for ( int i = 1; i <= n; i++ )
        dist[i] = kInf;
    dist[start] = 0;
    q.push_back( start );
    while ( !q.empty() )
    {
        int u = q.front(); q.pop_front();
        inq[u] = false;
        for ( int i = first[u]; i != -1; i = next[i] )
        {
            int v = e[i].v;
            if ( dist[v] > dist[u] + e[i].w )
            {
                dist[v] = dist[u] + e[i].w;
                if ( !inq[v] )
                {
                    if ( !q.empty() && dist[v] < dist[q.front()] )
                        q.push_front( v );
                    else
                        q.push_back( v );
                    inq[v] = true;
                }
            }
        }
    }
}

void Solve ()
{
    for ( int i = 1; i <= f; i++ )
        SPFA ( r[i], d[i] );

    //for ( int i = 1; i <= f; i++ )
    //{
        //for ( int j = 1; j <= n; j++)
            //printf ( "%d ", d[i][j] );
        //puts ( "" );
    //}

    memset ( near, 0x7f, sizeof ( near ) );
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= f; j++ )
            near[i] = min ( near[i], d[j][i] );
    value = kInf;
    for ( int i = 1; i <= n; i++ )
    {
        SPFA ( i, d[f+1] );
        int t = 0;
        for ( int j = 1; j <= n; j++ )
            t = max ( t, min ( near[j], d[f+1][j] ) );
        if ( value > t)
        {
            ans = i;
            value = t;
        }
    }
}

int main ()
{
#ifndef ONLINE_JUDGE
    freopen ( "data.in", "r", stdin );
#endif

    int T;
    bool first_case = true;
    scanf ( "%d", &T );
    while ( T-- )
    {
        Input ();
        Solve ();

        if ( first_case )
            first_case = false;
        else
            puts ( "" );
        printf ( "%d\n", ans );
    }

    return 0;
}

lee1r 2011-09-08 00:08 发表评论

UVa 10168 Summation of Four Primes

lee1r — Tue, 06 Sep 2011 15:30:00 GMT

如果N为奇数，那么前两个素数为2和3；如果N为偶数，那么前两个素数为2和2。这样一来转化成了将一个偶数分解成两个素数的和。
以下是我的代码：

#include <cstdio>
using namespace std;

const int kMaxn = 10000000;

int cnt, Prime[680000];
bool isNotPrime[ kMaxn + 7 ];

int n;

void GetPrime ()
{
    cnt = 0;
    for ( int i = 2; i <= kMaxn; i++ )
    {
        if ( !isNotPrime[i] )
            Prime[++cnt] = i;
        for ( int j = 1; j <= cnt && i * Prime[j] <= kMaxn; j++ )
        {
            isNotPrime[ i * Prime[j] ] = true;
            if ( i % Prime[j] == 0 )
                break;
        }
    }
}

void Goldbach ( int x )
{
    for ( int i = 1; i <= cnt && Prime[i] <= x; i++ )
        if ( !isNotPrime[ x - Prime[i] ] )
        {
            printf ( "%d %d\n", Prime[i], x-Prime[i] );
            return;
        }
}

void Solve ()
{
    if ( n & 1 )
    {
        n -= 5;
        if ( n < 4 )
        {
            printf ( "Impossible.\n" );
            return;
        }
        printf ( "%d %d ", 2, 3 );
    }
    else
    {
        n -= 4;
        if ( n < 4 )
        {
            printf ( "Impossible.\n" );
            return;
        }
        printf ( "%d %d ", 2, 2 );
    }
    Goldbach ( n );
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen ( "data.in", "r", stdin );
#endif

    GetPrime ();
    //printf ( "%d\n", cnt );

    while ( scanf ( "%d", &n ) == 1 )
        Solve ();

    return 0;
}

lee1r 2011-09-06 23:30 发表评论