T1 Black Rock Shooter
Solution
GSS3原题qwq
Code
//By Menteur_Hxy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
#define ls (cur<<1)
#define rs (cur<<1|1)
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;
int read() {
int x=0,f=1; char c=getchar();
while(!isdigit(c)) {if(c=='-')f=-f; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*f;
}
const int INF=0x3f3f3f3f;
const int N=500010;
int n,m,asu,amx,als,ars,ans;
int sum[N<<2],lsu[N<<2],rsu[N<<2],mx[N<<2];
void pushup(int cur) {
sum[cur]=sum[ls]+sum[rs];
lsu[cur]=max(lsu[ls],sum[ls]+lsu[rs]);
rsu[cur]=max(rsu[rs],sum[rs]+rsu[ls]);
mx[cur]=max(max(mx[ls],mx[rs]),max(max(lsu[ls],rsu[rs]),rsu[ls]+lsu[rs]));
}
void build(int cur,int l,int r) {
if(l==r) {sum[cur]=lsu[cur]=rsu[cur]=mx[cur]=read();return ;}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(cur);
}
void merge(int cur) {
if(asu==-INF) asu=sum[cur],amx=mx[cur],als=lsu[cur],ars=rsu[cur];
else {
int a,b,c,d;
a=asu+sum[cur];
b=max(als,asu+lsu[cur]);
c=max(rsu[cur],ars+sum[cur]);
d=max(max(amx,mx[cur]),max(max(als,rsu[cur]),ars+lsu[cur]));
asu=a,als=b,ars=c,amx=d;
}
ans=max(max(als,ars),max(ans,amx));
}
void query(int cur,int l,int r,int L,int R) {
if(L<=l&&r<=R) {merge(cur);return ;}
int mid=(l+r)>>1;
if(L<=mid) query(ls,l,mid,L,R);
if(R>mid) query(rs,mid+1,r,L,R);
}
void update(int cur,int l,int r,int x,int k) {
if(l==x&&r==x) {sum[cur]=k,lsu[cur]=k,rsu[cur]=k,mx[cur]=k;return ;}
int mid=(l+r)>>1;
if(x<=mid) update(ls,l,mid,x,k);
else if(x>mid) update(rs,mid+1,r,x,k);
pushup(cur);
}
signed main() {
freopen("BRS.in","r",stdin);
freopen("BRS.out","w",stdout);
n=read(),m=read();
build(1,1,n);
F(i,1,m) {
ans=asu=amx=als=ars=-INF;
int opt=read(),x=read(),y=read();
if(opt==1) query(1,1,n,x,y),printf("%lld
",ans);
else update(1,1,n,x,y);
}
return 0;
}
T2 Fy's dota2
Solution
类似斐波那契的构造矩阵就行
(注意不要赋错初值qwq)
Code
//By Menteur_Hxy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
#define ls (cur<<1)
#define rs (cur<<1|1)
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define R(i,a,b) for(register int i=(b);i>=(a);i--)
using namespace std;
int read() {
int x=0,f=1; char c=getchar();
while(!isdigit(c)) {if(c=='-')f=-f; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*f;
}
const int MOD=7777777;
struct Matrix{
int da[11][11];
void clear() {F(i,1,10) F(j,1,10) da[i][j]=0;}
Matrix operator * (const Matrix oth) {
Matrix ret;ret.clear();
F(i,1,10) F(j,1,10) F(k,1,10)
ret.da[i][j]+=da[i][k]*oth.da[k][j]%MOD,ret.da[i][j]%=MOD;
return ret;
}
void print() {
F(i,1,10) {
F(j,1,10) cout<<da[i][j]<<" ";
cout<<endl;
}cout<<endl;
}
};
Matrix Qpow(Matrix ret,int d) {
Matrix res; res.clear();
F(i,1,10) res.da[i][i]=1;
while(d) {
if(d&1) res=res*ret;
ret=ret*ret; d>>=1;
}
return res;
}
signed main() {
// freopen("fyfy.in","r",stdin);
// freopen("fyfy.out","w",stdout);
int k=read(),n=read();
Matrix nxt;nxt.clear();
F(i,1,k) nxt.da[i][1]=1;
F(i,1,k) nxt.da[i][i+1]=1;
Matrix ans=Qpow(nxt,n);
printf("%lld",ans.da[1][1]%MOD);
return 0;
}
T3 Olddriver’s books
Solution
好像叫做扫描线什么的，这道题比较水n3就能过(我写的n2)
(注意不要少想一种情况qwq)
Code
//By Menteur_Hxy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#define int long long
#define ls (cur<<1)
#define rs (cur<<1|1)
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define R(i,a,b) for(register int i=(b);i>=(a);i--)
using namespace std;
int read() {
int x=0,f=1; char c=getchar();
while(!isdigit(c)) {if(c=='-')f=-f; c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*f;
}
const int INF=0x3f3f3f3f;
const int N=1100;
int n,cnt;
int hi[N],lo[N];
int vis[N];
struct xid{int da,id;}idx[N<<1];
struct yid{int da,fl,id;}idy[N<<1];
bool cmp1(xid a,xid b) {return a.da<b.da;}
bool cmp2(yid a,yid b) {return a.da<b.da;}
signed main() {
freopen("olddriver.in","r",stdin);
freopen("olddriver.out","w",stdout);
n=read();
F(i,1,n) {
idx[++cnt].da=read(),idx[cnt].id=i;
idy[cnt].da=read(),idy[cnt].fl=1,idy[cnt].id=i;
idx[++cnt].da=read(),idx[cnt].id=i;
idy[cnt].da=read(),idy[cnt].fl=-1,idy[cnt].id=i;
}
sort(idx+1,idx+1+cnt,cmp1);
sort(idy+1,idy+1+cnt,cmp2);
int ans=0;
F(i,1,cnt) {
int sum=0,l=0,tmp=0;
F(j,1,cnt) if(vis[idy[j].id]) {
if(!tmp) l=idy[j].da;
tmp+=idy[j].fl;
if(!tmp) sum+=idy[j].da-l;
}
ans+=sum*(idx[i].da-idx[i-1].da);
vis[idx[i].id]^=1ll;
}
printf("%lld",ans);
return 0;
}