Codeforces Round #352 (Div. 2) (A-D)

时间:2023-12-17 22:01:14

672A Summer Camp

题意:

1-n数字连成一个字符串, 给定n , 输出字符串的第n个字符。n 很小, 可以直接暴力。

Code:

#include <bits/stdc++.h>
using namespace std; int main() {
int n;
cin >> n;
int begin = 1;
for(;;)
{
int dig = log10(begin) + 1;
if(n <= dig)
{
char ss[10];
sprintf(ss, "%d", begin);
cout << ss[n-1] << endl;
break;
}
else {
begin ++;
n -= dig;
}
}
return 0;
}

672B Different is Good

题意:

给定一个字符串, 可以对字符串进行单个字符的修改, **要求所有子串都不相同**
所以每个字符都不能相同。

Code:

#include <bits/stdc++.h>
using namespace std;
int Sum[50];
int main() {
memset(Sum, 0, sizeof(Sum));
int n;
string s;
cin >> n >> s;
int Count = 0;
int Vis = 0;
for(int i = 0; i < s.length(); ++i)
{
int c = s[i]-'a';
Sum[c]++;
}
for(int i = 0; i < 26; ++i)
{
if(Sum[i]) Vis++;
if(Sum[i] > 1) Count += Sum[i] - 1;
}
int ANS = 0;
if(Count > (26 - Vis)) ANS = -1;
else ANS = Count;
cout << ANS << endl;
}

671A Recycling Bottles

题意:

有A , B两人, 垃圾桶T点, 坐标系中还有 n 个垃圾桶。
A,B两人去捡垃圾, 把垃圾放入垃圾桶中, 一次一个, 输出A,B两人的最短行走路线。
(A,B)并不是都要去捡, 可以只有一个人。
直接进行贪心就可以得出结果了。

Code:

#include <bits/stdc++.h>

using namespace std;
const double eps = 1e-8;
typedef long long LL;
const int maxn = 1e5 + 131;
struct Point {
LL x, y;
} ;
Point A, B, T;
Point Num[maxn];
int n; double Distance(Point a, Point b) {
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
} double Dis_T[maxn], Dis_A[maxn], Dis_B[maxn];
double GetIn() {
double Sum = 0.0;
cin >> A.x >> A.y >> B.x >> B.y >> T.x >> T.y;
cin >> n;
for(int i = 0; i < n; ++i)
{
cin >> Num[i].x >> Num[i].y;
Dis_T[i] = Distance(Num[i], T);
Dis_A[i] = Distance(Num[i], A);
Dis_B[i] = Distance(Num[i], B);
Sum += (Dis_T[i] * 2);
}
//总距离是在 2倍Dis_T 的基础上修改的。
return Sum;
} int main() {
double S ,Sum;
S = Sum = GetIn();
double MinA = 1e12, MinB = 1e12;
int posA = 0, posB = 0;
for(int i = 0; i < n; ++i)
{
if(Dis_A[i]-Dis_T[i] < MinA) // 找出 A 点最短的第一次捡垃圾路线
{
MinA = Dis_A[i]-Dis_T[i];
posA = i;
}
if(Dis_B[i]-Dis_T[i] < MinB) // 同理 B 点。
{
MinB = Dis_B[i]-Dis_T[i];
posB = i;
}
}
if(MinA < 0 && MinB < 0) { // 小于 0 则说明 Dis_A + Dis_T <2 * Dis_T 的;
if(posA == posB) {
S = min(S, Sum-Dis_T[posA]+Dis_A[posA]); //只有A 捡垃圾的情况
S = min(S, Sum-Dis_T[posB]+Dis_B[posB]); //只有B 捡垃圾的情况
for(int i = 0; i < n; ++i) if(i != posA)
S = min(S, Sum-Dis_T[posA]+Dis_A[posA]-Dis_T[i]+Dis_B[i]);
for(int i = 0; i < n; ++i) if(i != posB)
S = min(S, Sum-Dis_T[posB]+Dis_B[posB]-Dis_T[i]+Dis_A[i]);
}
else {
S = Sum + MinA + MinB;
}
}
else {
if(MinA < MinB)
S = Sum - Dis_T[posA]+Dis_A[posA];
else
S = Sum - Dis_T[posB]+Dis_B[posB];
}
printf("%.12f\n",S);
return 0;
}

671B Robin Hood

题意:

给一组序列, 有一个人, 每天会把序列的最大值 -1, 最小值 +1;
如果序列都相同, 不做任何动作。
输出 K 天后 序列的 Max - Min;
也是贪心。

Code:

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 5000000 + 131;
LL City[maxn];
LL n, k;
int main() {
std::ios::sync_with_stdio(false);
cin >> n >> k;
LL Sum = 0;
for(int i = 0; i < n; ++i) cin >> City[i], Sum += City[i];
sort(City, City+n);
LL Min = City[0], Max = City[n-1];
LL Use = k;
for(int i = 1; i < n; ++i) if(City[i] > Min) { //先把小的值一起抬高
LL temp = min(City[i]-Min, Use/LL(i));
Min += temp;
Use -= temp * i;//总共消耗的天数。
/* 这里Use 有余下, 也不会对 Max - Min 造成影响,*/
}
Use = k;
for(int i = n-2; i >= 0; --i) if(City[i] < Max) {
LL temp = min(Max-City[i], Use/LL(n-i-1));
Max -= temp;
Use -= temp * (n-i-1);
} LL Ans = Sum % n ? 1 : 0;
Ans = max(Ans, Max - Min);
cout << Ans <<endl;
return 0;
}

E 题