目录
复读
给定若干个字符串，不定数量，每行一个。有些字符串可能出现了多次。如果读入一个字符串后，发现这个字符串以前被读入过，则这个字符串被称为前面相同的字符串的复读，这个字符串被称为复读字符串。相应的，每个首次出现的字符串就是非复读字符串。
举个例子，
- abc
- def
- abc
- abc
- abc
第 1,3,4,51,3,4,5 行是字符串 abc，那么 3,4,53,4,5 行的字符串会被称为“复读”。
请你把所有的非复读字符串，按照行号从小到大的顺序，依次拼接为一个长串并输出。
多个字符串，每行一个，含义见题目描述。
注意：如果这个字符串是 0，说明所有字符串都读完了。这个 0 不认为是一个“非复读字符串”。
共一行，表示所有非复读字符串，按照行号从小到大依次连接的结果。
输入
- cc
- b
- a
- cc
- 0
输出
ccba【数据范围】
字符串的个数不超过 500 个，字符串总长度不超过 50000，每个字符串中只包含小写字母、数字、 . 、! 和 &，不包含空格等特殊符号。
标准水题，查重字符串，重复不接尾，对于字符串数组输出即可
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- vector<string> A;
- int main()
- {
- string s;
- while(cin >> s,s != "0")
- {
- vector<string>::iterator it = find(A.begin(),A.end(),s);
- if(it != A.end())A.push_back(s);
- }
- for(int i = 0;i < A.size();i ++ )cout << A[i];
- return 0;
-
- }
时钟
你有一个电子钟，可以显示 0:00 到 23:59 之间的所有时间，以数字的形式显示。其中小时是 0 到 23（0 时会显示一个 0，而 1 到 9 时不会显示前导 0），分钟是 00 到 59（0 到 9 分都会显示前导 0）。任何时刻，电子钟都会显示三个或者四个 00 到 99 的数字。如果在某时刻，这些数字依次组成了一个等差数列，则这个时刻被称为“好时刻”。
你感觉很无聊，从 0:00 时刻开始盯着这个电子钟。一共盯了 xx 分钟。请问整个过程中，"好时刻"来临了多少次（算上开头和结尾）？
一个不超过 10^9 的非负整数。
请输出"好时刻"来临了多少次？
输入
120输出
10输入
2880输出
79输入
987654321输出
26748975【样例解释】
你观察了 2 个小时，其中这些“好时刻”来临了：
- 0:00
- 0:12
- 0:24
- 0:36
- 0:48
- 1:11
- 1:23
- 1:35
- 1:47
- 1:59
一共是 10 个。
最后一个数据点把暴力做法卡掉了，因此我们可以采用打表的思维，由打表可得，算上从0:00-23:59，一共有39个“好时刻”，因此，我们只需要不断的卡掉1400即可，卡掉一个ans就加39，因此，即使数据为10^9左右，我们处理数据的次数也因1400而优化了许多，所以不会TLE
- #include <iostream>
- using namespace std;
- typedef long long ll;
- int main()
- {
- ll n;
- scanf("%lld",&n);
- ll sum = 0,ans = 0;
- while(n > 1439)
- {
- n = n - 1440;
- ans += 39;
- }
- for(ll i = 0;sum <= n;i ++,sum ++ )
- {
- if(i == 1440)i = 0;
- if(i == 0 || i == 12 || i == 24 || i == 36 || i == 48 || i == 71 || i == 83 || i == 95 || i == 107 || i == 119 || i == 130 || i == 142 || i == 154 || i == 166 || i == 178 || i == 201 || i == 213 || i == 225 || i == 237 || i == 260 || i == 272 || i == 284 || i == 296 || i == 331 || i == 343 || i == 355 || i == 390 || i == 402 || i == 414 || i == 461 || i == 473 || i == 520 || i == 532 || i == 591 || i == 671 || i == 754 || i == 837 || i == 1342 || i == 1425)ans ++ ;
- }
- printf("%lld",ans);
- }
平等的交易
你有 n 件道具可以买，其中第 i 件的价格为 ai。
你有 w 元钱。你仅能用钱购买其中的一件商道具。当然，你可以拿你手中的道具换取其他的道具，只是这些商道具的价值之和，不能超过你打算交换出去的道具。你可以交换无数多次道具。道具的价值可能是 0，但是你不能使用空集换取价值为 0 的商品。
请问，在这个条件下，最多可以换取多少件道具？
第一行一个正整数 n，表示道具个数。
接下来一行 n 个正整数，表示 an。
接下来一行 1 个正整数，表示 w。
一个正整数，表示答案。
输入
- 3
- 1 1 2
- 5
输出
2【样例解释】
买价值为 2 的道具，并交换为两个价值为 1 的道具。
【数据范围及约束】
测试数据满足，1≤n≤106，0≤ai≤10^9，1≤w≤2×10^9。
非常简单的一道题目，连二分都不用，我们只需要对于所有商品进行升序的排序，而后从队尾开始查，只要有商品的价值小于等于w，那么我们可以将其买下，更新w = a[i]，ans = 1(ans初始化为0)，利用前缀和思想处理排序后的数组，而后对于我们所买的商品的前一个下标开始向前遍历前缀和数组，若是前缀和数组s[i]的值小于w，证明我们手中的价值足以购买前i件商品，则答案更新为ans和i之间更大的值(因为i可能为1)
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int N = 1000000 + 10;
- typedef long long ll;
- ll a[N],s[N],n,w,ans = 0,idx;
- int main()
- {
- scanf("%lld",&n);
- for(ll i = 1;i <= n;i ++ )scanf("%lld",&a[i]);
- scanf("%lld",&w);
- sort(a + 1,a + 1 + n);
- for(ll i = 1;i <= n;i ++ )s[i] = s[i - 1] + a[i];
- for(ll i = n;i >= 1;i -- )
- {
- if(w > a[i])
- {
- ans = 1;
- w = a[i];
- idx = i - 1;
- break;
- }
- }
- for(ll i = idx;i >= 1;i -- )
- {
- if(w >= s[i])
- {
- ans = max(ans,i);
- break;
- }
- }
- cout << ans << endl;
- return 0;
- }
清洁工
有一个 n×n 的地块，一个连续 i 分钟没人经过的地面在第 i 分钟会落上 i 个单位的灰，有人经过时不会落灰但灰也不会清零，在人走后第一分钟又会落上一个单位的灰，以此类推。你在这个 n×n 的范围内移动，你的移动轨迹可以描述为一个由 N,S,W,E 组成的字符串，每个字母分别表示上、下、左、右。这个人一开始在点 (x,y)，每一分钟移动一步。
求最后每一个位置上落下的灰的量。
本题中的上和右分别表示 y 轴正方向和 x 轴正方向。保证你没有超过移动的范围。
第一行四个正整数 n,m,x,y，含义如题面所示，其中 x,y 表示横纵坐标，不是数组下标。
第二行一个长度为 m 的字符串，表示你的移动序列。
共n 行，每行 n 个数，第 i 行的第 j 个数表示坐标 (j,n−i+1) 上的灰的数量
输入
- 5 4 1 1
- NENW
输出
- 10 10 10 10 10
- 10 10 10 10 10
- 10 6 10 10 10
- 4 4 10 10 10
- 6 10 10 10 10
输入
- 7 14 1 1
- NENENENENESSSS
输出
- 105 105 105 105 105 105 105
- 105 105 105 105 55 61 105
- 105 105 105 49 51 69 105
- 105 105 51 49 105 79 105
- 105 61 55 105 105 91 105
- 79 69 105 105 105 105 105
- 91 105 105 105 105 105 105
输入
- 10 70 2 2
- NWSNSNNNSNNSSNNSENNNNEESNWSESESSWENNSEWESWWWESEEESENNSENWNESNWSNNNEESS
输出
- 2485 2485 2485 2485 2485 2485 2485 2485 2485 2485
- 2485 1407 1205 1267 2485 2485 2485 2485 2485 2485
- 2485 1435 1281 1167 2485 2485 2485 2217 2281 2347
- 2485 1465 2485 1255 1041 2485 2485 2155 2485 2415
- 1557 1497 2485 2485 969 1177 2485 1733 1807 2485
- 1471 1531 1315 907 935 1267 2485 1473 1647 2485
- 1631 2485 2485 1357 1381 1407 1435 1499 1645 2485
- 2021 2347 2485 2485 2485 2485 1465 1497 2485 2485
- 2087 2415 2485 2485 2485 2485 2485 2485 2485 2485
- 2485 2485 2485 2485 2485 2485 2485 2485 2485 2485
输入
- 5 4 2 1
- NENW
输出
- 10 10 10 10 10
- 10 10 10 10 10
- 10 10 6 10 10
- 10 4 4 10 10
- 10 6 10 10 10
本题 y 轴朝上，x 轴朝右，样例输出中的左下角表示 (1,1)，第一分钟你在初始点处，第二分钟移动到相应的位置，第 m+1 分钟移动到最后一个点，但是总共只有 m 分钟，因此最后一个点不受移动的影响
样例 1 解释：
你的移动路径为 (1,1)→(1,2)→(2,2)→(2,3)→(1,3)，共 4 分钟。
对于第 1 分钟，(1,1) 灰层数不变，其余点被落下了 1 层灰。
对于第 2 分钟，(1,2) 灰层数不变，(1,1) 被落下了 1 层灰，其余点落下 2 层灰。
对于第 3 分钟，(2,2) 灰层数不变，(1,1) 落下 2 层灰，(1,2)(1,2) 落下 1 层灰，其余点落下 3 层灰。
对于第 4 分钟，(2,3) 灰层数不变，(1,1) 落下 3 层灰，(1,2) 落下 2 层灰，(2,2) 落下 1 层灰，其余点落下 4 层灰。
注意最后你移动到了 (1,3)，但是时间只有 4 分钟，所以实际上不会对 (1,3) 造成影响。初始点不一定在 (1,1)。
1≤n≤50,1≤m≤1000。
no 记忆化路径处理
no 二维差分数组处理
no 坐标变幻公式推导
暴力是一种美学
二维数组的大小very small，所以我们不必使用二维差分进行处理，大不了重复遍历就完事儿，只要它不是我们脚下的位置，那么灰尘变化数组ddust则++，反之置为0，在处理过程之中对于sdust数组加上ddust即可，输出也不用管坐标的变换，按照题目输出即可(共n 行，每行 n 个数，第 i 行的第 j 个数表示坐标 (j,n−i+1) 上的灰的数量)
- #include <iostream>
- using namespace std;
- const int N = 1000 + 10;
- int sdust[N][N],ddust[N][N];
- int n,m,x,y;
- string s;
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- cin >> n >> m >> x >> y >> s;
- for(int idx = 0;idx < s.size();idx ++ )
- {
- for(int i = 1;i <= n;i ++ )
- {
- for(int j = 1;j <= n;j ++ )
- {
- if(i != x || j != y)
- {
- ddust[i][j] ++ ;
- sdust[i][j] += ddust[i][j];
- }
- else ddust[i][j] = 0;
- }
- }
- if(s[idx] == 'N')y ++;
- else if(s[idx] == 'S')y -- ;
- else if(s[idx] == 'W')x -- ;
- else if(s[idx] == 'E')x ++ ;
- }
- for(int i = 1;i <= n;i ++ )
- {
- for(int j = 1;j <= n;j ++ )
- {
- cout << sdust[j][n - i + 1] << ' ';
- }
- cout << endl;
- }
- return 0;
- }