Codeforces Round #721 (Div. 2)
A. And Then There Were K
思路
水题，要将最高位按位&掉，就要构造个(1<
策略 后走的可以将置1在先走的对位，再次构成回文串。最后只剩两个0时，绝杀后手少花费2分
一开始是回文串，
- 如果0的个数位偶数的话，那么先走的多花费2分，先走的输，
- 如果0为奇数的话，先走的花费1分，构造成回文串，将自己变为后走的，总的下来，开始先走会少花费1分，先走的嬴。
- 特判只有一个0的情况。
#include
using namespace std;
const int N=1e3+7;
int t,n;
char a[N];
int main(){
cin>>t;
while(t--){
cin>>n;
cin>>a+1;
int cnt=0;
for(int i=1;
i<=n;
i++){
if(a[i]=='0') cnt++;
}
if(cnt%2==0){
cout<<"BOB\n";
}else if(cnt==1){
cout<<"BOB\n";
}else{
cout<<"ALICE\n";
}
}
}
B2. Palindrome Game (hard version)
思路：
其实和上题差不多。
考虑不是回文串时，先手的可以决定当要构造成回文串时，自己能处于先手还是后手。所以先手有绝对的优势，除一种情况外平局，就是有2个0，且不是回文。
代码实现：
#include
using namespace std;
const int N=1e3+7;
int t,n;
char a[N];
int gao(){
int cnt=0;
for(int i=1;
i<=n/2;
i++){
if(a[i]!=a[n-i+1]) cnt++;
}
return cnt;
}
int main(){
cin>>t;
while(t--){
cin>>n;
cin>>a+1;
int cnt=0;
for(int i=1;
i<=n;
i++){
if(a[i]=='0') cnt++;
}
if(gao()==0){if(cnt%2==0){
cout<<"BOB\n";
}else if(cnt==1){
cout<<"BOB\n";
}else{
cout<<"ALICE\n";
}
}else if(gao()==1){
cnt--;
if(cnt==1){
cout<<"DRAW\n";
}else{
cout<<"ALICE\n";
}
}else{
cout<<"ALICE\n";
}
}
}
C. Sequence Pair Weight
思路：
【比赛|Codeforces Round #721 (Div. 2)】对于数 a i a_i ai?,与 a j ， j < i a_j，j 代码
#include
#include E. Partition Game(dp+线段树优化) 题目链接
思路：
首先想到的是 O ( n 2 k ) O(n^2k) O(n2k)的做法。
d p [ i ] [ j ] dp[i][j] dp[i][j]为前i个数划分为j段的答案。
那么状态转移为:d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ z ] [ j ? 1 ] + c o u n t ( z + 1 , i ) ) , z < i dp[i][j]=min(dp[i][j],dp[z][j-1]+count(z+1,i)),z 但是超时，这就要像怎么优化。
线段树优化 我们能将其 d p [ z ] [ j ? 1 ] dp[z][j-1] dp[z][j?1],放入线段树里面，之后要修改线段树的值，每次出现 a i a_i ai?，我们就将其前面出现的位置 l a s t i ? 1 last_i-1 lasti??1的每个数都 + ( i ? l a s t i ) +(i-last_i) +(i?lasti?)。最后区间查询 [ 1 , i ? 1 ] [1,i-1] [1,i?1]的最小值
#include
#include
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
const int inf=1e9;
const int N=35007;
int n,k;
int last[N],ma[N];
int a[N],b[N],dp[N][107],tree[4*N],tap[4*N];
void init(int k,int l,int r){
tap[k]=0;
if(l==r){
tree[k]=b[l];
return ;
}
init(lch,l,mid);
init(rch,mid+1,r);
tree[k]=min(tree[lch],tree[rch]);
}
int pushdown(int k){
if(tap[k]){
tree[lch]+=tap[k];
tree[rch]+=tap[k];
tap[lch]+=tap[k];
tap[rch]+=tap[k];
tap[k]=0;
}
}
int query(int k,int l,int r,int ql,int qr){
if(ql>qr) return 0;
if(ql<=l&&r<=qr){
return tree[k];
}
pushdown(k);
int mi=1e9;
if(ql<=mid) mi=min(mi,query(lch,l,mid,ql,qr));
if(mid+1<=qr) mi=min(mi,query(rch,mid+1,r,ql,qr));
return mi;
}
void update(int k,int l,int r,int ql,int qr,int val){
if(ql>qr) return ;
if(ql<=l&&r<=qr){
tree[k]+=val;
tap[k]+=val;
return ;
}
pushdown(k);
if(ql<=mid) update(lch,l,mid,ql,qr,val);
if(mid+1<=qr) update(rch,mid+1,r,ql,qr,val);
tree[k]=min(tree[lch],tree[rch]);
}
int main(){
scanf("%d %d",&n,&k);
for(int i=1;
i<=n;
i++){
scanf("%d",&a[i]);
last[i]=ma[a[i]];
ma[a[i]]=i;
} for(int i=1;
i<=n;
i++){
if(last[i]) dp[i][1]=dp[i-1][1]+i-last[i];
else dp[i][1]=dp[i-1][1];
}
for(int j=2;
j<=k;
j++){
for(int i=1;
i<=n;
i++) b[i]=dp[i][j-1];
init(1,1,n);
for(int i=1;
i<=n;
i++){
update(1,1,n,1,last[i]-1,i-last[i]);
dp[i][j]=query(1,1,n,1,i-1);
}
}
printf("%d\n",dp[n][k]);
}
推荐阅读
- CPU底层|【CPU底层那些事（数组和指针真的一样吗（）】）
- 单片机|单片机课设-60秒倒计时器
- 单片机|单片机课设-电子时钟设计（仿真图、代码全）
- 蓝桥杯|蓝桥杯C/C++A组省赛历年真题题解（2013~2021）
- leetcode|leetcode 344.反转字符串（reverse string）C语言
- ACM专题学习|Mayor‘s posters--线段树(区间修改)+离散化
- ACM专题学习|青蛙的约会--扩展欧几里得
- ACM专题学习|地毯--二维差分
- ACM专题学习|Buy Tickets--线段树（单点修改）