玩游戏

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<bits/stdc++.h>
using namespace std;
int n,k;
int main()
{
    cin>>n>>k;
    queue<int> q;
    for(int i =1;i<=n;i++) q.push(i);
    while(k--){
        int a;
        cin>>a;
        a%=q.size();
        for(int i =1;i<=a;i++){
            q.push(q.front());
            q.pop();
        }
        
        cout<<q.front()<<" ";
        q.pop();
    }
    return 0;
}

招聘

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>

using namespace std;

const int N = 1010;
int a[N];

int main() {
    int t; cin >> t;
    while(t--) {
        int n, m; cin >> n >> m;
        for(int i = 1; i <= m; i++) cin >> a[i];
        int res = 0;
        for(int i = 1; i <= n; i++) {
            res = (res + a[1 + (n - i) % m]) % i;
        }
        cout << res << endl;
    }
    return 0;
}

总结

数据小用模拟、数据大用dp

简单复述约瑟夫环问题的解法：

  1. f[1] = 0;
  2. i > 1, f[i] = (f[i - 1] + m) % i;

这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的。 递推公式： f(N,M)=(f(N−1,M)+M)%N

f ( N , M ) f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号 f ( N − 1 , M ) f(N-1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号