99學年度彰化高級中學資訊學科競賽

http://student.chsh.chc.edu.tw/JudgeOnline/

這是章裕老師最近架的OnlineJudge，雖然說是最近好像也有幾個月了，目前還算是測試版本，因為老師在另一個Judge上丟的題目比較多，只是未公開。如果弄好一個題目就釋出會害某人一直Coding都不讀書了。

今年校內初選題目還是跟往常差不多程度，只是和TOI，NPSC，全國賽的題目程度差的遠了。

有興趣看題目的可以到上面的OJ找，Problem ID 1043~1048。

比較癥結的大概只有1047(pE)，由於數據大小導致DP過不了TLE，但是似乎是因為題目的性質DP反而並不是那麼好，深搜剪枝快了幾百倍。

計概筆試就算了，老師透露今年好像是出跟上一年一樣的，可是我沒發現，而且我也考的很爛，這種東西最後一次看已經是TOI初選之前，好幾個月了。一直到初選早上才又拿出來翻一下，反正這東西到了TOI就用不到了。

不過學弟就有好幾個計概比我高分的，還好他們程設只有一個破台而且破台的計概分數低我一分，要不然比我高就被莫名拿走第一名了。

------------------------------------我是防雷線---------------------------------------

雖然說初選的題目根本不需要別人雷就能Co出來，但是李岳跟我說要叫我去跟章裕老師要學科題目的答案，但是程設題目根本就沒有標準答案阿，只是有作法可以解決題目，所以只能說參考答案，不一定是最佳的作法。以下提供敝人微不足道的想法及程式碼：

pA 三角形外接圓周長

要不是題目直接提供公式，這題可能會變成我最後才會寫的題目，一看到公式就馬上飆了，只是Code出來看起來有點噁心就是了，如果沒有提供公式我可能就卡提了，其實有學過三角函數應該推的出來不過現在都忘光光了，照公式換一下就能求出R了，最後要輸出圓周長還需要求π值，用cmath裡的acos(0.0)*2就能求π了。

#include <cstdio>
#include <cmath>

int main()
{
    double x1,y1,x2,y2,x3,y3,a,b,c,s,ans,pi=acos(0.0)*2;
    while (scanf("%lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3)==6){
        a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
        b=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
        c=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1));
        s=(a+b+c)/2;
        ans=2*pi*a*b*c/4.0/sqrt(s*(s-a)*(s-b)*(s-c));
        printf("%.6lf\n",ans);
    }
    return 0;
}

pB 阿凡達計畫

簡單來說就是給你一N個數字，從大到小排序後輸出，如果有重複的數字只要輸出一個代表就好，但是這題一開始就害一堆人WA了，因為題目沒說數字範圍到哪，N也不知道多少個，正常來想就只會開int，沒想到測資到long long，還是問當時問老師才知道，因為這樣WA就很不高興。

至於排序部份就用STL，簡潔方便又快速，記得要include <algorithm>，另外OJ是Linux的系統是用%lld輸出long long，如果在win的電腦上測試要用%I64d。

#include <cstdio>
#include <algorithm>

int n;
long long a[1000000];
bool cmp(long long i,long long j){
    return i>j;
}
int main()
{
    while (scanf("%d",&n)==1){
        for (int i=0;i<n;i++)
           scanf("%lld",&a[i]);
        std::stable_sort(a,a+n,cmp);
        long long f=a[0];
        printf("%lld",f);
        for (int i=1;i<n;i++){
            if (a[i]!=f){
                f=a[i];
                printf(" %lld",f);
            }
        }
        puts("");
    }
    return 0;
}

pC 接水問題

這題我本來以為是要找出一個方法使得所有需要時間最少，還在那邊想Greedy，浪費了十幾分鐘Co出來還是有Bug的也不知道作法對不對。後來才再看一次題目根本是照作而已，只是每一次搜尋M個水龍頭可以用heap做到O(logM)，可是M才一百直接全搜就過了，不過當時我是先Sort一次每次取第一個最小值加上下一個人之後在往後Swap到全部為由小到大，結果發現時間竟然還比柏岳直接搜的慢。

直接搜的Code，O(NM)：

#include <cstdio>

int main()
{
    int n,m,a[100],temp;
    while (scanf("%d %d",&n,&m)==2){
        for (int i=0;i<m;i++)
            scanf("%d",&a[i]);
        for (int i=m;i<n;i++){
            int mini=2147483647,miniat;
            scanf("%d",&temp);
            for (int i=0;i<m;i++)
                if (a[i]<mini)
                    mini=a[i],miniat=i;
            a[miniat]+=temp;
        }
        int ans=0;
        for (int i=0;i<m;i++)
            if (a[i]>ans)
                ans=a[i];
        printf("%d\n",ans);
    }
    return 0;
}

先排序後每次交換更新，O(NM)：

#include <cstdio>
#include <iostream>
#include <algorithm>

int main()
{
    int n,m,w[10000],now[100];
    while (scanf("%d %d",&n,&m)==2){
        for (int i=0;i<n;i++)
           scanf("%d",&w[i]);
        for (int i=0;i<m;i++)
            now[i]=w[i];
        std::stable_sort(now,now+m);
        for (int j=m;j<n;j++){
            now[0]+=w[j];
            int at=0;
            while (at+1<m&&now[at]>now[at+1]){
                std::swap(now[at],now[at+1]);
                at++;
            }
        }
        printf("%d\n",now[m-1]);
    }
    return 0;
}

Heap(堆) O(NlogM)：

#include <cstdio>

int heap[101],m;
void down(int x){
    int s=x<<1,v=heap[x];
    while (s<=m){
        if (s<m&&heap[s]>heap[s+1])
            s++;
        if (heap[s]>=v)
            break;
        heap[x]=heap[s];
        x=s;
        s<<=1;
    }
    heap[x]=v;
}
int main()
{
    int n,a[10001];
    while (scanf("%d %d",&n,&m)==2){
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for (int i=1;i<=m;i++)
            heap[i]=a[i];
        for (int i=m>>1;i>=1;i--)
            down(i);
        for (int i=m+1;i<=n;i++){
            heap[1]+=a[i];
            down(1);
        }
        int ans=0;
        for (int i=1;i<=m;i++)
            if (heap[i]>ans)
                ans=heap[i];
        printf("%d\n",ans);
    }
    return 0;
}

pD 字卡遊戲

一開始看不懂題目在說什麼，什麼按照由小而大順序排列的個數較多，往下一翻看到DP Lis，頓時無言，因為那一行敘述好詭異，反正就是找最長遞增子序列，經典問題，而且是字串小寫字母，不用做到O(NlogN)，O(N^2)就可以了，如果是數字而且很多的話才需要二分搜作O(NlogN)。

O(N^2)：

#include <cstdio>
#include <string.h>

int lis(char s[]){
    int len=strlen(s),dp[40],ans=1;
    for (int i=0;i<len;i++)
        dp[i]=1;
    for (int i=1;i<len;i++){
        for (int j=0;j<i;j++)
            if (s[i]>s[j]&&dp[j]+1>dp[i])
                dp[i]=dp[j]+1;
        if (dp[i]>ans)
            ans=dp[i];
    }
    return ans;
}
int main()
{
    char a[40],b[40];
    int ansa,ansb;
    while (scanf("%s %s",a,b)!=EOF){
        ansa=lis(a);
        ansb=lis(b);
        if (ansa>ansb)
            puts("Win");
        else if (ansa==ansb)
            puts("Fair");
        else
            puts("Lose");
    }
    return 0;
}

pE 教學檔案備分

一開始直覺DP，可是沒算暴搜和DP的比較，DP就TLE了，DP我想到的是背包O(NF)，但是深搜是O(2^F)，如果F夠大說不定能夠把深搜卡掉，可是這題深搜剪枝非常的有效？本來我只是直接搜目前選了哪幾個，如果總和超過容量馬上cut掉，可是柏岳又多加了一個目前總合加上剩下未選擇的能夠都放入容量的話就更新目前最佳答案並且cut掉，瞬間從3xx ms變成 0ms。至於Sort是為了避免多餘的深搜能夠多cut一點。

深搜剪枝：

#include <cstdio>
#include <algorithm>

int file[25],ans,f,n,s[26];
bool cmp(int i,int j){
    return i>j;
}
void dfs(int x,int sum){
    if (sum+s[x]<=n){
        if (sum+s[x]>ans)
            ans=sum+s[x];
        return;
    }
    if (sum>n)
        return;
    dfs(x+1,sum+file[x]);
    dfs(x+1,sum);
}
int main()
{
    while (scanf("%d",&n)==1){
        ans=0;
        scanf("%d",&f);
        for (int i=0;i<f;i++)
            scanf("%d",&file[i]);
        std::stable_sort(file,file+f,cmp);
        s[f]=0;
        for (int i=f-1;i>=0;i--)
            s[i]=s[i+1]+file[i];
        dfs(0,0);
        printf("%d\n",ans);
    }
    return 0;
}

pF 數字系統轉換

N進制的轉換我就只會這樣做了吧，每一次mod N把數字存起來，最後倒著輸出，好像不太好？

#include <cstdio>

void change(int n,int x){
    int a[100],num=0;
    while (x!=0){
        a[num++]=x%n;
        x/=n;
    }
    for (int i=num-1;i>=0;i--)
        printf("%d",a[i]);
}
int main()
{
    int n,x,y,z;
    while (scanf("%d %d %d",&n,&x,&y)==3){
        z=x+y;
        change(n,x);
        printf(" + ");
        change(n,y);
        printf(" = ");
        change(n,z);
        puts("");
    }
    return 0;
}