NOIP2011提高組 選擇客棧 hotel 解題報告

【問題描述】 
麗江河邊有n 家很有特色的客棧，客棧按照其位置順序從1 到n 編號。每家客棧都按照某一種色調進行裝飾（總共k 種，用整數0 ~ k-1 表示），且每家客棧都設有一家咖啡店，每家咖啡店均有各自的最低消費。兩位遊客一起去麗江旅遊，他們喜歡相同的色調，又想嘗試兩個不同的客棧，因此決定分別住在色調相同的兩家客棧中。晚上，他們打算選擇一家咖啡店喝咖啡，要求咖啡店位於兩人住的兩家客棧之間（包括他們住的客棧），且咖啡店的最低消費不超過p。他們想知道總共有多少種選擇住宿的方案，保證晚上可以找到一家最低消費不超過p元的咖啡店小聚。

 【輸入】輸入文件hotel.in，共n+1 行。第一行三個整數n，k，p，每兩個整數之間用一個空格隔開，分別表示客棧的個數，色調的數目和能接受的最低消費的最高值；接下來的n 行，第i+1 行兩個整數，之間用一個空格隔開，分別表示i 號客棧的裝飾色調和i 號客棧的咖啡店的最低消費。

 【輸出】輸出文件名為hotel.out。輸出只有一行，一個整數，表示可選的住宿方案的總數。 

【輸入輸出樣例1】 
hotel.in 
5 2 3
 0 5 
1 3 
0 2 
1 4 
1 5 
hotel.out 

3 
【輸入輸出樣例說明】

客棧編號	①	②	③	④	⑤
色調	0	1	0	1	1
最低消費	5	3	2	4	5

2人要住同樣色調的客棧，所有可選的住宿方案包括：住客棧①③，②④，②⑤，④⑤，但是若選擇住4、5 號客棧的話，4、5 號客棧之間的咖啡店的最低消費是4，而兩人能承受的最低消費是3 元，所以不滿足要求。因此只有前3 種方案可選。 

【數據范圍】
 對於30%的數據，有n≤100； 
對於50%的數據，有n≤1,000； 
對於100%的數據，有2≤n≤200,000，0<k≤50，0≤p≤100， 0≤最低消費≤100。

【分析】
 記憶化枚舉，或者動態規劃。
可以邊讀入邊計算：
 Pre[i]：前i個客棧中，最後一個 消費小於P的客棧。
Sum[i,j]：前j個客棧中，第i種顔色的總數量。   
S：總方案數

定義ci,pi表示讀入時第i個客棧的顔色、價格。
Sum[ci,i]=Sum[ci,i-1]+1;
Sum[j,i]=Sum[j-1,i](j!=ci)
 
如果pi<=P，Pre[i]=Pre[i-1]+1，S+=Sum[ci][Pre[i]]-1。
如果pi>P，Pre[i]=Pre[i-1]，S+=Sum[ci][Pre[i]]。


最後輸出S即可。沒有必要使用long long類型。

時間複雜度：O（NK）
空間複雜度：NK


【我的代碼】

C++语言: Codee#24285

01 /*
02 *Problem:NOIP2011-Senior-Hotel
03 *Date:2011.11.27
04 *Author:Yee-fan Zhu
05 */
06 #include <cstdio>
07 #include <cstdlib>
08 #include <iostream>
09 using namespace std;
10
11 const int MAXN=200002;
12 int Sum[52][MAXN];
13 int Pre[MAXN];
14 int S=0;
15 int N,P,K;
16
17 void init()
18 {
19     std::ios::sync_with_stdio(false);
20     scanf("%d %d %d\n",&N,&K,&P);
21    
22     for (int i=0;i<=N;i++)
23         Pre[i]=0;
24     for (int i=0;i<=N;i++)
25         for (int j=0;j<=K;j++)
26             Sum[j][i]=0;
27    
28     int c,p;
29     for (int i=1;i<=N;i++)
30     {
31         scanf("%d %d\n",&c,&p);
32         Sum[c][i]=Sum[c][i-1]+1;
33        
34         for (int j=0;j<K;j++)
35             if(j!=c)
36                 Sum[j][i]=Sum[j][i-1];
37        
38         if(p<=P)
39         {
40             Pre[i]=i;
41             S+=Sum[c][Pre[i]]-1;
42         }
43         else
44         {
45             Pre[i]=Pre[i-1];
46             S+=Sum[c][Pre[i]];
47         }
48     }
49     printf("%d\n",S);
50 }
51
52 int main()
53 {
54     freopen("hotel.in","r",stdin);
55     freopen("hotel.out","w",stdout);
56     init();
57     return 0;
58 }

【評測結果】
正在连接评测机...

已连接到评测机

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

正在编译...
编译成功

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

运行完成
运行时间 0.564 s
平均内存使用 41681 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
已完成数据库校验。

[模擬]NOIP2011_Day1 鋪地毯 carpet 解題報告

題目連結：
Google Docs

【分析】
本題作為NOIP2011提高組Day1的第一題，水的不能再水了。剛一看上去，感覺很難，再一看，水爆了！直接從N號毯到1號毯 依次判斷每個毯的坐標，只要找到了就輸出並break，沒找到就輸出-1～

【我的代碼】
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class CARPET
{
public:
    int x1,y1;
    int x2,y2;
}C[10001];

int N;
int X,Y;
void init()
{
    scanf("%d\n",&N);
    int x,y;
    for (int i=1;i<=N;i++)
    {
        scanf("%d %d %d %d\n",&C[i].x1,&C[i].y1,&x,&y);
        C[i].x2=C[i].x1+x;
        C[i].y2=C[i].y1+y;
    }
    scanf("%d %d\n",&X,&Y);
    return;
}

void work()
{
    for (int i=N;i>=1;i--)
    {
        if(C[i].x1<=X && C[i].x2>=X && C[i].y1<=Y && C[i].y2>=Y)
        {
            printf("%d\n",i);
            return;
        }
    }
    printf("-1\n");
}

int main()
{
    freopen("carpet.in","r",stdin);
    freopen("carpet.out","w",stdout);
    init();
    work();
    return 0;
}

[基本練習][枚舉]OI練習題： 排序工作量 sortt

【問題描述】

Sort公司是一個專門爲人們提供排序服務的公司，該公司的宗旨是：“順序是最美麗的”。他們的工作是通過一系列移動，將某些物品按順序擺好。他們的服務是通過工作量來計算的，即移動東西的次數。所以，在工作前必須先考察工作量，以便向用戶提出收費數目。

用戶並不需要知道精確的移動次數，實質上，大多數人都是憑感覺來認定這一列物品的混亂程度，根據Sort公司的經驗，人們一般是根據“逆序對”的數目多少來稱呼這一序列的混亂程度。假設我們將序列中第I件物品的參數定義爲A[I]，那麼，排序就是指將A數組從小到大排序。所謂“逆序對”是指目前A[1..N]中元素各不相同，若I<J且A[I]>A[j]，則[I,J]就爲一個“逆序對”。

例如，數組<3,1,4,5,2>的“逆序對”有<3,1>,<3,2>,<4,2>,<5,2>，共4個(如圖所示)。

  請你爲 Sort 公司做一個程序，在儘量短的時間內，統計出“逆序對”的數目。 

【輸入格式】

文件的第一行爲一個整數N（1<=N<=10000）。

文件的第二行爲N個實數。

【輸出格式】

文件共一行，爲“逆序對”的數目。

【輸入輸出樣例】

輸入：

sortt.in

5

3 1 4 5 2

輸入：

sortt.out

4

【分析】

直接枚舉即可。時間複雜度 O（n^2），不會超時。

【代碼】

#include <cstdio>
using namespace std;
double M[10001];
int N;
int T;

int main()
{
    freopen("sortt.in","r",stdin);
    freopen("sortt.out","w",stdout);
    scanf("%d",&N);
    for (int i=1;i<=N;i++)
        scanf("%lf",&M[i]);
    for (int i=1;i<=N-1;i++)
        for (int j=i+1;j<=N;j++)
            if(M[i]>M[j])
                T++;
    printf("%d\n",T);
    return 0;
}

NOIP2001 提高組 一元三次方程求解 3cfc 解題報告

問題描述

有形如：ax3+bx2+cx+d=0 這樣的一個一元三次方程。給出該方程中各項的係數(a，b，c，d 均爲實數)，並約定該方程存在三個不同實根(根的範圍在-100至100之間)，且根與根之差的絕對值>=1。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，並精確到小數點後2位。

提示：記方程f(x)=0，若存在2個數x1和x2，且x1<x2，f(x1)*f(x2)<0，則在(x1，x2)之間一定有一個 根。

樣例

輸入：1 -5 -4 20

輸出：-2.00 2.00 5.00

【分析】

由於精度不大，直接枚舉即可。

以下代碼參考了BYVoid（http://www.byvoid.com）的代碼~他的代碼比我的簡練多了~

【代碼】

01 //NOIP2001 一元三次方程求解
02 #include <cstdio>
03 #include <iostream>
04 using namespace std;
05 int main()
06 {
07     double a,b,c,d,x,v;
08     int X;
09     freopen("3cfc.in","r",stdin);
10     freopen("3cfc.out","w",stdout);
11     cin>>a>>b>>c>>d;
12     for (X=-10000;X<=10000;x=(++X)/100.0)
13     {
14         v=a*x*x*x+b*x*x+c*x+d;
15         if (v>=-0.01 && v<=0.01)   
16             printf("%.2lf ",x);   
17     }
18     return 0;
19 }

正在连接评测机...

已连接到评测机

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

正在编译...
编译成功

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

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

NOIP2008提高組 火柴棒等式 matches 解題報告

【問題描述】

給你n根火柴棍，你可以拼出多少個形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整數（若該數非零，則最高位不能是0）。用火柴棍拼數字0-9的拼法如圖所示：

注意：

1. 加號與等號各自需要兩根火柴棍

2. 如果A≠B，則A+B=C與B+A=C視爲不同的等式（A、B、C>=0）

3. n根火柴棍必須全部用上

【輸入】

輸入文件matches.in共一行，又一個整數n（n<=24）。

【輸出】

輸出文件matches.out共一行，表示能拼成的不同等式的數目。

【輸入輸出樣例1】

matches.in	matches.out
14	2

【輸入輸出樣例1解釋】

2個等式爲0+1=1和1+0=1。

 【輸入輸出樣例2】

matches.in	matches.out
18	9

 【輸入輸出樣例2解釋】

9個等式爲：

0+4=4

0+11=11

1+10=11

2+2=4

2+7=9

4+0=4

7+2=9

10+1=11

11+0=11

【分析】

NOIP2008的第二道模擬題，直接窮舉所有情況即可。

和與加數中較大的一個數位數相同或者大一。理想情況下11111和11111，可是另一個加數爲0也有6個火柴棒的花費，4個“1”的情況也不可能，所以和枚舉到“1111”就可以了。（事實證明也是如此的，因爲1比其他字母少用很多火柴），時間效率已經完全可以承受了。

具體操作時，先枚舉和，在枚舉其中一個加數，另一個加數可以用和減去枚舉的加數得到。

 可以先初始化一個數組，表示拼成1-9每個數字所用的火柴棒個數。

PS.由於N<=24，本題完全可以打表

【我的代碼】

//NOIP2008 火柴棒等式
#include <fstream>
using namespace std;
int M[10]={6,2,5,5,4,5,6,3,7,6};
int Mat[2500];
ifstream fin("matches.in");
ofstream fout("matches.out");
int Cat;
int total=0;
void init()
{
    fin>>Cat;
    fin.close();
    int bai,shi,ge,qian;
    for (int i=0;i<=2225;i++)
    {
        if (i<10)
        {
            Mat[i]=M[i];
            continue;
        }
        if (i>=10&&i<100)
        {
            Mat[i]=M[i/10]+M[i%10];
            continue;
        }
        if (i>=100&&i<=999)
        {  
            bai=i/100;
            shi=(i-bai*100)/10;
            ge=i-bai*100-shi*10;
            Mat[i]=M[bai]+M[shi]+M[ge];
            continue;
        }
        if(i>=1000)
        {
            qian=i/1000;
            bai=(i-qian*1000)/100;
            shi=(i-qian*1000-bai*100)/10;
            ge=i-qian*1000-bai*100-shi*10;
            Mat[i]=M[qian]+M[bai]+M[shi]+M[ge];
            continue;
        }
    }
  
    for (int i=0;i<=1111;i++)
    {
        for (int j=0;j<=1111;j++)
        {
            if (Mat[i]+Mat[j]+Mat[i+j]+4==Cat) total++;
        }
    }
    return;
}

int main()
{
    init();
    fout<<total;
    fout.close();
    return 0;
}