1001 Senior’s Array

这题暴力枚举替换哪一个,然后dp就行。。O(n^2)的复杂度
这题一开始看错了,一直用线段树WA了好多发,好伤。

//author: CHC
//First Edit Time: 2015-07-11 20:00
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+4;
const int MAXM=1e+5;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
LL A[MAXN]; LL B[MAXN]; LL dp[MAXN];
int n,p,t;
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++){
scanf("%I64d",&A[i]);
B[i]=A[i];
}
LL ans=p;
for(int i=1;i<=n;i++){
B[i]=(LL)p;
dp[0]=0;
for(int j=1;j<=n;j++){
dp[j]=max(B[j],dp[j-1]+B[j]);
ans=max(ans,dp[j]);
}
B[i]=A[i];
}
printf("%I64d\n",ans);
}
return 0;
}

1002 Senior’s Gun

这题排序,然后攻击力最大的打防御力最小的,一个O(n)就可以了。
这题我数组范围开小了导致最后Judge大数据的时候WA了。

//author: CHC
//First Edit Time: 2015-07-11 20:17
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=100000+10;
const int MAXM=1e+5;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
LL A[MAXN],B[MAXN];
int n,m;
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%I64d",&A[i]);
for(int i=0;i<m;i++)scanf("%I64d",&B[i]);
sort(A,A+n);
sort(B,B+m);
LL sum=0;
for(int i=n-1,j=0;i>=0&&j<m;i--,j++){
if(A[i]>=B[j])sum+=A[i]-B[j];
else break;
}
printf("%I64d\n",sum);
}
return 0;
}

1003 Senior’s String

这题当时我没有做出,其实题解写的很清楚了。

//author: CHC
//First Edit Time: 2015-07-14 00:06
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1010;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
const int mod=1e+9 + 7;
char str1[MAXN],str2[MAXN];
int dp[MAXN][MAXN],P[MAXN][MAXN],dp2[MAXN][MAXN];
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf(" %s %s",str1+1,str2+1);
int lenx=strlen(str1+1);
int leny=strlen(str2+1);
memset(dp,0,sizeof(dp));
for(int i=1;i<=lenx;i++)
for(int j=1;j<=leny;j++){
if(str1[i]==str2[j])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
memset(P,0,sizeof(P));
for(int i=1;i<=lenx;i++)
for(int j=1;j<=leny;j++)
if(str1[i]==str2[j])P[i][j]=j;
else P[i][j]=P[i][j-1];
memset(dp2,0,sizeof(dp2));
for(int i=1;i<=lenx;i++)
for(int j=1;j<=leny;j++){
if(dp[i][j]==0){
dp2[i][j]=1;
continue;
}
if(dp[i][j]==dp[i-1][j])dp2[i][j]+=dp2[i-1][j];
dp2[i][j]%=mod;
if(P[i][j]&&dp[i][j]==dp[i-1][P[i][j]-1]+1){
if(dp2[i-1][P[i][j]-1]==0)
dp2[i][j]+=dp2[i-1][P[i][j]-1]+1;
else dp2[i][j]+=dp2[i-1][P[i][j]-1];
}
dp2[i][j]%=mod;
//printf("%d %d %d %d\n",i,j,dp2[i][j],dp[i][j]==dp[i-1][j]);
}
printf("%d\n",dp2[lenx][leny]);
}
return 0;
}

1004 Senior’s Fish

这题当时我也没做出来,后来看题解的时候第一感觉就是复杂度很高。后来才反应过来。。。过了的时候那种极度不科学的感觉那种冲击。。

//author: CHC
//First Edit Time: 2015-07-14 13:41
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=100000+100;
const LL LL_INF=numeric_limits<LL>::max();
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
long long X[4],Y[4];
long long tx[MAXN],ty[MAXN];
struct Tree {
long long maX[4],maY[4],addx,addy,sum[4];
}tr[MAXN<<2];
void pushup(int rt){
for(int i=0;i<4;i++){
tr[rt].maX[i]=max(tr[rt<<1].maX[i],tr[rt<<1|1].maX[i]);
tr[rt].maY[i]=max(tr[rt<<1].maY[i],tr[rt<<1|1].maY[i]);
tr[rt].sum[i]=tr[rt<<1].sum[i]+tr[rt<<1|1].sum[i];
}
}
void pushdown(int rt){
if(tr[rt].addx){
tr[rt<<1].addx+=tr[rt].addx;
tr[rt<<1|1].addx+=tr[rt].addx;
for(int i=0;i<4;i++){
tr[rt<<1].maX[i]+=tr[rt].addx;
tr[rt<<1|1].maX[i]+=tr[rt].addx;
}
tr[rt].addx=0;
}
if(tr[rt].addy){
tr[rt<<1].addy+=tr[rt].addy;
tr[rt<<1|1].addy+=tr[rt].addy;
for(int i=0;i<4;i++){
tr[rt<<1].maY[i]+=tr[rt].addy;
tr[rt<<1|1].maY[i]+=tr[rt].addy;
}
tr[rt].addy=0;
}
}
void build(int L,int R,int rt){
tr[rt].addy=tr[rt].addx=0;
if(L==R){
for(int i=0;i<4;i++){
tr[rt].maX[i]=tx[L];
tr[rt].maY[i]=ty[L];
tr[rt].sum[i]=1;
}
return ;
}
int mid=(L+R)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int L,int R,int rt,int l,int r,long long v,int flag){
if(l<=L&&R<=r){
if(flag==0){
for(int i=0;i<4;i++) tr[rt].maX[i]+=v;
tr[rt].addx+=v;
}
else {
for(int i=0;i<4;i++) tr[rt].maY[i]+=v;
tr[rt].addy+=v;
}
return ;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)update(lson,l,r,v,flag);
if(r>mid)update(rson,l,r,v,flag);
pushup(rt);
}
void adjust(int L,int R,int rt){
int mid=(L+R)>>1;
for(int i=0;i<4;i++){
if(tr[rt].maX[i]>X[i]||tr[rt].maY[i]>Y[i]){
if(L==R){
tr[rt].maX[i]=LL_INF+1;
tr[rt].maY[i]=LL_INF+1;
tr[rt].sum[i]=0;
continue;
}
pushdown(rt);
adjust(lson);adjust(rson);
pushup(rt);
}
}
}
LL query(int L,int R,int rt,int l,int r,int f){
if(l<=L&&R<=r)return tr[rt].sum[f];
int mid=(L+R)>>1;
LL ans=0;
if(l<=mid)ans+=query(lson,l,r,f);
if(r>mid)ans+=query(rson,l,r,f);
return ans;
}
int main()
{
int n,m,t;
int xx1,xx2,yy1,yy2;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
scanf("%d%d%d%d",&xx1,&yy1,&xx2,&yy2);
X[0]=xx2;Y[0]=yy2;
X[1]=xx1-1;Y[1]=yy2;
X[2]=xx2;Y[2]=yy1-1;
X[3]=xx1-1;Y[3]=yy1-1;
for(int i=1;i<=n;i++){
scanf("%I64d%I64d",&tx[i],&ty[i]);
}
build(1,n,1);
int type,d,tl,tr;
scanf("%d",&m);
while(m--){
scanf("%d",&type);
if(type==1){
scanf("%d%d%d",&tl,&tr,&d);
update(1,n,1,tl,tr,(LL)d,0);
}
if(type==2){
scanf("%d%d%d",&tl,&tr,&d);
update(1,n,1,tl,tr,(LL)d,1);
}
if(type==3){
adjust(1,n,1);
scanf("%d%d",&tl,&tr);
LL ans=query(1,n,1,tl,tr,0)-query(1,n,1,tl,tr,1)-query(1,n,1,tl,tr,2)+query(1,n,1,tl,tr,3);
printf("%I64d\n",ans);
}
}
}
return 0;
}