青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

此 blog 已棄。

微軟2014實(shí)習(xí)生及秋令營技術(shù)類職位在線測試


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


解法:
窮舉兩元素交換,使用修改的歸并排序求逆序?qū)?shù),時間復(fù)雜度O(n*n*n*logn)。



4.Most Frequent Logs
不會。










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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            99综合在线| 亚洲卡通欧美制服中文| 欧美日韩精品不卡| 久久字幕精品一区| 国产精品一区亚洲| 99精品免费| 夜夜躁日日躁狠狠久久88av| 久久久久久尹人网香蕉| 欧美伊久线香蕉线新在线| 欧美性视频网站| 亚洲精品精选| 亚洲美女视频在线观看| 老鸭窝亚洲一区二区三区| 久久久精品国产免费观看同学| 国产精品久久久久久av福利软件| 亚洲伦理在线| 99国产精品久久久久老师| 欧美成人视屏| 亚洲黄色尤物视频| 日韩亚洲欧美一区二区三区| 欧美国产日韩一区二区| 亚洲激情综合| 99综合电影在线视频| 欧美日本国产一区| 一区二区三区视频免费在线观看| 亚洲视频中文字幕| 国产精品日韩欧美| 亚洲欧美日韩国产中文| 久久精品二区| 在线看片一区| 欧美成人午夜剧场免费观看| 亚洲人成小说网站色在线| 99精品国产99久久久久久福利| 欧美伦理在线观看| 亚洲视频一区二区免费在线观看| 亚洲欧美伊人| 狠狠狠色丁香婷婷综合久久五月| 久久久久久有精品国产| 欧美激情综合色| 国产精品99久久久久久人| 欧美午夜免费电影| 久久国产精彩视频| 亚洲国产精品美女| 亚洲专区国产精品| 激情久久婷婷| 欧美极品影院| 亚洲欧美日韩第一区| 免费欧美日韩| 在线综合欧美| 国产在线观看精品一区二区三区| 开心色5月久久精品| 99热在线精品观看| 久久亚洲春色中文字幕久久久| 亚洲理伦在线| 国产一区三区三区| 欧美国产精品v| 性8sex亚洲区入口| 亚洲精品欧洲| 久久乐国产精品| 一区二区三区精品视频| 国产亚洲成av人在线观看导航| 免费h精品视频在线播放| 亚洲精品视频在线观看网站| 久久久久亚洲综合| 亚洲天堂网在线观看| 精品999在线播放| 国产精品videossex久久发布| 久久视频免费观看| 亚洲一区国产精品| 91久久线看在观草草青青| 久久久99爱| 亚洲欧美成人一区二区在线电影| 亚洲福利小视频| 国产日韩欧美综合一区| 欧美日韩精品一区二区三区四区| 久久久av网站| 午夜精品视频在线观看一区二区| 亚洲精品国产精品国产自| 美女999久久久精品视频| 午夜精品美女自拍福到在线 | 含羞草久久爱69一区| 国产精品jizz在线观看美国| 欧美不卡一卡二卡免费版| 久久九九免费视频| 亚洲欧美一区二区三区久久| 一本色道久久综合狠狠躁篇怎么玩 | 久久噜噜亚洲综合| aⅴ色国产欧美| 久久久精彩视频| 欧美在线不卡| 亚洲在线中文字幕| 日韩视频永久免费| 亚洲三级网站| 亚洲国产精品一区制服丝袜| 国产自产高清不卡| 国产欧美在线视频| 国产美女在线精品免费观看| 国产精品久久久久毛片大屁完整版 | 亚洲韩国日本中文字幕| 久久久天天操| 欧美一区二区三区在| 亚洲欧美另类在线观看| 亚洲一区二区伦理| 亚洲一区二区三区在线| 亚洲图片欧洲图片av| 99亚洲一区二区| 国产精品99久久久久久人| 一区二区久久| 亚洲午夜久久久久久久久电影院| 99在线精品观看| 亚洲系列中文字幕| 午夜亚洲视频| 久久精品综合网| 女生裸体视频一区二区三区| 欧美a级大片| 亚洲经典视频在线观看| 99在线精品视频在线观看| 亚洲午夜激情| 久久精品亚洲热| 免费视频一区二区三区在线观看| 欧美ed2k| 国产精品成人一区二区三区吃奶| 国产精品日韩精品| 在线成人激情视频| 日韩视频三区| 午夜在线精品| 欧美成年人视频网站| 亚洲精品乱码久久久久久久久 | 亚洲一区欧美| 久久久久久久综合| 亚洲国产精品高清久久久| 99精品视频免费观看| 性色一区二区| 欧美黄色aaaa| 国产精品午夜在线| 亚洲高清在线精品| 亚洲欧美中文字幕| 欧美肥婆在线| 亚洲综合视频1区| 玖玖玖国产精品| 国产精品高精视频免费| 精品电影在线观看| 亚洲性线免费观看视频成熟| 久久天天狠狠| 在线一区二区三区四区五区| 久久久久国产一区二区| 欧美肉体xxxx裸体137大胆| 国产一区再线| 亚洲一区二区三区四区在线观看| 美女精品国产| 亚洲一区免费观看| 欧美激情一区在线观看| 国产一区二区精品| 亚洲午夜国产成人av电影男同| 久久久爽爽爽美女图片| 99成人精品| 欧美**人妖| 黄色工厂这里只有精品| 亚洲在线1234| 亚洲二区在线视频| 久久国产精品久久国产精品| 欧美日韩天天操| 亚洲国产欧美日韩| 久久久久高清| 亚洲欧美日韩精品久久亚洲区 | 亚洲精品日韩精品| 久久亚洲风情| 国产在线欧美日韩| 亚洲综合色自拍一区| 91久久综合亚洲鲁鲁五月天| 久久久噜噜噜久噜久久| 国产美女精品视频| 亚洲欧美国产毛片在线| 日韩一区二区精品| 欧美大片在线观看一区| 在线看视频不卡| 另类春色校园亚洲| 久久黄金**| 韩国在线视频一区| 久久久久久久久久久一区| 午夜激情综合网| 国产欧美日韩三区| 欧美一区二区三区久久精品茉莉花| 一区二区精品在线| 欧美性jizz18性欧美| 亚洲一区二区三区精品在线| 亚洲美女黄网| 欧美日韩综合一区| 亚洲专区一区二区三区| 一区二区三区四区国产| 欧美午夜国产| 欧美亚洲视频一区二区| 亚洲免费综合| 国内精品国产成人| 另类图片国产| 欧美大尺度在线观看| 99国产精品国产精品久久| 夜夜嗨av色一区二区不卡| 国产精品成人一区| 久久疯狂做爰流白浆xx|