【Codeforces】Codeforces Round #683 Div. 2

https://codeforces.com/contest/1446

A. Add Candies

sb题，输出 \(1,2,...,n\) 就行了。

B. Numbers Box

也是sb题，可以证明，其实题目等同于可以选择任意两个格子然后同时乘以 \(-1\)，也就是说我们可以让整个网格的负数数量小于等于1，depends on 负数数量的奇偶性和有没有0

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<‘0‘||c>‘9‘) {if(c==‘-‘) f=-1; c=getchar();}
    while(c>=‘0‘&&c<=‘9‘) {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int T,n,m,sum,sml;

signed main() {
	T=read();
	while(T--) {
		n=read(), m=read();
		int num=0,c=0;
		sum=0, sml=0x3f3f3f3f;
		rep(i,1,n) rep(j,1,m) {
			int a=read();
			if(a==0) c=1;
			else num+=(a<0);
			sum+=abs(a);
			sml=min(sml,abs(a));
		}
		if(num%2&&!c) printf("%lld\n",sum-2*sml);
		else printf("%lld\n",sum);
	}
	return 0;
}

C. Knapsack

也是sb题。我们发现，我们对于每一个物品，若它比背包总大小小，那么我们尝试放进去。若放进去后的总重量为 \(t\)。分类讨论。若 \(t>w\)，那么这个物品的重量就大于 \(w/2\) 了；若 \(t\) 满足条件，那么直接输出；其余情况，放进去肯定不会有问题。

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=200009;

inline int read() {
    register int x=0, f=1; register char c=getchar();
    while(c<‘0‘||c>‘9‘) {if(c==‘-‘) f=-1; c=getchar();}
    while(c>=‘0‘&&c<=‘9‘) {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int T,n,w,k,a[N];
vector <int> ans;

signed main() {
	T=read();
	while(T--) {
		n=read(), w=read();
		k=(w+1)/2;
		rep(i,1,n) a[i]=read();
		ans.clear();
		int sum=0;
		bool flg=0;
		rep(i,1,n) {
			if(a[i]>w) continue;
			if(sum+a[i]>w) {
				ans.clear();
				ans.push_back(i);
				flg=1;
				break;
			}
			sum+=a[i];
			ans.push_back(i);
			if(sum>=k) {
				flg=1;
				break;
			}
		}
		if(!flg) puts("-1");
		else {
			cout<<ans.size()<<endl;
			for(int i=0;i<ans.size();i++) printf("%lld ",ans[i]);
			puts("");
		}
	}
	return 0;
}

D. Catching Cheaters

也蛮简单的题目。很明显 DP。\(f(i,j)\) 表示 A 串前 i 个字符，B 串前 j 个字符，以 i 和 j 结尾的子串，最大的 \(s\) 值事多少。

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=5009;

int n,m,f[N][N],ans;
char a[N],b[N]; 

int main() {
	scanf("%d%d%s%s",&n,&m,a+1,b+1);
	rep(i,1,n) rep(j,1,m) {
		if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+2;
		f[i][j]=max(f[i][j],max(f[i-1][j],f[i][j-1])-1);
		ans=max(ans,f[i][j]);
	}
	printf("%d\n",ans);
	return 0;
}

【Codeforces】Codeforces Round #683 Div. 2

原文：https://www.cnblogs.com/TetrisCandy/p/13991472.html