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
",sum-2*sml);
else printf("%lld
",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
",ans);
return 0;
}
E. Xor Tree
首先，我们发现这个图肯定不会出现 (n) 条不同的边。于是我们现在必须看一下是否会出现不连通的情况。我们考虑一下按位贪心（？）首先看最高位，把所有数按照这个位是否为1去分类。若其中一个类是空的，那么我们就继续看下一个位。若不是，那么我们很容易发现，每一个类中不能同时保留大于 1 个。于是我们可以枚举分类讨论，看哪一个类只能保留 1 个，剩下的类就直接单独递归处理。
#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=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 n,a[N];
int calc(int l,int r,int k) {
if(l==r||k==-1) return 1;
int x=r;
while(x>=l&&(a[x]&(1<<k))) x--;
if(x==l-1||x==r) return calc(l,r,k-1);
else {
int ret=1+max(calc(l,x,k-1),calc(x+1,r,k-1));
//cout<<l<<" "<<r<<" "<<ret<<endl;
return ret;
}
}
int main() {
n=read();
rep(i,1,n) a[i]=read();
sort(a+1,a+n+1);
cout<<n-calc(1,n,30);
return 0;
}