这一场div2只A了两题 竟然加了70多分orz（肯定是基础分太低
A.Exercising Walk
题意:
向左走a步，向右走b步，向下走c步，向上走d步，问能否在执行所有操作的过程中始终处于题目给的范围内
思路:
只需判断同方向移动步数的代数和是否满足条件即可，注意特判下x1 == x2 和 y1 == y2的情况
这里我们用ta和tb代表一对相反方向的差
对于ta 为什么用b-a而不用a-b呢
可以这样思考 b-a为向右移动的步数
当b-a大于0时代表最终向右移动 此时x+ta恰好比x大 也代表向右移动 如果ta取a-b 就达不到这种效果 tb同理
当x1 == x2 时 在水平方向上不能移动 此时之后a == b == 0是符合要求的 所以特判x1 == x2 和 y1 == y2 的情况
ps（x2>=x1, y2>=y1，本蒟蒻没看到条件orz）
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<map> #include<cstdio> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' using namespace std; typedef long long ll; const int maxn = 1e3+10; int main() { int a, b, c, d; int x, y, x1, y1, x2, y2; int t;cin >> t; while (t--) { cin >> a >> b >> c >> d; cin >> x >> y >> x1 >> y1 >> x2 >> y2; int flag = 1; int ta = b - a; int tb = d - c; ta += x; tb += y; if ((x1 == x2 && (a || b)) || (y1 == y2 && (c || d)))printf("NO\n"); else if (ta >= x1 && ta <= x2 && tb >= y1 && tb <= y2)printf("YES\n"); else printf("NO\n"); } }
B.Composite Coloring
题意
给一个长度不超过1000的数组，每个数不超过1000且为合数，如果两个数不互质这这两个数颜色相同，且一个数只能有一种颜色，不同颜色数1<= m <= 11，且颜色不能出现断层 即m之前的所有数都要出现（m取5 那么1，2，3，4，5都要出现）
思路:
可以发现第11个素数31 * 31 < 1000 但31 * 37 > 1000,很容易想到，前1000个整数都可以被11个素数中的一个整除，可以用set存出现的不同最小质因数的种类 vis记录每个最小值引述对应的编号 vis[a[i]]就表示这个质因数对应的编号 输出即可
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<map> #include<cstdio> #include<set> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' using namespace std; typedef long long ll; const int maxn = 1e3+10; int a[maxn]; int ans[maxn]; int b[13] = { 0,2,3,5,7,11,13,17,19,23,29,31 }; int vis[20]; int main() { int t;cin >> t; while (t--) { set<ll>s; memset(a, 0, sizeof(a)); memset(vis, 0, sizeof(vis)); memset(ans, 0, sizeof(ans)); int n;cin >> n; for (int i = 1;i <= n;++i) { cin >> a[i]; } for (int i = 1;i <= n;++i) { for (int j = 1;j <= 11;++j) { if (a[i] % b[j] == 0) { a[i] = j; s.insert(j); break; } } } cout << s.size() << endl; ll k = 0; for (auto i : s) { vis[i] = ++k; } for (int i = 1;i <= n;++i) { cout << vis[a[i]] << " "; } } }
C. K-Complete Word
题意：
一个长度为n的字符串，分成k个部分要求这k个子字符串都相同且为回文串
求最小修改操作数
##思路
既然是回文串那么每一部分的i和k-i-1位置上的字符串是相同的，看一下哪个字幕出现的次数最多就用哪个字母
i == k-i-1时只需要搜索一次，其他情况两次
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' using namespace std; typedef long long ll; const int maxn = 2e5 + 10; char s[maxn]; int main() { int t;cin >> t; while (t--) { int n, k;cin >> n >> k; cin >> s; int ans = n; for (int i = 0;i <= k - i - 1;++i) { vector<int>a(26, 0);//定义一个具有26个整型变量的vector数组，并初始化为0 //i == k-i-1时只需要搜索一次 for (int j = i;j < n;j += k) { a[s[j] - 'a']++; } if (i < k - i - 1) { for (int j = k - i - 1;j < n;j+=k) { a[s[j] - 'a']++; } } ans -= *max_element(a.begin(), a.end());//减去不需要修改的 } printf("%d\n", ans); } }
