latex預處理

\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年1月20日 星期三

[ codeforces ] ACM ICPC 2015–2016, Northeastern European Regional J Jump

題目:
http://codeforces.com/gym/100851
互動題,猜字串遊戲,輸入n表示字串長度,你要輸出一個字串給他
他會輸入你猜的字串的回傳值,只有當猜對的字元數=n/2或n時回傳值才會是猜對的字元數,否則回傳值是0
n<=1000,你要在n+500次內猜出他的字串是什麼

解法:
根據斯特靈(Stirling)公式
可知隨機找出剛好一半字元是正確的機率近似於
幾乎可以在sqrt(n)次內找出剛好一半字元是正確的字串,接下因為字串有一半是錯的,所以可以把字元分成兩堆,設字串為s,分法如下:

分成A、B兩堆
設s[0]屬於A,對於s[1]~s[n-1],把他們分別跟s[0]取not,假設現在是第i個字元
s[0]^=1;
s[i]^=1;
輸出答案進行判斷,如果回傳值仍是n/2表示s[i]屬於A,否則s[i]屬於B
如果過程中出現回傳值=n就結束程式

最後先對A裡面所有字元取not,如果不是答案再把整個字串取not即可
記住記得要清空輸出的緩衝區確保及時輸出
c用fflush(stdout);
c++用cout.flush();

code:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
int n,an;
char s[1005];
bool is[1005];
int main(){
    srand(time(0));
    scanf("%d",&n);
    for(;;){
        for(int i=0;i<n;++i){
            s[i]=rand()%2+'0';
        }
        puts(s);fflush(stdout);
        scanf("%d",&an);
        if(an)break;
    }
    if(an==n)return 0;
    s[0]^=1;
    for(int i=1;i<n;++i){
        s[i]^=1;
        puts(s);fflush(stdout);
        scanf("%d",&an);
        if(an==n)return 0;
        if(an)is[i]=1;
        s[i]^=1;
    }
    s[0]^=1;
    for(int i=0;i<n;++i){
        if(is[i])s[i]^=1;
    }
    puts(s);fflush(stdout);
    scanf("%d",&an);
    if(an==n)return 0;
    for(int i=0;i<n;++i){
        s[i]^=1;
    }
    puts(s);fflush(stdout);
    scanf("%d",&an);
    return 0;
}

沒有留言:

張貼留言