当前位置:网站首页>[2018 Blue Bridge Cup final] d-joseph ring

[2018 Blue Bridge Cup final] d-joseph ring

2020-11-10 17:23:40 Fool_one

Answer key

   Look at the data range first ,n, k <= 1e6, If you use a queue to solve problems , Time complexity can reach $O(n * k)$ It's bound to be overtime .

        obviously , This problem should be solved mathematically , You can use $O(n)$ To solve the time complexity of , How to solve it ?

        Let's first look at the schematic diagram :

  

   It's actually a recursive relationship ,f[i] Express i personal , from 1 Start counting , The number of the last loser , When the number is k The person whose number is k - 1 When you're out of the team , There's only one left i - 1 personal , and f[i - 1] Express i - 1 personal ,k from 1 Start counting , Finally, the number of the person left , Obviously from 1 The one who started counting , The number is not 0 , And become k, But in the recursion time needs to record the original number, needs to add k, Then the mathematical recurrence formula is :

      f[i] = (f[i - 1] + k) % n.

#include <iostream>
using namespace std;

int n, m, ans = 0;

//  Mathematical methods  
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        ans = (ans + m) % i;
    }
    cout << ans + 1 << endl;    
    return 0;
}

 

版权声明
本文为[Fool_one]所创,转载请带上原文链接,感谢