2012年9月27日 星期四

CodeForces #140 (Div 2)

I have figure out the solution for the last problem,

but I didn't notice one of the point, so I didn't accepted it in the contest.

Though I have accepted it afterward. This is surely a great competition.

I learned a lot from it, and I should become stronger.

One more thing, my code is always full of bugs, I should get rid of this awful custom.

2012年9月23日 星期日

Ural 1002 Phone Numbers

I figure out that pasting a code here isn't that useful.

More importantly, we must understand the outline of what we're suppose to code

as soon as we figure out the algorithm to solve it.

So I will put a diagram here to show the process instead.

I use Aho_Corasick Algorithm to solve this.

============================================================


2012年9月15日 星期六

Class

What is the difference between Class and Struct?

Class can change the accessibility to it's content, but Struct can not.

And the default to class is private, and to Struct is Public.

This is just a memo and organization of what I've learned so far.

public means you can call or act on it from outside the class,

protected means you can call or act on it only from the class or the derived classes,

private means you can call or act on it only from the class.

1. Inheritance:

//By momo
#include<iostream>
using namespace std;
class A{
    public:
    int x;
};
class B: public A{
    public:
    int y;
}x;

Using class XXX: xxxxx XXX, use the code above as an example, B inherit from A.

But what is Inherit??? It actually means that all the functions and variables in A can be used in B,

and that is why we call B inherit from A.

And when you use inheritance, use the code above as an example, it can rewrite as this:

//By momo
#include<iostream>
using namespace std;
class B:{
    public:
    int x;
    public:
    int y;
}x;

they are both the same, you can taste a little bit about it.

2. Friendship:

If you are a friend with someone, you two share all the protected and private information with each other(only if you two are true friends)

//By momo
#include<iostream>
using namespace std;
class A{
    private:
    int x;
    friend class B;
}a;
class B{
    public:
    int y;
    void prnt(A x){cout << x.x << endl;}
}b;

Like this is OK, it won't give a compile error. And the friend statement can be written at anywhere in the class. But something like this is not OK,

//By momo
#include<iostream>
using namespace std;
class A{
    private:
    int x;
}a;
class B{
    public:
    int y;
    friend class A;
    void prnt(A x){cout << x.x << endl;}
}b;

It will give out a CE that says x is not accessible. The friend statement is only single way.

3. Constructor:

Just one thing to remember, constructor should always have it's accessibility turned to public.

//By momo
#include<iostream>
using namespace std;
class A{
    public:
    A(){ x = 1; }
    private:
    int x;
}a;

------------------------------------------------------------------------------------------------------------

Class is such a fun thing, and I am told today that the array inside will be initialize, so convenient( from Yo Chiang )

2012年9月12日 星期三

URAL 1051. Simple Game on a Grid

//By momo
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    if(n > m) swap(n, m);
    if(n == 1) printf("%d\n", (m+1)/2);
    else if(n%3 == 0 || m%3 == 0) puts("2");
    else puts("1");
}

先排除 n 或 m 是 1 的可能。(數量很簡單算,就是 (n+1)/2)

---------------------------------------------------------------------------------

所以來討論只看 n > 1 且 m > 1 的情況:

證 n == 3k || m == 3k' 時,答案不可能是1:

作法(來自Yuhc's Blog)-

讓 a = (x+y)=0(mod 3), b = (x+y)=1(mod 3), c = (x+y)=2(mod 3),

當吃掉旁邊時,兩個減一,一個加一,且發現此情況,a = b = c, 故a%2 = b%2 = c%2,

因此場面剩下一個,代表其一為 1, 剩餘為 0, 不可能發生,QED。


再加上兩種神奇的消去法,可以把所有大的型態全部歸納出幾種,

除了其一是 3k 時是 2,其他都是 1。

方法一

方法二

2012年9月9日 星期日

CodeForces 204D. Little Elephant and Retro Strings

//By momo
#include<cstdio>
#define N 1000010
#define M 1000000007
#define LL long long

LL n, k, ans, i; char a[N];
LL W[N], B[N], b[N], cnt;

int main(){
    scanf("%I64d%I64d%s", &n, &k, a+1);
    
    b[0] = 1; cnt = 0;
    for(i = 1; i <= n; i++){
        if(a[i] == 'W') cnt = 0;
        else cnt++;
        if(a[i] == 'X') b[i] = (b[i-1]*2)%M;
        else b[i] = b[i-1];
        
        if(cnt < k) continue;
        if(i == k) b[i] = (b[i]-1+M)%M, B[i] = 1;
        else if(a[i-k] != 'B')
            b[i] = (b[i]-b[i-k-1]+M)%M, B[i] = b[i-k-1];
    }
    
    b[n+1] = 1; cnt = 0;
    for(i = n; i >= 1; i--){
        if(a[i] == 'B') cnt = 0;
        else cnt++;
        if(a[i] == 'X') b[i] = (b[i+1]*2)%M, W[i] = (W[i+1]*2)%M;
        else b[i] = b[i+1], W[i] = W[i+1];

        if(cnt < k) continue;
        if(i == n-k+1) b[i] = (b[i]-1+M)%M, W[i] = 1;
        else if(a[i+k] != 'W')
            b[i] = (b[i]-b[i+k+1]+M)%M, W[i] = (W[i]+b[i+k+1])%M;
    }
    for(i = 1; i <= n; i++) ans = (ans+B[i]*W[i+1]%M)%M;
    printf("%I64d\n", ans);
}
This problem is way complicated than I expected it.After I finish reading the problem, something comes to my mind.

I can do the left half of it then do the right one,

so I then wrote something idiotic that has many same combination in it. I try to fix the problem, but suddenly found out I am STUCK. After eating my lunch, I finally figure it out.

And here comes the solution...

First, I'll do the left part of it, which is the Bs.

To cross out the repeated combination, the thing I keep track of ( B[i] ) is a set of combination that end at point i, with no other k consecutive Bs on its left. b[i] does the job of subtracting the combination with other k consecutive Bs, and B[i] is the thing we need.

Second, I'll use the same method to find the right part of it, which is the Ws.

But we can have more freedom on the right side( you can choose which side you want to give more freedom to, but there should only be one side. )

For example:

k = 3 ( O means optional. )

OOOWBBB | WWWOOOO
OOOWBBB | OOOWWWO
OOOWBBB | OWWWOOO

the left side must be WBBB, but the right side has more freedom, you can choose which position you want to put 3Ws in. But if you give freedom to both side, sth terrible will happen:

Take another example,

k = 3

WWWBBB   B | WWWWWWW
WWWBBB | B   WWWWWWW

they are the same but will be counted twice.
Be careful and you can easily accept this problem.

2012年9月6日 星期四

CodeForces 220C. Little Elephant and Shifts

//By momo
#include<set>
#include<cstdio>
#include<algorithm>
#define N 100010
using namespace std;
multiset<int> s;
int n, a[N], b[N], c[N], i, j;
int main(){
    scanf("%d", &n);
    for(i = 0; i < n; i++) scanf("%d", &j), c[j] = i;
    for(i = 0; i < n; i++) scanf("%d", &b[i]), s.insert(i - c[b[i]]);
    for(i = 0; i < n; i++){
        multiset<int>::iterator it = s.lower_bound(i);
        int ans = 999999999;
        if(it != s.end())   ans = min(ans, *it-i);
        if(it != s.begin()) ans = min(ans, i-(*(--it)));
        printf("%d\n", ans);
        s.erase(s.find(i-c[b[i]]));
        s.insert((i+n)-c[b[i]]);
    }
}
There are so much great problems in Codeforces.

This is one of the best problem I have.

It's not hard but fun, and I've learned a lot from it.

Multiset:

1. insert(x): log(Size)
   insert(pos, x): if x is inserted right after pos, Constant.
   insert(begin, end): Nlog(N+size)

2. erase(pos): Constant
   erase(x): Erase all value of x

3. lower_bound(x): find the pos with value >= x
   upper_bound(x):                         >

4. equal_range(x): return a pair of iterator

5. find(x): return iterator point at x(if not found return end())

Multiset is a pretty useful tool, it's an upgrade of set, with all of the functions from set available in it.