Joseph UVA 1452 Jump-白红宇

Joseph UVA 1452 Jump

阅读量：7250 次

发布时间：2019-06-29

本文共 1607 字，大约阅读时间需要 5 分钟。

1 /* 2     数学：的变形，首先定义f[i]表示剩下i个人时，最后一个选出的人，有个公式：f[i] = (f[i-1] + m) % i 3         f[1] = 0(编号从0开始)，那么类似最后一个数的求法，先找到剩2个人和剩3个人时，最后的编号，然后跟着最后一个的一起递推 4 */ 5 /************************************************ 6 * Author        :Running_Time 7 * Created Time  :2015-8-8 14:26:38 8 * File Name     :UVA_1459.cpp 9  ************************************************/10 11 #include 
     
      12 #include 
      
       13 #include 
       
        14 #include 
        
         15 #include 
         
          16 #include 
          
           17 #include 
           
            18 #include 
            
             19 #include 
             
              20 #include 
              
               21 #include 
               
                22 #include 
                
                 23 #include 
                 24 #include 
                  
                   25 #include 
                   
                    26 #include 
                    
                     27 #include 
                     
                      28 using namespace std;29 30 #define lson l, mid, rt << 131 #define rson mid + 1, r, rt << 1 | 132 typedef long long ll;33 const int MAXN = 5e5 + 10;34 const int INF = 0x3f3f3f3f;35 const int MOD = 1e9 + 7;36 37 void Joseph(int n, int m) {38 int ans1 = 0, ans2 = 0, ans3 = 0;39 for (int i=2; i<=n; ++i) {40 ans1 = (ans1 + m) % i;41 if (i == 2) { //2个人就是0或142 ans2 = !ans1;43 }44 else if (i == 3) {45 ans2 = (ans2 + m) % i;46 bool vis[3]; memset (vis, false, sizeof (vis)); 47 vis[ans1] = vis[ans2] = true;48 for (int i=0; i<3; ++i) {49 if (!vis[i]) {50 ans3 = i; break;51 }52 }53 }54 else {55 ans2 = (ans2 + m) % i;56 ans3 = (ans3 + m) % i;57 }58 }59 60 printf ("%d %d %d\n", ans3 + 1, ans2 + 1, ans1 + 1);61 }62 63 int main(void) { //UVA 1452 Jump64 int T; scanf ("%d", &T);65 while (T--) {66 int n, m; scanf ("%d%d", &n, &m);67 Joseph (n, m);68 }69 70 return 0;71 }