Codeforces Round #683 A~C题解

发布于 2020-11-17  0 次阅读


A. Add Candies(思维)

题目大意:

n个数分别为1 、 2 、 3…. n 1 、 2 、 3…. n1、2、3….n
现在有一种操作,第j次操作能让除j以外的被操作数的其他所有数都加上j。
如果要最后n个数相等,输出需要的操作次数和每次被操作的数的下标。

思路:

第j次操作会使得被选中的数字少增加一个j
最开始数组相邻差为1
所以应该先从后往前选数即可,操作次数即为n

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=998244353;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n;
void solve(){
    cin>>n;
    cout<<n<<endl;
    for(int i=1; i<=n; i++) cout<<i<<" ";
    cout<<endl;
    return ;
}
signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

B. Numbers Box(思维)

题目大意:

给你一个n ∗ m 的矩阵,你可以选择两个相邻的单元,然后将两个值分别乘以-1
求任意次操作后,整个矩阵的数值的最大和

思路:

显然,两个负数无论相差多选都可以相互抵消
显然,一个0可以抵消任意多个任意距离的负数
所以统计矩阵中负数出现的个数和标记0是否出现即可
奇数个负数时,使整个矩阵最小的数(无论正负)为唯一负数即可

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, m, x;
int flag, cnt, sum;
void solve(){
	flag=cnt=sum=0;
	int mn=INF;
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin>>x;
			if(x==0) flag=1;
			if(x<0) cnt++;
			mn=mymin(mn,fabs(x));
			sum+=fabs(x);
		}
	}
	if(flag || !(cnt&1)) cout<<sum<<endl;
	else{
		cout<<sum-mn-mn<<endl;
	}
	return ;
}
signed main(){
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

C. Knapsack(贪心)

题目大意:

给你n件物品和一个容量为w的背包,每件物品只能装入一次
求将背包装到w / 2 − w w/2-ww/2−w的一种方案,输出物品数量和装入物品的序号

思路:

1、考虑标记是否有存在w / 2 − w w/2-ww/2−w的物品,有就可直接输出
2、考虑是否全部的值加起来都小于w / 2 w/2w/2
3、考虑是否全部的值都大于w ww
前三种情况排除后,贪心:讲物品非递减排序,然后从最小的开始依次装入背包,当装入的东西大于w / 2 w/2w/2时即可输出响应的序列

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
struct node
{
	int da, id;
}a[N];
int n, w;
int sum, flag, idx, l, r;

bool cmp(node a, node b){
	return a.da<b.da;
}

void solve(){
	cin>>n>>w;
	l=(w+1)/2; r=w;
	sum=flag=0; idx=-1;
	for(int i=1; i<=n; i++){
		cin>>a[i].da; a[i].id=i;
		if(a[i].da>=l && a[i].da<=r) flag=1, idx=i;
		if(a[i].da<l) sum+=a[i].da;
	}
	if(flag) {cout<<1<<endl<<idx<<endl; return ;}
	if(sum<l || sum==0 ) {cout<<"-1"<<endl; return;}

	sort(a+1,a+1+n,cmp);
	sum=0;
	for(int i=1; i<=n; i++){
		sum+=a[i].da;
		if(sum>=l && sum<=r){
			cout<<i<<endl;
			for(int j=1; j<=i; j++){
				cout<<a[j].id<<" ";
			}
			cout<<endl;
			return ;
		}
	}
	return ;
}
signed main(){
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

平平无奇的在校大学生