[數據結構][隊列]USACO Dec07 Bronze Card Stacking 洗牌作弊 cheat

題目描述

譯 by CmYkRgB123

貝茜正在和她的N-1個奶牛朋友們玩撲克牌，她們用了一疊有K (N ≤ K ≤ 100,000 K是N的整倍數) 張牌的撲克。這疊撲克有 M = K/N 張“好牌”和 K-M 張“壞牌”。貝茜負責給大家發牌，當然，她想把所有的好牌發給自己。她非常喜歡贏。

她們坐成一圈，逆時針方向發牌。她的朋友們懷疑她會搞鬼，於是發明瞭一個特殊的發牌規則，試圖阻止貝茜搞鬼。她們把規則列舉如下：

從貝茜的右面的奶牛開始發牌。

每發一張牌，貝茜必須把接下來的 P (1 ≤ P ≤ 10) 張牌按原順序放到這疊撲克的最後。

逆時針方向發牌，對每個人都這樣。

然而，貝茜發了瘋，不顧一切的想贏。她請你幫她設計洗牌一個方案，使她能得到所有的“好牌”。每張牌按順序標號，第一張爲#1，第二張爲#2，等等。

輸入

第 1 行: 三個整數 N , K , P

輸出

第 1..M 行: 升冪順序排列，每行爲一張好牌的位置，使得貝茜她能得到所有的“好牌”。

樣例輸入

3 9 2

樣例輸出

3

7

8

【分析】

這是一個比較簡單的隊列題，隊列不用開的很大，11,000,000就行了。

設置兩個指針，一個隊頭、一個隊尾，每次發完牌後，隊頭指針和隊尾指針都向後移動P位。發牌時，判斷這張牌是不是Bessie的（如果A%N==0，則第A張發下去的牌是Bessie的），最後把Bessie的牌按從大到小的順序快排一下，輸出即可。

這種算法的效率很高，看看我的評測結果：

正在连接评测机...

已连接到评测机

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

正在编译...

编译成功

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

运行完成

运行时间 0.223 s

平均内存使用 47149 KB

测试点通过状况 AAAAAAAAAAA

得分：100

恭喜你通过了全部测试点!

本題測試數據下載：http://ace.delos.com/TESTDATA/cheat.zip

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int Bessie[1000001];
int B=0;

int Q[11000001];
int N,P,K;
int G=0;
int q,h;

void init()
{
    scanf("%d %d %d",&N,&K,&P);
    for (int i=1;i<=K;i++)
        Q[i]=i;
    G=K/N;
}

void Put(int i)
{
    for (int j=i+1;j<=P+i;j++)
    {
        q++;
        Q[q]=Q[j];
        h++;
    }
}

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

void Work()
{
    q=K;
    h=0;
    int tmp=0;
    while(B<G && h<=q)
    {
        h++;
        tmp++;
        if(tmp%N==0)
        {
            B++;
            Bessie[B]=Q[h];
        }
        Put(h);
    }
   
    qsort(Bessie+1,B,sizeof(int),cmp);
    for (int i=1;i<=B;i++)
        cout<<Bessie[i]<<endl;
}

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

[基本練習]USACO Jan08 奶牛的選舉 elect

題目描述
在推翻了Farmer John這個殘暴的統治者後，奶牛們舉行了她們的第一次總統大選，貝茜也是N(1 <= N <= 50,000)頭候選奶牛之一。不過，作爲一頭有遠見的奶牛，貝茜想在選舉開始前就計算出，哪頭奶牛最有可能在競爭中勝出。

選舉分兩輪進行。第一輪中，得票最多的K(1 <= K <= N)頭奶牛晉級到下一輪，在第二輪選舉中得票最多的奶牛成爲最終的總統。

現在，貝茜告訴了你奶牛i在第一輪投票中的期望得票數A_i(1 <= A_i <= 1,000,000,000)以及她在第二輪投票中的期望得票數B_i(1 <= B_i <= 1,000,000,000)（如果奶牛i能成功晉級的話），她希望你幫她計算一下，如果這些數據無誤，那麼哪頭奶牛將成爲總統。任何數值都不會在A_i 列表中出現兩次，在B_i列表中也是如此。

程序名: elect

輸入格式:

第1行: 2個用空格隔開的整數：N 和 K

第2..N+1行: 第i+1爲2個用空格隔開的整數：A_i 和 B_i

輸入樣例 (elect.in):

5 3

3 10

9 2

5 6

8 4

6 5

輸入說明:

一共有5頭奶牛參加選舉，在第一輪中得票最多的3頭奶牛可以晉級至第二輪。奶牛們在第一輪中的得票期望分別爲3，9，5，8，6，第二輪中，分別爲10，2，6，4，5。

輸出格式:

第1行: 輸出1個整數，爲將被選爲總統的奶牛的編號

輸出樣例 (elect.out):

5

輸出說明:

奶牛2，4，5晉級到第二輪。奶牛5在第二輪投票中得到了最多的5票，贏得了選舉的最終勝利。

【分析】

通過分析發現，這就是一個簡單的排序問題，通過兩次快速排序即可解決問題。

可以用一個結構來儲存某一奶牛的編號、第一輪得票數、第二輪得票數，先對第一輪得票數調用快速排序函數，再對第二輪得票數調用快速排序函數，最後輸出排在數組第一位的奶牛的編號即可。

【代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef unsigned int usint;

class COW
{
public:
    usint Fir;
    usint Sec;
    usint num;
}C[50001];

int N,K;

int cmp(const void *a,const void *b)
{
    class COW *c=(class COW *)a;
    class COW *d=(class COW *)b;
    return d->Fir-c->Fir;
}

int Cmp(const void *a,const void *b)
{
    class COW *c=(class COW *)a;
    class COW *d=(class COW *)b;
    return d->Sec-c->Sec;
}

void init()
{
    scanf("%d %d\n",&N,&K);
    for (int i=1;i<=N;i++)
    {
        C[i].num=i;
        scanf("%d %d\n",&C[i].Fir,&C[i].Sec);
    }
    qsort(C+1,N,sizeof(C[0]),cmp);
    qsort(C+1,K,sizeof(C[0]),Cmp);
    return;
}

void print()
{
    for (int i=1;i<=N;i++)
        printf("%d %d %d\n",C[i].num,C[i].Fir,C[i].Sec);
}

int main()
{
    freopen("elect.in","r",stdin);
    freopen("elect.out","w",stdout);
    init();
    //print();
    cout<<C[1].num<<endl;
    return 0;
}

[廣度優先搜索]USACO Feb07 Bronze 青銅蓮花池 Bronze Lilypad (bronlily) 解題報告

譯 By CmYkRgB123

【題目描述】

Farmer John 建造了一個美麗的池塘，用於讓他的牛們審美和鍛鍊。這個長方形的池子被分割成了 M 行和 N 列( 1 ≤ M ≤ 30 ; 1 ≤ N ≤ 30 ) 正方形格子的 。某些格子上有驚人的堅固的蓮花，還有一些岩石，其餘的只是美麗，純淨，湛藍的水。

貝茜正在練習芭蕾舞，她從一個蓮花跳躍到另一個蓮花，當前位於一個蓮花。她希望在蓮花上一個一個的跳，目標是另一個給定蓮花。她能跳既不入水，也不到一個岩石上。

令門外漢驚訝的是，貝茜的每次的跳躍像國際象棋中的騎士一樣：橫向移動M1(1 ≤M1 ≤ 30 )，縱向移動然後量M2 (1 ≤M2 ≤ 30 ;M1 ≠ M2 ) ，或縱向移動然後量M1，橫向移動M2。貝茜有時可能會有多達8個選擇的跳躍。

給定池塘的佈局和貝茜的跳躍格式，請確定貝茜從從她的出發位置，到最終目的地，最小的跳躍次數，貝茜在給出測試數據一定可以跳到目的地。

輸入

第 1 行: 四個用空格隔開的整數: M, N, M1, M2

第 2..M + 1 行: 第 i + 1 行 有 N 個整數，表示該位置的狀態: 0 爲水; 1 爲蓮花; 2 爲岩石; 3 爲貝茜開始的位置; 4 爲貝茜要去的目標位置.

輸出

第 1 行: 一個整數，從起始點到要去的位置，貝茜最小的跳躍次數。

樣例輸入

4 5 1 2

1 0 1 0 1

3 0 2 0 4

0 1 2 0 0

0 0 0 1 0

樣例輸出

2

輸入解釋

貝茜從第2行第1個位置開始，她的目標在第2行最右邊。幾個

輸出解釋

貝茜聰明地跳躍到了第1行第3個位置，然後就到了目的地。

【分析】

這是跳馬問題的變形，但是這個題不能使用深度優先搜索，因為遞歸會爆棧的。我們可以開一個二維的布爾數組，當然整型數組亦可，由於題目中給的岩石和水的作用一樣，直接賦值為false或0，讀入時如果遇到3就記錄下起點的橫縱坐標，如果遇到4就記錄下終點的橫縱坐標，然後把所有的荷花置為true或1。然後處理8種移動方式，可參照2002年NOIP普及組的“過河卒”一題。

接著進行廣度優先搜索，把每一個到過的點全部賦值為false或0，以免重複。還可以加一個剪枝優化：如果當前的跳躍次數不小於已經得到的最優值，直接跳過這個點即可。這樣，就可以把時間複雜度壓得很低了。

 我的測評結果：

正在连接评测机...

已连接到评测机

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

正在编译...

编译成功

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

运行完成

运行时间 0.005 s

平均内存使用 58877 KB

测试点通过状况 AAAAAAAAAAAAA

得分：100

恭喜你通过了全部测试点!

【代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class BRON
{
public:
    int x;
    int y;
    int t;
};

int mat[50][50];
int step[9][2];
int S=0x7fffffff;
int M,N,M1,M2;
int Sx,Sy;
int Ex,Ey;
bool flag[31][31];


void init()
{
    scanf("%d %d %d %d",&M,&N,&M1,&M2);
   
    for (int i=1;i<=M;i++)
        for (int j=1;j<=N;j++)
            flag[i][j]=true;
   
    int tmp;
    for (int i=1;i<=M;i++)
    {
        for (int j=1;j<=N;j++)
        {
            scanf("%d",&tmp);
            if(tmp==0 || tmp==2)
                mat[i][j]=0;
            else
                mat[i][j]=tmp;
            if(mat[i][j]==3)
            {
                Sx=i;
                Sy=j;
                continue;
            }
            if(mat[i][j]==4)
            {
                Ex=i;
                Ey=j;
                continue;
            }
        }
    }
    step[1][0]=M1,step[1][1]=M2;
    step[2][0]=M1,step[2][1]=-M2;
    step[3][0]=-M1,step[3][1]=M2;
    step[4][0]=-M1,step[4][1]=-M2;
    step[5][0]=M2,step[5][1]=M1;
    step[6][0]=M2,step[6][1]=-M1;
    step[7][0]=-M2,step[7][1]=M1;
    step[8][0]=-M2,step[8][1]=-M1;
    return;
}

BRON Q[5000000];
void bfs()
{
    int q=1;
    int h=0;
    Q[0].x=Sx,Q[0].y=Sy,Q[0].t=0;
    int Tx,Ty,Tt;
    int Nx,Ny;
    while(h<q)
    {
        Tx=Q[h].x,Ty=Q[h].y,Tt=Q[h].t;
       
        if(Tx==Ex && Ty==Ey)
        {
            if(Tt<S)
                S=Tt;
            h++;
            continue;
        }
       
        if(Tt>=S)
        {
            h++;
            continue;
        }
       
        if(!flag[Tx][Ty])
        {
            h++;
            continue;
        }
       
        flag[Tx][Ty]=false;
       
        for (int i=1;i<=8;i++)
        {
            Nx=step[i][0]+Tx;
            Ny=step[i][1]+Ty;
            if(Nx>=1 && Nx<=M && Ny>=1 && Ny<=N && flag[Nx][Ny])
            {
                if(mat[Nx][Ny]!=0)
                {
                    Q[q].x=Nx;
                    Q[q].y=Ny;
                    Q[q].t=Tt+1;
                    q++;
                }
            }
        }
        h++;
    }
    cout<<S<<endl;
}

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

[貪心策略]NOIP2009模擬題：貨物搬運 move

天地無情人有情，一方有難八方支援！目前災區最緊缺的就是救災帳篷，全國各地支援的帳篷正緊急向災區運送。假設圍繞汶川縣有環行排列的 n 個救災帳篷的存儲點，每個存儲點存有帳篷數量分別是 M1 ， M2 ，…， Mn ，且 S=M1+M2+ … +Mn 必爲 n 的倍數。可以在任意一個存儲點中任取任意數量的帳篷搬運到相鄰的存儲點。

現在需要找到一種搬運方法，搬運最少的帳篷使得每個存儲點中的帳篷數目相同。

例如： n=5 ，每個存儲點帳篷的數量分別爲 17 ， 9 ， 14 ， 16 ， 4 。我們進行如下搬運：

（1） 存儲點①向存儲點②搬運 1 個帳篷；

（2） 存儲點①向存儲點⑤搬運 4 個帳篷；

（3） 存儲點③向存儲點②搬運 2 個帳篷；

（4） 存儲點④向存儲點⑤搬運 4 個帳篷。

搬運帳篷的總數量是 1+4+2+4=11 ，並且可以證明這樣的搬運方法是最佳搬運方法。

【 輸入文件 】

第一 行一個整數 n （ n ≤ 10000 ），表示有 n

儲存點；第二行 n 個整數（ integer 範圍）

表示 n 個存儲點中帳篷數量。

【 輸出文件 】

一個整數，表示最少搬運的帳篷數量。

【 樣例輸入 】

5

17 9 14 16 4

【 樣例輸出 】

11

 【分析】

大家都做過NOIP2002第二題——均分紙牌吧。這個題就是“均分紙牌”的變形，因為這是個環，可以參照USACO 1.1中的Broken Necklace這個題，把原數組複製一遍，然後每次從中取出長度為N的數組，進行一次“均分紙牌”。詳細請看網上均分紙牌的解題報告。一共N次，找出這N次中的最小移動次數，輸出這個數即可。

注意：C++中要用long long數據類型。

【我的代碼】

#include <iostream>
#include <cstdio>
using namespace std;

int absint(int a)
{
    if(a<0)
        return -a;
    else
        return a;
}

long long N,avg,ans;


int main()
{
    long long S[20001];
    long long T[20001];
    int i;
    freopen("move.in","r",stdin);
    freopen("move.out","w",stdout);
    cin>>N;
   
    for (i=1;i<=N;i++)
    {
        cin >> S[i];
        avg+=S[i];
    }
    avg/=N;
   
    for (int i=1;i<=N;i++)
    {
        S[i+N]=S[i];
    }       
    long long Max=0x7fffffff;
    long long tmp;
    for (int j=1;j<=N;j++)
    {
        ans=0;
        for (int i=j;i<=N+j;i++)
        {
            T[i-j+1]=S[i];
        }
       
        for (int i=1;i<=N;i++)
        {
            if (T[i]!=avg)
            {
                tmp=T[i]-avg;
                T[i+1]+=tmp;
                T[i]=avg;
                ans+=absint(tmp);
            }
        }
        if(ans<Max)
            Max=ans;
    }
    cout<<Max<<endl;
    return 0;
}

USACO Nov09 Silver : The Grand Farm-off 盛大的Farmoff 解題報告

【英文原題】
Problem 7: The Grand Farm-off [Haitao Mao, 2009]

Farmer John owns 3*N (1 <= N <= 500,000) cows surprisingly numbered
0..3*N-1, each of which has some associated integer weight W_i (1 <=
W_i <= d). He is entering the Grand Farm-off, a farming competition
where he shows off his cows to the greater agricultural community.

This competition allows him to enter a group of N cows. He has given
each of his cows a utility rating U_i (1 <= U_i <= h), which
represents the usefulness he thinks that a particular cow will have
in the competition, and he wants his selection of cows to have the
maximal sum of utility.

There might be multiple sets of N cows that attain the maximum
utility sum. FJ is afraid the competition may impose a total weight
limit on the cows in the competition, so a secondary priority is
to bring lighter weight competition cows.

Help FJ find a set of N cows with minimum possible total weight
among the sets of N cows that maximize the utility, and print the
remainder when this total weight is divided by M (10,000,000 <= M
<= 1,000,000,000).

Note: to make the input phase faster, FJ has derived polynomials
which will generate the weights and utility values for each cow.
For each cow 0 <= i < 3*N,

       W_i = (a*i^5+b*i^2+c) mod d
 and   U_i = (e*i^5+f*i^3+g) mod h

with reasonable ranges for the coefficients (0 <= a <= 1,000,000,000;
0 <= b <= 1,000,000,000; 0 <= c <= 1,000,000,000; 0 <= e <=
1,000,000,000; 0 <= f <= 1,000,000,000; 0 <= g <= 1,000,000,000;
10,000,000 <= d <= 1,000,000,000; 10,000,000 <= h <= 1,000,000,000).

The formulae do sometimes generate duplicate numbers; your algorithm
should handle this properly.

PROBLEM NAME: farmoff

INPUT FORMAT:

* Line 1: Ten space-separated integers: N, a, b, c, d, e, f, g, h, and
        M

SAMPLE INPUT (file farmoff.in):

2 0 1 5 55555555 0 1 0 55555555 55555555

INPUT DETAILS:

The functions generate weights of 5, 6, 9, 14, 21, and 30 along
with utilities of 0, 1, 8, 27, 64, and 125.

OUTPUT FORMAT:

* Line 1: A single integer representing the lowest sum of the weights
        of the N cows with the highest net utility.

SAMPLE OUTPUT (file farmoff.out):

51

OUTPUT DETAILS:

The two cows with the highest utility are cow 5 and 6, and their combined
weight is 21+30=51.

【中文翻譯】
問題描述:

農夫約翰擁有 3*N(1 <= N <= 500,000)只牛，它們的編號爲0..3*N-1，每隻牛都有一個體重 W_i(1 <= W_i <= d)。約翰參加了一個叫做 Farm-off 的盛大競賽活動，在這個活動上他可以在整個農業界炫耀他的牛。

這個競賽約翰可以派出一隊共 N 頭牛參賽，他的每頭牛都有一個效率值 U_i (1 <= U_i <= h)，這個值用來描述他認爲在這個競賽中每頭牛的有用值。約翰想讓他選擇的一羣牛有一個最大的效率總值。

可能有很多種 N 頭牛的集合可以達到這個最大的效率總值。農夫約翰爲了防止競賽中的欺騙行爲，對牛的體重加以限制。所以第二個要考慮的因素便是參加競賽的牛的體重。

幫助約翰從所有以N頭牛組合而得的效率總值最大的集閤中，找到一個最小體重的組合。 並且打印出體重總值被M (10,000,000 <= M <= 1,000,000,000)整除後的餘數。

注意：爲了儘快地輸入，約翰找到一個能夠表示出每頭牛體重及效率值的多項式：

對於每頭牛 0 <= i < 3*N，

W_i = (a*i^5+b*i^2+c) mod d

U_i = (e*i^5+f*i^3+g) mod h 

合理的係數範圍：

0 <= a <= 1,000,000,000;

0 <= b <= 1,000,000,000;

0 <= c <= 1,000,000,000;

0 <= e <= 1,000,000,000;

0 <= f <= 1,000,000,000;

0 <= g <= 1,000,000,000;

10,000,000 <= d <= 1,000,000,000;

10,000,000 <= h <= 1,000,000,000.

公式有時會產生一些重複的數字，你的算法應該能夠適應這種情況。

PROBLEM NAME: farmoff

輸入格式：

第一行：用空格隔開的10個數字：N, a, b, c, d, e, f, g, h,M

輸入樣例：(file farmoff.in):

2 0 1 5 55555555 0 1 0 55555555 55555555

根據公式計算出來的 W_i 分別是：5, 6, 9, 14, 21,30；計算出來的U_i分別是：0, 1, 8, 27, 64,125

輸出格式：

第一行：一個單獨的整數用來描述：N頭牛的淨效率總值最大的條件下的最小體重總值。

輸出樣例（farmoff.out）：

51

兩隻牛的組閤中效率最大的是牛5和牛6，它們的體重總值爲：21+30=51

【分析】

本題並不是很難，因為沒有用到很難的算法。

因為數據很大，當然可以用高精度算法來實現。

但是高精度算法不僅代碼複雜度高，而且時間複雜度也不低。

所以，我們可以通過餘數定理來實現把大數據變小，變到long long的範圍（2^63-1）之內。

 =======================================

[餘數定理]

a：兩數的和除以m的餘數等於這兩個數分別除以m的餘數和。

實例：7÷3=…1，5÷3=…2，這樣（7+5）÷3的餘數就等於1+2=3，所以餘0。

b: 兩數的差除以m的餘數等於這兩個數分別除以m的餘數差。

實例：8÷3=…2，4÷3=…1，這樣（8-4）÷3的餘數就等於2-1=1，所以餘1。

如果是（7-5）÷3呢? 會出什麼問題？

c: 兩數的積除以m的餘數等於這兩個數分別除以m的餘數積。

實例：7÷3=…1，5÷3=…2，這樣（7×5）÷3的餘數就等於1×2=2，所以餘2。

attention:

對a，餘數和應再對m取次餘

對b，餘數差應加上m後再對m取次餘

 ========================================

然後 ，本題剩下的部分就是利用編程語言中的快速排序(qsort)，對結構體進行二級排序即可。

【我的代碼】

（在記憶體為512MB，CPU為1.6GHz的評測機上，10組測試數據共運行4.813秒。）

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
long long a,b,c,D,e,f,g,H;
long long M;
long long S=0;
long long tt;

class COW
{
public:
    long long W;
    long long U;
}C[1500001];

int cmp(const void *a,const void *b)
{
    class COW *c=(class COW *)a;
    class COW *d=(class COW *)b;
    if(c->U!=d->U)
        return d->U-c->U;
    return c->W-d->W;
}

long long pl(long long num,long long level,long long moder)
{
    long long temp=1;
    while (level)
    {
        temp=(temp*num)%moder;
        level--;
    }
    return(temp);
}

void init()
{
    cin>>N;
    cin>>a>>b>>c>>D>>e>>f>>g>>H;
    cin>>M;
    long long w,u;
    for (int i=0;i<3*N;i++)
    {
        w=((((a%D)*pl(i,5,D))%D+((b%D)*pl(i,2,D))%D)+c%D)%D;
        u=((((e%H)*pl(i,5,H))%H+((f%H)*pl(i,3,H))%H)+g%H)%H;
        C[i].W=w;
        C[i].U=u;
    }

    qsort(C,3*N,sizeof(C[0]),cmp);
  
    for (int i=0;i<N;i++)
    {
        S+=C[i].W;
        S%=M;
    }
    cout<<S<<endl;
}

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

[基本練習]OI練習題：燈 light

【題目描述】

在一條無限長的路上，有一排無限長的路燈，編號爲1，2，3，4，……。

每一盞燈只有兩種可能的狀態，開或者關。如果按一下某一盞燈的開關，那麼這盞燈的狀態將發生改變。如果原來是開，將變成關。如果原來是關，將變成開。

在剛開始的時候，所有的燈都是關的。

小明每次可以進行如下的操作：

指定兩個數，a，t（a爲實數，t爲正整數）。將編號爲[a]，[2*a]，[3*a]，……，[t*a]的燈的開關各按一次。其中[k]表示實數k的整數部分。

在小明進行了n次操作後，小明突然發現，這個時候只有一盞燈是開的，小明很想知道這盞燈的編號，可是這盞燈離小明太遠了，小明看不清編號是多少。

幸好，小明還記得之前的n次操作。於是小明找到了你，你能幫他計算出這盞開着的燈的編號嗎？

【輸入格式】

第一行一個正整數n，表示n次操作。

接下來有n行，每行兩個數，ai，ti。其中ai是實數，小數點後一定有6位，ti是正整數。

【輸出格式】

僅一個正整數，那盞開着的燈的編號。

【輸入樣例】

3

1.618034 13

2.618034 7

1.000000 21

【輸出樣例】

20

【數據規模】

記T=t1+t2+t3+……+tn。

對於30%的數據，滿足T<=1000

對於80%的數據，滿足T<=200000

對於100%的數據，滿足T<=2000000

對於100%的數據，滿足n<=5000，1<=ai<1000，1<=ti<=T

數據保證，在經過n次操作後，有且只有一盞燈是開的，不必判錯。

【分析】

這數據規模太坑人了！

其實測試數據中，燈的最大編號僅為20000000。

也就是說，開個20000001的布爾數組即可。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
bool flag[20000001]={false};
int Max=0;
int Min=0x7fffffff;
int N;

int QZ(int a,double b)
{
    double c=(double)(a);
    b=b*c;
    return (int)floor(b);
}

int main()
{
    freopen("light.in","r",stdin);
    freopen("light.out","w",stdout);
    cin>>N;
    int T;
    double B;
    int Tmp;
    for (int i=1;i<=N;i++)
    {
        cin>>B>>T;
        for (int j=1;j<=T;j++)
        {
            Tmp=QZ(j,B);
            if(Tmp<Min)
                Min=Tmp;
            if(Tmp>Max)
                Max=Tmp;
            flag[Tmp]=!flag[Tmp];
        }
    }
   
    for (int i=Min;i<=Max;i++)
    {
        if(flag[i])
        {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}
 

[基本練習]OI練習題：漂亮字串 bs

【问题描述】

小 x 认为 O 和 X 是最优美的两个字母，由 O 和 X 组成的串是最优美的串。在这些最优美的串中，如果任意只包含 X 的子串，长度不超过 maxX ，任意只包含 O 的子串，长度不超过 maxO ，且整个串最多有 countO 个 O ， countX 个 X 。那么这个就是超级优美无敌串。

现在 小 x 想知道最长的优美无敌串有多长，希望你告诉他。

【输入格式】

输入包含多行，每行一组数据，至文件结束为止；

每行四个数，依次是 countO 、 countX ， maxO ， maxX 。

【输出格式】

每组数据输出一行，一个数表示最长的超级优美无敌串的长度。

【输入样例】

10 10 0 0

3 5 1 1

【输出样例】

0

7

【数据规模】

0<= countO,countX,maxO,maxX<=1000000

最多 1000 组数据。

其中 30% 的数据 0<= countO,countX,maxO,maxX<=20 ，且数据组数不超过 20 组。

【注意事项】

第二个样例的解释：“ XOXOXOX ”

 

【分析】

如果countO或者maxO等於0，直接輸出Min{countX,maxX}。

如果countX或者maxX等於0，直接輸出Min{countO,maxX}。

如果countO等於countX，輸出countO+countX。

如果countO小於countX，輸出Min{maxX*(countO+1),countX}+countX。

如果countO大於countX，輸出Min{maxO*(countX+1),countO}+countX。

【代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
//#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
using namespace std;

int main()
{
    freopen("bs.in","r",stdin);
    freopen("bs.out","w",stdout);
    int tco,tcx,tmo,tmx;
    long long tmp;
    long long co,cx,mo,mx;
    while(scanf("%d %d %d %d\n",&tco,&tcx,&tmo,&tmx)==4)
    {
        co=tco;
        cx=tcx;
        mo=tmo;
        mx=tmx;
        if(co==0||mo==0)
        {
            tmp=Min(cx,mx);
            cout<<tmp<<endl;
            continue;
        }
        if(cx==0||mx==0)
        {
            tmp=Min(co,mo);
            cout<<tmp<<endl;
            continue;
        }
       
        if(co==cx)
        {
            cout<<co+cx<<endl;
            continue;
        }
        if(co<cx)
        {
            tmp=mx*(co+1);
            tmp=Min(tmp,cx);
            cout<<co+tmp<<endl;
            continue;
        }
        if(co>cx)
        {
            tmp=mo*(cx+1);
            tmp=Min(tmp,co);
            cout<<tmp+cx<<endl;
            continue;
        }
    }
    return 0;
}

[數學遞推]OI練習題：Binacy

【題目描述】

求所有可以只用1和00拼成的長度爲N的二進制數的個數除以1 5746的餘數。

比如當N=4的時候，有5個可能的二進制：0011，0000，1001，1100，1111。

【輸入格式】

第一行一個正整數N

【輸出格式】

輸出所有可以只用1和00拼成的長度爲N的二進制數的個數除以15746的餘數。

【輸入樣例】

4

【輸出樣例】

5

【數據範圍】

在100％的數據中，1≤N<1000000

【分析】

先嘗試寫出前幾個，找找規律：

N=0時 結果為0

N=1時 結果為1

N=2時 結果為2

N=3時 結果為3

N=4時 結果為5

......

可以看出，這是斐波那契數列。

所以，只需要遞推出斐波那契數列即可。

遞推式：

               S[0]=0,S[1]=1,

               S[2]=2;

               S[n]=S[n-2]+S[n-1] (n>2)

【代碼】

這是我以前的代碼，不知道我當時為何要把前幾個數打成表。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
unsigned long long S[1000001];
int main()
{
    freopen("binacy.in","r",stdin);
    freopen("binacy.out","w",stdout);
    int N;
    cin>>N;
    if(N<=4)
    {
        switch(N)
        {
        case 0:
            cout<<0<<endl;
            break;
        case 1:
            cout<<1<<endl;
            break;
        case 2:
            cout<<2<<endl;
            break;
        case 3:
            cout<<3<<endl;
            break;
        case 4:
            cout<<5<<endl;
            break;
        }
        return 0;
    }
    S[3]=3;
    S[4]=5;
    for (int i=5;i<=N;i++)
        S[i]=(S[i-1]+S[i-2])%15746;
    cout<<S[N]<<endl;
    return 0;
}

位運算中 x&(-x) 的意義

 位運算中 x&(-x) 的意義是：
             把x的二進制表示中，除了最右邊的一個“1”留下，其他全部變成0後的十進制表達。

例如： 10&(-10)=？
    10的二進制表示的後4位為：1010，
   -10的二進制表示的後4位為：0110；
由於10的二進制表示中除了後四位以外均為0，-10的二進制表示中除了後四位以外都是1，所以這些數取“與”運算的結果都是0，不予考慮。
所以：1010與0110取“與”運算的結果就是：
                   0010，即2。


應用：
11&(-11)=1    => 11(base 10)=1011(base 2)  => 0001 =>1
12&(-12)=4    => 12(base 10)=1100(base 2)  => 0100 =>4

位運算中 x&(x-1)表達式的意義

請看下面的函數：

int func(int x)
{
    int countx = 0;
    while(x)
    {
        countx++;
        x = x&(x-1);
    }
    return countx;
} 

假定x = 9999

則返回多少？

答案: 8
解析：9999的二進制的表示為10011100001111，看它的二進制表示中有幾個1。

其實這個函數的意義是統計X的二進制表示中1的個數。
 注: 每執行一次x = x&(x-1)，會將x用二進制表示時最右邊的一個1變爲0，因爲x-1將會將該位(x用二進制表示時最右邊的一個1)變爲0。

【應用】

判斷一個數(x)是否是2的n次方

-------------------------------------

#include <stdio.h>

int func(int x)
{
    if( (x&(x-1)) == 0 )
        return 1;
    else
        return 0;
}

int main()
{
    int x = 8;
    printf("%d\n", func(x));
}

注:

(1) 如果一個數是2的n次方，那麼這個數用二進制表示時其最高位爲1，其餘位爲0。

(2) == 優先級高於 &

[基本練習][枚舉]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;
}

NOIP2000提高組 進制轉換 jzzh 解題報告

描述 Description

我們可以用這樣的方式來表示一個十進制數：將每個阿拉伯數字乘以一個以該數字所處位置的（值減1）爲指數，以10爲底數的冪之和的形式。例如，123可表示爲1*10^2+2*10^1+3*10^0這樣的形式。

與之相似的，對二進制數來說，也可表示成每個二進制數碼乘以一個以該數字所處位置的（值-1）爲指數，以2爲底數的冪之和的形式。一般說來，任何一個正整 數R或一個負整數-R都可以被選來作爲一個數制系統的基數。如果是以R或-R爲基數，則需要用到的數碼爲0，1,....R-1。例如，當R=7時，所需 用到的數碼是0，1，2, 3，4，5和6，這與其是R或-R無關。如果作爲基數的數絕對值超過10，則爲了表示這些數碼，通常使用英文字母來表示那些大於9的數碼。例如對16進制 數來說，用A表示10，用B表示11，用C表示12，用D表示13，用E表示14，用F表示15。在負進制數中是用-R作爲基數，例如-15（＋進制）相 當於110001（-2進制），

並且它可以被表示爲2的冪級數的和數：

110001=1*(-2)^5+1*(-2)^4+0*(-2)^3+0*(-2)^2+0*(-2)^1+1*(-2)^0

問題求解:

設計一個程序，讀入一個十進制數的基數和一個負進制數的基數，並將此十進制數轉換爲此負進制下的數：-R∈{-2，-3，-4,....-20}

輸入格式 Input Format

輸入文件有若干行，每行有兩個輸入數據。

第一個是十進制數N（-32768<=N<=32767）; 第二個是負進制數的基數-R。

輸出格式 Output Format

輸出此負進制數及其基數，若此基數超過10，則參照16進制的方式處理。【具體請參考樣例】

樣例輸入 Sample Input

30000 -2

-20000 -7

28800 -16

-25000 -16

樣例輸出 Sample Output

30000=11011010101110000(base -2)

-20000=263526(base -7)

28800=19180(base -16)

-25000=7FB8(base -16)

【分析+代碼】
比較基礎的題，只要注意整除函數即可。

以下代碼是BYVoid(www.byvoid.com)大牛的，他的代碼真是精練！
#include <iostream>
#include <cstdio>
using namespace std;
int N,M,base;

inline int Div(int a,int b)
{
    int n;
    n=a/b;
    if (n*b<=a)
        return n;
    return n+1;
}

void work()
{
    int num[100];
    int top=0;
    if(N==0)
    {
        cout<<0;
    }
    int P;
    while (N)
    {
        P=Div(N,base);
        num[++top]=N-P*base;
        N=P;
    }
    for (;top>=1;top--)
    {
        if (num[top]<10)
            cout<<num[top];
        if (num[top]>=10)
            cout<<(char)(num[top]-10+'A');
    }
        cout<<"(base "<<base<<")"<<endl;
}

int main()
{
    freopen("fjz.in","r",stdin);
    freopen("fjz.out","w",stdout);
    while(cin>>N)
    {
        cin>>base;
        M=N;
        cout<<N<<"=";
        work();
    }
    return 0;
}


正在连接评测机...

已连接到评测机

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

正在编译...
编译成功

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

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

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
恭喜你通过了全部测试点!