A:牛牛的方程式
裴蜀定理裸题，注意判断一下gcd=0的情况，剩下然后我们判断一下是否整除
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL gcd(LL x,LL y){
if(!y)return x;
return gcd(y,x%y);
}
int main(){
int T;scanf("%d",&T);
while(T--){
LL x,y,z,d;
scanf("%lld%lld%lld%lld",&x,&y,&z,&d);
if(x<0)x=-x;if(y<0)y=-y;if(z<0)z=-z;
LL g=gcd(x,gcd(y,z));
if(!g){if(d)puts("NO");else puts("YES");}
else{if(d%g==0)puts("YES");else puts("NO");}
}
return 0;
}B:牛牛的猜球游戏
有点小细节，我们只需要维护一个类似于置换的东西就可以了，具体我们可以用st表，线段树，前缀和等方法维护
考试的时候发现细节有点难考虑，直接码上了一个线段树，具体就是线段树的常规操作！
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
struct swp{int x,y;}a[N];
struct node{int p[10];}t[N<<2];
int n,m,Ans[10];
node merge(node a,node b){
node c;
for(int i=0;i<10;i++)c.p[i]=b.p[a.p[i]];
return c;
}
void build(int rt,int l,int r){
if(l==r){
for(int i=0;i<10;i++)t[rt].p[i]=i;
swap(t[rt].p[a[l].x],t[rt].p[a[l].y]);
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
t[rt]=merge(t[rt<<1],t[rt<<1|1]);
}
node ask(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R)return t[rt];
int mid=(l+r)>>1;
if(R<=mid)return ask(rt<<1,l,mid,L,R);
if(L>mid)return ask(rt<<1|1,mid+1,r,L,R);
return merge(ask(rt<<1,l,mid,L,R),ask(rt<<1|1,mid+1,r,L,R));
}
int read(){
int x=0,c;
while(!isdigit(c=getchar()));
while(isdigit(c))x=x*10+c-48,c=getchar();
return x;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)a[i].x=read(),a[i].y=read();
build(1,1,n);
while(m--){
int l=read(),r=read();
node c=ask(1,1,n,l,r);
for(int i=0;i<=9;i++)Ans[c.p[i]]=i;
for(int i=0;i<=9;i++)printf("%d%c",Ans[i]," \n"[i==9]);
}
return 0;
}C:牛牛的凑数游戏
考虑mex的一个性质
直接给出结论：我们按照区间中的数排序，如果我们统计直接的mex，如果这个数没有大于之前的mex+1那么我们显然是可以继续拼接下来更新一下新的mex，因此我们有了平方log的做法，然后我们考虑这个过程每次统计的是1个sum，这个增长的速度大约是log或是ln的，于是我们用主席树维护区间的size和sum加速这个模拟的过程就可以了！
接下来是考试的时候的代码，拼了暴力，大家可以看看，或许能帮助更好地理解
代码：
namespace force{
int b[N];
void solve(){
while(m--){
int l,r,tp=0;
scanf("%d%d",&l,&r);
for(int i=l;i<=r;i++)b[++tp]=a[i];
sort(b+1,b+tp+1);
LL lst=0,ans;bool fl=false;
for(int i=1;i<=tp;i++){
if(b[i]>lst+1){ans=lst+1;fl=true;break;}
lst+=(LL)b[i];
}
if(!fl)ans=lst+1;
printf("%lld\n",ans);
}
}
}
namespace subtask1{
int Root[N],tot,lim=1e9;
struct seg{
int siz[N<<6],ls[N<<6],rs[N<<6];LL sum[N<<6];
void insert(int rt,int pre,int l,int r,int x){
siz[rt]=siz[pre]+1;sum[rt]=sum[pre]+(LL)x;
if(l==r)return;
int mid=(l+r)>>1;
ls[rt]=ls[pre];rs[rt]=rs[pre];
(x<=mid)?insert(ls[rt]=++tot,ls[pre],l,mid,x):insert(rs[rt]=++tot,rs[pre],mid+1,r,x);
}
int asksiz(int rt,int pre,int l,int r,int L,int R){
if(L<=l&&r<=R)return siz[rt]-siz[pre];
int mid=(l+r)>>1,res=0;
if(L<=mid)res+=asksiz(ls[rt],ls[pre],l,mid,L,R);
if(R>mid)res+=asksiz(rs[rt],rs[pre],mid+1,r,L,R);
return res;
}
LL asksum(int rt,int pre,int l,int r,int L,int R){
if(L<=l&&r<=R)return sum[rt]-sum[pre];
int mid=(l+r)>>1;LL res=0;
if(L<=mid)res+=asksum(ls[rt],ls[pre],l,mid,L,R);
if(R>mid)res+=asksum(rs[rt],rs[pre],mid+1,r,L,R);
return res;
}
}t;
LL query(int l,int r){
int tt=t.asksiz(Root[r],Root[l-1],1,lim,1,1);
if(!tt)return 1LL;
LL v=tt,nowsiz=tt;
while(v<lim){
int newsiz=t.asksiz(Root[r],Root[l-1],1,lim,1,v+1);LL newv;
if(newsiz==nowsiz)return v+1;
nowsiz=newsiz;
newv=t.asksum(Root[r],Root[l-1],1,lim,1,v+1);
v=newv;
}
return t.asksum(Root[r],Root[l-1],1,lim,1,lim)+1;
}
void solve(){
for(int i=1;i<=n;i++)t.insert(Root[i]=++tot,Root[i-1],1,lim,a[i]);
while(m--){
int l,r;scanf("%d%d",&l,&r);
printf("%lld\n",query(l,r));
}
}
}D:牛牛的RPG游戏
这道题比较裸，就是推一个式子维护一下凸壳，然后具体可以用李超树维护，当然也可以分治维护。
然后考试的时候写了一个关于sqrt(n)有关的复杂度，就是考虑n和m我们用小的当做行数，这样更新是小于根号n的，然后在用李超树查询即可，这样是根号log的，拼上部分分能通过70分，时空复杂度都较大，代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,m;
vector<int>b[N],a[N];
void init(){
for(int i=1;i<=n;i++)a[i].resize(m+1),b[i].resize(m+1);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
}
namespace force{
int a[35][35],b[35][35],dp[35][35];
void solve(){
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dp[i][j]=a[i][j];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
for(int lsti=1;lsti<=i;lsti++)for(int lstj=1;lstj<=j;lstj++)
if(i!=lsti||j!=lstj)dp[i][j]=max(dp[i][j],dp[lsti][lstj]+b[lsti][lstj]*(i-lsti+j-lstj)+a[i][j]);
printf("%d\n",dp[n][m]);
}
}
namespace subtask1{
vector<int>dp[N];
bool check(){
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(b[i][j])return false;
return true;
}
void solve(){
for(int i=1;i<=n;i++)dp[i].resize(m+1);
if(a[1][1]>0)dp[1][1]=a[1][1];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
if(i>1)dp[i][j]=max(dp[i][j],dp[i-1][j]),dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i][j]);
if(j>1)dp[i][j]=max(dp[i][j],dp[i][j-1]),dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i][j]);
}
printf("%d\n",dp[n][m]);
}
}
const LL inf=1e18;
namespace subtask2{
LL dp[N],k[N],bb[N];int A[N],B[N],id[N<<2];
LL calc(int id,int x){return (LL)k[id]*x+bb[id];}
void change(int rt,int l,int r,int d){
if(!id[rt]){id[rt]=d;return;}
int mid=(l+r)>>1;
if(calc(d,mid)>calc(id[rt],mid))swap(id[rt],d);
if(l==r)return;
if(k[d]<k[id[rt]])change(rt<<1,l,mid,d);
else change(rt<<1|1,mid+1,r,d);
}
LL query(int rt,int l,int r,int p){
if(!id[rt])return -inf;
int mid=(l+r)>>1;LL res=calc(id[rt],p);
if(l!=r){
if(p<=mid)res=max(res,query(rt<<1,l,mid,p));
else res=max(res,query(rt<<1|1,mid+1,r,p));
}
return res;
}
void solve(){
if(n==1){
n=m;
for(int i=1;i<=n;i++)A[i]=a[1][i],B[i]=b[1][i];
}else{
for(int i=1;i<=n;i++)A[i]=a[i][1],B[i]=b[i][1];
}
dp[1]=A[1];
for(int i=1;i<=n;i++){
if(i!=1)dp[i]=max(query(1,1,n,i)+A[i],(LL)A[i]);
k[i]=B[i];bb[i]=dp[i]-(LL)i*B[i];
change(1,1,n,i);
}
printf("%lld\n",dp[n]);
}
}
namespace subtask3{
const int S=1.5e7+5;
LL k[N],bb[N];int id[S],ls[S],rs[S],tot;
LL calc(int id,int x){return (LL)k[id]*x+bb[id];}
struct seg{
void change(int rt,int l,int r,int d){
if(!id[rt]){id[rt]=d;return;}
int mid=(l+r)>>1;
if(calc(d,mid)>calc(id[rt],mid))swap(id[rt],d);
if(l==r)return;
if(k[d]<k[id[rt]])change(!ls[rt]?ls[rt]=++tot:ls[rt],l,mid,d);
else change(!rs[rt]?rs[rt]=++tot:rs[rt],mid+1,r,d);
}
LL query(int rt,int l,int r,int p){
if(!rt||!id[rt])return -inf;
int mid=(l+r)>>1;LL res=calc(id[rt],p);
if(l!=r){
if(p<=mid)res=max(res,query(ls[rt],l,mid,p));
else res=max(res,query(rs[rt],mid+1,r,p));
}
return res;
}
}t[355];
int dfn,Root[355];
vector<int>A[N],B[N];
vector<LL>dp[N];
void solve(){
if(n>m){
swap(n,m);
for(int i=1;i<=n;i++)A[i].resize(m+1),B[i].resize(m+1);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)A[i][j]=a[j][i],B[i][j]=b[j][i];
}else{
for(int i=1;i<=n;i++)A[i].resize(m+1),B[i].resize(m+1);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)A[i][j]=a[i][j],B[i][j]=b[i][j];
}
for(int i=1;i<=n;i++)dp[i].resize(m+1);
dp[1][1]=A[1][1];tot=n;
for(int i=1;i<=n;i++)Root[i]=i;
for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){
if(i!=1||j!=1){
dp[j][i]=A[j][i];
for(int trsid=1;trsid<=j;trsid++){
dp[j][i]=max(dp[j][i],t[trsid].query(Root[trsid],1,n,j-trsid+i)+A[j][i]);
}
}
k[++dfn]=B[j][i];bb[dfn]=dp[j][i]-(LL)i*B[j][i];
t[j].change(Root[j],1,n,dfn);
}
printf("%lld\n",dp[n][m]);
}
}
int main(){
scanf("%d%d",&n,&m);
if(n<=30&&m<=30)force::solve();
else{
init();
if(subtask1::check())subtask1::solve();
else if(min(n,m)==1)subtask2::solve();
else subtask3::solve();
}
return 0;
}100分代码待补...
京公网安备 11010502036488号