Yeefan's Blog

2011年10月26日星期三

NOIP2006普及組明明的隨機數 random 解題報告

【問題描述】

明明想在學校中請一些同學一起做一項問卷調查，爲了實驗的客觀性，他先用計算機生成了 N 個 1 到 1000 之間的隨機整數（ N ≤ 100 ），對於其中重複的數字，只保留一個，把其餘相同的數去掉，不同的數對應着不同的學生的學號。然後再把這些數從小到大排序，按照排好的順序去找同學做調查。請你協助明明完成“去重”與“排序”的工作。

【輸入格式】

輸入文件 random.in 有 2 行，第 1 行爲 1 個正整數，表示所生成的隨機數的個數：N

第 2 行有 N 個用空格隔開的正整數，爲所產生的隨機數。

【輸出格式】

輸出文件 random.out 也是 2 行，第 1 行爲 1 個正整數 M ，表示不相同的隨機數的個數。第 2 行爲 M 個用空格隔開的正整數，爲從小到大排好序的不相同的隨機數。

【輸入輸出樣例】

輸入：

20 40 32 67 40 20 89 300 400 15

輸出：

15 20 32 40 67 89 300 400

【分析】

再水不過的題了，直接模擬，然後上快速排序。

【我的代碼】

//NOIP2006-Junior-Random
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

int Compare(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}

int main()
{
    freopen("random.in","r",stdin);
    freopen("random.out","w",stdout);
    int num[101]={0};
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    int reduce=0;
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            if (num[j]!=1001 && num[i]!=1001 && num[j]==num[i])
                {
                    num[j]=1001;
                    reduce++;
                }
    qsort(num+1,n,sizeof(int),Compare);
    cout<<n-reduce<<endl;
    for(int i=1;i<=n-reduce;i++)
        cout<<num[i]<<" ";
    cout<<endl;
    return 0;
}

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.018 s	273 KB	0
2	正确	10	0.001 s	273 KB	0
3	正确	10	0.001 s	273 KB	0
4	正确	10	0.001 s	273 KB	0
5	正确	10	0.001 s	273 KB	0
6	正确	10	0.001 s	273 KB	0
7	正确	10	0.001 s	273 KB	0
8	正确	10	0.001 s	273 KB	0
9	正确	10	0.001 s	273 KB	0
10	正确	10	0.001 s	273 KB	0

运行完成
运行时间 0.024 s
平均内存使用 273 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

NOIP2002普及組選數 choose 解題報告

[問題描述]:

已知 n 個整數 x1,x2,…,xn，以及一個整數 k（k＜n）。從 n 個整數中任選 k 個整數相加，可分別得到一系列的和。例如當 n=4，k＝3，4 個整數分別爲 3，7，12，19 時，可得全部的組合與它們的和爲：

3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。

現在，要求你計算出和爲素數共有多少種。

例如上例，只有一種的和爲素數：3＋7＋19＝29）。

[輸入]：

鍵盤輸入，格式爲：

n , k （1<=n<=20，k＜n）

x1,x2，…,xn （1<=xi<=5000000）

[輸出]：

格式爲：一個整數（滿足條件的種數）。

[輸入輸出樣例]:

輸入：choose.in

4 3

3 7 12 19

輸出：choose.out

【分析】

排列組合問題，直接深度優先搜索（遞歸）即可。

//NOIP2002 Junior
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int sum=0;//當前總和
int num[21];
int n,k;
int tot=0;

bool prime(int num)
{
    if (num==1)return false;
    for (int i=2;i<=(int)sqrt(double(num));i++)
        if (num%i==0)
            return false;
    return true;    
}


void dg(int dep,int loc)
{
    if(k-dep>n-loc) return;
    if (dep==k+1)
    {
        if (prime(sum))
            tot++;
    }
    if (dep<k+1)
    {
        for (int i=loc;i<=n;i++)
        {
            sum+=num[i];
            dg(dep+1,i+1);
            sum-=num[i];
        }
    }
}

int main()
{
    freopen("choose.in","r",stdin);
    freopen("choose.out","w",stdout);
    cin>>n>>k;
    for (int i=1;i<=n;i++)
        cin>>num[i];
    dg(1,1);
    cout<<tot<<endl;
    return 0;
}

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	20	0.026 s	275 KB	0
2	正确	20	0.001 s	275 KB	0
3	正确	20	0.001 s	275 KB	0
4	正确	20	0.001 s	275 KB	0
5	正确	20	0.001 s	275 KB	0

运行完成
运行时间 0.028 s
平均内存使用 275 KB
测试点通过状况 AAAAA
得分：100
恭喜你通过了全部测试点!

NOIP2005普及組采藥 medic 解題報告

【問題描述】

辰辰是個天資聰穎的孩子，他的夢想是成爲世界上最偉大的醫師。爲此，他想拜附近最有威望的醫師爲師。醫師爲了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裏對他說：“孩子，這個山洞裏有一些不同的草藥，採每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間裏，你可以採到一些草藥。如果你是一個聰明的孩子，你應該可以讓採到的草藥的總價值最大。”

如果你是辰辰，你能完成這個任務嗎？

【輸入文件】

輸入文件的第一行有兩個整數 T （ 1 <= T <= 1000 ）和 M （ 1 <= M <= 100 ），用一個空格隔開， T 代表總共能夠用來採藥的時間， M 代表山洞裏的草藥的數目。接下來的 M 行每行包括兩個在 1 到 100 之間（包括 1 和 100 ）的整數，分別表示採摘某株草藥的時間和這株草藥的價值。

【輸出文件】

輸出文件包括一行，這一行只包含一個整數，表示在規定的時間內，可以採到的草藥的最大總價值。

【樣例輸入】

70 3

71 100

69 1

1 2

【樣例輸出】

【數據規模】

對於 30% 的數據， M <= 10 ；

對於全部的數據， M <= 100 。

【分析】

本題是經典的0/1背包問題，直接DP即可，不需要任何優化。

【我的代碼】

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;

typedef unsigned short int usint;

class medic

{

public:

usint t; //Time

usint v; //Value

}Med[101];

usint T,M;//T: Total Time , M: The number of the medicine.

usint F[101][1001];

void init()

{

cin>>T>>M;

//初始化二維表

for (usint i=1;i<=M;i++)

for (usint j=1;j<=T;j++)

F[i][j]=0;

//從文件中讀入

for(usint i=1;i<=M;i++)

cin>>Med[i].t>>Med[i].v;

//預處理動態規劃 Pre-Dynamic Programing

for (usint i=Med[1].t;i<=T;i++)

F[1][i]=Med[1].v;

return;

}

void Dynamic()

{

usint i,j;

for (i=2;i<=M;i++)

{

for(j=1;j<=T;j++)

{

if(Med[i].t>j)

F[i][j]=F[i-1][j];

else

{

F[i][j]=( (F[i-1][j]) > (F[i-1][j-Med[i].t]+Med[i].v) ?

(F[i-1][j]) : (F[i-1][j-Med[i].t]+Med[i].v) );

}

int main()

{

freopen("medic.in","r",stdin);

freopen("medic.out","w",stdout);

init();

Dynamic();

cout<<F[M][T]<<endl;

return 0;

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.024 s	464 KB	0
2	正确	10	0.001 s	464 KB	0
3	正确	10	0.002 s	464 KB	0
4	正确	10	0.002 s	464 KB	0
5	正确	10	0.002 s	464 KB	0
6	正确	10	0.002 s	464 KB	0
7	正确	10	0.002 s	464 KB	0
8	正确	10	0.002 s	464 KB	0
9	正确	10	0.002 s	464 KB	0
10	正确	10	0.001 s	464 KB	0

运行完成
运行时间 0.041 s
平均内存使用 464 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

金明今天很開心，家裏購置的新房就要領鑰匙了，新房裏有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過 N 元錢就行”。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的 N 元。於是，他把每件物品規定了一個重要度，分爲 5 等：用整數 1 ~ 5 表示，第 5 等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過 N 元（可以等於 N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。

設第 j 件物品的價格爲 v[j] ，重要度爲 w[j] ，共選中了 k 件物品，編號依次爲 j1 ， j2 ，……， jk ，則所求的總和爲：

v[j1]*w[j1]+v[j2]*w[j2]+ … +v[jk]*w[jk] 。（其中 * 爲乘號）

請你幫助金明設計一個滿足要求的購物單。

【輸入格式】

輸入文件 happy.in 的第 1 行，爲兩個正整數，用一個空格隔開：

N m

（其中 N （ < 30000 ）表示總錢數， m （ <25 ）爲希望購買物品的個數。）

從第 2 行到第 m+1 行，第 j 行給出了編號爲 j-1 的物品的基本數據，每行有 2 個非負整數

v p

（其中 v 表示該物品的價格 (v<=10000) ， p 表示該物品的重要度 (1~5) ）

【輸出格式】

輸出文件 happy.out 只有一個正整數，爲不超過總錢數的物品的價格與重要度乘積的總和的最大值（ <100000000 ）。

【輸入輸出樣例】

輸入：

1000 5

800 2

400 5

300 5

400 3

200 2

輸出：

3900

【分析】

本題和NOIP2006提高組第二題——金明的預算方案形成對應。都是同一類型、同一背景的題。
這是個典型的、簡單的0/1背包問題，
F[i,k]表示前i件物品花費最大為k時物品價格與物品重要度乘積的最大值。
W[i]表示第i件物品的價格。
V[i]表示第i件物品的重要度。
狀態轉移方程：
F[i,k]= F[i-1,k] (W[i]>k)
F[i,k]=max{ F[i-1,k], F[i-1,k-W[i]]+W[i]*V[i]} (W[i]<=k)
邊界條件：
(數組下標從1開始)
F[1][k]=W[i]*V[i] (W[i]>=k)

【我的代碼】

#include <iostream>
using namespace std;
int TolM;//總錢數
int TolThing;//總物品
int F[26][100001];
class THING
{
public:
    int v;//價格
    int p;//重要度
}T[25];

int getval(int i)
{
    return (T[i].v*T[i].p);
}

void init()
{
    cin>>TolM>>TolThing;
    for (int i=1;i<=TolThing;i++)
    {
        cin>>T[i].v>>T[i].p;
    }
    fclose(stdin);
    return;
}

void predp()
{
    int i,j;
    for (i=1;i<=TolThing;i++)
        for (j=1;j<=TolM;j++)
            F[i][j]=0;

    int q=getval(1);
    for (i=T[1].v;i<=TolM;i++)
    {
        F[1][i]=q;
    }
    return;
}

void print()
{
    int i,j;
    for (i=1;i<=TolThing;i++)
    {
        for (j=1;j<=TolM;j++)
            cout<<F[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}

void dp()
{
    int i,j;
    for (i=2;i<=TolThing;i++)
    {
        for (j=1;j<=TolM;j++)
        {
            if (T[i].v>j)
                F[i][j]=F[i-1][j];
            else
                F[i][j]=
                ((F[i-1][j])>(F[i-1][j-T[i].v]+getval(i))?
                (F[i-1][j]):(F[i-1][j-T[i].v]+getval(i)));
        }
    }
}

int main()
{
    freopen("happy.in","r",stdin);
    freopen("happy.out","w",stdout);
    init();
    predp();
    dp();
    //print();
    cout<<F[TolThing][TolM]<<endl;
    return 0;
}

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.001 s	10424 KB	0
2	正确	10	0.001 s	10424 KB	0
3	正确	10	0.002 s	10424 KB	0
4	正确	10	0.002 s	10424 KB	0
5	正确	10	0.008 s	10424 KB	0
6	正确	10	0.005 s	10424 KB	0
7	正确	10	0.008 s	10424 KB	0
8	正确	10	0.011 s	10424 KB	0
9	正确	10	0.013 s	10424 KB	0
10	正确	10	0.001 s	10424 KB	0

运行完成
运行时间 0.052 s
平均内存使用 10424 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

NOIP2005提高組过河 river 解題報告

【問題描述】

在河上有一座獨木橋，一隻青蛙想沿着獨木橋從河的一側跳到另一側。在橋上有一些石子，青蛙很討厭踩在這些石子上。由於橋的長度和青蛙一次跳過的距離都是正整數，我們可以把獨木橋上青蛙可能到達的點看成數軸上的一串整點： 0 ， 1 ，……， L （其中 L 是橋的長度）。座標爲 0 的點表示橋的起點，座標爲 L 的點表示橋的終點。青蛙從橋的起點開始，不停的向終點方向跳躍。一次跳躍的距離是 S 到 T 之間的任意正整數（包括 S,T ）。當青蛙跳到或跳過座標爲 L 的點時，就算青蛙已經跳出了獨木橋。

題目給出獨木橋的長度 L ，青蛙跳躍的距離範圍 S,T ，橋上石子的位置。你的任務是確定青蛙要想過河，最少需要踩到的石子數。

【輸入文件】

輸入文件的第一行有一個正整數 L （ 1 <= L <= 10^9 ），表示獨木橋的長度。第二行有三個正整數 S ， T ， M ，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個數，其中 1 <= S <= T <= 10 ， 1 <= M <= 100 。第三行有 M 個不同的正整數分別表示這 M 個石子在數軸上的位置（數據保證橋的起點和終點處沒有石子）。所有相鄰的整數之間用一個空格隔開。

【輸出文件】

輸出文件只包括一個整數，表示青蛙過河最少需要踩到的石子數。

【輸入輸出樣例】

river .in

2 3 5

2 3 5 6 7

river .out

【數據規模】

對於30%的數據，L <= 10000；

對於全部的數據，L <= 10^9。

【分析】

以下題解来自：http://www.byvoid.com/blog/noip-allsolutions/

動態規劃，需要狀態壓縮。

狀態

F[i] 跳到距離i處碰到的最少的石子數。

狀態轉移方程

F[i]=min{ F[i-k] } + F[i] (S<=k<=T i-k>=0)

邊界條件

F[i]=1 i處有石子

目標結果

min{ F[k] } (L+1<=k<=L+T-1)

狀態壓縮

由於L最大爲10^9，直接綫性遞推會超時。發現石子數很少，這意味着路徑上有許多很長的空白段。我們可以把長度大於S*T的空白段都縮小到S*T，這樣最長只有10090了。

【我的代碼】

//NOIP2005 river
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;
ifstream fin("river.in");
ofstream fout("river.out");
int F[100000]={0};
int stone[1000];
int maxd, //每次跳跃的最大距离
    mind, //每次跳躍的最小距離
    S, //石子的长度
    L; //独木桥的长度

int Compare(const void *elem1, const void *elem2)
{
    return *((int *)(elem1)) - *((int *)(elem2));
}

void init()
{
    fin>>L;
    fin>>mind>>maxd>>S;
    for(int i=1;i<=S;i++)
    {
        fin>>stone[i];
    }
    fin.close();
}

void compress()
{
    int p=maxd*mind;
    int k;
    stone[0]=0;
    stone[S+1]=L;
    for (int i=1;i<=S+1;i++)
    {
        if (stone[i]-stone[i-1]>p)
        {
            k=stone[i]-stone[i-1]-p;
            for (int j=i;j<=S+1;j++)
                stone[j]-=k;
            stone[i]=stone[i-1]+p;
        }
        F[stone[i]]=1;
    }
    L=stone[S+1];
}

void dp()
{
    int best;
    for (int i=1; i<=L+maxd-1; i++)
    {
        best=0xfffffff;
        for (int k=mind;k<=maxd;k++)
        {
            if (i-k>=0)
            {
                if (best>F[i-k])
                    best=F[i-k];
            }
        }
        F[i]+=best;
    }
}

int main()
{
    init();

    if (maxd==mind)
    {
        int best=0;
        for (int i=1;i<=S;i++)
            if (stone[i]%mind==0) best++;
        fout<<best<<endl;
        return 0;
    }

    qsort(stone+1,S,sizeof(int),Compare);
    compress();


    dp();
    int best=0xfffffff;
    for (int k=L+1;k<=L+maxd-1;k++)
    {
        if (best>F[k])
            best=F[k];
    }
    fout<<best<<endl;
    return 0;
}

NOIP2005提高組誰拿了最多獎學金 scholar 解題報告

【問題描述】

某校的慣例是在每學期的期末考試之後發放獎學金。發放的獎學金共有五種，獲取的條件各自不同：

1) 院士獎學金，每人8000元，期末平均成績高於80分（>80），並且在本學期內發表1篇或1篇以上論文的學生均可獲得；

2) 五四獎學金，每人4000元，期末平均成績高於85分（>85），並且班級評議成績高於80分（>80）的學生均可獲得；

3) 成績優秀獎，每人2000元，期末平均成績高於90分（>90）的學生均可獲得；

4) 西部獎學金，每人1000元，期末平均成績高於85分（>85）的西部省份學生均可獲得；

5) 班級貢獻獎，每人850元，班級評議成績高於80分（>80）的學生幹部均可獲得；

只要符合條件就可以得獎，每項獎學金的獲獎人數沒有限制，每名學生也可以同時獲得多項獎學金。例如姚林的期末平均成績是87分，班級評議成績82分，同時他還是一位學生幹部，那麼他可以同時獲得五四獎學金和班級貢獻獎，獎金總數是4850元。

現在給出若干學生的相關數據，請計算哪些同學獲得的獎金總數最高（假設總有同學能滿足獲得獎學金的條件）。

【輸入文件】

輸入文件scholar.in的第一行是一個整數N（1 <= N <= 100），表示學生的總數。接下來的N行每行是一位學生的數據，從左向右依次是姓名，期末平均成績，班級評議成績，是否是學生幹部，是否是西部省份學生，以及發表的論文數。姓名是由大小寫英文字母組成的長度不超過20的字符串（不含空格）；期末平均成績和班級評議成績都是0到100之間的整數（包括0和100）；是否是學生幹部和是否是西部省份學生分別用一個字符表示，Y表示是，N表示不是；發表的論文數是0到10的整數（包括0和10）。每兩個相鄰數據項之間用一個空格分隔。

【輸出文件】

輸出文件scholar.out包括三行，第一行是獲得最多獎金的學生的姓名，第二行是這名學生獲得的獎金總數。如果有兩位或兩位以上的學生獲得的獎金最多，輸出他們之中在輸入文件中出現最早的學生的姓名。第三行是這N個學生獲得的獎學金的總數。

【樣例輸入】

YaoLin 87 82 Y N 0

ChenRuiyi 88 78 N Y 1

LiXin 92 88 N N 0

ZhangQin 83 87 Y N 1

【樣例輸出】

ChenRuiyi

9000

28700

【分析】

這幾乎是NOIP中最水的題了，只要學過編程的人都會做，只要看清題目，就能一次AC。

【我的代碼】

#include <cstring>

#include <fstream>

using namespace std;

ifstream fin("scholar.in");

ofstream fout("scholar.out");

class Student

{

public:

string name;//學生姓名

unsigned int final;//期末成績

unsigned int Class;//班級評議

bool cadre; //是否幹部

bool west; //是否西部學生

short int lunwen;//論文數量

long long total;

Student()

{

cadre=false;

west=false;

total=0;

}

}N[101];

int n;

int maxn=0;

int maxx=0;

long long s=0;

void init()

{

char chr;

fin>>n;

for (int i=1;i<=n;i++)

{

fin>>N[i].name>>N[i].final>>N[i].Class;

fin>>chr;

if (chr=='Y') N[i].cadre=true;

fin>>chr;

if (chr=='Y') N[i].west=true;

fin>>N[i].lunwen;

}

return;

}

void compute(int num)

{

if (N[num].final>80 && N[num].lunwen>=1) N[num].total+=8000;

if (N[num].final>85 && N[num].Class>80) N[num].total+=4000;

if (N[num].final>90) N[num].total+=2000;

if (N[num].final>85 && N[num].west) N[num].total+=1000;

if (N[num].Class>80 && N[num].cadre) N[num].total+=850;

if (N[num].total>maxn)

{

maxn=N[num].total;

maxx=num;

}

s+=N[num].total;

}

int main()

{

init();

for (int i=1;i<=n;i++)

compute(i);

fout<<N[maxx].name<<endl<<N[maxx].total<<endl<<s<<endl;

return 0;

}

正在连接评测机...
已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.001 s	270 KB	0
2	正确	10	0.000 s	270 KB	0
3	正确	10	0.000 s	270 KB	0
4	正确	10	0.000 s	270 KB	0
5	正确	10	0.000 s	270 KB	0
6	正确	10	0.000 s	270 KB	0
7	正确	10	0.001 s	270 KB	0
8	正确	10	0.000 s	270 KB	0
9	正确	10	0.000 s	270 KB	0
10	正确	10	0.001 s	270 KB	0

运行完成
运行时间 0.005 s
平均内存使用 270 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

訂閱：文章 (Atom)

Yeefan's Blog

申請SAE

2011年10月26日星期三

NOIP2006普及組明明的隨機數 random 解題報告

NOIP2002普及組選數 choose 解題報告

NOIP2005普及組采藥 medic 解題報告

NOIP2006普及組開心的金明 happy 解題報告

NOIP2005提高組过河 river 解題報告

NOIP2005提高組誰拿了最多獎學金 scholar 解題報告

申請SAE

2011年10月26日 星期三

NOIP2006普及組 明明的隨機數 random 解題報告

NOIP2002普及組 選數 choose 解題報告

NOIP2005普及組 采藥 medic 解題報告

NOIP2006普及組 開心的金明 happy 解題報告

NOIP2005提高組 过河 river 解題報告

NOIP2005提高組 誰拿了最多獎學金 scholar 解題報告

2011年10月26日星期三

NOIP2006普及組明明的隨機數 random 解題報告

NOIP2002普及組選數 choose 解題報告

NOIP2005普及組采藥 medic 解題報告

NOIP2006普及組開心的金明 happy 解題報告

NOIP2005提高組过河 river 解題報告

NOIP2005提高組誰拿了最多獎學金 scholar 解題報告