6 热水器

C1教学楼的5楼有一个热水器，学生们可以在课间来这里接热水喝。

这个热水器可以在每分钟提供W升的热水。

现在有n名同学来这里打水，第i名同学打算在Si ~ Ti(不包括第Ti分钟)的时间内接热水，每分钟接走Pi的热水。热水器并不会储存热水，也就是说每分钟只有W升的热水，可以多名同学在同一分钟同时接水。

现在请你判断这个热水器能不能满足所有同学的打水的需求呢？

输入格式

第一行两个正整数，分别代表n和W.

后面n行，每行三个整数，分别为Si,Ti,Pi。

1≤n≤2×105

0≤Si≤Ti≤2×105

1≤Wi,Pi≤109

所有输入均为整数

输出格式

如果可以满足所有同学的打水的需求，输出Yes，否则输出No。

测试样例一

4 10
1 3 5
2 4 4
3 10 6
2 4 1

No

测试样例二

4 10
1 3 5
2 4 4
3 10 6
2 3 1

Yes

参考代码：

#include 
using namespace std;
typedef long long LL;
const int N = 200010;
LL n,w;
LL s[N];int main()
{scanf("%lld%lld",&n,&w);int l,r,c,maxn=0;for(int i=0;iw){fg=false;break;}}if(fg)printf("Yes");else printf("No");return 0;
}

7 走方格

给定一个n行m列的网格S，每个格子都是小正方形。其中有的小方格上面有障碍物，有的是空白。

其中，如果Si,j是#，代表该位置放有一个障碍物；如果Si,j是.，代表该位置是空白。

Rain Sure同学站在(1,1)位置，每次他可以向右或者向下或者沿对角线向右下走任意数量的格子，但是不可以走到障碍物上！

请你求出Rain Sure同学从(1,1)走到(n,m)一共有多少种方案，请输出答案对1e9+7取模的结果。

输入格式

第一行包括两个正整数，分别为n和m。

后面n行，每行一个长度为m的字符串，代表网格。

2≤n,m≤2000

Si,j是#或者.

S1,1和Sn,m一定是.

输出格式

输出答案对1e9+7取模的结果

测试样例一

3 3
...
.#.
...

10

测试样例二

4 4
...#
....
..#.
....

84

参考代码：

#include 
using namespace std;
typedef long long LL;
const int N = 2010, mod = 1e9 + 7;
int n, m;
char ch[N][N];
LL f[N][N];
LL s1[N][N],s2[N][N],s3[N][N];int main()
{scanf("%d%d", &n, &m);getchar();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++)scanf("%c", &ch[i][j]);getchar();}f[1][1] = 1,s1[1][1]= s2[1][1] = s3[1][1] =1;for(int i=1;i<=n;i++)for (int j = 1; j <= m; j++) {if (ch[i][j] == '#') { continue; }f[i][j] += ((s1[i - 1][j] + s2[i][j - 1])%mod + s3[i - 1][j - 1])%mod;s1[i][j] = (f[i][j] + s1[i - 1][j])%mod;s2[i][j] = (f[i][j] + s2[i][j - 1]) % mod;s3[i][j] = (f[i][j] + s3[i - 1][j - 1]) % mod;}cout << f[n][m];return 0;
}

8 朋友圈

有n名学生在一个学校里，其中第i名学生是Ci班的。

他们将在学校认识新的朋友，现在给定q次查询，每次查询是下面两种查询中的一种：

1 a b :a同学和b同学交朋友，并且a同学的朋友圈和b同学的朋友圈会合并为一个大朋友圈。

2 x y : 要求你回答出，学生x的朋友圈中有多少名同学是来自班级y的。

输入格式

第一行两个正整数，分别代表n和q。

第二行有n个正整数，代表n名同学来自哪个班。

后面q行，每行代表一个查询，格式如题中描述

1≤n≤2×105

1≤q≤2×105

1≤Ci,a,b,x,y≤n

在查询1 a b中，保证a=b

输出格式

对于每个2 x y输出答案。

测试样例一

5 5
1 2 3 2 1
1 1 2
1 2 5
2 1 1
1 3 4
2 3 4

2
0

测试样例二

5 4
2 2 2 2 2
1 1 2
1 1 3
1 2 3
2 2 2

3

参考代码：

#include 
using namespace std;
typedef long long LL;
const int N = 200010, mod = 1e9 + 7;
int n, q, x;
int a, b, c;
int p[N];
map res[N];
int siz[N];
int find(int x) {if (x != p[x])p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> q;for (int i = 1; i <= n; i++) {siz[i] = 1;scanf("%d", &x);res[i][x]++;p[i] = i;}while (q--) {scanf("%d%d%d" ,&c, &a, &b);if (c == 1) {a = find(a), b = find(b);if (a != b) {if (siz[a] > siz[b]) {p[b] = a;siz[a] += siz[b];for (auto it : res[b]) {res[a][it.first] += it.second;}}else {p[a] = b;siz[b] += siz[a];for (auto it : res[a]) {res[b][it.first] += it.second;}}}}else {a = find(a);printf("%d\n", res[a][b]);}}return 0;
}

9 交保护费

RainSure同学对数字非常敏感，他有m个不喜欢的数字，分别是D1,D2,⋯,Dm

RainSure同学需要定期向HBU里的黑社会老大Arbalest提交保护费，并且每次不得少于n元，否则下场就会很惨。。。

同时，RainSure同学希望他提交的保护费在十进制表示中不能出现他不喜欢的数字。

请你告诉他，他每次最少需要交多少钱，保护费要求是一个正整数，因为Arbalest不喜欢小数点。

输入格式

第一行包含两个正整数分别为n和m。

第二行m个数字，表示RainSure同学不喜欢的数字。

1≤n<10000

1≤m<10

0≤D1<D2<D3,⋯,Dm≤9

{D1,D2,⋯,Dm}=1,2,3,4,5,6,7,8,9

输出格式

输出一个正整数，代表每次最少需要提交的保护费。

测试样例一

1000 8
1 3 4 5 6 7 8 9

2000

样例说明，首先，RainSure至少需要提交1000元的保护费，并且十进制表示下只能包括0和2。大于等于1000的最小的只包括0和2的数字就是2000。所以，答案为2000.

测试样例二

9999 1
0

9999

参考代码：

#include 
using namespace std;
typedef long long LL;
int w, n;
int a[20];
int main()
{cin >> w >> n;memset(a, 0, sizeof(a));for (int i = 0; i < n; i++) {int x;cin >> x;if(x>=0&&x<10)a[x] = 1;}for (int i = w; i <= 100000; i++) {int j = i;bool fg = true;while (j != 0) {int x = j % 10;j /= 10;if (a[x] == 1) {fg = false;break;}}if (fg) {cout << i;return 0;}}return 0;
}

10 走方格

有一个n行m列的网格，你每一次只能向右或者向下走，直到走到右下角的格子。

现在，在网格的左下角有一个a行b列的小网格被障碍物挡住了，你不可以经过这些区域。

请你求出在不经过障碍物区域的情况下，从左上角(1, 1)走到右下角(n, m)一共有多少种方案。

方案数可能很大，请输出答案对1e9+7取模的结果。

输入格式

一行包括四个正整数，分别代表n,m,a,b。

1≤n,m≤105

1≤a<n

1≤b<m

输出格式

输出方案数对1e9+7取模的结果。

测试样例一

2 3 1 1

2

说明：两种方案：右右下、右下右。

测试样例二

10 7 3 4

3570

测试样例三

100000 100000 99999 99999

1

参考代码：

#include 
using namespace std;
typedef long long LL;
const int N = 200010, mod = 1e9 + 7;
int n, m, a, b;int fact[N], infact[N];
int qmi(int a, int k, int p)
{int res = 1;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}LL com(int n, int m) {return ((LL)fact[n] * infact[m] % mod * infact[n - m]) % mod;
}int main()
{scanf("%d%d%d%d", &n, &m, &a, &b);fact[0] = infact[0] = 1;for (int i = 1; i < N; i++){fact[i] = (LL)fact[i - 1] * i % mod;infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;}LL res = 0;for (int i = 0; i < n - a; i++) {LL t = ((LL)com(b + i - 1, b - 1) * com(n + m - b - i - 2, n - i - 1))%mod;res = (res + t)%mod;}cout << res;return 0;
}

11 和与积

给定两个正整数S和P。请你回答是否存在一对正整数(n,m)满足条件：n+m=S并且n×m=P。

如果存在，输出Yes；否则，输出No.

输入格式

一行内两个正整数，分别代表S和P。

1≤S,P≤1012

输出格式

如果存在，输出Yes；否则，输出No。

测试样例一

3 2

Yes

测试样例二

1000000000000 1

No

参考代码：

#include 
using namespace std;
typedef long long LL;
LL S, P;
int main()
{cin >> S >> P;LL j = 0;for (LL i = 1; i <= P/i; i++) {j = S - i;if ((LL)i * j == P) {cout << "Yes";return 0;}}cout << "No";return 0;
}

12 缩短字符串

给定一个长度为n的只包含小写字母的字符串。HBU的算竞大哥Arbalest想让Rain Sure把这个字符串变的尽可能短，并且要求他只能进行如下操作任意次：

如果字符串中存在子串fox，可以将其删去，然后将左右两个字符串再拼在一起。

Rain Sure表示完全不会，请你帮帮他！

输出能够得到的最短长度。

输入格式

第一行一个正整数n，代表字符串长度。

第二行一个长度为n的，只包含小写字母的字符串。

1≤n≤2×105

输出格式

一个整数，代表可能的最短长度。

测试样例一

6
icefox

3

参考代码：

#include 
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, mod = 1e9 + 7;
string s;
char st[N];
int top,n;
int main()
{cin >> n;cin >> s;for (int i = 0; i < n; i++) {if (top >= 1) {if (st[top - 1] == 'f' && st[top] == 'o' && s[i] == 'x') {top -= 2;continue;}}if (top >= 0 && i < n - 1) {if (st[top] == 'f' && s[i] == 'o' && s[i + 1] == 'x') {top--, i++;continue;}}st[++top] = s[i];}cout << top;return 0;
}

13 买木棒

Rain Sure同学想去商店买木棒，他需要长度1 ~ n的木棒各一个。商店现在有长度为1 ~ n+1的木棒各一个，且售价均为1元。

Rain Sure买下一个木棒后，可以回家将它分成任意多段，比如一根长度为L的木棒，如果将其分成k段，长度分别为L1,L2,⋯,Lk，需要满足L1+L2+⋯+Lk=L。

Rain Sure想要花尽可能少的钱得到长度为1 ~ n的木棒各一个，请你帮他算出他最少需要花多少钱。

输入格式

输入一个正整数，代表n。

1≤n≤1018

输出格式

输出最少需要花费多少钱。

测试样例一

4

3

参考代码：

#include 
using namespace std;
typedef long long LL;
LL S, P;
int main()
{cin >> S;P = S;S++;int i = 1;while (S >= i) {S -= i;i++;}cout << P - i + 2;return 0;
}