ACM/ICPC 小球鐘——時間與運動

問題描述

時間是運動的一種方式，所以常常用運動來度量時間。如圖所示的小球鍾就是一個通過不斷在軌道上移動小球來度量時間的簡單設備。

每分鐘，一個轉動臂將一個小球從小球隊列的底部擠走，將它上升到鐘的頂部並安置在一個表示分鐘， 5 分鐘和小時的軌道上。這裡可以顯示從 1:00 到 12:59 範圍內的時間，但無法表示 “a.m.” 和 “p.m.” 。若有 2 個球在分鐘軌道， 6 個球在 5 分鐘軌道及 5 個球在小時軌道上，就顯示時間 5:32 。

不幸的是，大多數市場上提供的小球鍾無法顯示日期，儘管只需要簡單地加上一些軌道就可以了。當小球通過鐘的機械裝置被移動後，它們就會改變其初始次序。仔細研究它們隨著時間的流逝發生的次序的改變，可以發現相同的次序會不斷出現。由於小球的初始次序最後遲早會被重複，所以這段時間的長短是可以被度量的，這完全取決於所提供小球的總數。

每分鐘，最近最少使用的那個小球從位於球鍾底部的小球隊列被移走，並將上升安置於顯示分鐘的軌道上，這裡可以放置 4 個小球。當第 5 個小球滾入該軌道，它們的重量使得軌道傾斜，原先在軌道上的 4 個小球按照與它們原先滾入軌道相反加入到鍾底部的小球隊列。引起傾斜的第 5 個小球滾入顯示 5 分鐘的軌道，該軌道可以放置 11 個球。當第 12 個小球滾入該軌道，它們的重量使得軌道傾斜，原先 11 個小球同樣以相反的次序加入鍾底部的小球隊列。而這第 12 個小球滾入了顯示小時的軌道。該軌道同樣可以放置 11 個球，但這裡有一個外加的固定不能被移動的小球，這樣小時的值域就變為 1 到 12 。從 5 分鐘軌道滾入的第 12 個小球將使小時軌道傾斜，這 11 個球同樣以相反的次序加入鍾底部的小球隊列，然後第 12 個小球同樣加入鍾底部的小球隊列。

輸入小球的個數，輸出該時鐘在經過多少天的運行可以回到它的初始小球序列。例如有 45 個小球的鐘經過 378 天會回到初始狀態。

[數據結構][隊列]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;
}

字典樹（Trie Tree）的應用舉例

字典樹是一種很牛的字符串操作算法，可以在短時間內完成字符串的插入、刪除、查找等功能，是NOIP、NOI必備資料之一。

關於字典樹的具體算法可以到維基百科 上學習，這裡我僅僅通過舉例來說明如何運用字典樹。


例題：

题目名	scanword
输入文件名	scanword.in
输出文件名	scanword.out
时间限制	1000 ms
内存限制	128 MB

全国英语四级考试就这样如期来了，可是小 y 依然没有做好充分准备。为了能够大学毕业可怜的小 y 决定作弊。
小 y 费尽心机，在考试的时候夹带了一本字典进考场，但是现在的问题是，考试的时候可能有很多的单词要查，小 y 能不能来得及呢？
输入格式：
第一行一个整数 N ，表示字典中一共有多少个单词（ N<=10000 ）。
接下来每两行表示一个单词，其中：
第一行是一个长度 <=100 的字符串，表示这个单词，全部小写字母，单词不会重复。
第二行是一个整数，表示这个单词在字典中的页码。
接下来是一个整数 M ，表示要查的单词数 (M<=10000) 。
接下来 M 行，每行一个字符串，表示要查的单词，保证在字典中存在。
输出格式：
M 行，每行一个整数，表示第 I 个单词在字典中的页数。
输入样例：
2
scan
10
word
15
2
scan
word
输出样例
10
15

這是一道基礎的字典樹的應用題，以下是我的代碼，十分簡單易懂，適合參加各種OI的選手。

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

const int sonnum=26;
const char base='a';
class Trie
{
public:
    bool isStr;
    int Page;
    class Trie *son[sonnum];
};

Trie *NewTrie()
{
    Trie *temp=new Trie;
    temp->isStr=false;
    for (int i=0;i<sonnum;i++)
        temp->son[i]=NULL;
    return temp;
}

void InsertStr(Trie *pnt,char *s,unsigned int len,int P)
{
    Trie *temp=pnt;
    for (unsigned int i=0;i<len;i++)
    {
        if (temp->son[s[i]-base]==NULL)
            temp->son[s[i]-base]=NewTrie();
        temp=temp->son[s[i]-base];
    }
    temp->isStr=true;
    temp->Page=P;
}

int GetPage(Trie *pnt,char *s,unsigned int len)
{
    Trie *temp=pnt;
    for (unsigned int i=0;i<len;i++)
        temp=temp->son[s[i]-base];
    return temp->Page;
}

Trie *pnt=NewTrie();

void init()
{
    int N;
    cin>>N;
    for (int i=1;i<=N;i++)
    {
        char STR[101];
        int p;
        cin>>STR>>p;
        InsertStr(pnt,STR,strlen(STR),p);
    }
    cin>>N;
    for (int i=1;i<=N;i++)
    {
        char STR[101];
        cin>>STR;
        cout<<GetPage(pnt,STR,strlen(STR))<<endl;
    }
}

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