ToB企服应用市场:ToB评测及商务社交产业平台

标题: Codeforces CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!) A-D 题解 [打印本页]

---

作者: 灌篮少年    时间: 2022-9-5 06:57
标题: Codeforces CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!) A-D 题解
A. Two 0-1 Sequences

　大致翻译：
两个长度为n和m的二进制序列a和b（题目保证n >= m）
两个操作：
op1: 改变a(2) 为min(a(1), a(2)),并且移除a（1）
op2: 改变a(2) 为max(a(1), a(2)),并且移除a（1）
每次操作后，原先的a(i)变成a(i + 1), 长度减少1，即前移。
　　a二进制序列能否通过这两个操作变成b二进制序列？
解题思路：刚开始想的是判断a2后缀跟a1后缀是否相同，再判断，a1前面有没有1和0（因为有1和0，就表示op1和op2可以随意完成）。写的时候又陆陆续续发现需要几个特判，想a1长度为1等。
于是就debug，慢慢发现只要前面有a2的第一个数字，并且后缀相同就可以对了。最终写出来了。
不过我写的查找是自己造轮子，我发现大佬就是用stl中的count()来写的，就拿过来改进了改进自己的code

1. #include <iostream>
2. #include <vector>
3. #include <string>
4. #include <set>
5. #include <map>
6. #include <stdio.h>
7. #include <algorithm>
8. using namespace std;
10. #define rep(i,x,n) for(int i = x; i <= n; i++)
12. typedef long long LL;
13. typedef pair<int,int> PII;
15. const int N = 10021;
17. void solve() {
18.     int n, m;
19.     cin>>n>>m;
20.     string a, b;
21.     cin>>a>>b;
22.     if(a.substr(n-m+1) == b.substr(1) && count(a.begin(), a.begin() +n - m + 1, b[0])) {
23.         puts("YES");
24.     } else puts("NO");
25. }
26. void test();
27. int main()
28. {
29.     int n;
30.     cin>>n;
31.     while(n--) solve();
33.     return 0;
34. }

复制代码

B. Luke is a Foodie

　　大致翻译：
对于a数组中的每一个元素，满足 |v−ai|≤x， （x是固定的值，由题目给出， v是可以变化调动的值）
问最少需要调动几次v，才能使得a数组中所有元素满足|v−ai|≤x
解题思路：

<strong>用数组的话存不下1e9+21的int型，而且题目是要找改了几次v。由|v- ai| t;    while(t--) {        LL n,x;        scanf("%lld %lld", &n, &x);        LL cnt = 0;        LL ma, mi;        scanf("%d", &ma);        mi = ma;        rep(i,2,n) {            LL k;            scanf("%lld", &k);            if(mi > k) mi = k;            if(ma < k) ma = k;            if(abs(ma - mi)

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4