leetcode每日一题

1823. 找出游戏的获胜者

共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。

游戏遵循如下规则：

从第 1 名小伙伴所在位置 开始 。
沿着顺时针方向数 k 名小伙伴，计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤 2 继续执行。
否则，圈子中最后一名小伙伴赢得游戏。
给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。

输入：n = 5, k = 2
输出：3
解释：游戏运行步骤如下：1) 从小伙伴 1 开始。
2) 顺时针数 2 名小伙伴，也就是小伙伴 1 和 2 。
3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。
4) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 4 。
5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。
6) 顺时针数 2 名小伙伴，也就是小伙伴 5 和 1 。
7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。
8) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 5 。
9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。

做法一：约瑟夫环直接带公式

class Solution {
public:int findTheWinner(int n, int k) {int s=0;for(int i=2;i<=n;i++)s=(s+k)%i;return s+1;}
};

做法二：模拟队列
每次去除第k个，所以前k-1拿出来并且加入队尾，第k个pop，最后剩下的一个即为答案

class Solution {
public:int findTheWinner(int n, int k) {queue<int>q;for(int i=1;i<=n;i++)q.push(i);while(q.size()>1){for(int i=1;i<k;i++){q.push(q.front());q.pop();}q.pop();}return q.front();}
};

Codeforces Round #786 (Div. 3)

A. Number Transformation

思路：
暴力求

x*b^a==y任意一组解

#include <bits/stdc++.h>
using namespace std;
#define int long long
int _;
int x,y;
void solve()
{cin>>x>>y;bool f=false;int i=0,j=0;for( i=1;i<=y;i++){int sum=x;for( j=1;j<=y;j++){sum*=i;if(sum==y){f=true;break;}}if(f)break;}if(f)cout<<j<<' '<<i<<endl;else cout<<0<<' '<<0<<endl;
}
signed main()
{cin>>_;while(_--)solve();return 0;
}

B. Dictionary

思路：
数学题，类似于26进制，只不过两个位上的字母不一样，减去相同的情况即可

#include <bits/stdc++.h>
using namespace std;
int _;
int n;
void solve()
{string s;cin>>s;cout<<(s[0]-'a')*26+(s[1]-'a')-(s[0]-'a')-(s[1]>s[0])+1<<endl;
}
int main()
{cin>>_;while(_--)solve();return 0;
}

C. Infinite Replacement

思路：
如果t为a，那只有一种结果（s不变）
否则当t中只要有一个a就会无限递归
否则如果t中没有a，通过组合计数，2^s的长度种字符串

#include <bits/stdc++.h>
#define int long long
using namespace std;
int _;
void solve()
{string s,t;cin>>s>>t;int sum=0;for(auto x:t)if(x=='a')sum++; if(t=="a")cout<<1<<endl;else if(sum)cout<<-1<<endl;else cout<<(int)pow(2,(int)s.size())<<endl;
}
signed main()
{cin>>_;while(_--)solve();return 0;
} 

D. A-B-C Sort

思路：
总结规律可以发现：每次取出a的尾部当作b的中间元素，然后当作c的首部，所以数组c无非就是数组a的每两个元素进行交换

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int _;
int n;
int a[N];
void solve()
{cin>>n;for(int i=0;i<n;i++)cin>>a[i];for(int i=n%2;i<n;i+=2){if(a[i]>a[i+1])swap(a[i],a[i+1]);}for(int i=1;i<n;i++){if(a[i]<a[i-1]){cout<<"NO"<<endl;return;}}cout<<"YES"<<endl;
}
signed main()
{cin>>_;while(_--)solve();return 0;
}