Codeforces 198E. Gripping Story

線段樹的變形真的很經典

這題要做的就是我們希望可以把 距離 <=  r 的區段

重量都小於等於力量的物質挑出來，放入queue裡

每一個物質都有兩個變量，距離以及重量

要對 <= 某距離內，找出 <= 某重量 的物質

這時，我們要用到一個很基本的概念：區段樹

就是一個線段樹，但是他的每一個節點，不是單單包含一個值

而是包含了這個區段的所有元素！

這麼看的話，感覺還挺崩潰的，但是可以知道每個元素只會被lgn個包含

所以元素數量是 NlgN ，非常的好用

有了這個方向之後，是否就很簡單了呢？答案是：Yes

只要讓那個區段的值都是由小排到大的，之後在query時

就從前面開始取出即可

（我是用Set去讓他由小到大的，整體複雜度nlg^2n，但只要質量小的放到質量大的，就可以用nlgn的時間，解出來了）

想要看code，可以直接去codeforces，上面找。

Codeforces 266D BerDonalds

奇怪的題目名字，應該是學 Mcdonalds 的吧

如果他說只能在點上，就好辦了

直接做一次Floyd，就可以得到答案了

但！問題就在於你可以位於其中的無限多個點的其中一個

前面都很無腦，接下來就需要用到好腦袋惹～
（要了解很簡單，但要想到有點難＝＝）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

其實可以這樣想，先想對於一個邊你要到所有人的最短距離

就是，這邊的兩端為 a, b，min( x + dis[ a ][ i ], c - x + dis[ b ][ i ] )對所有 i 的max要最小

直接做枚舉可能答案的動作，是最簡單也是最方便的（比起二分搜或三分搜）

所以就先朝著枚舉答案的方向思考（也就是哪些中間點要試放看看這樣）

假設所有點的集合是這樣（a, b, c, d, e...），將他分成兩個集合A, B

A代表要讓這個邊的 a 去連會是min， B代表要讓這個邊的 b 去連會是min

也就是我們假定對A集合min(剛剛那團) 會是 a 的比較小，B也是同樣的道理

而若是這麼一回事的話，拿A的最大值，B的最大值，就可以組出想要的 x 了。

枚舉A的最大值，然後求B（補集）的最大值，弄出所有可能的X，再取最小的即可。

//By momo
#include
#include
#include
#define N 210
#define INF 999999999
using namespace std;

double ans = INF;
int n, m, dis[N][N];
int a[N*N], b[N*N], c[N*N];
struct pairr{ int a, b; }d[N];
bool comp(pairr x, pairr y){ return x.a > y.a; }

int main (){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) dis[i][j] = INF;
        dis[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        a[i]--, b[i]--;
        dis[a[i]][b[i]] = dis[b[i]][a[i]] = c[i];
    }
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dis[i][j] = min(dis[i][j],
                            dis[i][k] + dis[k][j]);
    for(int i = 0; i < m; i++){
        int C = c[i];
        for(int j = 0; j < n; j++){
            d[j].a = dis[a[i]][j];
            d[j].b = dis[b[i]][j];
        }
        sort(d, d+n, comp);
        int M = d[0].b; ans = min(ans, 1.0*d[0].a);
        for(int j = 1; j < n; j++){
            double val;
            if(d[j].a > M - C && M + C > d[j].a)
                val = (d[j].a+M+C) / 2.0;
            else val = max(d[j].a, M);
            ans = min(ans, val);
            M = max(M, d[j].b);
        }
    }
    printf("%lf\n", ans);
}

Codeforces 258B Little Elephant and Election 4/10

非常經典的一個題目

重點在他的第一個部分：

給一個  有N位 的數字 M，問1~M

有1個4 or 7的有幾個

有2個4 or 7的有幾個

有3個4 or 7的有幾個

…

這樣。

比較好的作法應該是

從最高位開始，從那位以前都一樣

但枚舉那一位的大小（小於原本的值）

再去枚舉剩下的位置有幾個4

最後再用nCm去計算～

這樣編程複雜度低，時間複雜度也很低

scanf("%d", &m), m++, cnt[0]--;

while(m) a[++n] = m % 10, m /= 10;

for (int i = 0; i <= 15; i++)

    for (int j = 0; j <= i; j++)

        C[i][j] = i && j? (C[i-1][j-1]+C[i-1][j]) % M: 1;

for (int i = n; i; i--){

    for (int j = 0; j < a[i]; j++){

        LL now = 1LL << i-1;

        for (int k = i-1; k >= 0; k--){

            cnt[prv+(j == 4 || j == 7)+k] += now * C[i-1][k];

            now *= 8/2;

        }

    }

    prv += (a[i] == 4 || a[i] == 7);

}

Codeforces 243B Hydra

題目敘述：

給一個圖，沒有自環或重邊，問有沒有一隻多頭龍

有一個很簡單的作法可行：

『枚舉 u，然後枚舉 v，接著判斷可不可以』


也就是O(E)＊一個不知道是多少但感覺很大的東西


感覺就會TLE，但這題神奇的地方就在於他的時間複雜度

先把可以當成頭的點記錄起來，接下來判斷可以當成尾巴的點的數量

作法如下：

如果head的數量夠多，且某個head可以當成tail，那就把它當成tail

如果他只能是tail，照樣把它當成tail

一直做到有足夠的tail了或是沒辦法再有其他tail了，就結束

for(int i = 0; cnt < t && i < SZ(G[v]); i++)

{

    int x = G[v][i];

    if(x == u) continue;

    if(rem && vst[x]) rem--, tail[cnt++] = x;

    else if(!vst[x]) tail[cnt++] = x;

}

重點其實就是怕cnt不會變多（因為 t <= 100）

但如果cnt不會變多，其實也就是 rem == h

那麼最多跑 h 次，cnt便又會開始增加

因此時間複雜度為O(h+t)，總時間複雜度O(E*(h+t))，2*10^7

//By momo
#include<cstdio>
#include<vector>
#include<algorithm>

#define N 100010
#define PB push_back
#define SZ(x) (int)((x).size())
#define FOR(it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)

using namespace std;

int n, m, h, t;
int vst[N], rev[N], che[N];
vector<int> G[N];

int main(){
    scanf("%d%d%d%d", &n, &m, &h, &t);
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        G[a].PB(b); G[b].PB(a);
    }
   
    for(int u = 1; u <= n; u++)
    {
        if(SZ(G[u]) <= h) continue;
        FOR(it, G[u]) vst[*it] = 1;
        FOR(it, G[u])
        {
            if(SZ(G[*it]) <= t) continue;

            int v = *it;
            int cnt = 0;
            int rem = SZ(G[u])-h-1;

            for(int i = 0; cnt < t && i < SZ(G[v]); i++)
            {
                int x = G[v][i];
                if(x == u) continue;
                if(rem && vst[x]) rem--, che[x] = 1, rev[cnt++] = x;
                else if(!vst[x]) rev[cnt++] = x;
            }

            if(cnt == t)
            {
                printf("YES\n%d %d\n", u, v);
                int c = 0;
                FOR(it2, G[u])
                {
                    if(che[*it2] || *it2 == v) continue;
                    printf("%d ", *it2);
                    if((++c) == h) break;
                }puts("");
                for(int i = 0; i < cnt; i++) printf("%d ", rev[i]);
                puts("");

                return 0;
            }

            for(int i = 0; i < cnt; i++) che[rev[i]] = 0;
        }
        FOR(it, G[u]) vst[*it] = 0;
    }
    puts("NO");
}

Codeforces 228E The Road to Berland is Paved With Good Intentions

因為去兩次等於沒去，題目也沒問最小天，亂做即可

也就是只需判斷可不可以符合所有條件

條件是什麼？

if C(u, v) == 1, P(u)  = P(v)（即是 若P(u)則P(v)&若!P(v)則!P(v)，反向亦可）

if C(u, v) == 0, P(u) != P(v) （同上）

C為有沒有上過柏油，P為要不要上柏油

所以，

Disjoint Set!

酷似2-SAT，但是無需用這麼複雜的方法

因為2-SAT其實是一個較廣泛，不論解單向或雙向的條件皆可的作法
如：『若A則B且若!A則!B，然後反向不一定有』

但這題既然是雙向，那何不用簡單的並查集呢？

//By momo
#include<cstdio>
#include<algorithm>
#define N 210
using namespace std;

int n, m, det[N], fa[N], ans[N];
void init(){ for(int i = 0; i < 2*n; i++) fa[i] = i; }
int find(int x){ return fa[x] = (fa[x]==x?x:find(fa[x])); }
void unio(int a, int b){ fa[find(a)] = find(b); }

int main(){
    
    scanf("%d%d", &n, &m);
    
    int flag = 0; init();
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c); a--, b--;
        if(c) unio(a, b),   unio(a+n, b+n);
        else  unio(a, b+n), unio(a+n, b);
        if(find(a) == find(a+n) || find(b) == find(b+n)) flag = 1;
    }
    if(flag) return puts("Impossible"), 0;
    
    for(int i = 0; i < n; i++){
        if(det[i] == 0){
            det[i] = 1;
            for(int j = 0; j < n; j++){
                if(find(i) == find(j)) det[i] = 1;
                if(find(i) == find(j+n)) det[i] = -1;
            }
        }
    }

    int cnt = 0;
    for(int i = 0; i < n; i++) if(det[i] == 1) ans[cnt++] = i+1;
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++) printf("%d%c", ans[i], i == cnt-1?'\n':' ');
}

Codeforces 228D Zigzag

用BIT來實作，接下來就是枚舉所有的可能

本以為有更好的解法，但是CF的主機快，不會TLE

而且官方解答也是如此

//By momo
#include<cstdio>
#include<algorithm>
#define N 100010
#define LL long long
using namespace std;

LL n, a[N];
struct BIT{

    LL dat[N];
    void ins(LL x, LL v, LL d){ while(x <= n){ dat[x] += v-d; x += x&-x; } }
    LL qry(LL x){ LL ret = 0; while(x > 0){ ret += dat[x]; x -= x&-x; } return ret; }

}bit[10][11];

int main(){
    
    scanf("%I64d", &n);
    for(LL x = 1; x <= n; x++){
        scanf("%I64d", &a[x]);
        for(LL i = 2; i <= 10; i += 2) bit[i/2+1][x%i].ins(x, a[x], 0);
    }
    
    LL m; scanf("%I64d", &m);
    while(m--){

        LL ty;
        scanf("%I64d", &ty);

        if(ty == 1){
            LL x, v;
            scanf("%I64d%I64d", &x, &v);
            for(LL i = 2; i <= 10; i += 2) bit[i/2+1][x%i].ins(x, v, a[x]);
            a[x] = v;
        }
        else{
            LL l, r, z;
            scanf("%I64d%I64d%I64d", &l, &r, &z);
            LL ans = 0, M = 2*(z-1);
            for(LL i = 1; i <= M; i++){
                LL v = (i == M? 2: ((i <= z)? i: 2 * z - i));
                ans += v * (bit[z][(i+l-1) % M].qry(r) - bit[z][(i+l-1) % M].qry(l-1));
            }
            printf("%I64d\n", ans);
        }

    }
}

Codeforces 226B Naughty Stone Piles

It is just like a tree.

    O

  O  O

OO OO

the answer is the sum of (value * depth)

So the bigger the value is the topper the depth is.

Like the problem: Fence Repair

//By momo
#include<cstdio>
#include<algorithm>
using namespace std;

char a[100][100], b[100][100];

int main(){
    
    int n, m, n2, m2;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%s", a[i]);
    scanf("%d%d", &n2, &m2);
    for(int i = 0; i < n2; i++) scanf("%s", b[i]);
    
    int bst = -1, bsx, bsy;
    for(int x = -50; x <= 50; x++){
        for(int y = -50; y <= 50; y++){
            int sum = 0;
            for(int i = 0; i < n && i+x < n2; i++){
                if(i+x < 0) continue;
                for(int j = 0; j < m && j+y < m2; j++){
                    if(j+y < 0) continue;
                    sum += (a[i][j]-'0') * (b[i+x][j+y]-'0');
                }
            }
            if(sum > bst){
                bst = sum;
                bsx = x;
                bsy = y;
            }
        }
    }
    printf("%d %d\n", bsx, bsy);

}

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.

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.