日月卦長的解題紀錄: 1月 2016

2016年1月25日星期一

[ codeforces ] Round #340 (Div. 2) E. XOR and Favorite Number

題目:
http://codeforces.com/contest/617/problem/E
給一個序列a1,a2,a3......an，再給一個k
接下來有m個詢問，給兩個數字l,r，問:
對於所有的i,j滿足l<=i<=j<=r，ai 到 aj所有數字的xor值=k的(i,j)有幾個

解法:
很直接就想到莫隊，關於該算法的實作就不多說了
先把序列做前綴xor再進行處理
注意計數用的陣列大小必須大於2^20 (1000000的二進位是11110100001001000000，但是兩個<1000000的數xor起來可以到11111111111111111111=(2^20)-1)
還有add,sub裡面操作的順序也要注意

code:

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define MAXQ 100000
struct Q{
    int l,r,i,block;
    inline bool operator<(const Q &b)const{
        return block==b.block?r<b.r:block<b.block;
    }
}q[MAXQ+5];
int n,m,k;
int s[MAXN+5];
long long ans[MAXQ+5];
int p[(1<<20)+1];
long long cur_ans;
inline void add(int x){
    cur_ans+=p[x^k];
    ++p[x];
}
inline void sub(int x){
    --p[x];
    cur_ans-=p[x^k];
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i){
        scanf("%d",&s[i]);
        s[i]^=s[i-1];
    }
    int lim=1+(int)sqrt(n);
    for(int i=0;i<m;++i){
        scanf("%d%d",&q[i].l,&q[i].r);
        --q[i].l;
        q[i].block=q[i].l/lim;
        q[i].i=i;
    }
    sort(q,q+m);
    for(int i=0,L=0,R=-1;i<m;++i){
        while(R<q[i].r)add(s[++R]);
        while(L>q[i].l)add(s[--L]);
        while(R>q[i].r)sub(s[R--]);
        while(L<q[i].l)sub(s[L++]);
        ans[q[i].i]=cur_ans;
    }
    for(int i=0;i<m;++i)printf("%lld\n",ans[i]);
    return 0;
}

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:

#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;
}

2016年1月5日星期二

[ UVA ] 741 - Burrows Wheeler Decoder

題目:
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=682

解法:
BWT 逆轉換，可以參考Morris的這篇，透過觀察題目範例:

1. A B A N A N
2. A N A B A N
3. A N A N A B
4. B A N A N A
5. N A B A N A
6. N A N A B A
(我們只知道最後一行(設為字串s)的NNBAAA和原字串在第4個位置)

發現我們只能利用排序求出第一行的AAABNN，因為BWT轉換是利用字串rotate，所以可以把s和它結合起來
NA
NA
BA
AB
AN
AN
在排序就可以得到前兩行了
AB
AN
AN
BA
NA
AN
同樣發現因為rotate的關係，所以可以再開頭加上s求出前三行.....以此類推

code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    bool is=0;
    string s;
    for(int p;cin>>s>>p;){
        if(s=="END")break;
        if(is)cout<<endl;
        is=1;
        int n=s.length();
        string a[n];
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j)a[j]=s[j]+a[j];
            sort(a,a+n);
        }
        cout<<a[p-1]<<endl;
    }
    return 0;
}

latex預處理

2016年1月25日 星期一