CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)
vp时间：2023.7.11
总结记录：考场上过了前三题，第四题没看懂题面，感觉看懂了就会了，第五题不会dp爆寄，还是要总结提升dp能力
A.Tenzing and Tsondu
因为宝可梦之间对抗是小的死掉，大的变成差，所以我们发现，把 \(a_1,a_2,b_1,b_2\) 比出结果，等价于把 \(a_1+a_2,b_1+b_2\) 比较
因此，我们可以直接把所有宝可梦的能力值加起来比较，还是相当显然的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100;
ll a[maxn],b[maxn],sum=0,T,n,m;
int main(){
scanf("%lld",&T);
while(T-->0){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) sum+=a[i];
for(int i=1;i<=m;i++) scanf("%lld",&b[i]);
for(int i=1;i<=m;i++) sum-=b[i];
if(sum>0) puts("Tsondu");
else if(sum==0) puts("Draw");
else puts("Tenzing");
for(int i=1;i<=n;i++) a[i]=0;
for(int i=1;i<=m;i++) b[i]=0;
sum=0;
}
return 0;
}
B.Tenzing and Books
我们发现，因为按位或满足以下性质：
1、 \(a|b|a = a|b\)
2、 每一位之间独立
3、任何数与1按位或都是1，只有0和0按位或才能产生一个0
因此，我们考虑把取数的约束关系给破坏掉，可以发现如果我们取了 \(a_i\) ，就一定会取 \(a_1,a_2,\cdots ,a_{i-1}\) ，我们可以维护每个序列的按位或前缀和，然后先后的约束关系就没有了
接下来我们考虑如何凑数，不难发现，如果 \(x\) 的某一位上是 1 ,那么待检验数的对应位上是任何数都无所谓；但如果 \(x\) 的某一位上是 0 ,那么待检验数的对应位上是就只能是0。不然就不能取这个数。
因此，我们要保证选取的数都满足上述条件，如果都取了还是凑不到，那么就一定无解。
时间复杂度 \(O(n \log x)\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5;
ll a[maxn],b[maxn],c[maxn],sum=0,T,n,m,bits[32],bita[maxn][32],bitb[maxn][32],bitc[maxn][32],visa[maxn],visb[maxn],visc[maxn];
int main(){
scanf("%lld",&T);
while(T-->0){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
for(int i=1;i<=n;i++) a[i]=(a[i]|a[i-1]),b[i]=(b[i]|b[i-1]),c[i]=(c[i]|c[i-1]);
for(int i=0;i<=31;i++) bits[i]=0;
for(int i=0;i<=31;i++) bits[i]=(m>>i&1);
for(int i=1;i<=n;i++){
for(int j=0;j<=31;j++){
if(a[i]>>j&1) bita[i][j]=1;
if(b[i]>>j&1) bitb[i][j]=1;
if(c[i]>>j&1) bitc[i][j]=1;
}
}
for(int i=1;i<=n;i++) visa[i]=visb[i]=visc[i]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=31;j++){
if(bita[i][j]==1&&bits[j]==0) visa[i]=0;
if(bitb[i][j]==1&&bits[j]==0) visb[i]=0;
if(bitc[i][j]==1&&bits[j]==0) visc[i]=0;
}
}
ll temp=0;
for(int i=1;i<=n;i++){
temp=temp|(visa[i]*a[i]);
temp=temp|(visb[i]*b[i]);
temp=temp|(visc[i]*c[i]);
}
if(temp==m||m==0) puts("Yes");
else puts("No");
for(int i=1;i<=n;i++) a[i]=0;
for(int i=1;i<=n;i++) b[i]=0;
for(int i=1;i<=n;i++) c[i]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=31;j++){
visa[i]=0,visb[i]=0,visc[i]=0;
bita[i][j]=bitb[i][j]=bitc[i][j]=0;
}
}
}
return 0;
}
C.Tenzing and Balls
不难发现，这道题目中对于操作次数没有限制，只询问了最优解，因此考虑dp
为了方便，调换题目中 \(i,j\) 的大小关系。
设状态 \(f_i\) 表示前 \(i\) 个数里最多能删 \(f_i\) 个数
我们可以得到状态转移方程：
\(f_i = \max(f_{j-1}+i-j+1,f_{i-1})\)
其中 \(a_i = a_j\)
我们发现，这个方程的复杂度瓶颈在于如何快速求出前半段，我们可以额外维护一个数组，用来表示每个不同的数的最大 \(f_{j-1}-j+1\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=1e9;
int a[maxn],f[maxn],pos[maxn];
int main(){
int T;
scanf("%d",&T);
while(T-->0){
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) f[i]=pos[i]=-inf;
for(int i=1;i<=n;i++){
f[i]=max(pos[a[i]]+1+i,f[i-1]);
pos[a[i]]=max(f[i-1]-i,pos[a[i]]);
ans=max(ans,f[i]);
}
printf("%d\n",ans);
}
return 0;
}