NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組決賽
 npsc2004國決 D 獎落誰家

作者 主題: npsc2004國決 D 獎落誰家  (閱讀 427 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
npsc2004國決 D 獎落誰家
« 於: 五月 13, 2015, 12:24:54 am »

我的方法是使用鍵結方式,不曉得有沒有其他的公式?
代碼: [選擇]
// npsc04-j2d (2004國中決 題目 D 獎落誰家)
// 用 link list , struct {左、右} a[maxn];
// 第1列 c 代表 c 組,每組兩個數字 n , k :n個人、每次數 k 下,數到的出局
// cnt每數1回剩下的人,一開始 cnt = n ; x 目前由誰開始數,為方便計算 x=0~n-1
// s 每一回要數的 k下,但k>=cnt 取mod以免重複數,每一回不超過 cnt 而且 mod 後更少
// 找到每一回要刪的 x 以鍵結方式模擬 牽手

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const int maxn = 10010;
struct node
{
int lt,rt;
} a[maxn];
int main()
{
  int c,n , i,j,x,s;
  unsigned k;
cin >> c;
while(c--) // c組,每組2個數字 n , k
{
cin >> n >> k;
for(i=0;i<n;++i)
{
a[i].lt = (i+1)%n;
a[i].rt = (i-1+n)%n;
}
int cnt=n;
int lt,rt;
x=0;
while(cnt>1)
{
s=(k+cnt-1)%cnt;
while(s--) // 數 s 步
{
x=a[x].lt;
}
// x 是要刪的點,將 x 的左右牽手
lt=a[x].lt; rt=a[x].rt;
a[lt].rt = rt;
x = a[rt].lt = lt;
--cnt;
}
cout << x+1 << endl;
}
  return 0;
}
/*
輸入範例:
6
5 3
8 4
7 99
100 9999
1000 34567
10000 2147483647
輸出範例:
4
6
3
94
207
6735
*/

記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組決賽
 npsc2004國決 D 獎落誰家