DS round
A
\(ax+by+cz=d\) 的形式,发现裴蜀定理即可。注意下 \(\gcd(-a,b)=\gcd(a,b),\gcd(a,0)=a\),即变绝对值和去掉 \(0\) 即可。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
int gcd(int x,int y) {
return !y?x:gcd(y,x%y);
}
void sol() {
int a,b,c,d;
cin>>a>>b>>c>>d;
a=abs(a); b=abs(b); c=abs(c);
if(!a&&!b&&!c) {
if(d==0) {
cout<<"YES\n"; return ;
} else {
cout<<"NO\n"; return ;
}
} else if(!a&&!b) {
if(d%c==0) {
cout<<"YES\n"; return ;
} else {
cout<<"NO\n"; return ;
}
} else if(!a&&!c) {
if(d%b==0) {
cout<<"YES\n"; return ;
} else {
cout<<"NO\n"; return ;
}
} else if(!b&&!c) {
if(d%a==0) {
cout<<"YES\n"; return ;
} else {
cout<<"NO\n"; return ;
}
} else if(!a) {
int qwq=gcd(b,c);
if(d%qwq==0) {
cout<<"YES\n"; return ;
} else {
cout<<"NO\n"; return ;
}
} else if(!b) {
int qwq=gcd(a,c);
if(d%qwq==0) {
cout<<"YES\n"; return ;
} else {
cout<<"NO\n"; return ;
}
} else if(!c) {
int qwq=gcd(a,b);
if(d%qwq==0) {
cout<<"YES\n"; return ;
} else {
cout<<"NO\n"; return ;
}
} else {
int qwq=gcd(a,gcd(b,c));
if(d%qwq==0) {
cout<<"YES\n"; return ;
} else {
cout<<"NO\n"; return ;
}
}
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int T; cin>>T; while(T--) sol();
return 0;
}
B
假如你不会正解,显然这样子置换是满足结合律的,于是倍增即可。即记 \(st[i][j]\) 为初始局面跳 \(2^i\) 次,第 \(j\) 个位置是哪颗球。
你推不出来转移随便搓一下就好了。
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
using namespace std;
const int N=(int)(1e5+5);
struct node {
int x,y;
}a[N];
struct nd {
int a[10];
}st[20][N];
int n,m,v[10],tmp[10];
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i].x>>a[i].y;
}
for(int i=1;i<=n;i++) {
for(int j=0;j<=9;j++) v[j]=j;
swap(v[a[i].x],v[a[i].y]);
for(int j=0;j<=9;j++) st[0][i].a[j]=v[j];
}
for(int i=1;(1<<i)<=n;i++) {
for(int j=1;j+(1<<i)-1<=n;j++) {
for(int k=0;k<=9;k++) {
int x=st[i-1][j+(1<<(i-1))].a[k];
x=st[i-1][j].a[x];
st[i][j].a[k]=x;
}
}
}
while(m--) {
int l,r; cin>>l>>r;
for(int i=0;i<=9;i++) v[i]=i;
int qwq=r-l+1,nw=l;
for(int i=18;i>=0;i--) {
if(qwq>=(1<<i)) {
qwq-=(1<<i);
for(int j=0;j<=9;j++) tmp[j]=v[j];
for(int j=0;j<=9;j++) {
int x=st[i][nw].a[j];
v[j]=tmp[x];
}
nw+=(1<<i);
}
}
for(int i=0;i<=9;i++) cout<<v[i]<<' ';
cout<<'\n';
}
return 0;
}
C
考虑找第一个不能表示的,一定是 \([1,ans)\) 都可以,\(ans\) 不行。
考虑维护当前能表示的值域区间,显然一定是个前缀,考虑加上一个数,对于这条线段平移即可。
然后发现你要从小到大加数,然后写个主席树+模拟上述过程即可。
关于复杂度:感觉是自然根号的样子,但是不知道为啥带个 \(\log\) 还跑过去了。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=(int)(1e5+5),M=(int)(1e9);
int n,m,a[N],tot;
int sum[N*50],ls[N*50],rs[N*50],rt[N];
void upt(int pre,int &cur,int l,int r,int pos,int v) {
if(!cur) cur=++tot;
sum[cur]=sum[pre]+v;
if(l==r) return ;
int mid=(l+r)>>1;
if(pos<=mid) rs[cur]=rs[pre],upt(ls[pre],ls[cur],l,mid,pos,v);
else ls[cur]=ls[pre],upt(rs[pre],rs[cur],mid+1,r,pos,v);
}
int qry(int cur,int l,int r,int cl,int cr) {
if(!cur) return 0;
if(cl<=l&&r<=cr) return sum[cur];
int mid=(l+r)>>1,res=0;
if(cl<=mid) res=qry(ls[cur],l,mid,cl,cr);
if(cr>mid) res+=qry(rs[cur],mid+1,r,cl,cr);
return res;
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i];
upt(rt[i-1],rt[i],1,M,a[i],a[i]);
}
while(m--) {
int l,r; cin>>l>>r;
int R=0,las=0;
while(1) {
int qwq=qry(rt[r],1,M,las+1,R+1)-qry(rt[l-1],1,M,las+1,R+1);
if(qwq) {
las=R+1; R+=qwq;
} else break ;
}
cout<<R+1<<'\n';
}
return 0;
}
D
别看错题就好。
考虑 \(f(x,y)\) 为到 \((x,y)\) 的最大价值,每次枚举上一个有价值的转移过来即可。
暴力方程 \(f(i,j)=\max\{f(x,y)+a(x,y)+c(x,y)+(i+j-x-y)\}\),因为一有贡献,然后我钦定你从那里转移过来,显然中间怎么走的没有贡献。
至于正确性,注意看看起点终点都是无贡献的。
考虑优化,显然 \(nm\le 10^5\) 提醒我们可以看看记 id 的形式,考虑枚举行后枚举列本质上就是扫 id,显然还有一个限制就是 \(s\%m\le t\%m\),若是 \(s\) 能转移到 \(t\) 的话。
为了这个限制,你需要把下标从 \(0\) 开始。/fad
接下来,发现转移是一次函数最值问题,但是你发现转移点是个矩阵,以及转移决策点并没有单调性质。
显然李超树,对于第二维的话我们发现没办法李超树维护前缀(),显然可以分块,实际上应该还是可以二进制分组的。
然后,现在复杂度是 \(O(nm\sqrt{m}\log{nm})\) 的,注意到 \(nm\le 1e5\) 的限制,意味着我们可以将 \(\sqrt{m}\) 通过根号分治转为 \(\sqrt{\min(n,m)}\),显然这个就是 \((10^5)^{1/4}\),其实还是挺快的。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=(int)(1e5+5),M=1000,MM=350,inf=(int)(2e18);
int n,m,v[N],c[N],f[N],L[N],R[N],bl;
inline int ID(int x,int y) {
return x*m+y;
}
struct node {
int K,B;
}s[N];
int val[N*40],ls[N*40],rs[N*40],rt[N*2],tot,id[N],NEX;
int cal(int id,int x) {
return s[id].K*x+s[id].B;
}
void upt(int &cur,int l,int r,int id) {
if(!cur) {
cur=++tot; val[cur]=id; return ;
}
int mid=(l+r)>>1,v=val[cur],res1=cal(v,mid),res2=cal(id,mid);
if(l==r) {
if(res1<res2) val[cur]=id;
return ;
}
if(s[v].K<s[id].K) {
if(res1<res2) {
val[cur]=id;
upt(ls[cur],l,mid,v);
} else {
upt(rs[cur],mid+1,r,id);
}
} else {
if(res1<res2) {
val[cur]=id;
upt(rs[cur],mid+1,r,v);
} else {
upt(ls[cur],l,mid,id);
}
}
}
int query(int cur,int l,int r,int pos) {
if(!cur) return -inf;
int res=cal(val[cur],pos);
if(l==r) return res;
int mid=(l+r)>>1;
if(pos<=mid) return max(res,query(ls[cur],l,mid,pos));
else return max(res,query(rs[cur],mid+1,r,pos));
}
int qry(int l,int r,int x) {
if(id[l]==id[r]) {
int res=-inf;
for(int i=l;i<=r;i++) {
res=max(res,query(rt[i],0,n+m,x));
}
return res;
} else {
int res=-inf;
for(int i=l;i<=R[id[l]];i++) res=max(res,query(rt[i],0,n+m,x));
for(int i=id[l]+1;i<id[r];i++) res=max(res,query(rt[i+NEX],0,n+m,x));
for(int i=L[id[r]];i<=r;i++) res=max(res,query(rt[i],0,n+m,x));
return res;
}
}
void UPT(int x,int v) {
// cout<<x<<" "<<id[x]<<'\n';
upt(rt[x],0,n+m,v);
upt(rt[id[x]+NEX],0,n+m,v);
}
signed main() {
// freopen("D.in","r",stdin);
cin.tie(0); ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
cin>>c[ID(i,j)];
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
cin>>v[ID(i,j)];
}
}
memset(f,-0x3f,sizeof(f));
f[ID(0,0)]=0;
if(n>=m) {
bl=sqrt(m); int las=0; NEX=m;
for(int i=0;i<m;i++) {
id[i]=i/bl+1;
if(id[i]!=las) {
L[id[i]]=R[id[i]]=i; las=id[i];
} else R[id[i]]=i;
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
int x=ID(i,j);
f[x]=max(f[x],qry(0,x%m,i+j));
s[x].K=c[x]; s[x].B=f[x]+v[x]-(i+j)*c[x];
UPT(x%m,x);
}
}
} else {
bl=sqrt(n); int las=0; NEX=n;
for(int i=0;i<n;i++) {
id[i]=i/bl+1;
if(id[i]!=las) {
L[id[i]]=R[id[i]]=i; las=id[i];
} else R[id[i]]=i;
}
for(int j=0;j<m;j++) {
for(int i=0;i<n;i++) {
int x=ID(i,j);
f[x]=max(f[x],qry(0,x/m,i+j));
s[x].K=c[x]; s[x].B=f[x]+v[x]-(i+j)*c[x];
UPT(x/m,x);
}
}
}
cout<<f[ID(n-1,m-1)];
return 0;
}
标签:10,tg1,return,cur,int,long,2020,id,define
From: https://www.cnblogs.com/xugangfan/p/16750424.html