3030. 天黑请闭眼

╮ 潜心 ╰

这题就是标准的约瑟夫问题
可以说是模板题了 模拟思路很多 数学方法也可以
放一个链表做法

include

#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
} node;

node *create (int n)
{
    node *p = NULL, *head;
    head = (node *)malloc(sizeof(node));
    p = head; // p是指向当前结点的指针
    node *s;
    int i = 1;
    if (0 != n) // 说明链表不为空
    {
        while (i <= n)
        {
            s = (node *)malloc(sizeof(node)); //临时的,是第一个生成的节点
            s->data = i++; //临时生成的节点交给p
            p->next = s;
            p = s;
        }
        s->next = head -> next; // 指向第一个节点,然后去掉头结点(辅助作用)
    }
    free(head);
    return s->next; // 返回头结点

}
int main ()
{
    int cas;
    scanf("%d", &cas);
    for (int t=0; t<cas; t++)
    {
        int n, m, i;
        scanf("%d%d", &n, &m);

        node *p = create(n);
        node *temp; // 临时指针

        m %= n;

        while (p != p->next) // 指向自己就是空表了
        {
            for (i=1; i<m-1; i++)
                p = p->next; // 执行完这个循环后指向第三个,进行数数功能
            //printf("%d->", p->next->data);

            temp = p->next;
            p->next = temp->next;
            free(temp); // 这一段进行删除节点,删除三后,二就指向四

            p = p->next;
        }
        printf("case #%d:\n%d\n", t, p->data);
    }
    return 0;

}

数学方法也很简单,不外乎通过计数算出每次要死的人的号码
要注意的是越界的处理 取模即可

include

#include<cstdio>

using namespace std;

int main()
{
    int cas, n, m, f;
    cin >> cas;
    for (int t=0; t<cas; t++)
    {
        f = 0;
        cin >> n >> m;
        for (int i=2;i<=n;i++)
            f=(f+m)%i;
        printf("case #%d:\n%d\n", t, f+1);
    }
    return 0;
}
Li Dao

我来送答案啦
直接模拟,这道题对效率要求不高

include

using namespace std;
int T,n,m;
int live[1010];
void inc(int& pos,int step)
{
for(int i=1;i<=step;i++)
{
pos=(pos+1-1)%n+1;
while(!live[pos]) pos=(pos+1-1)%n+1;
}
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) live[i]=1;

int pos=0;
for(int i=1;i<=n-1;i++)
{
inc(pos,m);
live[pos]=0;
}
for(int i=1;i<=n;i++) if(live[i]) cout<<i<<endl;
return;
}

int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

10175102128
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> loop(n);
    for (int i = 0; i < n; i++) {
        loop[i] = i+1;
    }
    auto it = loop.begin()+m-1;
    while (loop.size() > 1) {
        it = loop.erase(it);
        it = loop.begin() + (it - loop.begin() + m-1) % loop.size();
    }
    cout << loop[0] << endl;
}
你当前正在回复 博客/题目
存在问题!