二月二十五日まとめ

25299 ワード
締め括りをつける
2月25日の練習試合
NOIP 2008年再試合1:1.愚かなサル(word.pas/c/cpp)【問題の説明】愚かなサルの語彙量は小さいので、英語の選択問題をするたびに頭が痛い.しかし、彼は1つの方法を見つけて、この方法で選択肢を選ぶ時に正しい確率が非常に大きいことを実験で証明しました!この方法の具体的な説明は以下の通りである:maxnは単語の中で最も出現回数の多いアルファベットの出現回数であり、minnは単語の中で最も出現回数の少ないアルファベットの出現回数であり、maxn-minnが質数であれば、愚かなサルはこれがLucky Wordであると考え、このような単語が正しい答えである可能性が高い.【入力】入力ファイルword.inは1行のみで、単語で、小文字のみが表示され、長さは100未満です.【出力】出力ファイルword.outは2行で、1行目は文字列で、入力した単語がLucky Wordであると仮定すると、「Lucky Word」を出力し、そうでなければ「No Answer」を出力する.2行目は整数で、入力単語がラッキーワードであればmaxn-minnの値を出力し、そうでなければ0を出力します.【入出力サンプル1】word.in word.out error Lucky Word 2【入出力サンプル1解釈】単語errorで最も多く出現したアルファベットrは3回出現し、出現回数が最も少ないアルファベットは1回出現し、3-1=2、2は素数である.【入出力サンプル2】word.in word.out olympic No Answer 0【入出力サンプル2解釈】単語olympicで最も多く出現したアルファベットiは2回出現し、出現回数が最も少ないアルファベットは1回出現し、2-1=1、1は素数ではない.
n<100だからそのままバケツで並べてmax-minが素数かどうかを判断すればいい(ルートnだけで素数を判断できるがデータが水っぽい)
/********************
     Accepted

   : 3 ms
0 / 0       .
    
   #word1.in    :AC         :  256kB          :  0ms     
   #word10.in    :AC         :  128kB          :  1ms     
   #word2.in    :AC         :  256kB          :  0ms     
   #word3.in    :AC         :  256kB          :  0ms     
   #word4.in    :AC         :  256kB          :  0ms     
   #word5.in    :AC         :  128kB          :  1ms     
   #word6.in    :AC         :  256kB          :  0ms     
   #word7.in    :AC         :  256kB          :  0ms     
   #word8.in    :AC         :  256kB          :  0ms     
   #word9.in    :AC         :  256kB          :  1ms 
*********************/
#include 
#include 
#include 
#include 
using namespace std;

const int oo = 0x3f3f3f3f;

char s[105];
int a[30];

int main() {
    scanf( "%s", &s );
    int len = strlen (s);
    memset( a, 0, sizeof(a) );
    for ( int i = 0; i < len; i++ ) 
    a[s[i]-'a']++;
    int maxx = 0, minn = oo;
    for ( int i = 0; i < 26; i++ ) {
        if ( a[i] != 0 ) {
            if ( a[i] > maxx ) maxx = a[i];
            if ( a[i] < minn ) minn = a[i];
        }
    }
    int num = maxx - minn;
    int j;
    for ( j = 2; j <= num - 1; j++ )
    if ( num%j == 0 ) break;
    if ( j == num ) {
        printf("Lucky Word
");
        printf("%d
",num);
        return 0;
    }
    else {
        printf("No Answer
");
        printf("0
");
        return 0;
    }
}

二:2.マッチ棒等式(matches.pas/c/cpp)【問題の説明】マッチ棒をn本あげます.「A+B=C」のような等式をいくつつづることができますか.等式中のA,B,Cはマッチ棒でつづった整数(この数がゼロでなければ最高位は0にならない).マッチ棒で数字0-9をつづるつづりは図のようになります.
注意:1.プラス記号と等号にはそれぞれマッチ棒が2本必要だ.A≠Bの場合、A+B=CとB+A=Cは異なる式(A、B、C>=0)3とする.n本のマッチ棒は全部使わなければならない.
【入力】入力ファイルmatches.inは1行で、もう1つの整数n(n<=24).【出力】出力ファイルmatches.outは1行で、綴ることができる異なる等式の数を表す.
【入出力サンプル1】matches.in matches.out 14 2【入出力サンプル1解釈】2等式は0+1=1と1+0=1である.
【入出力サンプル2】matches.in matches.out 18 9【入出力サンプル2解釈】9等式:0+4=4 0+11=11+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11+0=11
暴力、この問題は表を打つことができて、n<24が更に4本のマッチを減らして最大20そんなに20マッチの組成の最大の数字が11111なため、そんなに直接1—11111これらの数字のマッチの根の数を計算して2つの加数を列挙して判断することができます
/********************
     Accepted

   : 10 ms
0 / 0       .
    
   #matches1.in    :AC         :  364kB          :  1ms     
   #matches10.in    :AC         :  360kB          :  1ms     
   #matches2.in    :AC         :  364kB          :  1ms     
   #matches3.in    :AC         :  360kB          :  1ms     
   #matches4.in    :AC         :  360kB          :  1ms     
   #matches5.in    :AC         :  364kB          :  1ms     
   #matches6.in    :AC         :  364kB          :  1ms     
   #matches7.in    :AC         :  364kB          :  1ms     
   #matches8.in    :AC         :  360kB          :  1ms     
   #matches9.in    :AC         :  364kB          :  1ms  
********************/
#include 
#include 
#include 
using namespace std;

struct date{
    int tot, num[12000];
    date() {
        tot = 0;
    }
};
date gun[30];
int a[11] = {6,2,5,5,4,5,6,3,7,6};
int n;
int main() {
    freopen("matches.in","r",stdin);
    freopen("matches.out","w",stdout);
    int res = 0;
    scanf( "%d", &n );
    n = n - 4;
    for ( int i = 0; i <= 12000; i++ ) {
        int k = i, sum = 0;
        do
        {
            sum += a[k%10];
            k /= 10;
        }while ( k!= 0 );
        if ( sum <= n )
        gun[sum].tot++;
        gun[sum].num[gun[sum].tot] = i;
    }
    for ( int i = 2; i <= n; i++ ) {
        for ( int j = 2; j <= n; j++ ) {
            int last = n - i - j;
            if ( last < 0 ) continue;
            for ( int a1 = 1; a1 <= gun[i].tot; a1++ )
                for ( int b1 = 1; b1 <= gun[j].tot; b1++ )
                    for ( int c1 = 1; c1 <= gun[last].tot; c1++ )
                    if ( (gun[i].num[a1] + gun[j].num[b1]) == gun[last].num[c1] ) {
                    //  printf("%d %d %d
",gun[i].num[a1], gun[j].num[b1], gun[last].num[c1]);
                        res++;
                    } 
        }
    }
    printf( "%d
", res );
    return 0;
}

三:3.伝紙(message.pas/c/cpp)【問題の説明】小渕と小軒は親友で同級生で、彼らは一緒にいていつも話が尽きない話題がある.ある素質の開拓活動の中で、クラスの同級生はm行、n列の行列を作るように手配したが、小渕と小軒は行列の対角線の両端に配置されたので、彼らは直接話をすることができなかった.幸いなことに、彼らはメモを伝えることで交流することができます.メモは多くの学生を通じて相手の手に伝わり、小渕は行列の左上隅、座標(1,1)、小軒は行列の右下隅、座標(m,n)に座っている.小渕から小軒に伝わるメモは下または右にしか伝わらず、小軒から小渕に伝わるメモは上または左にしか伝わらない.イベントの進行中、小渕は小軒にメモを渡したいと同時に、小軒に返事をしてほしいと望んでいた.クラスの中ですべての学友はすべて彼らを伝达することができて、しかし一回だけ彼らを助けることができて、つまりこの人が小渕が小軒のメモを渡した时に手伝うならば、小軒が小渕に渡した时に二度と手伝うことはありません.逆もまた然り.もう一つ注意しなければならないことは、クラス全員が手伝ってくれる好感度が高いか低いか(注意:小渕と小軒の好意の程度は定義されていないので、入力時に0で表す)、0-100の自然数で表すことができ、数が大きいほど好意を表すことができます.小渊と小轩はできるだけ好意の程度の高い学友を探して纸を伝えることを手伝って、つまり往復の2本の伝达の経路を探し当てて、この2つの経路の上で学友の好意の程度はただ最大になります.今、小渕と小軒がこのような2つの経路を見つけるのを助けてください.
【入力】入力ファイルmessage.inの最初の行には、スペースで区切られた整数mとnが2つあり、クラスにm行n列(1<=m,n<=50)があることを示す.次のm行はm*nの行列であり、行列中のi行j列目の整数はi行j列目に座っている学生の好意の程度を表す.各行のn個の整数の間をスペースで区切る.
【出力】出力ファイルmessage.outは1行で、1つの整数を含み、往復2つの道で紙切れの伝達に参加した学生の好意の程度の和の最大値を表す.
【入出力サンプル】message.in message.out 3 3 0 3 9 2 8 5 5 7 0 34
【制限】30%のデータ満足:1<=m、n<=10 100%のデータ満足:1<=m、n<=50
この問題はdpのやり方で、右下から左上へ等価に右上から左下へ歩くことができるため、2つは同じであるが、4次元の配列で状態dp【i】【j】【k】【p】を保存して2つの点(i,j)(k,p)まで行ける最大の好感度を表すと、状態遷移方程式は簡単に詳細を書くことができるコードを参照する.
/********************
     Accepted

   : 113 ms
0 / 0       .
    
   #message1.in    :AC         :  256kB          :  0ms     
   #message10.in    :AC         :  23532kB          :  30ms     
   #message2.in    :AC         :  256kB          :  1ms     
   #message3.in    :AC         :  492kB          :  1ms     
   #message4.in    :AC         :  1004kB          :  0ms     
   #message5.in    :AC         :  2540kB          :  0ms     
   #message6.in    :AC         :  7276kB          :  4ms     
   #message7.in    :AC         :  18408kB          :  20ms     
   #message8.in    :AC         :  21100kB          :  25ms     
   #message9.in    :AC         :  23532kB          :  32ms
********************/
#include 
#include 
#include 
#include 
using namespace std;

int mp[51][51];
int dp[51][51][51][51];
int m, n;


int main() {
    scanf( "%d%d", &m, &n );
    for ( int i = 1; i <= m; i++ )
        for ( int j = 1; j <= n; j++ ) scanf( "%d", &mp[i][j] );
    for ( int i = 1; i <= m; i++ )
        for ( int j = 1; j <= n; j++ )
            for ( int k = 1; k <= m; k++ )
                for ( int p = 1; p <= n; p++ ) {
                if ( i == k && j == p && i != m && j != n && k != m && p != n ) 
                    continue;
                    if ( (i + j) != (k + p) ) continue;
                    int tmp1 = 0;
                    int i1, i2, j1, j2, k1, k2, p1, p2;
                    i1 = i; j1 = j - 1;
                    i2 = i - 1; j2 = j;
                    k1 = k; p1 = p - 1;
                    k2 = k - 1; p2 = p;
                    if ( i1 != k1 || j1 != p1 ) 
                    tmp1 = max( tmp1, dp[i1][j1][k1][p1] );
                    if ( i1 != k2 || j1 != p2 ) 
                    tmp1 = max( tmp1, dp[i1][j1][k2][p2] );
                    if ( i2 != k1 || j1 != p1 ) 
                    tmp1 = max( tmp1, dp[i2][j2][k1][p1] );
                    if ( i2 != k2 || j2 != p2 ) 
                    tmp1 = max( tmp1, dp[i2][j2][k2][p2] );
                    dp[i][j][k][p] = tmp1 + mp[i][j] + mp[k][p];
                }
    printf( "%d
", dp[m][n][m][n] );
    return 0;
}
  • デュアルスタックソート(twostack.pas/c/cpp)【問題の説明】Tomは最近興味深いソート問題を研究している.図に示すように、2つのスタックS 1およびS 2によって、Tomは、以下の4つの動作によって入力シーケンスを昇順にソートすることを望む.操作a入力シーケンスが空でない場合、第1要素をスタックS 1に押し込む操作bスタックS 1が空でない場合、出力シーケンス操作cにS 1スタックトップ要素をポップアップする入力シーケンスが空でない場合、第1要素をスタックS 2に押し込む操作dスタックS 2が空でない場合、S 2スタックトップ要素を出力シーケンスにポップアップする1~nの配列Pが一連の操作により出力シーケンスを1,2,…,(n−1),n,Tomを「ダブルスタック並べ替え可能配列」と呼ぶことができる.例えば(1,3,2,4)は「ダブルスタックソート可能シーケンス」であり、(2,3,4,1)はそうではない.以下に、(1,3,2,4)を並べ替える(入出力サンプル1)twostackを示す.in twostack.out 4 1 3 2 4 a b a b b a b b(入出力サンプル2)twostack.in twostack.out 4 2 3 4 1 0【入出力サンプル3】twostack.in twostack.out 3 2 3 1 a c a b b d

    • 二分図マッチングでは、Stackに対して、iがjより小さいという性質があり、p[i]およびp[j]がstackを表す要素サイズi、jがStackを表す順序であり、k>jが存在し、p[k]がa[i]より小さいと、いずれにしてもi、jは規則的に出力できない.したがって,このようなi,jを見つけて,2つの間に1つのエッジを接続し,その2つが1つのstackに存在できないことを示すと,最後に2つのstackで出力できれば必然的に1つの二分図となり,1つの集合に2つのエッジがあれば成立しないためである.このような2つのi,jをどのように探すかについて、i以降の連続数列の最小値を表す接尾辞最小配列f[i]を設定する.図を作成した後に染色を行い,そのうちの1つを1,1つを2に染色すると,最後にシミュレーションを行うことでa,b,c,dの優先順位でシミュレーションを行うことができる(筆者は最初はどのように正解するか考えていなかったので,シミュレーションをすばやく3点通過できるようにした)
    /********************
     Accepted

   : 5 ms
0 / 0       .
    
   #twostack1.in    :AC         :  256kB          :  0ms     
   #twostack10.in    :AC         :  256kB          :  0ms     
   #twostack2.in    :AC         :  256kB          :  1ms     
   #twostack3.in    :AC         :  128kB          :  1ms     
   #twostack4.in    :AC         :  256kB          :  0ms     
   #twostack5.in    :AC         :  256kB          :  1ms     
   #twostack6.in    :AC         :  256kB          :  0ms     
   #twostack7.in    :AC         :  256kB          :  0ms     
   #twostack8.in    :AC         :  128kB          :  1ms     
   #twostack9.in    :AC         :  128kB          :  1ms 
********************/
#include 
#include 
#include 
using namespace std;

struct Edge{
    int v, next;
};
Edge e[2005];
int head[1005], num, n, aa[1005], f[1005], col[1005], sa[1005], sb[1005], ta, tb, pos = 1;
void adde( int i, int j ) {
    e[++num].v = j;
    e[num].next = head[i];
    head[i] = num;
    e[++num].v = i;
    e[num].next = head[j];
    head[j] = num;
}
void dfs( int u, int c ) {
    col[u] = c;
    for ( int i = head[u]; i; i = e[i].next ) {
        int v = e[i].v;
        if ( col[v] == c ) {
            printf("0
    "    );
            exit(0);
        }
        if ( !col[v] ) dfs(v, 3 - c);
    }
}
int main() {
    scanf( "%d", &n );
    for ( int i = 1; i <= n; i++ ) scanf( "%d", &aa[i] );
    f[n + 1] = 0x3f3f3f3f;
    for ( int i = n; i >= 1; i-- ) f[i] = min( f[i + 1], aa[i] ); 
    for ( int i = 1; i < n; i++ )
        for ( int j = i + 1; j <= n; j++ ) if ( aa[i] < aa[j] && f[j + 1] < aa[i] ) adde(i, j);
    for ( int i = 1; i <= n; i++ ) if ( !col[i] ) dfs(i, 1);
    for ( int i = 1; i <= n; i++ ) {
        if ( col[i] == 1 ) {
            sa[++ta] = aa[i];
            printf("a ");
        } else {
            sb[++tb] = aa[i];
            printf("c ");
        }
        while ( ta && sa[ta] == pos || tb && sb[tb] == pos ) {
            if ( ta && sa[ta] == pos ) {
                ta--;
                printf("b ");
            }
            if ( tb && sb[tb] == pos ) {
                tb--;
                printf("d ");
            }
            pos++;
        }
    }
    return 0;
}
    jqに基づいてAPKファイルのドラッグアップロードを実現し、jsはAPK情報を解析する
    汽車の切符の販売