文章目录

• A. Lame King【简单模拟、贪心】
• B.Vaccination【模拟、贪心】
• C.Pull Your Luck【规律题、余数、找周期】

A. Lame King【简单模拟、贪心】

分析
首先符号并不重要，我们可以放到第一象限里进行考虑，不妨设x >= y,记向x正方向移动为A，向y正方向移动记为B，不动记为O，如果x==y，我们可以ABABABABAB,走两倍x的时间。如果说x>y，ABABABABABABAOAOA,在A中穿插B和O，共2x-1。
实现

#include 
#define ll long long
#define inf 0x3f3f3f3f
#define inf 0x3f3f3f3f
#define ls (id << 1)
#define rs (id << 1 | 1)
using namespace std;
typedef pair PII;
const int N = 55;
void solve() {int a, b;cin >> a >> b;a = abs(a);b = abs(b);if (a == b) cout << a + b << '\n';else cout << 2 * max(a, b) - 1 << '\n'; 
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

B.Vaccination【模拟、贪心】

分析
开新的一包有两种情况，一种是人已经到k个了，又来一个；一种是最长可覆盖时间(w+d)也到不了这个人的时间了，必须再开一包，即使前面的一包剩下部分疫苗来的也没办法用了。
实现

#include 
#define ll long long
#define inf 0x3f3f3f3f
#define inf 0x3f3f3f3f
#define ls (id << 1)
#define rs (id << 1 | 1)
using namespace std;
typedef pair PII;
const int N = 2e5 + 5;
int a[N];
void solve() {int n, k, d, w;cin >> n >> k >> d >> w;for (int i = 1; i <= n; i++) cin >> a[i];int cnt = 1, now = 1, t = a[1];//t是开包时间，now是已用次数，cnt是开包数for (int i = 2; i <= n; i++) {if (a[i] <= t + d + w && now < k) now++;//时间有效，仍有次数else if (now == k || a[i] > t + d + w) cnt++, t = a[i], now = 1;//重置时间，次数}cout << cnt << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

C.Pull Your Luck【规律题、余数、找周期】

分析
一个简单的想法，我们遍历有的i，求出mod = i*(i + 1)/ 2 % n，使得 (x + mod) % n == 0,刚好余数为0,，但是这里的p实在是太大了，1e9无法承受，所以我们考虑周期，通过打表观察我们可以发现，周期是2n(奇数可以是n)。这样就可以遍历1e5数量级了。
证明
首先证明余数具有递推关系首先证明余数具有递推关系首先证明余数具有递推关系
记Si是前i项和，ri是其mod n的余数
Si+2=Si+1+ai+2=Si+1+Si+1−Si+d=2Si+1−Si+1S_{i+2}=S_{i+1}+a_{i+2}=S_{i+1}+S_{i+1}-S_{i}+d=2S_{i+1}-S_{i}+1Si+2​=Si+1​+ai+2​=Si+1​+Si+1​−Si​+d=2Si+1​−Si​+1
ri+2=(2ri+1−r1+1+n)%nr_{i+2}=(2r_{i+1}-r_1+1+n)\% nri+2​=(2ri+1​−r1​+1+n)%n
只需∃i>0,ri=r1且ri+1=r2即可出现循环只需\exist i > 0,r_{i}=r_{1}且r_{i+1}=r_2即可出现循环只需∃i>0,ri​=r1​且ri+1​=r2​即可出现循环
因为递推关系的存在，我们可以用这两个相同的余数生成相同的序列。
∑i=12n=(2n+1)n\sum_{i=1}^{2n}=(2n+1)n∑i=12n​=(2n+1)n被n整除
r1=1%n,r2=(1+2)%n=3%n,......,r2n+1=((2n+1)n+2n+1)%n=1%n,r2n+2=((2n+1)n+2n+1+2n+2)%n=3%nr_1=1\% n,r_2=(1+2)\% n= 3 \% n, ......,r_{2n + 1}=((2n+1)n+2n+1)\% n=1\% n,r_{2n+2}=((2n+1)n+2n+1+2n+2)\%n=3\% nr1​=1%n,r2​=(1+2)%n=3%n,......,r2n+1​=((2n+1)n+2n+1)%n=1%n,r2n+2​=((2n+1)n+2n+1+2n+2)%n=3%n
∴r1=r2n+1,r2=r2n+2\therefore r_1=r_{2n+1},r_2=r_{2n+2}∴r1​=r2n+1​,r2​=r2n+2​
完毕。
实现

#include 
#define ll long long
#define inf 0x3f3f3f3f
#define inf 0x3f3f3f3f
#define ls (id << 1)
#define rs (id << 1 | 1)
using namespace std;
typedef pair PII;
const int N = 2e5 + 5;
void solve() {int n, x, p;cin >> n >> x >> p;int m = min(p, 2 * n);for (int i = 1; i <= m; i++) {int mod = 1ll * i * (i + 1) / 2 % n;if ((mod + x) % n == 0) {cout << "Yes\n";return;}}cout << "No\n";
}
main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}