SGU 183 Painting the balls

對於一個題目，可以寫出來的DP形式非常多種

最重要的是要找到一個可以使時間複雜度最低的方法

像是這題 Painting the balls

可以想成dp[i][j] 是 考慮到 i , 且放的位置為 i 和 i-j 時，最小的cost

這時就可以構造出一個O(m)的轉移過程

總time complexity為O(n^2*m)

在分析轉移過程的時候，可能會看到一些奇妙的東西

這時如果把dp[i][j] 變成 考慮到 i , 且放的位置為 i 和 i-1~ i-j 當中最小cost 

轉移式就可以變成：

dp[ i ][1] = dp[i-1][m-1] + cost[ i ]

dp[ i ][ j ] = min(dp[ i ][j-1], dp[i-j][m-j] + cost[ i ])

這樣總time complexity就壓成O(nm) 了

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

int n, m, ans = INF, c[10010];
class mod_array{
    public:
    int dat[128][128];
    int* operator[](int x){ return dat[x & 127]; }
}opt;

int main(){
    fill((int*)opt.dat, (int*)opt.dat+127*127, INF);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &c[i]);
    for(int i = 0; i < n; i++){
        for(int j = 1; j < m && j <= i; j++){
            if(i < m) opt[i][j] = min(opt[i][j-1], c[i-j]+c[i]);
            else if(j == 1) opt[i][j] = opt[i-1][m-1] + c[i];
            else opt[i][j] = min(opt[i][j-1], opt[i-j][m-j] + c[i]);
        }
    }
    for(int i = n-m+1; i < n; i++)
        ans = min(ans, opt[i][i-n+m]);
    printf("%d\n", ans);
}

可以注意的地方是我的opt寫法，那是來自網路上某中國強者的寫法
http://hi.baidu.com/yccbolg/item/06e9351a84445cf487ad4ec9

寫成這樣之後就不用像以前在下面寫一大堆的模運算了，代碼漂亮很多

SGU 128 Snakes

對於每一個節點，都要連出兩條線

一條沿X軸，一條沿Y軸

所以可以知道一定是如下圖







對於X軸及Y軸方向，皆是如此

連完之後，要判斷是否全部都在同一集合中（並查集）

然後要判斷會不會發生相交的情況（BIT）

//By momo
#include<cstdio>
#include<algorithm>
#define N 10010
#define M 11000
using namespace std;

int n, pos[N], up[N], in[N];

int fa[N];
void init(){ for(int i = 0; i < 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); }

struct coord{ int x, y; }co[N], que[N];
bool comx(int a, int b){
    return co[a].x < co[b].x || co[a].x == co[b].x && co[a].y < co[b].y;
}
bool comy(int a, int b){
    return co[a].y < co[b].y || co[a].y == co[b].y && co[a].x < co[b].x;
}

struct BIT{
    int dat[3*M];
    void insert(int x, int v){
        while(x < 3*M){
            dat[x] += v;
            x += x&-x;
        }
    }
    int query(int x){
        int ret = 0;
        while(x > 0){
            ret += dat[x];
            x -= x&-x;
        } return ret;
    }
}bit;

void input(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d%d", &co[i].x, &co[i].y);
        pos[i] = i;
    }
}

int solve(){
    int ret = 0;
    init();
    sort(pos, pos+n, comx);
    for(int x = 0; x < n; x += 2){
        int i = pos[x], j = pos[x+1];
        if(co[i].x != co[j].x) return 0;
        up[i] = j;
        ret += co[j].y - co[i].y;
        unio(i, j);
    }
    sort(pos, pos+n, comy);
    for(int x = 0; x < n; x += 2){
        int i = pos[x], j = pos[x+1];
        if(co[i].y != co[j].y) return 0;
        in[i] = 1;
        in[j] = 0;
        ret += co[j].x - co[i].x;
        unio(i, j);
    }
    int st = find(0);
    for(int i = 1; i < n; i++) if(find(i) != st) return 0;
    sort(pos, pos+n, comx);
    for(int i = 0; i < n; i++){
        int p = pos[i];
        if(up[p]){
            int v = bit.query(co[up[p]].y+M)-bit.query(co[p].y+1+M);
            if(v) return 0;
        }
        if(in[p]) bit.insert(co[p].y+1+M, 1);
        else bit.insert(co[p].y+1+M, -1);
    }
    return ret;
}

int main(){
    input();
    printf("%d\n", solve());
}

SGU 122 The book

論文出處：
http://www.sciencedirect.com/science/article/pii/S0898122197002253

哈密頓迴路本是NP問題，但題目有加條件

條件：deg(u) + deg(v) >= |V|

先亂連一個圈，沒有相鄰也沒關係

對於一個在圈上相鄰卻在圖上沒有相鄰的點對

一定可以找到兩個在圈上相鄰的點對，且...就如圖所示：

至於原因的話，其實就是因為那個限制，可以自己證證看，蠻好玩的，概念跟n+1隻鴿子放入n個籠子中，至少有一個籠子會有兩隻鳥，是一樣的道理。

所以像前面這樣不斷的連連連，最多連n次，每次尋找的時間複雜度O(n)，所以整體的複雜度便是O(n^2)

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

char che;
bool tbl[N][N];
int L[N], R[N];

int main(){
    int n; scanf("%d", &n);

    for(int i = 0, to; i < n; i++){
        while(1){
            scanf("%d", &to); tbl[i][to-1] = 1;
            char j = getchar();
            if(j == '\n' || j == '\r' || j == EOF) break;
        }
    }

    for(int i = 0; i < n; i++) R[i] = (i+1)%n;
    for(int i = 0; i < n; i++) L[i] = (i-1+n)%n;

    bool upd = 1;
    while(upd){
        upd = 0;
        int x = 0;
        while(1){
            if(tbl[x][R[x]] == 0){
                upd = 1;
                int y = 0;
                while(1){

                    int u = x, v = R[x];
                    int p = y, q = R[y];
                   
                    if(v != p && u != p && u != q){

                        if(tbl[u][p] && tbl[v][q]){
                            R[u] = L[u]; L[u] = p;
                            R[v] = R[v]; L[v] = q;
                            L[p] = L[p]; R[p] = u;
                            L[q] = R[q]; R[q] = v;
                            for(int z = R[u]; z != q; z = R[z])
                                swap(R[z], L[z]);
                            break;
                        }
                    }

                    y = R[y];
                    if(y == 0) break;
                }
                break;
            }
            x = R[x];
            if(x == 0) break;
        }
    }

    int x = 0;
    while(1){
        printf("%d ", x+1), x = R[x];
        if(x == 0) break;
    }
    puts("1");
}

SGU 121 Bridges painting

想到一個解法，傳上去也AC了

想一想發現居然有錯OAO

網路上也有一堆人都是錯的

決定改成用周源的作法重寫一遍～

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

做一個DFS樹：

選第一個節點連黑，其餘皆連紅，分層塗色

若有回溯邊，就連他沒有連過的顏色。

如果根節點只有一個子節點：

選一個連到根的回溯邊，將他變成紅色

若其為葉子，往上不斷的換顏色，直到該點有連出不只兩條邊

若找不到，puts("No solution")

//By momo
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 110
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;

vector<int> G[N];
int n, vs[N], clr[N][N], fa[N], lf[N];

void CC(int a, int b, int c){ clr[a][b] = clr[b][a] = c+1; }

void dfs(int p, int f, int c){
    fa[p] = f;
    vs[p] = 1;
    CC(f, p, c);
    FOR(it, G[p]){
        if(vs[*it]){
            if(clr[p][*it] == 0) CC(p, *it, c^1);
            continue;
        }
        dfs(*it, p, c^1);
        lf[p] = 0;
    }
}

bool solve(){
    for(int i = 0; i < n; i++){
        if(vs[i]) continue;
        int cnt = 0;
        vs[i] = 1;
        FOR(it, G[i]){
            if(vs[*it]) continue;
            dfs(*it, i, (cnt&&1)); cnt++;
        }
        if(cnt != 1 || G[i].size() == 1) continue;
        int nx = G[i][1];
        if(lf[nx]){
            int x = nx, c;
            CC(i, x, c = 1);
            for(; x != i && G[x].size() == 2; x = fa[x])
                CC(x, fa[x], c ^= 1);
            if(x == i) return 0;
        }
        else CC(i, nx, 1);
    }
    return 1;
}

void input(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        int x; lf[i] = 1;
        while(scanf("%d", &x), x != 0) G[i].push_back(x-1);
    }
}

void output(){
    for(int i = 0; i < n; i++){
        FOR(it, G[i]) printf("%d ", clr[i][*it]);
        puts("0");
    }
}

int main(){
    input();
    if(solve()) output();
    else puts("No solution");
}

SGU 114 Telecasting station

The answer must be on one of the cites.

pf:

There's only n city, numerate all

SGU 120 Arhipelago

題目實質：

要你先求出此正多邊形的中心，再不斷的瞬時針旋轉求答案。

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

當你逆時針旋轉角，則向量(x, y)會變成下圖：



透過上式，可以解二元一次方程式求出中心

再來因為他是要瞬時針旋轉，記得要改成負的

然後Pi值要精準，因為 x, y 都很大（Pi = 3.1415926535897932384626）

//By momo
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 200
#define EPS 1e-9
#define Pi (3.1415926535897932384626)
using namespace std;

int n, a, b;
double ansx[N], ansy[N];
void find(double a1, double b1, double c1, double a2, double b2, double c2, double& x, double& y){
    x = (b2*c1-b1*c2) / (a1*b2-a2*b1);
    y = (a2*c1-a1*c2) / (a2*b1-a1*b2);
}

int main(){
   
    double x, y, x1, y1, x2, y2;
    scanf("%d%d%d", &n, &a, &b);
    scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
    if(a > b) b += n;
   
    double theta = 2.0 * Pi * (b-a) / n;
    double phi   = 2.0 * Pi *  (-1) / n;
    double sn  = sin(theta), cs  = cos(theta);
    double snp = sin(  phi), csp = cos(  phi);
    find(cs-1, sn, x1*cs+y1*sn-x2, -sn, cs-1, y1*cs-x1*sn-y2, x, y);
   
    double xi = x1-x, yi = y1-y;
    for(int i = 0; i < n; i++){
        int pos = (a+i-1) % n;
        ansx[pos] = xi+x; ansy[pos] = yi+y;
        double nx = xi * csp - yi * snp;
        double ny = yi * csp + xi * snp;
        xi = nx, yi = ny;
    }
    for(int i = 0; i < n; i++) printf("%.6lf %.6lf\n", ansx[i]+EPS, ansy[i]+EPS);

}

SGU 119 Magic Pairs

前提：gcd(N, a0, b0) = 1

• 若 gcd(N, a0) = 1 或 gcd(N, b0) = 1

          若有一個答案(a, b) 不是 (ia0, ib0)，可以找到一個 ia0，使a = ia0

        接著，可以找到一個答案(X, 1)，符合ia0X+ib0 = 1 (mod N)  

        因為b != ib0，那b = kN+b0 (k != 0)，但在mod N的同餘係中，他們是相等的

        故 (ia0, jb0) != (ka0, kb0)(0<= k <= N-1) 是不存在的。

• 若gcd(N, a0) != 1 and gcd(N, b0) != 1

        設 N = a0 * b0 * k ，

        可以找到 (N/a0, 0) 跟 (0, N/b0) 的解，代入後可以發現，(a, b) = (ia0, jb0)

        而又可以發現說，(a, b) = (ia0, ib0) (0 <= i <= N-1)包含了所有的(ia0, ib0+jkb0)

        有必定有一個(x, y)解 = ((k-1)a0, b0)，代入ia0x+(ib0+jkb0)y = 0(mod N)，如果
        有別的(a, b)解，必定要加上kb0，那還是位於(ia0, ib0+jkb0)之中，跳不出來，
        故 (ia0, jb0) != (ka0, kb0)(0<= k <= N-1) 是不存在的。

//By momo
#include<cstdio>
#include<set>
#include<algorithm>
#define MP make_pair
using namespace std;

typedef pair<int, int> PII;
set<PII> che;

int main(){
    int n, x, y;
    scanf("%d%d%d", &n, &x, &y);
    for(int i = 0; i < n; i++){
        int a = (x*i) % n;
        int b = (y*i) % n;
        che.insert(MP(a, b));
    }
    printf("%d\n", (int)che.size());
    for(set<PII>::iterator it = che.begin(); it != che.end(); it++)
        printf("%d %d\n", it->first, it->second);
}

Syntax Highlight

之前的tohtml要花錢才能使用了

只好換一個地方～

http://quickhighlighter.com/index.php?lng=php

SGU 110 Dungeon

//By momo
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100
#define INF 999999999
#define EPS 1e-7
using namespace std;

int n, prv = -1;
double x[N], y[N], z[N], r[N];
double sx, sy, sz, vx, vy, vz;

double sq(double a){ return a*a; }
double findx2(double a, double b, double c){
    if(sq(b) - 4*a*c + EPS >= 0){
        double x1 = ( sqrt(sq(b) - 4*a*c) - b) / (2*a);
        double x2 = (-sqrt(sq(b) - 4*a*c) - b) / (2*a);
        if(x2 >= 0) return x2;
        return x1;
    }
    return -1;
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%lf%lf%lf%lf", &x[i], &y[i], &z[i], &r[i]);
    scanf("%lf%lf%lf%lf%lf%lf", &sx, &sy, &sz, &vx, &vy, &vz); vx -= sx, vy -= sy, vz -= sz;
    for(int t = 0; t < 11; t++){
        double P = INF;
        int idx = 0;
        for(int i = 0; i < n; i++){
            if(i == prv) continue;
            double a = vx*vx + vy*vy + vz*vz;
            double b = 2*(vx*(sx-x[i]) + vy*(sy-y[i]) + vz*(sz-z[i]));
            double c = sq(sx-x[i]) + sq(sy-y[i]) + sq(sz-z[i]) - sq(r[i]);
            double ans = findx2(a, b, c);
            if(ans+EPS >= 0 && P+EPS > ans) P = ans, idx = i;
        }
        if(P+EPS > INF && P < INF+EPS) break;
        if(t == 10) printf("etc.");
        else printf("%d ", idx+1);
        prv = idx;
        double nx = x[idx] - (sx + P*vx);
        double ny = y[idx] - (sy + P*vy);
        double nz = z[idx] - (sz + P*vz);
        double ln = sqrt(sq(nx) + sq(ny) + sq(nz));
        nx /= ln, ny /= ln, nz /= ln;
        double dt = vx*nx + vy*ny + vz*nz;
        sx += P*vx, sy += P*vy, sz += P*vz;
        vx -= 2*dt*nx, vy -= 2*dt*ny, vz -= 2*dt*nz;
    }
    puts("");
}