• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            coreBugZJ

            此 blog 已棄。

            微軟2014實習生及秋令營技術類職位在線測試


            1.String reorder

            Time Limit: 10000ms
            Case Time Limit: 1000ms
            Memory Limit: 256MB

             

            Description

            For this question, your program is required to process an input string containing only ASCII characters between ‘0’ and ‘9’, or between ‘a’ and ‘z’ (including ‘0’, ‘9’, ‘a’, ‘z’).

            Your program should reorder and split all input string characters into multiple segments, and output all segments as one concatenated string. The following requirements should also be met,
            1. Characters in each segment should be in strictly increasing order. For ordering, ‘9’ is larger than ‘0’, ‘a’ is larger than ‘9’, and ‘z’ is larger than ‘a’ (basically following ASCII character order).
            2. Characters in the second segment must be the same as or a subset of the first segment; and every following segment must be the same as or a subset of its previous segment.

            Your program should output string “<invalid input string>” when the input contains any invalid characters (i.e., outside the '0'-'9' and 'a'-'z' range).

             

            Input

            Input consists of multiple cases, one case per line. Each case is one string consisting of ASCII characters.

             

            Output

            For each case, print exactly one line with the reordered string based on the criteria above.

             

            Sample In

            aabbccdd
            007799aabbccddeeff113355zz
            1234.89898
            abcdefabcdefabcdefaaaaaaaaaaaaaabbbbbbbddddddee


            Sample Out

            abcdabcd
            013579abcdefz013579abcdefz
            <invalid input string>
            abcdefabcdefabcdefabdeabdeabdabdabdabdabaaaaaaa


            代碼:
             1#include <cstdio>
             2#include <cstring>
             3
             4using namespace std;
             5
             6typedef  long long  Lint;
             7
             8#define  L  256
             9Lint cnt[ L ];
            10Lint tot;
            11
            12#define  INVALID  "<invalid input string>"
            13
            14int main() {
            15        int ch = 1;
            16        int i;
            17        int invalid;
            18        while ( EOF != ch ) {
            19                memset( cnt, 0sizeof(cnt) );
            20                for ( ch = getchar(); (EOF != ch) && ('\n' != ch); ch = getchar() ) {
            21                        ++cnt[ ch ];
            22                        ++tot;
            23                }

            24                invalid = 0;
            25                for ( i = 0; i < L; ++i ) {
            26                        if (    (0 < cnt[ i ]) && 
            27                                (!      (       ( ('0' <= i) && ('9' >= i)
            28                                                ) || 
            29                                                ( ('a' <= i) && ('z' >= i)
            30                                                )
            31                                        )
            32                                )
            33                        ) {
            34                                invalid = 1;
            35                                break;
            36                        }

            37                }

            38                if ( invalid ) {
            39                        puts( INVALID );
            40                        continue;
            41                }

            42
            43                while ( 0 < tot ) {
            44                        for ( i = 0; i < L; ++i ) {
            45                                if ( 0 < cnt[ i ] ) {
            46                                        putchar( i );
            47                                        --cnt[ i ];
            48                                        --tot;
            49                                }

            50                        }

            51                }

            52                puts( "" );
            53        }

            54        return 0;
            55}

            56




            2.K-th string

            Time Limit: 10000ms
            Case Time Limit: 1000ms
            Memory Limit: 256MB

             

            Description

            Consider a string set that each of them consists of {0, 1} only. All strings in the set have the same number of 0s and 1s. Write a program to find and output the K-th string according to the dictionary order. If s​uch a string doesn’t exist, or the input is not valid, please output “Impossible”. For example, if we have two ‘0’s and two ‘1’s, we will have a set with 6 different strings, {0011, 0101, 0110, 1001, 1010, 1100}, and the 4th string is 1001.


            Input

            The first line of the input file contains a single integer t (1 ≤ t ≤ 10000), the number of test cases, followed by the input data for each test case.
            Each test case is 3 integers separated by blank space: N, M(2 <= N + M <= 33 and N , M >= 0), K(1 <= K <= 1000000000). N stands for the number of ‘0’s, M stands for the number of ‘1’s, and K stands for the K-th of string in the set that needs to be printed as output.


            Output

            For each case, print exactly one line. If the string exists, please print it, otherwise print “Impossible”.


            Sample In

            3
            2 2 2
            2 2 7
            4 7 47

            Sample Out

            0101
            Impossible
            01010111011


            代碼:
             1#include <cstdio>
             2#include <cstring>
             3
             4using namespace std;
             5
             6#define  IMP  "Impossible"
             7
             8typedef  long long  Lint;
             9
            10#define  L  35
            11
            12Lint c[ L ][ L ];
            13char ans[ L+L ];
            14
            15void init() {
            16        int i, j;
            17        memset( c, 0sizeof(c) );
            18        c[ 0 ][ 0 ] = 1;
            19        for ( i = 1; i < L; ++i ) {
            20                c[ i ][ 0 ] = c[ i ][ i ] = 1;
            21                for ( j = 1; j < i; ++j ) {
            22                        c[ i ][ j ] = c[ i-1 ][ j-1 ] + c[ i-1 ][ j ];
            23                }

            24        }

            25}

            26
            27static int solve_i( int n0, int n1, int idx, int off ) {
            28        if ( (0 == n0) && (0 == n1) && (0 == idx) ) {
            29                return 1;
            30        }

            31
            32        if ( ((1 > n0) || (1 > n1)) && (1 != idx) ) {
            33                return 0;
            34        }

            35
            36        if ( 1 == idx ) {
            37                for ( int i = 0; i < n0; ++i ) {
            38                        ans[ off + i ] = '0';
            39                }

            40                for ( int i = 0; i < n1; ++i ) {
            41                        ans[ off + n0 + i ] = '1';
            42                }

            43                return 1;
            44        }

            45
            46        int i = 0;
            47        while ( c[n1+i-1][i] < idx ) {
            48                idx -= c[n1+i-1][i];
            49                ++i;
            50        }

            51        for ( int j = 0; j < n0 - i; ++j ) {
            52                ans[ off + j ] = '0';
            53        }

            54        ans[ off + n0 - i ] = '1';
            55        return solve_i( i, n1-1, idx, off + n0 - i + 1 );
            56}

            57
            58/*
            59n0=n=4, n1=m=7, idx=k=47
            60
            61i   n0      n1
            62
            630   0000    1??????     c[6][0] = 1
            641   0001    ???????     c[7][1] = 7
            652   001?    ???????     c[8][2] = 28
            663   01??    ???????     c[9][3] = 84
            674   1???    ???????     c[10][4]
            68
            69*/

            70
            71int solve( int n, int m, int k ) {
            72        if ( c[n+m][n] < k ) {
            73                return 0;
            74        }

            75        memset( ans, 0sizeof(ans) );
            76        return solve_i( n, m, k, 0 );
            77}

            78
            79int main() {
            80        int tot_case;
            81        int n, m, k;
            82
            83        init();
            84
            85        scanf( "%d"&tot_case );
            86        while ( 0 < tot_case-- ) {
            87                scanf( "%d%d%d"&n, &m, &k );
            88
            89                if ( solve( n, m, k ) ) {
            90                        puts( ans );
            91                }

            92                else {
            93                        puts( IMP );
            94                }

            95        }

            96
            97        return 0;
            98}

            99




            3.Reduce inversion count

            Time Limit: 10000ms
            Case Time Limit: 1000ms
            Memory Limit: 256MB

            Description

            Find a pair in an integer array that swapping them would maximally decrease the inversion count of the array. If such a pair exists, return the new inversion count; otherwise returns the original inversion count.

            Definition of Inversion: Let (A[0], A[1] ... A[n]) be a sequence of n numbers. If i < j and A[i] > A[j], then the pair (i, j) is called inversion of A.

            Example:
            Count(Inversion({3, 1, 2})) = Count({3, 1}, {3, 2}) = 2
            InversionCountOfSwap({3, 1, 2})=>
            {
              InversionCount({1, 3, 2}) = 1 <-- swapping 1 with 3, decreases inversion count by 1
              InversionCount({2, 1, 3}) = 1 <-- swapping 2 with 3, decreases inversion count by 1
              InversionCount({3, 2, 1}) = 3 <-- swapping 1 with 2 , increases inversion count by 1
            }


            Input

            Input consists of multiple cases, one case per line.Each case consists of a sequence of integers separated by comma.

            Output

            For each case, print exactly one line with the new inversion count or the original inversion count if it cannot be reduced.


            Sample In

            3,1,2
            1,2,3,4,5

            Sample Out

            1
            0


            解法:
            窮舉兩元素交換,使用修改的歸并排序求逆序對數,時間復雜度O(n*n*n*logn)。



            4.Most Frequent Logs
            不會。










            posted on 2014-04-13 19:11 coreBugZJ 閱讀(3738) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm

            伊人久久大香线焦综合四虎| 欧美午夜A∨大片久久 | 四虎国产精品免费久久久| 热久久这里只有精品| 一本色综合久久| 久久久久久a亚洲欧洲aⅴ| 免费久久人人爽人人爽av| 97久久精品国产精品青草| 亚洲性久久久影院| 成人国内精品久久久久影院VR | 久久精品成人免费网站| 一本久道久久综合狠狠躁AV| a高清免费毛片久久| 国产成人无码精品久久久性色| 品成人欧美大片久久国产欧美| 欧美黑人激情性久久| 久久精品亚洲男人的天堂| 国产91久久精品一区二区| 国产美女亚洲精品久久久综合| 欧美久久一级内射wwwwww.| 99久久精品免费观看国产| 国产精品久久久久影院色| 亚洲AV无码久久精品成人| 国产69精品久久久久观看软件| 久久久精品波多野结衣| 久久―日本道色综合久久| 1000部精品久久久久久久久| 久久人妻少妇嫩草AV无码专区| 99久久精品免费看国产一区二区三区 | 亚洲成色WWW久久网站| 久久精品中文字幕第23页| 久久久久久亚洲精品影院| 亚洲国产成人久久一区WWW| 久久国产精品视频| 日本精品久久久久影院日本 | 午夜不卡久久精品无码免费| 伊人久久大香线蕉亚洲| 亚洲欧洲日产国码无码久久99| 99久久国产综合精品女同图片| 色婷婷久久综合中文久久蜜桃av| 久久精品www人人爽人人|