// 比赛链接：https://codeforces.com/contest/1200
题意：
有一家旅馆有10间房，编号0~9，从左到右顺序排列。旅馆有左右两扇门，每次新来旅客从进来门的方向分配最近的空闲房间。给你一段旅客到来方向以及离开位置的序列，输出最终旅馆房间使用情况。
输入：
8
LLRL1RL1
输出：
1010000011
题解：
序列长度不超过10^5，暴力模拟复杂度O(10*n)。
AC代码：
#include<iostream> #include<cstdio> using namespace std; char s[100010]; bool r[10]; // true:有人 false:无人 int main() { int n; cin>>n; scanf("%s", s); for(int i=0;i<n;i++) { if(s[i]==‘L‘) { for(int j=0;j<=9;j++) { if(!r[j]) { r[j] = 1; break; } } } else if(s[i]==‘R‘) { for(int j=9;j>=0;j--) { if(!r[j]) { r[j] = 1; break; } } } else { r[s[i]-‘0‘] = 0; } } for(int i=0;i<=9;i++) { putchar(r[i]?‘1‘:‘0‘); } return 0; }
题意：
从起点到终点有 n 个格子，每块高度 h[i]，初始时背包有m块方块，从 i 跳到 i+1 有三种选择，1. 把背包的方块放到当前的格子上；2. 把当前格子的方块放到背包里；3.跳到下一块。
只有当 | h[i] - h[i+1] | <= k 才能跳到下一块。 问是否能跳到终点。
输入：
第一行组数，后面每组第一行 n，m，k，第二行 n个值代表 h[i]。
5
3 0 1
4 3 5
3 1 2
1 4 7
4 10 0
10 20 10 20
2 5 5
0 11
1 9 9
99
输出：
YES
NO
YES
NO
YES
题解：
贪心。
如果能跳到下一块，（左边能凑到的最多方块要大于等于右边最少需要的方块，即m+h[i]>= h[i+1]-k ），把前一块上的方块取到前后差值不超过 k。否则跳不到终点。
AC代码：
#include<iostream> #include<cstdio> using namespace std; int h[110]; int main() { int t; cin>>t; while(t--) { int n, m, k; scanf("%d %d %d", &n, &m, &k); for(int i=0;i<n;i++) { scanf("%d", &h[i]); } bool flag = true; for(int i=0;i+1<n;i++) { if(h[i]+m>=h[i+1]-k) { if(h[i+1]>=k) m = h[i]+m - (h[i+1]-k); else m = h[i]+m; } else { flag = false; break; } } if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }
题意：
一个圆盘，内层分割成m块，外层分割成n块，给出 q 个询问，判断所给两块区域是否连通。
输入：
第一行 n，m，q，后面 q 行，每行四个数 sx，sy，ex，ey。sx，ex 为 1 代表内层，为 2 代表外层；sy，ey 代表编号，如图顺时针排序。
4 6 3
1 1 2 3
2 6 1 2
2 6 2 4
输出：
YES
NO
YES
题解：
思维题。设 g = gcd(m, n)，由图可知 1*g，2*g，3*g，…… k*g 把圆盘分割开。这些单独块之内连通，不在同一块则不连通。
AC代码：
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; ll gcd(ll a, ll b) { return b==0?a:gcd(b, a%b); } ll g, m, n; ll f(int d, ll v) { // 计算 v 所在块的编号 if(d==1) return v/(m/g); else return v/(n/g); } int main() { int q; cin>>m>>n>>q; int sx, ex; ll sy, ey; g = gcd(m, n); while(q--) { scanf("%d %lld %d %lld", &sx, &sy, &ex, &ey); if(f(sx, sy-1)==f(ex, ey-1)) printf("YES\n"); else printf("NO\n"); } return 0; }
题意：
输入：
输出：
题解：
AC代码：
原文：https://www.cnblogs.com/izcat/p/11338978.html
