NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

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

顯示文章

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

主題 - sagit

頁: [1] 2 3 ... 6
1
NPSC2017高中組初賽 / G.A|B Problem
« 於: 十月 17, 2018, 02:39:55 pm »
這題要以二進位來思考,
假設 A=100100010,
則滿足 A+B=A|B 條件的 B,
在 A 中為 1 的位元必定為 0,
也就是 B=0xx0xxx0x,
其中的 x 可為 0 或 1,
因此只要數一下 A 裡面有幾個位元是 0,
算出 2 的次方就可以得到答案。

但是題目又規定 B <=X ,
所以我們要將 X 分段處理,
假設 X=1001000100,
先找出最左邊第一個出現的 1 為 1000000000,
分出第一段數字 xxxxxxxxx,(不含上面的數)
也就是 0 ~ 111111111 (1000000000-1),
再用這一段去找有幾個位元在 A 中是 0。
接下來再找出第二個出現的 1 為 1000000,
而第二段數字為 1000xxxxxx,
也就是 1000000000 ~ 1000111111 (1001000000-1),
數字的最前面固定是 1000,
一樣找出後面的位元有幾個在 A 中是 0。
要注意的是,如果這個位元在 X 和在 A 中同時為 1,
則後面就不會再有答案,必須中斷。

再來,因為這個做法只能處理到 X-1,
所以 X 要另外處理。
最後,因為題目要求要正整數,
但這個做法會包含 0,
所以答案要再減一。

核心程式碼:
代碼: [選擇]
for (bit=(1<<30), ans=0; bit; bit>>=1)
{
    if ((bit&x)==0) continue;
    for (bit2=(bit>>1), c=0; bit2; bit2>>=1)
        if ((bit2&a)==0) c++;
    ans+=A[c];
    if (bit&a) break;
}
if ((a|x)==(a+x)) ans++;
printf("%d\n", ans-1);
PS. A[ i ] 為 2i, 可在程式一開始先算出它們的值。

2
NPSC2014高中組初賽 / G.華麗內餡格狀超好吃巧克力
« 於: 十月 15, 2018, 02:56:08 pm »
這題答案的長方形,如果不是 1x2,就一定是 1x3 的大小,
以這個方式每個都找一找就可以找到答案。

3
NPSC2017高中組初賽 / D.魔法施放距離
« 於: 十月 15, 2018, 02:49:58 pm »
將下限L設為 1,上限U設為 4e18 (即 4*1018),
< 和 <= 時修正U (k比U小的時候才修正),
而 > 和 >= 時修正L (k比L大的時候才修正),
U-L+1即是答案,
要注意如果答案是負的則輸出0,
而答案大於 1e18 則是 INF。

4
NPSC2017高中組初賽 / A.A+B Problem
« 於: 十月 15, 2018, 02:43:36 pm »
假設字串長度為L,
以兩層的for迴圈,
第一層 i=1~L/2,第二層 j=i+1~L*2/3,
則可以分解成三個子字串:0~i-1、i~j-1、j~L-1,
任一子字串的長度為2以上,且第一個字元為0時不合法,
接下來再將三個子字串各自轉成long long int,
再判斷a+b==c是否成立即可。

5
NPSC2016高中組初賽 / NPSC 2016 高中組初賽 B.騎士出任務
« 於: 十一月 09, 2017, 01:41:55 pm »
對於一個N>=3且M>=3的棋盤,
只要依序3、6、1即可往右移一格,
依序4、1、6即可往下移一格,
所以任一棋盤只要符合N>=3且M>=3則一定有解,
N>M>>>3的情況就走3,反之則走4,
若其中一個為3,另一個很大,
則走3、6可以往下兩格,走4、1可以往右兩格,
走到最後,一定可以變長一個為3,另一個為2或3,
就可以解出來。

至於N=1或M=1則是無解,
而N=2或M=2的情況下,
另一個如果是3、7、11等4K-1的數則是有解,
其他情況則無解。

6
NPSC2016高中組初賽 / NPSC 2016 高中組初賽 D.水晶球傳送問題
« 於: 十一月 08, 2017, 03:50:57 pm »
先找出所有祭壇裡面法力門檻最低的是 K,
再來一一找出哪些水晶球可以形成一個循環,
每組循環可以以該循環中法力門檻最低(假設為 L)的那個祭壇做交換,
假設這個循環有 N 個水晶球,
則只要交換 N-1 次就可以讓這 N 個水晶球回到自己的位置,
總花費是 (N-1)*L,但這不一定是最佳解,
另一種做法則是先把其中一個跟全體法力門檻最低的那個交換,
全部交換完一圈則是有 N+1 次的交換,
總花費則是 (N+1)*K,
我們取比較小的那個。

例如官方第57組測資:
9
5 6 9 13 100 200 15 7 20
2 3 1 5 6 4 8 9 7
可以分成123、456、789這三組循環,
123這組剛好有全體法力門檻最低的祭壇,
所以花費是 (3-1)*5=10,
456這組法力門檻最低的祭壇是13,
所以兩種花費分別是 (3-1)*13=26、(3+1)*5=20,取20這一個,
最後789這組法力門檻最低的祭壇是7,
所以兩種花費分別是 (3-1)*7=14、(3+1)*5=20,取14這一個,
整體最小花費就是10+20+14=44。

7
NPSC2016高中組初賽 / NPSC 2016 高中組初賽 G.普遜與食安問題
« 於: 十一月 07, 2017, 01:58:47 pm »
因為最多只有15個點,所以可以用回溯法來寫,
每個點都只有取與不取兩種情況,
所以題目最多就是 215 種組合,
每個組合再以 M 次的迴圈檢查每條邊的兩個點是否至少有一個點有被選取,
如果符合,則是一組答案。

因為答案是依字母順序,在寫回溯法時可以先做"取"再做"不取"的,
以三個點的情況來說,則是 O--、OO-、OOO、OOX、OX-、OXO、OXX…
O代表該點要取,X代表該點不取,-代表還沒判斷。
而找到的答案先記錄起來,並記錄取了幾個點,
如果尋找的過程中取的點數超過了之前最佳的答案,
後面的部分就不需要再展開,以加快處理。

8
NPSC2016高中組初賽 / NPSC 2016 高中組初賽 F.逆序數對
« 於: 十一月 07, 2017, 01:45:22 pm »
使用到排列組合的數學題,
先分析題目中有多少組連續的>,例如 >>><>>,
可分成前面的 >>> 和後面的 >>,
前面的 >>> 代表有四個遞減的數,
這四個數任選兩個都是符合題目要求的送序數對,
總共有 C(4,2)=4*3/2=6 組,
而後面的 >> 則是 C(3,2)=3*2/2=3 組,
答案則是 6+3=9組。

9
NPSC2016高中組初賽 / NPSC 2016 高中組初賽 E.廢文 mining
« 於: 十一月 07, 2017, 01:38:04 pm »
N=1和N=2的情況直接處理,
N=3以上的情況,可以用
代碼: [選擇]
for (int i=3; i<=n; i++)
{
    s=s2+s1;
    s1=s2;
    s2=s;
}
這樣的寫法來取得第 N 天的文章,
但是如果N超大的情況,這個字串的長度可能會超過電腦的記憶體,
幸好題目有說我們要的第 K 字元的 K 最大只到 106
而當文章長度超過 106 時,
接下來不管多少天,前  106 的內容還是一樣的,
所以可以在前面的 for 裡加上一行:
代碼: [選擇]
if (s.size()>=1000000) break;
這樣問題應該就解決了。

10
站務區 / 註冊須知
« 於: 十一月 01, 2016, 02:35:16 pm »
1.本站開放註冊時間為每年10月1日至12月31日,其他時間關閉註冊。

2.請使用非免費信箱註冊,本站免費信箱只接受 gmail,使用其他信箱者一律刪除。

3.本站採兩階段認證,第一階段由站長審核 email 是否符合規定之後,再發出確認信,
第二階段收到確認信之後再點選其中的連結,即可啟用帳號。

11
NPSC2015高中組決賽 / NPSC 2015 高中組決賽 F.非對稱之美
« 於: 十月 20, 2016, 02:05:42 pm »
先排除所有字元都相同的情況,
接下來如果字串長度是 N,
則不可能同時找到長度為 N 和 N-1 的回文,
因此,答案只有 0、N-1、N 這三種。

12
NPSC2015高中組決賽 / NPSC 2015 高中組決賽 D.三角尼姆
« 於: 十月 20, 2016, 02:03:16 pm »
先分析,因為每個人只能放一顆或三顆棋子,
第一個人放的是第一或第三顆棋子,
而第二個人則是第二、四、六顆棋子,
再回來第一個人則是第三、五、七、九顆棋子,
發現不管怎麼放,第一個人放的最後一顆一定是奇數,
而第二個人放的最後一顆一定是偶數,
所以只要計算總共有幾顆棋子,
就知道最後一顆是誰放的了。

13
NPSC2015高中組初賽 / NPSC2015 高中組初賽 F.秋刀魚捕撈季
« 於: 十月 19, 2016, 04:04:01 pm »
將魚的重量從大排到小,取前 F 重量在 W 以上的加起來就行,
比較麻煩的是魚的重量會出現 other,
因此先以字串的方式輸入,
如果 s[ 0 ]!='o',再將這個字串轉換成數字,
for (i=0, w=0; i<s.size(); i++) w=w*10+s[ i ]-'0';
上面是轉換寫法的一個例子,
只要對字串轉換沒有恐懼,
這題應該是這次初賽中最簡單的一題。

14
NPSC2015高中組初賽 / NPSC2015 高中組初賽 E.零
« 於: 十月 19, 2016, 03:57:56 pm »
由於答案要取結尾有 m 個 0 的 N! 最小的那個,所以這個 N 一定是 5 的倍數。
可以寫一個函數計算 N! 的結尾有幾個 0,
一個一個找上去,但這樣會 TLE,
所以改成從 5~5*109 這範圍做二分搜尋,
就可以 AC。

15
NPSC2015高中組初賽 / NPSC2015 高中組初賽 B.盜墓迷城
« 於: 十月 19, 2016, 03:50:40 pm »
這題我的做法可能不是正解,
但至少官方的測資能過,
給大家參考。

我是先用兩個二維陣列 Aij、Cij
分別記錄從 (1,1)~(i,j) 這範圍內有幾個 A 和 C,
可以一邊輸入一邊計算,時間複雜度為 O(NM)。

再來用四層迴圈求所有 (x1,y1)-(x2,y2) 內的 A、C 個數是否相等,
相等就記錄其大小,記錄最大的那一個,
為了加快速度,我是 x1、y1 從小到大,而 x2、y2 從大到小,
所以矩形會慢慢變小,而如果做到一半發現接下來的矩形不可能比目前找到的最大的區域還大,
就可以不用再找下去了。

最後,有兩種會 TLE 的情況,分別是全部都是 A 或是 C,
這兩種排除可能 AC。

16
NPSC2013高中組初賽 / pD.RPG 遊戲之料理奇蹟
« 於: 十二月 19, 2013, 10:06:15 am »
字串苦工題, 會字串拆解應該就沒什麼難度。
食材部分, 因為需要快速找到對應編號的價格,所以直接把食材價格儲存到對應編號的格子中,
例如第 k 號的價格就存到 Food[k], 而不存在的食材就設成最大值。
料理的部分, 需要會用 stringstream (C++)或 strtok (C) 來做字串拆解,
要注意的是食材價格乘上數量會超過 int 的範圍,
記得宣告成 long long int。

參考程式:
代碼: [選擇]
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <cstring>
#include <cstdlib>

using namespace std;

long long int Item[100000];
int Food[100000], FN;

int main()
{
    int T, s, n, num, i;
    long long int sum, money;
    char str_num[12], c;
    string line;
    stringstream sin;
    cin >> T;
    while (T--)
    {
        for (i=0; i<100000; i++) Item[i]=100000000, Food[i]=0;
        cin >> s >> n;
        while (s--)
        {
            cin >> str_num >> c >> money;
            num=atoi(str_num+4);
            Item[num]=money;
        }
        for (FN=0; n--; )
        {
            cin >> str_num >> c >> money >> c;
            num=atoi(str_num+4);
            getline(cin, line);
            sin.clear();
            sin.str(line);
            sum=0;
            while (1)
            {
                sin >> s >> str_num;
                if (sin.fail()) break;
                sum+=Item[atoi(str_num+4)]*s;
                if (sum>=money) break;
            }
            if (sum<money) Food[FN++]=num;
        }
        sort(Food, Food+FN);
        for (i=0; i<FN; i++)
        {
            if (i) cout << "/";
            cout << "food" << Food[i];
        }
        if (FN==0) cout << "no such recipe.";
        cout << endl;
    }
    return 0;
}

17
NPSC2013高中組初賽 / pF.可魚果分配問題
« 於: 十二月 17, 2013, 02:55:24 pm »
取所有數的最大公因數,
先取前兩個數的最大公因數,
得到的數再跟第三個數取最大公因數,
反覆一直做到最後一個,
就可以得到答案。

參考程式:
代碼: [選擇]
#include <iostream>

using namespace std;

int GCD(int a, int b)
{
    int c;
    while (b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}

int main()
{
    int T, n, a, b, c, i;
    cin >> T;
    while (T--)
    {
        cin >> n >> a;
        for (i=1; i<n; i++)
        {
            cin >> b;
            a=GCD(a, b);
        }
        cout << a << endl;
    }
    return 0;
}

18
NPSC2013高中組初賽 / pC.胖胖天大大薯
« 於: 十二月 17, 2013, 02:37:36 pm »
先把這些數字從小排到大,
然後一個一個取,
如果出現過了, 就把它變成兩倍加到另一個空的佇列,
之後就從佇列跟這串數字找比較小的出來,
如果佇列的數字已經出現過, 則直接丟棄,
比較特別的是這串數字的第一個數字和佇列的一樣,
則是拿佇列的來處理, 而原本的數字變兩倍後再加到佇列的後面,
直到這串數字用完以及佇列也沒有數字為止,
就可以找到答案。

參考程式:
代碼: [選擇]
#include <iostream>
#include <algorithm>

using namespace std;

const int N=1000001, MAX=2000000001;
int a[N], b[N];

int main()
{
    int T, n, i, j, m, ans, now;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (i=0; i<n; i++)
            cin >> a[i];
        sort(a, a+n);
        a[n]=MAX;
        b[0]=MAX;
        for (i=0, j=0, m=0, now=0, ans=0; i<n || j<m; )
        {
            if (a[i]<b[j])
            {
                if (a[i]>now)
                {
                    now=a[i];
                    ans++;
                }
                else
                {
                    b[m++]=a[i]*2;
                    b[m]=MAX;
                }
                i++;
            }
            else if (a[i]>b[j])
            {
                if (b[j]>now)
                {
                    now=b[j];
                    ans++;
                }
                j++;
            }
            else // a[i]==b[j]
            {
                b[m++]=a[i]*2;
                b[m]=MAX;
                if (b[j]>now)
                {
                    now=b[j];
                    ans++;
                }
                i++;
                j++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

19
NPSC2013高中組初賽 / pB.重建薑餅部落
« 於: 十二月 17, 2013, 02:24:32 pm »
要把所有點連在一起, 這就是最小生成樹了,
因為所有的點都可以連到其他的點,
所以邊的數量是 N*(N-1)/2,
因此用 Prim 的效率會比 Kruskal 來得高,
而答案是最小生成樹裡的最長邊的一半。
演算法筆記http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html

參考程式:
代碼: [選擇]
#include <iostream>
#include <cmath>

using namespace std;

const long long int MAX=8000000000000000001LL;
long long int x[1000], y[1000], d[1000][1000], p[1000], ans;

int main()
{
    int T, n, i, j, k;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (i=0; i<n; i++)
            cin >> x[i] >> y[i];
        for (i=0; i<n; i++)
            for (j=0; j<n; j++)
                d[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
        for (p[0]=MAX, i=1; i<n; i++)
            p[i]=d[0][i];
        ans=0;
        while (1)
        {
            for (i=1, k=0; i<n; i++)
                if (p[i]<p[k]) k=i;
            if (k==0) break;
            if (p[k]>ans) ans=p[k];
            p[k]=MAX;
            for (i=1; i<n; i++)
                if (p[i]<MAX && d[k][i]<p[i]) p[i]=d[k][i];
        }
        cout << int(ceil(sqrt(ans)+1)/2) << endl;
    }
    return 0;
}

20
NPSC2013高中組初賽 / pA.蚯蚓國的謎題
« 於: 十二月 17, 2013, 01:56:09 pm »
簡單的暴力解, 用三層迴圈 i=1~3、j=i+1~4、k=j+1~5,
乘起來的平方是所有數乘積就是一種分法,
第6個永遠算另一邊的, 這樣就不會有重覆的分法了,
而如果所有數乘積不是完全平方數也不用再去算了, 直接輸出 0,
另外, 因為6個數的乘積會超過 int 的範圍,
所以記得要開 long long int。

參考程式:
代碼: [選擇]
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int T, a[6], i, j, k, ans;
    long long int s, l;
    cin >> T;
    while (T--)
    {
        for (i=0, s=1; i<6; i++)
        {
            cin >> a[i];
            s*=a[i];
        }
        l=sqrt(s);
        if (l*l<s)
        {
            cout << 0 << endl;
            continue;
        }
        for (i=0, ans=0; i<3; i++)
            for (j=i+1; j<4; j++)
                for (k=j+1; k<5; k++)
                    if (a[i]*a[j]*a[k]==l) ans++;
        cout << ans << endl;
    }
    return 0;
}

頁: [1] 2 3 ... 6