Codeforces Round #617(div3) (A-E1)
A.Array with Odd Sum
题意：
给你一个数组 可以将数组中的任意一个数变成数组中存在的另一个数
不限制这种操作的次数 问数组最后是否能变成这样一种状态：数组内所有元素的和为奇数
我们可以分为以下几种情况
思路：
1.数组内所有元素都为偶数
这种情况下无法满足题意
2. 数组内的元素全部为奇数
这时又分为两种情况: (1).数组长度(元素个数)为偶数 不满足题意
(2).数组长度(元素个数)为奇数 满足题意
3.数组内既有奇数又有偶数
这种情况满足所有条件
综上 只要数组中有奇数但不全是奇数 即可满足题意
#include<bits/stdc++.h>
using namespace std;
int a[2005];
int main()
{
int t;cin >> t;
while (t--)
{
int n;cin >> n;
for (int i = 1;i <= n;i++)
scanf("%d", &a[i]);
int flag = 0;
for (int i = 1;i <= n;i++)
{
if (a[i] & 1)
{
flag++;
}
}
if (flag == 0 || (flag == n && n % 2 == 0))cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}B. Food Buying
题意：
Mishka每花10块钱就会返利1块钱 问给n元钱，最多能买多少钱的东西
思路：
对于当前的n 如果n >= 10 ans += n / 10 * 10 即可以获得返利的部分 更新后的n为可以获得的返利加上之前的n的不可返利的部分即个位数
new n = n/10*10 + n % 10
#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;
int getbit(int n)
{
int t = 10;
while (n / t >= 10)t *= 10;
return n / t * t;
}
int main()
{
int t;cin >> t;
while (t--)
{
int n;cin >> n;
int ans = 0;
while (n >= 10) {
ans += n / 10 * 10;
n = n / 10 + n % 10;
}
ans += n;
printf("%d\n", ans);
}
return 0;
} 题意：
减少尽可能少的移动步数使终点坐标不变
思路：
开一个map存当前位置的坐标，其值为字符串下标（即第几步走到当前位置）
若当前坐标的值存在，说明之前经过这个位置，可以删除两个位置之间的字符串，如果两者的差小于ans，就更新ans 和当前坐标对应的字符串下标
#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;
map<pair<int, int>, int>mp;//存储某坐标最近一次出现的位置
int main()
{
int t;cin >> t;
while (t--) {
int x = 0, y = 0, tx = 0, ty = 0;
int n;cin >> n;
int ans = INF;
mp.clear();
string s;cin >> s;
mp[{0, 0}] = -1;
for (int i = 0;i < s.size();++i) {
if (s[i] == 'L')--tx;
if (s[i] == 'R')++tx;
if (s[i] == 'U')++ty;
if (s[i] == 'D')--ty;
if (mp.count({ tx, ty })) {
if (ans > i - mp[{tx, ty}] + 1) {
x = mp[{tx, ty}] + 2;
y = i + 1;
ans = i - mp[{tx, ty}] + 1;
}
}
mp[{tx, ty}] = i;
}
if (ans == INF)printf("-1\n");
else printf("%d %d\n", x, y);
}
}
C. Yet Another Walking Robot
题意：
尽可能少的减少机器人移动的步数，使终点不变
思路：
用map记录当前位置对应的字符串下标，当下次再到相同位置时，两个下标相减即可得到应删除的字符串长度，维护其最小值即可
#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;
map<pair<int, int>, int>mp;//存储某坐标最近一次出现的位置
int main()
{
int t;cin >> t;
while (t--) {
int x = 0, y = 0, tx = 0, ty = 0;
int n;cin >> n;
int ans = INF;
mp.clear();
string s;cin >> s;
mp[{0, 0}] = -1;
for (int i = 0;i < s.size();++i) {
if (s[i] == 'L')--tx;
if (s[i] == 'R')++tx;
if (s[i] == 'U')++ty;
if (s[i] == 'D')--ty;
if (mp.count({ tx, ty })) {
if (ans > i - mp[{tx, ty}] + 1) {
x = mp[{tx, ty}] + 2;
y = i + 1;
ans = i - mp[{tx, ty}] + 1;
}
}
mp[{tx, ty}] = i;
}
if (ans == INF)printf("-1\n");
else printf("%d %d\n", x, y);
}
}
D. Fight with Monsters
题意：
你和你的对手轮流打怪，如果是你打死了怪物，你得一分，如果是对手打死了怪物，都不得分，你有一个秘密的技巧，可以让对手跳过他的攻击回合（🐕），但是你只能使用k次，问最多能得到多少分
思路：
我们可以用怪物的血量对a + b 求余得mod，来获得当前怪兽最后一个回合的情况，如果mod为0，说明这个怪兽是由对手杀死（因为我们是先手），所以应该用ceil(b/a)(ceil代表向上取整)次技巧才能得分，如果mod不为0，应该用ceil(mod/a)-1次技巧才能得分，为什么是ceil(mod/a)-1而不是ceil(mod/a)次呢，可以假设a == 2， b == 6，假如mod为5，当前是我们的回合，所以我们可以不使用技巧攻击一次，所以需要使用ceil(mod/a)-1 == 2次技巧，而余数为0的时，在我们已经攻击的情况还要对怪物造成b血量的伤害，所以直接ceil(b/a)即可
#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;
int arr[maxn],ans[maxn];
int n, a, b, k;
int main()
{
cin >> n >> a >> b >> k;
for (int i = 1;i <= n;++i) {
cin >> arr[i];
arr[i] %= (a + b);
}
int res = 0;
for (int i = 1;i <= n;++i) {
if (arr[i] == 0)ans[i] = ceil(b / float(a));
else if (arr[i] <= a)ans[i] = 0;
else ans[i] = ceil(arr[i] / float(a)) - 1;
}
sort(ans + 1, ans + n + 1);
for (int i = 1;i <= n;++i) {
if (k - ans[i] >= 0) {
++res;
k -= ans[i];
}
else break;
}
printf("%d", res);
}
E1. String Coloring (easy version)
题意：
给一串长度为n的字符串，对每个字符串进行染色0或1，颜色不同的位置可以互换，问是否能给字符串上色，以在进行交换操作之后可以使原字符串非严格单调递增
思路：
同一颜色的相邻字符不能交换，说明相同颜色的字符一定非严格单调递增，我们用s1，s2记录染色为0、1的子字符串的字典序最大值，如果当前字符大于等于s1，我们将它染色成0，否则判断其是否能被染色成1，即当前字符是否大于等于s2，如果小于s2，说明至少三个颜色才能满足要求，此情况直接输出NO
#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;
int ans[maxn];
int main()
{
int n;cin >> n;
int s1 = -1, s2 = -1;
string s;cin >> s;
for (int i = 0;i < s.size();++i) {
if (s[i] - 'a' >= s1) {
s1 = s[i] - 'a';
ans[i] = 0;
}
else if (s[i] - 'a' >= s2) {
s2 = s[i] - 'a';
ans[i] = 1;
}
else {
printf("No\n");
return 0;
}
}
printf("YES\n");
for (int i = 0;i < n;++i) {
printf("%d", ans[i]);
}
}
记录一些学习过程中遇到的好的题目和算法，以后可能还会有技术交流
投递华为等公司10个岗位 >
