NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » lose 的個人資料 » 顯示文章
 主題

顯示文章

這裡允許您檢視這個會員的所有文章。請注意, 您只能看見您有權限閱讀的文章。

主題 - lose

頁: [1]
1
NPSC2019高中組決賽 / 轉發 FB 現場題解概要
« 於: 十二月 08, 2019, 07:00:08 pm »
原文網址: https://www.facebook.com/permalink.php?story_fbid=431563037518690&id=338441636830831

引用
NPSC題解
先講下,我是拉基我只有一題,寫這題解是聽裁判寫出來的,只是因為想找去年題解找不到覺得很不爽,才幫別人紀錄一下,拜託電神別嘴,等等邊聽邊更新。

pA 逆序輸出
題:給一正整數及24格儲存整數的格子,構造一指令印出從N ~ 0的數字,指令有將任意格複製到另一格,任一格 +1,輸出第x格,要求兩次輸出中不得超過15個指令。
使用log2(N)個格子,分別儲存lowbit為(1 << i)(i <= log2(N))的值,每次取小於且最接近需要的值的格子複製過來,在暴力加到需要的值,證明感覺很麻煩,不過應該可以感覺的到,每次操作都不會太多。

pB 忙碌的國度
題:一二維座標平面存在兩種點,一種代表公司並包含該公司下班時間,另一種代表餐廳並包含打烊時間及美味程度。問對於每一間公司,可以在下班後並在打烊前到達的餐廳的美味程度最大值為和?
formula : (Off work time + abs(x2 - x1) + abs(y2 - y1) <= Closure)
這題留言裡有超級電神的解釋,去膜拜吧。

pC 最小三倍完全數
題:求最小N倍完全數(N >= 1 && N <= 5)
這題我坐在那思考著自己跟垃圾有什麼差別時聽到了許多的解法,評審的解法也感覺很酷,但是,\爆搜!!/。

pD 回文樹
題:給一字串,將其排成字典序最小的回文字串。
引用評審的一句話:就排阿。

pE 密碼鎖
題:給N, K,及一N數字排列,問有幾種排列在移動K次後會剛好等於該排列。
首先應該很快的可以想到,不管排列長什麼樣子,結果都一樣,也就是答案只跟N, K有關,再來好像可以位元DP,這題我聽題解時在恍神,所以還要再推一下,之後更新。

pF 猜數字
題:互動題,給k個數字n,做最少次詢問得到每一個數字,每次詢問回傳是否大於詢問。
首先定義一函數F(N, K) 表示K個數字N大小區間的最佳詢問,就這樣去做分治。
這題其實我也沒有搞很懂為甚麼是那一坨東西,坐等電神解釋。
那一坨東西:F(N, K) = ( (N - 1) mod 2 * ceil( log2 ( (N - 1) / 2K + 1 ) ) ) + 1
我不會打很酷的數學符號QQ

pG 航線建設
題:給N, Q代表對於N個節點的圖有K次操作,每次操作可以加上一條邊或刪除一條邊,對於每次操作輸出當前MST的直徑,若不連通則輸出-1。
這題評審講了兩個解法,不過第一個解法我完全聽不懂,所以就講第二種。
記得沒錯的話就是很簡單的暴力,每次操作就用並查及維護及確認是否連通,做出最小生成樹,並找直徑。應該沒有這麼簡單拉,不過我有點忘了。

pH 鐵路維修問題
題 : 給N個節點及N - 1條邊,求任兩點間距離乘上路上最大邊權的和。

這題評審給了3個做法,第二個我不是很會用treap,第三個我直接問號
,所以就講第一個就好。

首先要先想辦法用O(n)的時間求出每一個點到任意點的邊數,方便後續查詢。可以先從任意點開始DFS,使用簡易dp求出對於每個節點的所有子節點到該節點的邊數和。接下來再做一次DFS,這時我們已經有了每個節點的下面的邊數和,所以就剩下上面的。而上面的我們可以再用祖先的狀態推過來,對於每個節點,他上面的邊數和會是祖先除了自己以外所有的邊數和加上祖先自己上面的邊數和,這樣就可以求出對於任意點的邊數和了。

再來整題就變簡單了。因為是乘上最大的邊,所以我們可以對於所有的邊,去算出以這條邊為最大的邊的答案。直接依照邊權去由小排到大,當增到第i個邊權時,代表目前圖中最大的邊權就會是i這條邊,所以就用目前的圖去算出答案,一直到把全部的邊都加進去。

最近粉專突然被一堆電神看到,有點緊張。感覺內容有超級多的錯誤,如果電神們看到有問題,請不要吝嗇直接辱罵並糾正我吧。

2
NPSC2018高中組決賽 / E. 背包問題
« 於: 十二月 08, 2019, 04:53:27 pm »
題目要求:可分割價值的物品,一旦要分割有額外的花費

參考概念:
轉換成數形幾何去思考,X 軸為重量,Y 軸為價值,我們會得到一個 X、Y 嚴格遞增的單調曲線。若我們從前 i 個物品的曲線推到前 i+1 個物品的曲線,可以知道是兩個曲線的最大值,而放入這第 i+1 個物品的曲線是前一個曲線配上 Minkowski Sum 的結果。只看這一個物品的曲線,也是一個單調遞增的曲線。

仔細推敲兩個合併的結果,可以發現不論怎麼取最大值、疊合曲線,每一個曲線上的線段都恰好對應到一個物品的分割或不分割。因此最佳解至多有一個物品被分割。那麼窮舉會分割的物品,時間複雜度落於 O(n^2 m)。

離上一次參與已離七年有餘,礙於沒地方測試,可能會 TLE 的代碼如下

代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;

struct Item {
int w, v, c;
bool operator<(const Item &o) const {
return w < o.w;
}
};

int main() {
int n;
int m;
Item items[2005];
while (scanf("%d %d", &n, &m) == 2) {
for (int i = 1; i <= n; i++)
assert(scanf("%d %d %d", &items[i].w, &items[i].v, &items[i].c) == 3);

double ans = 0;
static int dpBase[2005][10005] = {};
for (int j = 1; j <= n; j++) {
int w = items[j].w;
int v = items[j].v;
for (int k = 0; k <= m; k++) {
dpBase[j][k] = dpBase[j-1][k];
if (k >= w)
dpBase[j][k] = max(dpBase[j][k], dpBase[j-1][k-w] + v);
}
}
for (int i = 0; i <= m; i++)
ans = max(ans, (double) dpBase[n][i]);
for (int i = 1; i <= n; i++) {
if (items[i].v <= items[i].c)
continue;
static int dp[10005];
memcpy(dp, dpBase[i-1], sizeof(dp[0])*(m+1));
for (int j = i+1; j <= n; j++) {
int w = items[j].w;
int v = items[j].v;
for (int k = m; k >= w; k--)
dp[k] = max(dp[k], dp[k-w] + v);
int same = memcmp(dp, dpBase[j], sizeof(dp[0])*(m+1));
if (same == 0) {
memcpy(dp, dpBase[n], sizeof(dp[0])*(m+1));
break;
}
}

for (int j = 0; j <= m; j++) {
double val = dp[j];
if (m-j >= items[i].w) {
val += items[i].v;
} else {
double cwv = (double) (m-j) / items[i].w * items[i].v - items[i].c;
if (cwv > 0)
val += cwv;
}
ans = max(ans, val);
}
}
printf("%.20lf\n", ans);
}
return 0;
}

3
NPSC2012高中組決賽 / pA. 曉涵的紙牌遊戲
« 於: 四月 13, 2013, 03:47:55 pm »
題目簡述:
所有嚴格遞增的序列中(全生成為2^N種)有多少符合條件的序列。
這個條件是,不存在 "任何一條給定的序列" 為子字串。(sub string)

題目分析:
//窮舉應該是可以過的。
AC自動機 DP。
將遞增序列忽略,先當成任意字串由給定的字母集構成的。
將輸入的限制當作一個字串,將這些限制建成一棵 Trie,
並且建成 AC自動機,其中要標記字串的前綴是否存在某一個字串的結尾。

而最後由遞迴公式 dp[len][node]去更新dp[len+1][Next[node]]
釐清一點:Next[node] 可能需要走失敗指針。
len 是走的步數(又或者當作字串長度),node 是節點編號。
設定 dp[0][root] = 1,模擬 AC自動機匹配的方式進行,
為了要生成遞增序列,更新的時候試圖增加比當前結尾還大的字符,
但在 dp 表格中不想存放結尾字符,只有在 root 會發生問題,
其餘的節點都可以拿當前節點所代表的字符表示。

因此一開始增加所有字符插入 Trie 中,而這些字符不是限制。

代碼: [選擇]
#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct Node {
    Node *next[20], *fail, *prev;
    int eos;//prefix has a string end
    int dp[20];
    int ASCII;
    Node() {
        fail = NULL, prev = NULL;
        memset(next, 0, sizeof(next));
        memset(dp, 0, sizeof(dp));
        eos = 0;
        ASCII = 0;
    }
};
void insertTrie(const int str[], Node *root, int label) {
    static Node *p;
    static int i, idx, eos;
    p = root, eos = 0;
    for(i = 0; str[i] > 0; i++) {
        idx = str[i];
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
            p->next[idx]->prev = p;
            p->next[idx]->ASCII = idx;
        }
        eos |= p->eos;
        p = p->next[idx];
        p->eos |= eos;
    }
    p->eos |= label;
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 20; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
        delete nd;
    }
}
void buildACautomation(Node *root) {
    queue<Node*> Q;
    Node *nd, *p;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 20; i++) {
            if(nd->next[i] == NULL)
                continue;
            Q.push(nd->next[i]);
            p = nd->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                nd->next[i]->fail = root;
            else {
                nd->next[i]->fail = p->next[i];
                nd->next[i]->eos |= p->next[i]->eos;//special for dp
            }
        }
    }
}
void dp(Node *root, int len) {
    queue<Node*> Q;
    Node *nd, *p;
    root->dp[0] = 1;
    int k, i, j;
    int ans = 0, tot = 0;
    for(k = 0; k <= len; k++) {
        Q.push(root);
        ans = 0;
        while(!Q.empty()) {
            nd = Q.front(), Q.pop();
            for(i = nd->ASCII+1; i <= len; i++) {
                if(nd->next[i] != NULL) {
                    if(nd->next[i]->eos)
                        continue;//not safe
                    nd->next[i]->dp[k+1] = nd->next[i]->dp[k+1] + nd->dp[k];
                    Q.push(nd->next[i]);
                } else {
                    p = nd;
                    while(p != root && p->next[i] == NULL)
                        p = p->fail;
                    p = p->next[i];
                    if(p == NULL)
                        puts("NULL");
                    if(p->eos)
                        continue;//not safe
                    p->dp[k+1] += nd->dp[k];
                }
            }
            ans += nd->dp[k];
        }
        if(k >= 2)
            tot += ans;
    }
    if(tot == 0)
        puts("so sad");
    else
        printf("%d\n", tot);
}
int main() {
    int t, n, p;
    int x, A[20];
    int i, j, k;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &p);
        Node *root = new Node();
        for(i = 0; i < p; i++) {
            scanf("%d", &x);
            for(j = 0; j < x; j++)
                scanf("%d", &A[j]);
            A[x] = -1;
            insertTrie(A, root, 1);
        }
        for(i = 1; i <= n; i++) {
            A[0] = i;
            A[1] = -1;
            insertTrie(A, root, 0);
        }
        buildACautomation(root);
        dp(root, n);
        freeTrie(root);
    }
    return 0;
}

4
NPSC2012高中組決賽 / pD. 小可魚兒向上游
« 於: 四月 13, 2013, 08:27:54 am »
題目簡述:
轉化成一棵有根樹支持兩種操作
1. 將某節點當作新的一棵樹分裂出來
2. 查詢某節點所在的樹根
×一開始一定會給定以 0 為樹根的一棵樹。

題目分析:
先說,接下來描述的作法不是很好,也是又臭又長的。
先將一棵樹進行後序走訪,對於一個父節點 O,
後序結果:[[子樹 ... 子樹]O ...[子樹 ... 子樹]O]O
得到父節點的節點編號一定大於子樹的所有節點,同時要記錄每個父節點的控制子節點的區間。

根據後序走訪的結果,建立 ST 線段樹,對應的其父節點在後序走訪中的編號。
因此每個節點一開始都是 n,
然後在
操作 1 時,使用懶操作(標記),將區間 [l, r] 的每個元素與某個值k取 min。
區間[l, r]決定於父節點的控制區間,而 k 是後序走訪的編號。

操作 2 時,直接由 ST 線段樹得到其單一元素數值,記住,
在這裡得到的數值 val 指得是後序走訪編號,因此要得到樹根編號,必須打個映射。

這做法不是很好

AC(1.2s, 14.4MB) judge by this@ZeroJudge
代碼: [選擇]
#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
vector<int> g[100005];
int ST[530000], label[530000];
int RC[100005][2];
int postOrder[100005], visited[100005], pidx;
void build(int nd) {
    int i;
    RC[nd][0] = pidx;
    for(i = 0; i < g[nd].size(); i++)
        build(g[nd][i]);
    postOrder[pidx] = nd;
    visited[nd] = pidx;
    RC[nd][1] = pidx;
    pidx++;
}
void relax(int k, int l, int r) {
    if(label[k] < 0)    return;
    int m = (l+r)/2;
    ST[k] = min(ST[k], label[k]);
    if(l <= m) {
        if(label[k<<1] < 0)
            label[k<<1] = label[k];
        else
            label[k<<1] = min(label[k], label[k<<1]);
    }
    if(m+1 <= r) {
        if(label[k<<1|1] < 0)
            label[k<<1|1] = label[k];
        else
            label[k<<1|1] = min(label[k], label[k<<1|1]);
    }
    label[k] = -1;
}
int argv;
void modify(int k, int l, int r, int ql, int qr) {
    if(l > r)   return ;
    relax(k, l, r);
    if(ST[k] <= argv)
        return;
    if(l == ql && r == qr) {
        label[k] = argv;
        relax(k, l, r);
        return ;
    }
    int m = (l+r)/2;
    if(m >= qr)
        modify(k<<1, l, m, ql, qr);
    else if(m < ql)
        modify(k<<1|1, m+1, r, ql, qr);
    else {
        modify(k<<1, l, m, ql, m);
        modify(k<<1|1, m+1, r, m+1, qr);
    }
}
int query(int k, int l, int r, int qx) {
    relax(k, l, r);
    if(l == r && l == qx)
        return ST[k];
    int m = (l+r)/2;
    if(qx <= m)
        return query(k<<1, l, m, qx);
    else
        return query(k<<1|1, m+1, r, qx);
}
int main() {
    int T;
    int n, q;
    int i, j, x;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &q);
        for(i = 0; i <= n; i++)
            g[i].clear();
        for(i = 1; i < n; i++) {
            scanf("%d", &x);
            g[x].push_back(i);
        }
        pidx = 0;
        build(0);
        memset(ST, 63, sizeof(ST));
        memset(label, -1, sizeof(label));
        argv = visited[0];
        modify(1, 0, n-1, RC[0][0], RC[0][1]);
        int ans = 0;
        for(i = 1; i <= q; i++) {
            scanf("%d", &x);
            argv = query(1, 0, n-1, visited[x]);
            argv = postOrder[argv];
            ans ^= argv + i;
            //printf("%d %d [%d %d]\n", argv, visited[x], RC[x][0], RC[x][1]);
            argv = visited[x];
            modify(1, 0, n-1, RC[x][0], RC[x][1]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

5
NPSC2012高中組決賽 / pE. E. 胖胖天天天胖
« 於: 四月 12, 2013, 09:17:34 am »
题目简述:
在指定区间抓取总合不大于 S 的元素集合,而集合大小越大越好

题目分析:
对于区间[L,R]很明显地,从小排到大,依序挑入即可,照贪婪的思路。
但没办法对每个询问区间进行排序,因此使用归并树。
将合并排序的每个过程记录下来,然后二分边界数值。
小心,等价的边界数值要特别处理。
可能不是这个解法,速度稍慢了些。

AC(3.7s, 10.8MB) judge by this@ZeroJudge 
代碼: [選擇]
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
short ST[20][100010];
int AST[20][100010];
void build(int dep, int l, int r) {
    if(l < r) {
        int m = (l+r)/2, i;
        memcpy(ST[dep+1]+l, ST[dep]+l, (r-l+1)*2);
        build(dep+1, l, m);
        build(dep+1, m+1, r);
        int idx1 = l, idx2 = m+1, top = l, tmp = 0;
        while(idx1 <= m && idx2 <= r) {
            if(ST[dep+1][idx1] < ST[dep+1][idx2])
                ST[dep][top] = ST[dep+1][idx1++];
            else
                ST[dep][top] = ST[dep+1][idx2++];
            tmp += ST[dep][top];
            AST[dep][top++] = tmp;
        }
        while(idx1 <= m) {
            ST[dep][top] = ST[dep+1][idx1++];
            tmp += ST[dep][top];
            AST[dep][top++] = tmp;
        }
        while(idx2 <= r) {
            ST[dep][top] = ST[dep+1][idx2++];
            tmp += ST[dep][top];
            AST[dep][top++] = tmp;
        }
    }
    if(l == r)
        AST[dep][l] = ST[dep][l];
}
int L, R, S;
int key, Count, cost, same;
void query(int dep, int l, int r, int ql, int qr) {
    if(cost > S)   return ;
    if(l == ql && r == qr) {
        int ff = upper_bound(ST[dep]+l, ST[dep]+r+1, key)-(ST[dep]+l);
        int gg = lower_bound(ST[dep]+l, ST[dep]+r+1, key)-(ST[dep]+l);
        same += ff-gg;
        if(gg) {
            Count += gg;
            cost += AST[dep][gg+l-1];
        }
        return;
    }
    int m = (l+r)/2;
    if(m >= qr)
        query(dep+1, l, m, ql, qr);
    else if(m < ql)
        query(dep+1, m+1, r, ql, qr);
    else {
        query(dep+1, l, m, ql, m);
        query(dep+1, m+1, r, m+1, qr);
    }
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int t;
    int n, q, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &q);
        for(i = 1; i <= n; i++) {
            //scanf("%d", &ST[0][i]);
            ReadInt(&j);
            ST[0][i] = j;
        }
        build(0, 1, n);
        int ans = 0;
        ST[0][0] = 0;
        for(i = 1; i <= q; i++) {
            //scanf("%d %d %d", &L, &R, &S);
            ReadInt(&L);
            ReadInt(&R);
            ReadInt(&S);
            int l = 0, r = n, m;
            int x = 0;
            while(l <= r) {
                m = (l+r)/2;
                key = ST[0][m], Count = 0, cost = 0, same = 0;
                query(0, 1, n, L, R);
                if(cost <= S) {
                    l = m+1;
                    if(key)
                        Count += min((S-cost)/key, same);
                    if(Count > x)   x = Count;
                } else
                    r = m-1;
            }
            ans ^= x+i;
        }
        printf("%d\n", ans);
    }
    return 0;
}

6
NPSC2009高中組初賽 / 2009 NPSC 高中組初賽 F. 漆海報
« 於: 十二月 23, 2009, 10:04:28 pm »
作法 : 將資料離散化
     如果直接開2^16*2^16 的陣列  會暴掉
  此時  將出現過的X軸  Y軸記錄下來
  紀錄每段長之後  做邊長的壓縮  並將長度存在陣列中
  之後再跑計算面積的時候  再將長度拿出來做相乘
詳細做法  : http://www.matrix67.com/blog/archives/108
代碼: [選擇]
#include<stdlib.h>
#include<stdio.h>
#define U 32769
main()
{
  int N,Tt;
  int x[501][2],y[501][2];
  scanf("%d",&Tt);
  while(Tt--)
      {
         scanf("%d",&N);
         int AX[70000]={0},AY[70000]={0},T[502][502]={0};
         int a,b,c,t;
         for(a=0;a<N;a++)
           {
            scanf("%d %d %d %d",&x[a][0],&y[a][0],&x[a][1],&y[a][1]);
             AX[x[a][0]+U]=1,AX[x[a][1]+U]=1;
             AY[y[a][0]+U]=1,AY[y[a][1]+U]=1;
           }
         int DisX[501],DisY[501],topx=0,topy=0,LASTx=0,LASTy=0;
         for(a=0;a<=70000;a++)
           {
              if(AX[a]==1)
                 {
                     AX[a]=++topx;
                     DisX[topx]=-(LASTx-a);
                     LASTx=a;
                 }
              if(AY[a]==1)
                 {
                     AY[a]=++topy;
                     DisY[topy]=-(LASTy-a);
                     LASTy=a;
                 }
           }
         for(a=0;a<N;a++)
            {
               if(x[a][0]>x[a][1])
                 {t=x[a][0],x[a][0]=x[a][1],x[a][1]=t;}
               if(y[a][0]>y[a][1])
                 {t=y[a][0],y[a][0]=y[a][1],y[a][1]=t;}
               for(b=AX[x[a][0]+U]+1;b<=AX[x[a][1]+U];b++)
                  for(c=AY[y[a][0]+U]+1;c<=AY[y[a][1]+U];c++)
                      T[b][c]=1;
            }
         long long int ANS=0;
         for(a=0;a<=topx;a++)
              for(b=0;b<=topy;b++)
                if(T[a][b]==1)
                     ANS+=(DisX[a]*DisY[b]);
           printf("%lld\n",ANS);
      }
  return 0;
}

7
NPSC2006國中組初賽 / [C]2006 NPSC F. 費波那星
« 於: 十一月 29, 2009, 11:22:28 am »
費波那契數列  若A[a]==1 && A[a+1]==1  => A[a+2]++
              若A[a]==2  => 拆成 A[a+1] 跟 A[a-2]  在這裡會遇到問題  a-2必須 >=0
              若A[a]==3  => 拆成 A[a+2] 跟 A[a-1]
一直反覆的拆解  直到不能拆為止  就是答案
代碼: [選擇]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
main()
{
 char x[1001],y[1001];
 while(scanf("%s",x)==1)
   {
    if(x[0]==48&&strlen(x)==1) break;
    scanf("%s",y);
    int n=strlen(x),m=strlen(y),max=0,flag=0;
    int ans[1005]={0},a,b,c;
    for(a=0;a<n;a++)
     ans[a]=ans[a]+x[a]-48;
    for(a=0;a<m;a++)
     ans[a]=ans[a]+y[a]-48;
    for(a=0;a<=1004;a++)
     {
      if(ans[a]==1&&ans[a+1]==1)
       {
        ans[a]--;
        ans[a+1]--;
        ans[a+2]=ans[a+2]+1;
        flag=1;
       }
      if(ans[a]==2&&a>=2)
       {
        ans[a+1]=ans[a+1]+1;
        ans[a-2]=ans[a-2]+1;
        ans[a]=0;
        flag=1;
       }
      if(ans[a]==2&&a==0)
       {
        ans[a+1]=ans[a+1]+1;
        flag=1;
        ans[a]=0;
       }
      if(ans[a]==2&&a==1)
       {
        ans[a+1]=ans[a+1]+1;
        ans[a-1]=ans[a-1]+1;
        ans[a]=0;
        flag=1;
       }
      if(ans[a]==3)
       {
        ans[a+2]=ans[a+2]+1;
        ans[a-1]=ans[a-1]+1;
        ans[a]=0;
        flag=1;
       }
      if(ans[a]==1&&ans[a-1]==1)
       {
        ans[a]--;
        ans[a-1]--;
        ans[a+1]=ans[a+1]+1;
        flag=1;
       }
       if(flag==1&&a==1004) {a=-1;flag=0;}
     }
    for(a=1003;a>=0;a--)
     if(ans[a]!=0) {max=a+1;break;}
    for(a=0;a<max;a++)
     printf("%d",ans[a]);
    printf("\n"); 
   }
 return 0;
}


8
綜合討論區 / 不用內建作連接圖的方法
« 於: 十一月 29, 2009, 10:34:33 am »
在下分享一個無聊的東西  看看就好
通常在寫圖的時候
常常會卡在如何記如連接的部份     雖然說內建很好用
但是不會用內建的話  通常卻是用開一個陣列 char map[][];  去標記1
當作有連接 不過這樣的話  假使不是好的一張圖  所連接的邊  就會很少
就必須找到一個好的紀錄方法  來減少在做處理時候的次數  
如果不用內建的話
作法 I  :
    大開char map[N+1][N+1]; 去紀錄
    這樣的話  可能會有很多空的部份
    EX.
代碼: [選擇]
   while(scanf(“%d %d”,&N,&M)==2)
      {
        char map[100][100];//初使設定為0
         for(a=0;a<M;a++)
             scanf(“%d %d”,&x,&y),map[x][y]=1;
      }
作法 II :
    大開int map[N+1][K+1];
    N是點的編號最大號碼 K是一個點所能連接的最大節點個數
    當然這樣做的話,
    就必須再多一個陣列 int pt[N+1];去紀錄該點所連 接的節點個數
    EX.
代碼: [選擇]
     while(scanf(“%d %d”,&N,&M)==2)
      {
        int map[100][50],pt[100];//初使設定為0
         for(a=0;a<M;a++)
             scanf(“%d %d”,&x,&y),map[x][pt[x]++]=y;
      }
作法 III:
    當然大開 int map[N+1][K+1];
    還是有可能會得到一個RE,畢竟沒分配的那麼均勻
    所以假使他的邊最多有M個的話
    要記錄x->y的話
    則開 int xy[M][2]; //[][0]存放x [][1]存放y
    若會重複使用的話  最好將xy[][]對x做排序(y移動)
    如同上面的一樣  必須紀錄該點所連接的個數  所以必須開
    int pt[N+1];去紀錄該點所連接的節點個數  
    但是存的部份  依舊不是很容易找到  所以要開一個陣列 int sp[N+1];
    去紀錄x點在int xy[][] 的 最小索引值
    之後若要找x所連接的部份的話  則直接從
    
代碼: [選擇]
xy[sp[x]][1]->xy[sp[x]+pt[x]][1] 這些就都是x所連接的點了
代碼: [選擇]
#include<stdlib.h>
#include<stdio.h>
#define MAX 1000000001
int min(int x,int y)
{
     if(x>=y) return y;
     else return x;
}
int ptime[10002]={0},SP[10002]={0};
int data[1000000][3];
int MergeSort(int,int);
int Merge(int,int,int);
main()
{
  int N,M;
  while(scanf("%d %d",&M,&N)==2) //編號1~M個節點 有N個編
     {
        int a,b,c,d,x,y;
        for(a=0;a<N;a++)
           {
             scanf("%d %d %d",&x,&y,&d); //X->Y 權值 d
             data[a][0]=x,data[a][1]=y,data[a][2]=d;
             ptime[x]++; //紀錄點的個數
           }
        MergeSort(0,N-1);  //對X做排序
        for(a=1;a<=M;a++)    SP[a]=MAX; //先將索引值設定MAX
        for(a=0;a<N;a++)   //找出最小的索引值
            SP[data[a][0]]=min(a,SP[data[a][0]]);
        for(a=1;a<=M;a++)
          {
           printf("%d \n",a);
           for(b=SP[a],c=0;c<ptime[a];b++,c++)
             printf("    ->%d %d\n",data[b][1],data[b][2]);
          }
        for(a=1;a<=M;a++)// 用完記得歸0
           ptime[a]=0;
     }
   return 0;
}
int MergeSort(int l,int h)
{
   if(l<h)
      {
         int m=(l+h)/2;
         MergeSort(l,m);
         MergeSort(m+1,h);
         Merge(l,m,h);
      }
}
int x[100001][3];
int Merge(int l,int m,int h)
{
   int in1=l,in2=m+1,out=l;
   int top=0,a,b;
   while(in1<=m&&in2<=h)
      if(data[in1][0]>data[in2][0])
           x[top][2]=data[in2][2],x[top][1]=data[in2][1],x[top++][0]=data[in2++][0];
      else
           x[top][2]=data[in1][2],x[top][1]=data[in1][1],x[top++][0]=data[in1++][0];
   while(in1<=m)
       x[top][2]=data[in1][2],x[top][1]=data[in1][1],x[top++][0]=data[in1++][0];
   while(in2<=h)
       x[top][2]=data[in2][2],x[top][1]=data[in2][1],x[top++][0]=data[in2++][0];
   for(a=l,b=0;a<=h;a++,b++)
      data[a][0]=x[b][0],data[a][1]=x[b][1],data[a][2]=x[b][2];
}
做排序的部份  由於連接圖可能有很多重複的點  
對於快排可能比較不利  經過測試  合併排序會比較好
因為C語言沒有內建的  (貌似
而且不會用指標去做連接  所以才出此下策…

9
NPSC2006國中組初賽 / [C]2006 NPSC D. 水之都
« 於: 十一月 29, 2009, 09:41:05 am »
作法 : SPFA
算法大致流程是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。直到队列为空时算法结束。


代碼: [選擇]
#include<stdio.h>
#include<stdlib.h>
#define MAX 1000000000
int map[1001][300][2]={0};
int N,M,S,E;
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())    
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
int min(int x,int y)  
{  
     if(x>=y) return y;  
     else return x;  
}
int max(int x,int y)  
{  
     if(x>=y) return x;  
     else return y;  
}
short Queue[5000000],maptop[1001]={0};
int SPFA(int S,int N,int E)      
{      
   int Dis[1001]={0},a,b,c,used[1001]={0};      
   int top=-1;      
   Dis[S]=MAX;
   for(a=0;a<maptop[S];a++)      
     {      
      Dis[map[S][a][0]]=max(Dis[map[S][a][0]],map[S][a][1]);      
      if(used[map[S][a][0]]==0)
            Queue[++top]=map[S][a][0],used[map[S][a][0]]=1;      
     }      
   for(a=0;a<=top;a++)      
      {      
         int Qp=Queue[a];      
         used[Qp]=0;          
         for(b=0;b<maptop[Qp];b++)      
            {
              int R=min(Dis[Qp],map[Qp][b][1]);
              if(Dis[map[Qp][b][0]]<R)
                {      
                   Dis[map[Qp][b][0]]=R;      
                   if(used[map[Qp][b][0]]==0)      
                     Queue[++top]=map[Qp][b][0],used[map[Qp][b][0]]=1;      
               }      
            }
      }      
   printf("%d\n",Dis[E]);
}    
main()
{
 while(scanf("%d %d",&N,&M)==2&&N)
    {
       int a,b,c,x,y,data;
       for(a=0;a<M;a++)
         {
           x=input(),y=input(),data=input();
           map[x][maptop[x]][0]=y;
           map[x][maptop[x]++][1]=data;
           map[y][maptop[y]][0]=x;
           map[y][maptop[y]++][1]=data;
         }
        scanf("%d %d",&S,&E);
        SPFA(S,N,E);
        for(a=1;a<=N;a++)   maptop[a]=0;  
  }
 return 0;
}


頁: [1]