CodePlus 2017 11 月赛 div2 题解

本文主要是介绍CodePlus 2017 11 月赛 div2 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

div2的题目总体上来说比较简单。考试时都想出了正解，但是由于TUOJ考试期间不能提交导致心态爆炸，最后T4没有处理好。最后得分320，rank12，T桖到手。

T1 晨跑

就是求三个数的最小公倍数。连代码都不想放。

T2 汀博尔

timber n.木料，木材

看到数据范围比较大，容易想到套个logN的复杂度，那么显然二分答案。验证O(n)而且非常简单，只要这一天某个木材超过最低限度就使用它，看最后有没有超过S就可以了。

注意如果上界无脑取1e18会爆long long，更准确且不会爆long long的上界应该是只用一根木材就满足要求的时间的最小值。

#include<stdio.h>
#include<algorithm>
#define ll long long
#define MAXN 200005
using namespace std;int N;
ll S,Lim,H[MAXN],A[MAXN]; bool check(ll x)
{int i;ll tot=S;for(i=1;i<=N;i++)if(H[i]+x*A[i]>=Lim){tot-=(H[i]+x*A[i]);if(tot<=0)return true;}return false;
}int main()
{int i;scanf("%d%lld%lld",&N,&S,&Lim);for(i=1;i<=N;i++)scanf("%lld",&H[i]);for(i=1;i<=N;i++)scanf("%lld",&A[i]);ll L=0,R=1e18,mid;for(i=1;i<=N;i++)R=min(R,max((S-H[i])/A[i]+1,(Lim-H[i])/A[i]+1));while(L<=R){mid=L+R>>1;if(check(mid))R=mid-1;else L=mid+1;}printf("%lld",L);
}

T3 找爸爸

显然的DP。

显然不会出现上下两个对齐的位置都是空格的情况，因为这样的话去掉它们一定更优。那么对于每一个对对齐的位置，只会出现三种情况：上面是空格且下面不是、下面是空格且上面不是、上下都不是空格。于是很容易定出状态，考试时为了方便，开了两维分别记录上下位置是否是空格。

定义 $f[i][j][0/1][0/1]$ 为讨论完上面字符串的前i个、下面字符串的前j个且对齐，记录上下两字符串空格状态最小花费。转移具体参见代码。

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define MAXN 3005
using namespace std;char a[MAXN],b[MAXN];
int A,B,f[MAXN][MAXN][2][2],Hash[500],d[10][10],Ans;int main()
{int i,j,la,lb,x,y;scanf("%s%s",&a[1],&b[1]);Hash['A']=1;Hash['T']=2;Hash['G']=3;Hash['C']=4;la=strlen(a+1);lb=strlen(b+1);for(i=1;i<=4;i++)for(j=1;j<=4;j++)scanf("%d",&d[i][j]);scanf("%d%d",&A,&B);for(i=0;i<=la;i++)for(j=0;j<=lb;j++)f[i][j][0][0]=f[i][j][0][1]=f[i][j][1][0]=f[i][j][1][1]=-1e9;f[0][0][0][0]=0;for(i=0;i<=la;i++)for(j=0;j<=lb;j++){if(i==j&&i==0)continue;if(i)x=Hash[a[i]];if(j)y=Hash[b[j]];if(i&&j){f[i][j][0][0]=max(f[i][j][0][0],f[i-1][j-1][0][0]+d[x][y]);f[i][j][0][0]=max(f[i][j][0][0],f[i-1][j-1][0][1]+d[x][y]);f[i][j][0][0]=max(f[i][j][0][0],f[i-1][j-1][1][0]+d[x][y]);}if(i){f[i][j][0][1]=max(f[i][j][0][1],f[i-1][j][0][0]-A);f[i][j][0][1]=max(f[i][j][0][1],f[i-1][j][0][1]-B);f[i][j][0][1]=max(f[i][j][0][1],f[i-1][j][1][0]-A);}if(j){f[i][j][1][0]=max(f[i][j][1][0],f[i][j-1][0][0]-A);f[i][j][1][0]=max(f[i][j][1][0],f[i][j-1][0][1]-A);f[i][j][1][0]=max(f[i][j][1][0],f[i][j-1][1][0]-B);}}Ans=max(f[la][lb][0][0],max(f[la][lb][0][1],f[la][lb][1][0]));printf("%d",Ans);
}

T4 可做题

有了小奇挖矿、青蛙跳两道题的经验，猜到n多半是没有用的，大多数空格都是没用的。事实上确实是这样。一段空格的作用与一个空格的作用是完全相同的。简单地说是根据两点：异或的逆运算是它本身、空格里的数可以任选。

因此，以前置空格为界划分区间，每一个区间独立取最小值就能得到答案的最小值。对于每一个区间，都是解决这种形式的问题：

给定 $a_1,a_2,a_3,…,a_n$ ，K可在非负数内任选，求出 $a_1xorK+a_2xorK+a_3xorK+…+a_nxorK$ 的最小值。

由于异或是按位的，每一位都不会对其他位造成任何影响，因此很多与异或有关的极值问题都会用到贪心的思想。考虑把 $a$ 数组全部写成二进制形式，逐位统计出1出现的个数（或0出现的个数）。如果这一位上0比1多，那么 $K$ 的这一位取0更优；反之取1更优。

注意处理细节。第一段区间开头不是空格的情况特判处理一下就好。

#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXM 100005
#define ll long long
using namespace std;struct node{int pos,v;}A[MAXM];
bool operator<(node x,node y)
{return x.pos<y.pos;
}int N,M;ll Cnt[60];
ll Ans;int main()
{ll i,j,tmp=0,cnt=1;ll sum;scanf("%d%d",&N,&M);for(i=1;i<=M;i++)scanf("%d%d",&A[i].pos,&A[i].v);sort(A+1,A+M+1);i=1;if(A[1].pos==1){tmp=Ans=A[1].v;i=2;while(A[i].pos==A[i-1].pos+1)tmp^=A[i].v,i++,Ans+=tmp;}for(tmp=0;i<=M+1;i++){if(A[i].pos==A[i-1].pos+1){cnt++;tmp^=A[i].v;for(j=0;j<32;j++)if(tmp>>j&1)Cnt[j]++;}else{cnt++;sum=0;for(j=0;j<32;j++)sum+=min(Cnt[j],cnt-Cnt[j])*(1ll<<j);Ans+=sum;cnt=1;tmp=0;memset(Cnt,0,sizeof(Cnt));for(j=0;j<32;j++)if(A[i].v>>j&1)Cnt[j]++;tmp^=A[i].v;}}printf("%lld",Ans);
}