codeforces 1203 A（简单思维）B（简单题）C（思维）E（贪心）F1（贪心+思维）

65 阅读 0 评论 43 点赞

我是靠谱客的博主超级台灯，最近开发中收集的这篇文章主要介绍codeforces 1203 A（简单思维）B（简单题）C（思维）E（贪心）F1（贪心+思维），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A. Circle of Students（简单思维）

题目链接：codeforces 1203A

题意：

给n 个数，判断从某个位置开始循环一圈后是否是递增或递减，是输出“YES” 否则输出“NO”

题解：

判断相邻的两个元素的差值是否超过1，如果有2个以上超过1，则输出NO

#include<bits/stdc++.h>
using namespace std;
int t, n;
int a[305];
int main(){
cin >> t;
int cnt;
while(t--){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
cnt = 0;
if (abs(a[1] - a[n]) > 1){
cnt++;
}
for(int i = 1; i <= n-1; i++){
if(abs(a[i] - a[i+1])>1){
cnt++;
}
}
if(cnt >= 2){
cout << "NO" << endl;
}
else{
cout << "YES" << endl;
}
}
return 0;
}

B. Equal Rectangles（简单题）

题目链接：codeforces 1203B

题意：

给 4*n 个数，判断能构成n个面积相等的矩形

题解：

先判断每条相等的线段是否是偶数，如果不是偶数，那就构不成矩形，然后就是最长边* 最短边，次长边*次短边是否相等

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+9;
int a[maxn];
int main(){
int t;
cin >> t;
while(t--){
int n, mi = maxn, ma = 0;
cin >> n;
memset(a, 0, sizeof(a));
for(int i = 1; i <= n * 4; i++){
int k;
cin >> k;
mi = min(k, mi);
ma = max(k, ma);
a[k]++;
}
int ans = mi * ma;
bool
flag = true;
int l = 1, r = 10000, ansl, ansr;
while(l != r){
if(a[l] % 2 != 0){
flag = false;break;
}
while(a[l] == 0 && l <= r){
l++;
}
a[l] = a[l] - 2;
while(a[r] == 0 && r >= l){
r--;
}
if(l > r){
break;
}
a[r] = a[r] - 2;
if(l * r != ans){
flag = false;
break;
}
}
if(!flag){
cout << "NO" << endl;
}
else{
cout << "YES" << endl;
}
}
return 0;
}

C. Common Divisors（思维）

题目链接：codeforces 1203C

题意：

给n个数，判断所有数的共同的因子有多少个

题解：

其实就是判断所有元素的最大公约数的因子有多少个

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+9;
ll divided(ll n){
ll ans = 0;
for(ll i = 1;i <= sqrt(n); i++){
if(n % i == 0){
ans++;
if(i * i != n){
ans++;
}
}
}
return ans;
}
long long gcd(long long a, long long b){
return b == 0 ? a : gcd(b, a%b);
}
int main(){
int n;
cin >> n;
ll ans = 0, k, u = 1;
for(int i = 1; i <= n; i++){
cin >> k;
ans = gcd(ans, k);
}
ans = divided(ans);
cout << ans << endl;
return 0;
}

E. Boxers（贪心）

题目链接：codeforces 1203E

题意：
给n个数，每个数 a[i] 可以变成 a[i]-1或a[i] 或 a[i]+1 ，问最终最多能变成多少个不相同的数

解题思路：

贪心思想，将每个数（除了1）先向左扩展，在看本身，然后向右扩展

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50002;
int a[N], book[N];
int main() {
int n, ans = 0;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a+1, a+1+n);
for(int i = 1; i <= n; i++){
if(a[i] == 1){
if(book[1] == 0){
book[1] = 1;
}
else{
book[2] = 1;
}
}
else{
if(book[a[i]-1] == 0){
book[a[i]-1] = 1;
}
else if(book[a[i]] == 0){
book[a[i]] = 1;
}
else{
book[a[i]+1] = 1;
}
}
}
for(int i = 1; i <= a[n]+ 1; i++){
if(book[i]){
ans++;
}
}
cout << ans << endl;
return 0;
}

F1. Complete the Projects (easy version)（贪心+思维）

题目链接:codeforces 1203F1

题意：

有n个任务，每个任务等级为a[i], 完成之后会加上 b[i] ，初始等级为k，问能否将所有任务完成。

解题思路：

因为b[i] 可能会有负数，所以需要分类讨论。

当 b[i] >= 0 时，应该贪心的想法，先完成a[i] 小的，然后完成a[i] 大的

当 b[i] < 0 时，结论应该是先完成 a[i] + b[i] 大的，后完成 a[i] + b[i] 小的。

因为当b[i] >= 0时，很好想，所以只证明当b[i] < 0 ;

证明：当b[i] < 0时，a[i] + b[i] 大的应该先完成。

设 a1 + b1 > a2 + b2; 需证明如果 a1+b1 不符合情况，那么 a2 + b2 肯定不符合情况

k < a1 或者 k + b1 + b2 < 0都不符合情况

如果 k + b1 < a2 ，那么由a1+b1 > a2 +b2 得 a1+ b1 - a2 > b2，两边同时加上k得 k + a1 + b1 - a2 > b2 + k,

由k+b1 < a2 得， a2 + a1 - a2 > b2 + k，最终得 a1 > b2 + k 也不能使最终结果成立，所以

在a1 + b1 > a2 + b2时，a1+b1不符合情况的情况下，a2+b2也肯定不符合

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
struct node{
int x, y;
}u[maxn],t[maxn];
bool cmp1(node r, node e){
if(r.x == e.x){
return r.y > e.y;
}
return r.x < e.x;
}
bool cmp2(node r, node e){
if(r.x + r.y == e.x + e.y){
return r.x > e.x;
}
return r.x + r.y > e.x + e.y;
}
int main(){
int n, k, p = 1, q = 1;
cin >> n >> k;
for(int i = 1; i <= n; i++){
int a, b;
cin >> a >> b;
if(b >= 0){
u[p].x = a;	u[p].y = b;
p++;
}
else{
t[q].x = a;	t[q].y = b;
q++;
}
}
bool flag = true;
sort(u+1, u+p, cmp1);
sort(t+1, t+q, cmp2);
for(int i = 1; i < p; i++){
if(k < u[i].x){
flag = false;
break;
}
else{
k = k + u[i].y;
}
}
for(int i = 1; i < q; i++){
if(k < t[i].x){
flag = false;
break;
}
else{
k = k + t[i].y;
}
}
if(flag && k >= 0){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}
}