Codeforces Round #683——解题报告_codeforces 683contest 题解

作者：盐析白兔 | 2024-02-10 20:49:45

踩

codeforces 683contest 题解

题目链接：

https://codeforces.com/contest/1447

A题——Add Candies

题意：

给你一个数n，表示这个排列为1-n(即第i个数的值为i)，然后我们可以执行无限次一种特殊操作：对第i个数的第j次操作可以使除第i个数之外的其他 n 个数的值加 j 。让你输出一个方案使得所有位置的数的值相等。

题解：

样例给出的方案有点误导，因此我们需要自己构造一个合法的方案，观察操作不难发现，可以想办法尽可能的把每个位置的数都凑成n*(n+1)/2，即对于第i个数可以进行n-1次操作凑出答案(即进行出第i次的所有其他操作)，那么总操作次数就为n，操作方案就是1-n的顺序输出。

代码：


#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define debug puts("ac")
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
int main(){
	int T;cin>>T;
	while(T--){
		int m;cin>>m;
		printf("%d\n",m);
		rp(i,1,m) printf("%d%c",i,i==m?'\n':' ');
	}
	return 0;
}

B题——Numbers Box

题意：

给你一个n*m的矩阵，然后我们有一种操作：让两个相邻的数同时乘上-1，可以进行无限次这种操作，让你求出进行一些操作后这个矩阵的最大和。

题解：

这个题需要发现一个结论：即对于任意两个负数我们可以通过不断地操作使得这两个负数都变成正数，因此我们只需要求出负数的个数，如果为奇数，就需要剩下一个负数，根据贪心的思想，需要把绝对值最小的那个数剩下，那么答案就是所有数的绝对值的和减去 (绝对值最小的那个数) 的绝对值，否则答案就是所有数的绝对值的和。

代码：


#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define debug puts("ac")
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
const int N = 107;
int a[N][N];
vector<int> v;
int main(){
	int T;cin>>T;
	while(T--){
		int n,m;cin>>n>>m;
		rp(i,1,n) rp(j,1,m) cin>>a[i][j];
		ll sum=0;
		v.clear();
		int f=0;
		int MIN=INF;
		rp(i,1,n){
			rp(j,1,m){
				if(a[i][j]==0) f=1;
				sum+=abs(a[i][j]);
				MIN=min(MIN,abs(a[i][j]));
				if(a[i][j]<0) v.push_back(a[i][j]);
			}
		} 
		int len=v.size();
		if(f){
			cout<<sum<<endl;
			continue;
		}
		if(len%2==1) cout<<sum-2*MIN<<endl;
		else cout<<sum<<endl;
	}
	return 0;
}
/*
-1 -1 -2 -3
-1 -2 -3 -4
-2 -3 -4 -5
*/

C题——Knapsack

题意：

给你一个数W以及一个数组w,让你判断从w数组中能否选出一些数，使得这些数的和sum满足 $\left \lceil \frac{W}{2} \right \rceil \leqslant sum \leqslant W$ 。

题解：

解法一：从小到大的贪心（容易想到，但是需要加一个特判）

不难想到的一个贪心的解法就是对数组从小到大排序后，然后判断前缀和中是否有值满足，并记录一下位置就行了。需要注意的是，如果最后还没有符合的或者中间第i个数的前缀和小于 $\left \lceil \frac{W}{2} \right \rceil$ ，而第i+1个数的前缀和大于W的，那么输出-1.

hack: W=100, w={2,99}. 这组数据按照贪心的解法应该是-1，但是实际上直接取第二个数就行了，因此我们需要加一个特判，即如果数组中有数满足条件，直接输出这个数就行了.

优化:其实可以不排序，直接枚举，如果没有超过就加上，否则判断是否符合就行了。


#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define debug puts("ac")
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
const int N = 2e5+7;
struct node{
	int num,pos;
}a[N];
bool cmp(node a,node b){
	return a.num<b.num;
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int n;ll W;scanf("%d%lld",&n,&W);
		int ff=0;
		int ans=0;
		ll l=(W+1)/2;
		ll r=W;
		rp(i,1,n){
			scanf("%d",&a[i].num);
			if(a[i].num>=l&&a[i].num<=r){
				ff=1;
				ans=i;
			}
			a[i].pos=i;
		}
		if(ff){
			printf("1\n");
			printf("%d\n",ans);
			continue;
		}
		sort(a+1,a+1+n,cmp);
		ll sum=0;
		int f=0;
		vector<int> v;
		rp(i,1,n){
			if(sum+a[i].num<l){
				sum+=a[i].num;
				v.push_back(a[i].pos);
			}
			else if(sum+a[i].num>r){
				f=1;
				break;
			}
			else{
				sum+=a[i].num;
				v.push_back(a[i].pos);
				break;
			}
		}
		if(sum<l||sum>r) f=1;
		if(f) printf("-1\n");
		else{
			int len=v.size();
			printf("%d\n",len);
			rp(i,0,len-1) cout<<v[i]<<(i==len-1?"\n":" ");
		}
	}
	return 0;
}
/*
1
3 4
0 1 1 2
-1 -1 -1 2
2 2 2 2
*/

解法二：从大到小的贪心

跟前面的贪心差不多，只不过从大到小排序，这样就不用加特判了，因为如果sum=0+第一个数符合条件，会直接跳出。


#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define debug puts("ac")
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
const int N = 2e5+7;
struct node{
	int num,pos;
}a[N];
bool cmp(node a,node b){
	return a.num>b.num;
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int n;ll W;scanf("%d%lld",&n,&W);
		int ff=0;
		int ans=0;
		ll l=(W+1)/2;
		ll r=W;
		rp(i,1,n){
			scanf("%d",&a[i].num);
			a[i].pos=i;
		}
		sort(a+1,a+1+n,cmp);
		ll sum=0;
		int f=0;
		vector<int> v;
		rp(i,1,n){
			if(sum+a[i].num<l){
				sum+=a[i].num;
				v.push_back(a[i].pos);
			}
			else if(sum+a[i].num>r) continue;
			else{
				sum+=a[i].num;
				v.push_back(a[i].pos);
				break;
			}
		}
		if(sum<l||sum>r) printf("-1\n");
		else{
			int len=v.size();
			printf("%d\n",len);
			rp(i,0,len-1) cout<<v[i]<<(i==len-1?"\n":" ");
		}
	}
	return 0;
}
/*
1
3 4
0 1 1 2
-1 -1 -1 2
2 2 2 2
*/

D题——Catching Cheaters

题意：

给你两个串s和t，让你求出s和t的子串中最大的S值，C是s的子串，D是t的子串，定义S(C,D)表示4*LCS(C,D)-length(C)-length(D).

题解：

定义状态dp[i][j]表示s的前i个字符形成的子串，t的前j个字符形成的子串的S值。

状态转移方程：

if(s[i]==t[j]) dp[i][j]=dp[i-1][j-1]+2. 因为LCS会加1，对答案的贡献+4，而子串长度会各加1，因此对答案的贡献是-2.总的贡献就是+2.

else dp[i][j]=max(dp[i-1][j],dp[i][j-1])-1. 因为LCS不变，而长度会加1，对答案的贡献是-1。

最终答案就是dp数组的最大值。

代码：


#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define debug puts("ac")
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
inline ll lread(){
	ll s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
const int N = 5e3+7;
char s[N],t[N];
int dp[N][N];
int main(){
	int n,m;
	sc(n);sc(m);
	scanf("%s%s",s+1,t+1);
	rp(i,1,n){
		rp(j,1,m){
			if(s[i]==t[j]) dp[i][j]=dp[i-1][j-1]+2;
			else dp[i][j]=max(0,max(dp[i-1][j],dp[i][j-1])-1);
		}
	}
	int MAX=0;
	rp(i,1,n) rp(j,1,m) MAX=max(MAX,dp[i][j]);
	cout<<MAX<<endl;
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/75386