这一场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);
}
}
京公网安备 11010502036488号