HNOI 2016题解
HJWJBSR
posted @ 2016年4月18日 19:19
in 题解
, 886 阅读
感觉这次省选确实出的比较蛋疼。就这样6个DS对待HN选手感觉是很不妥。
D1T1：
做法一：对所有操作询问按a排序后分块，先把1~i-1块的内容和第i块的询问按照b排序，然后再扫一遍，每次加边用并查集维护连通块的maxa和maxb。
然后扫到一个块内询问的时候就暴力加入当前块的符合条件的边，用一个新的数组搞并查集就可以了。复杂度O(m*sqrt(m)*log(n))。细节好像非常厉害，想清楚之后写比较好。尤其是我最近比较喜闻乐见的入了下划线坑然后这种代码就比较容易混乱。。写过了之后没有判掉那些询问点对是相等的情况，所以后来是面向数据调代码的。然后写丑了，我的要加点优化才能勉强过。
考场上面并没有花时间去想。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
int sg[N],_sg[N],cz[N][4],fa[N],ma[N][2],_fa[N],_ma[N][2];
int Now[N],Nep[N],qu[N][4],wz[N],_wz[N],n,m,p,rt,st;
bool Ans[N],flag=false;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int Find(int x) {return fa[x]==x?x:(fa[x]=Find(fa[x]));}
int _Find(int x)
{
if (Now[x]!=st)
{
Now[x]=st;_ma[x][0]=ma[x][0];
_ma[x][1]=ma[x][1];_fa[x]=fa[x];
}
return _fa[x]==x?x:(_fa[x]=_Find(_fa[x]));
}
inline int Get(int x,int y)
{return x<0?qu[-x][y]:cz[x][y];}
inline bool cmp(int x,int y)
{return Get(x,3)<Get(y,3)||(Get(x,3)==Get(y,3)&&
(Get(x,2)<Get(y,2)||(Get(x,2)==Get(y,2)&&x>y)));}
inline bool _cmp(int x,int y)
{return Get(x,2)<Get(y,2)||(Get(x,2)==Get(y,2)&&
(Get(x,3)<Get(y,3)||(Get(x,3)==Get(y,3)&&x>y)));}
int main()
{
freopen("multiple.in","r",stdin);
freopen("multiple.out","w",stdout);
n=Read();m=Read();
for (int i=1;i<=m;i++)
for (int j=0;j<4;j++) cz[i][j]=Read();
for (int i=1;i<=m;i++) sg[i]=_sg[i]=i;
p=Read();
for (int i=1;i<=p;i++)
for (int j=0;j<4;j++) qu[i][j]=Read();
for (int i=1;i<=p;i++) _sg[i+m]=sg[i+m]=-i;
sort(_sg+1,_sg+m+p+1,_cmp);sort(sg+1,sg+m+p+1,cmp);
rt=(int)(sqrt(m+p));
if (m+p>10000) rt <<= true;
for (int i=1;i<=m+p;i++)
if (_sg[i]>0) wz[_sg[i]]=i; else _wz[-_sg[i]]=i;
for (int i=1;i<=m+p;i++) Nep[i]=(i-1)/rt;
for (int i=1;i<=m+p;)
{
int ri=i;while (ri<m+p&&Nep[ri+1]==Nep[ri]) ri++;
for (int j=1;j<=n;j++) fa[j]=j,ma[j][0]=ma[j][1]=false;
for (int j=1;j<=m+p;j++)
if (sg[j]>0&&wz[sg[j]]<i)
{
int k=Find(cz[sg[j]][0]),l=Find(cz[sg[j]][1]);
if (k!=l)
fa[l]=k,ma[k][0]=max(ma[k][0],ma[l][0]),
ma[k][1]=max(ma[k][1],ma[l][1]);
ma[k][0]=max(ma[k][0],cz[sg[j]][2]);
ma[k][1]=max(ma[k][1],cz[sg[j]][3]);
} else
if (sg[j]<0&&_wz[-sg[j]]>=i&&_wz[-sg[j]]<=ri)
{
st++;
for (int e=i;e<=ri;e++)
if (_sg[e]>0&&cz[_sg[e]][2]<=qu[-sg[j]][2]&&
cz[_sg[e]][3]<=qu[-sg[j]][3])
{
int k=_Find(cz[_sg[e]][0]);
int l=_Find(cz[_sg[e]][1]);
if (k!=l)
{
_fa[l]=k;
_ma[k][0]=max(_ma[k][0],_ma[l][0]);
_ma[k][1]=max(_ma[k][1],_ma[l][1]);
}
_ma[k][0]=max(_ma[k][0],cz[_sg[e]][2]);
_ma[k][1]=max(_ma[k][1],cz[_sg[e]][3]);
}
int k=_Find(qu[-sg[j]][0]),l=_Find(qu[-sg[j]][1]);
if (k==l&&_ma[k][0]==qu[-sg[j]][2]&&
_ma[k][1]==qu[-sg[j]][3]) Ans[-sg[j]]=true;
if (qu[-sg[j]][0]==qu[-sg[j]][1]&&!_ma[k][0]&&
!_ma[k][1]) Ans[-sg[j]]=false;
}
i=ri+1;
}
for (int i=1;i<=p;i++) puts(Ans[i]?"Yes":"No");
return 0;
}
做法二：UOJ群里面搞来的：
确实比较厉害。至于怎么维护黑点到根的max的min这明显可以用LCT上的splay直接维护每个点虚边上的最小值就好辣。还有因为有翻转操作所以要维护平衡树上从左到右和从右到左两个最小值。然后这东西看起来常数也很大。。（后来突然发现一个问题：怎么维护虚边上面的最小值，这东西我们不是有个叫做TopTree的很方便的东西吗，这样就是n log n辣（逃。。我们用个set就是n log^2 n的。。反正我不写。。
D1T2：
听说根号做法可以过。我的做法是点分治+平衡树。将操作拆到包含它的每个分治子树内，然后顶多只会有log个。每次询问在分治树上走。
假如当前走到的点是i，询问点为j，询问点在i的k子树内。分成两种情况：
1.操作的两个端点都不在i的k子树内。这种情况又分两种：第一种两个端点都在i的同一子树内，这个可以用set搞。第二种操作经过i点，这个用一棵平衡树维护i子树内的所有操作，按照权值维护，然后还维护平衡树子树内所有操作的公共端点。然后就可以在上面二分出第一个不经过k的操作了。
2.操作有一个端点在i的k子树内，有一个不在。这种情况再对于i的每个子树维护一个平衡树。维护的是满足(2)条件的所有操作。操作按照在k子树内的端点的dfs序维护，然后只要按照j和i的位置情况分类讨论一下可能的dfs区间就好了。
然后也是n log^2 n的。因为有两棵带删除的平衡树所以写起来非常蛋疼。。写到300h还没写完就弃坑了。。
网上找到了有人用n log^3 n强行艹过去了orz。是强行树套优先队列的所以常数比较小可能。总共跑了7s单点测试也没超时，随便过TAT。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define M 105
priority_queue <int> ad[N*4],del[N*4];
int fi[N],c[N*2][2],dfn[N][2],fa[N],h[N],rf[N],wei[N];
int cz[N*2][3],bd[M][2],sg[M],n,m,ss=1;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
h[x]=h[fa[x]]+1;wei[x]=true;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x])
fa[c[i][0]]=x,DFS(c[i][0]),wei[x]+=wei[c[i][0]];
return;
}
void DSF(int x,int y)
{
static int st=false;dfn[x][0]=++st;
rf[x]=y;int k=false;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&wei[c[i][0]]>wei[k]) k=c[i][0];
if (k) DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&c[i][0]!=k)
DSF(c[i][0],c[i][0]);
dfn[x][1]=st;
return;
}
inline int Query(int x,int y,int z,int o)
{
int mid = x + y >> 1 , j = z << 1 , k = -1;
while (!ad[z].empty()&&!del[z].empty()&&ad[z].top()==del[z].top())
ad[z].pop(),del[z].pop();
if (!ad[z].empty()) k=ad[z].top();
if (x!=y) if (o<=mid) k=max(k,Query(x,mid,j,o)); else
k=max(k,Query(mid+1,y,j+1,o));
return k;
}
inline bool cmp(int x,int y)
{return bd[x][0]<bd[y][0];}
void Modify(int x,int y,int z,int o,int p,int u,bool flag)
{
int mid = x + y >> 1 , j = z << 1;
if (x==o&&y==p)
{
if (flag) ad[z].push(u); else
del[z].push(u);
return;
}
if (p<=mid) Modify(x,mid,j,o,p,u,flag); else
if (o>mid) Modify(mid+1,y,j+1,o,p,u,flag); else
Modify(x,mid,j,o,mid,u,flag),
Modify(mid+1,y,j+1,mid+1,p,u,flag);
return;
}
void Insert(int x,int y,int z,bool flag)
{
int st=false;
while (rf[x]!=rf[y])
{
if (h[rf[x]]<h[rf[y]]) swap(x,y);
bd[++st][0]=dfn[rf[x]][0];bd[st][1]=dfn[x][0];
sg[st]=st;x=fa[rf[x]];
}
if (h[x]>h[y]) swap(x,y);
bd[++st][0]=dfn[x][0];bd[st][1]=dfn[y][0];sg[st]=st;
sort(sg+1,sg+st+1,cmp);
for (int i=1;i<=st;i++)
if (bd[sg[i-1]][1]+1!=bd[sg[i]][0])
Modify(1,n,1,bd[sg[i-1]][1]+1,bd[sg[i]][0]-1,z,flag);
if (bd[sg[st]][1]!=n)
Modify(1,n,1,bd[sg[st]][1]+1,n,z,flag);
return;
}
int main()
{
freopen("network.in","r",stdin);freopen("network.out","w",stdout);
n=Read();m=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
DFS(1);DSF(1,1);
for (int t=1;t<=m;t++)
{
int e=Read();
if (!e)
{
cz[t][0]=Read();cz[t][1]=Read();cz[t][2]=Read();
Insert(cz[t][0],cz[t][1],cz[t][2],true);
} else
if (e==1)
{
int k=Read();
Insert(cz[k][0],cz[k][1],cz[k][2],false);
} else
printf("%d\n",Query(1,n,1,dfn[Read()][0]));
}
return 0;
}
D1T3：最一眼的题：直接缩点然后树剖就好了。细节非常艹蛋。。不过想清楚之后也不用调很久。。编译完只调了三四个错就A了。。貌似跑的飞起。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 20
#define ll long long
ll bg[N],pre[N];int qu[N][4],rf[N],_rf[N],_fa[N],n,m,p,ss=true;
int wei[N],fi[N],c[N*2][2],h[N],sg[N],dfn[N][2],fa[N][3],rt[N];
int _dfn[N][2],li[N];
inline ll Read()
{
ll x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void _DFS(int x)
{
h[x]=h[_fa[x]]+1;wei[x]=true;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=_fa[x])
_fa[c[i][0]]=x,_DFS(c[i][0]),wei[x]+=wei[c[i][0]];
return;
}
void _DSF(int x,int y)
{
static int st=false;int k=false;
_rf[x]=y;dfn[x][0]=++st;sg[st]=x;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=_fa[x]&&wei[c[i][0]]>wei[k])
k=c[i][0];
if (k) _DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=_fa[x]&&c[i][0]!=k)
_DSF(c[i][0],c[i][0]);
dfn[x][1]=st;
return;
}
int LCA(int x,int y)
{
while (_rf[x]!=_rf[y])
{
if (h[_rf[x]]<h[_rf[y]]) swap(x,y);
x=_fa[_rf[x]];
}
return h[x]<h[y]?x:y;
}
struct Node
{
Node* c[2];int Cnt;
} statePool[N*M],*_rt[N],*cur,*emp,Emp;
inline Node* GetNew()
{return cur->c[0]=cur->c[1]=emp,cur++;}
Node* Insert(int x,int y,Node* z,int o)
{
int mid = x + y >> 1;Node* j=GetNew();
j->Cnt=z->Cnt+1;
if (x!=y) if (o<=mid)
j->c[1]=z->c[1],j->c[0]=Insert(x,mid,z->c[0],o); else
j->c[0]=z->c[0],j->c[1]=Insert(mid+1,y,z->c[1],o);
return j;
}
int Query(int x,int y,Node* z,Node* o,int p)
{
int mid = x + y >> 1,k=z->c[0]->Cnt-o->c[0]->Cnt;
if (x==y) return x;
if (k<p) return Query(mid+1,y,z->c[1],o->c[1],p-k); else
return Query(x,mid,z->c[0],o->c[0],p);
}
int Half_Find(int x,int y,ll z)
{
if (x>y) return false;
int mid = x + y >> 1;
if (z>=bg[mid]) return max(Half_Find(mid+1,y,z),mid); else
return Half_Find(x,mid-1,z);
}
void DFS(int x)
{
pre[x]=pre[fa[x][0]]+fa[x][2];wei[x]=true;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
DFS(c[i][0]),wei[x]+=wei[c[i][0]];
return;
}
void DSF(int x,int y)
{
static int st=false;_dfn[x][0]=++st;li[st]=x;
int k=false;rf[x]=y;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0]&&wei[c[i][0]]>wei[k])
k=c[i][0];
if (k) DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0]&&c[i][0]!=k)
DSF(c[i][0],c[i][0]);
_dfn[x][1]=st;
return;
}
ll GetAns(int x)
{
if (qu[x][0]==qu[x][2])
return h[qu[x][1]]+h[qu[x][3]]-2*h[LCA(qu[x][1],qu[x][3])];
ll ans=false;
if (pre[qu[x][0]]<pre[qu[x][2]])
swap(qu[x][0],qu[x][2]),swap(qu[x][1],qu[x][3]);
if (_dfn[qu[x][0]][0]>=_dfn[qu[x][2]][0]&&
_dfn[qu[x][0]][1]<=_dfn[qu[x][2]][1])
{
int la=qu[x][0];
ans=h[qu[x][1]]-h[rt[qu[x][0]]]+
h[qu[x][3]]-h[rt[qu[x][2]]]+
pre[qu[x][0]]-pre[qu[x][2]];
while (rf[qu[x][0]]!=rf[qu[x][2]])
la=rf[qu[x][0]],qu[x][0]=fa[rf[qu[x][0]]][0];
if (qu[x][0]==qu[x][2])
qu[x][0]=la; else
qu[x][0]=li[_dfn[qu[x][2]][0]+1];
ans-=2*h[LCA(fa[qu[x][0]][1],qu[x][3])]-
2*h[rt[qu[x][2]]];
} else
{
int la0=false,la1=false;
ans=pre[qu[x][0]]+pre[qu[x][2]]+
h[qu[x][1]]+h[qu[x][3]]-
h[rt[qu[x][0]]]-h[rt[qu[x][2]]];
while (rf[qu[x][0]]!=rf[qu[x][2]])
{
if (pre[rf[qu[x][0]]]<pre[rf[qu[x][2]]])
swap(qu[x][0],qu[x][2]),swap(la0,la1);
la0=rf[qu[x][0]];
qu[x][0]=fa[rf[qu[x][0]]][0];
}
int e=pre[qu[x][0]]<pre[qu[x][2]]?qu[x][0]:qu[x][2];
ans-=2*pre[e];
for (int j=0;j<3;j+=2)
if (qu[x][j]!=e) qu[x][j]=li[_dfn[e][0]+1]; else
qu[x][j]=0;
if (!qu[x][0]) qu[x][0]=la0;
if (!qu[x][2]) qu[x][2]=la1;
ans-=2*h[LCA(fa[qu[x][0]][1],fa[qu[x][2]][1])]-
2*h[rt[e]];
}
return ans;
}
int main()
{
freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);
n=Read();m=Read();p=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
cur=statePool;emp=&Emp;emp->c[0]=emp->c[1]=emp;
_DFS(1);_DSF(1,1);_rt[0]=emp;
for (int i=1;i<=n;i++)
_rt[i]=Insert(1,n,_rt[i-1],sg[i]);
memset(fi,0,sizeof fi);ss=bg[true]=rt[true]=true;
for (int i=2;i<=m+1;i++)
{
rt[i]=Read();ll l=Read();
fa[i][0]=Half_Find(1,i-1,l);
fa[i][1]=Query(1,n,_rt[dfn[rt[fa[i][0]]][1]],
_rt[dfn[rt[fa[i][0]]][0]-1],l-bg[fa[i][0]]+1);
fa[i][2]=1+h[fa[i][1]]-h[rt[fa[i][0]]];
bg[i]=bg[i-1]+wei[rt[i-1]];Line(i,fa[i][0]);
}
for (int i=1;i<=p;i++)
{
ll k=Read(),l=Read();
qu[i][0]=Half_Find(1,m+1,k);
qu[i][1]=Query(1,n,_rt[dfn[rt[qu[i][0]]][1]],
_rt[dfn[rt[qu[i][0]]][0]-1],k-bg[qu[i][0]]+1);
qu[i][2]=Half_Find(1,m+1,l);
qu[i][3]=Query(1,n,_rt[dfn[rt[qu[i][2]]][1]],
_rt[dfn[rt[qu[i][2]]][0]-1],l-bg[qu[i][2]]+1);
}
DFS(1);DSF(1,1);
for (int i=1;i<=p;i++) printf("%lld\n",GetAns(i));
return 0;
}
D2T1：如果询问一组我们直接元素排序之后一个一个加进来就好了。询问多组我们考虑维护答案。
设询问左端点右端点分别为x和y。那么当前我们加入坐标为i，i左边可以延伸到le，i右边可以延伸到ri，那么我们分类讨论x与le的大小关系还有ri与y的大小关系可以搞出不同的四个式子，这四个式子都可以看成a0xy+a1x+a2y+a3的形式，这个东西是可以看成4种不同的标记用线段树维护的。然后其影响的询问也就是转换成二维问题之后的一个矩形，所以我们直接扫描线+线段树就好了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define ll long long
#define PII pair <int,int>
#define fr first
#define sc second
#define mp make_pair
ll ad[N*4][4],Ans[N],cz[N*9][5],wz[N*9][3];
int sg[N*9],fa[N],bd[N][2],v[N],st,n,m;PII li[N];
inline int Read()
{
int x=0;char y;bool z=false;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
int Find(int x) {return fa[x]==x?x:(fa[x]=Find(fa[x]));}
inline void Get(int x,int y,int z,int o,ll _x,ll _y,ll _z,ll _o)
{
wz[++st][0]=x;wz[st][1]=z;wz[st][2]=o;
cz[st][0]=true;cz[st][1]=_x;cz[st][2]=_y;cz[st][3]=_z;cz[st][4]=_o;
wz[++st][0]=y;wz[st][1]=z;wz[st][2]=o;
cz[st][0]=false;cz[st][1]=-_x;cz[st][2]=-_y;cz[st][3]=-_z;cz[st][4]=-_o;
}
void Pretreat()
{
for (int i=1;i<=n;i++) li[i]=mp(-v[i],i);
sort(li+1,li+n+1);
for (int i=1;i<=n;i++)
{
int k=li[i].sc;fa[k]=bd[k][0]=bd[k][1]=k;
if (fa[k-1]) bd[k][0]=bd[Find(k-1)][0],fa[Find(k-1)]=k;
if (fa[k+1]) bd[k][1]=bd[Find(k+1)][1],fa[Find(k+1)]=k;
int bg=bd[k][0],ed=bd[k][1];
Get(bg,k+1,k,ed,-v[k],v[k]*(k-1LL),v[k]*(k+1LL),(1-1LL*k*k)*v[k]);
if (bg-1)
Get(1,bg,k,ed,0,0,(k-bg+1LL)*v[k],(k-bg+1LL)*(1LL-k)*v[k]);
if (ed<n)
Get(bg,k+1,ed+1,n,0,-(ed-k+1LL)*v[k],0,(k+1LL)*(ed-k+1LL)*v[k]);
if (bg-1&&ed<n)
Get(1,bg,ed+1,n,0,0,0,(k-bg+1LL)*(ed-k+1)*v[k]);
}
return;
}
inline bool cmp(int x,int y)
{return wz[x][0]<wz[y][0]||(wz[x][0]==wz[y][0]&&cz[x][0]<cz[y][0]);}
inline void Down(int z)
{
int j = z << 1;
for (int i=0;i<2;i++)
for (int k=0;k<4;k++) ad[j+i][k]+=ad[z][k];
for (int k=0;k<4;k++) ad[z][k]=false;
return;
}
inline void Modify(int x,int y,int z,int o,int p,ll _x,ll _y,ll _z,ll _o)
{
int mid = x + y >> 1, j = z << 1;
if (x==o&&y==p)
{
ad[z][0]+=_x;ad[z][1]+=_y;ad[z][2]+=_z;ad[z][3]+=_o;
return;
}
if (p<=mid) Modify(x,mid,j,o,p,_x,_y,_z,_o); else
if (o>mid) Modify(mid+1,y,j+1,o,p,_x,_y,_z,_o); else
Modify(x,mid,j,o,mid,_x,_y,_z,_o),
Modify(mid+1,y,j+1,mid+1,p,_x,_y,_z,_o);
return;
}
ll Query(int x,int y,int z,int o,int p)
{
if (x==y)
return 1LL*ad[z][0]*o*p+1LL*p*ad[z][1]+1LL*o*ad[z][2]+ad[z][3];
int mid = x + y >> 1, j = z << 1;Down(z);
if (o<=mid) return Query(x,mid,j,o,p); else
return Query(mid+1,y,j+1,o,p);
}
int main()
{
freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
n=Read();m=Read();st=m;
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<=m;i++) wz[i][0]=Read(),wz[i][1]=Read(),cz[i][0]=2;
Pretreat();
for (int i=1;i<=st;i++) sg[i]=i;
sort(sg+1,sg+st+1,cmp);
for (int i=1;i<=st;i++)
if (cz[sg[i]][0]!=2)
Modify(1,n,1,wz[sg[i]][1],wz[sg[i]][2],cz[sg[i]][1],cz[sg[i]][2],
cz[sg[i]][3],cz[sg[i]][4]); else
Ans[sg[i]]=Query(1,n,1,wz[sg[i]][1],wz[sg[i]][0]);
for (int i=1;i<=m;i++) printf("%lld\n",Ans[i]);
return 0;
}
D2T2：不懂平面图那套理论。。
D2T3：设1~i所形成的十进制数字为Prei，则当P!=2&&P!=5,i<j时，我们要求(Prej-Prei*10^(j-i))%P==0的个数。
化一下式子两遍都除以10^-j则Prej*10^(-j)==Prei*10^(-i) %P，然后就可以直接变成小z的袜子了。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
#define ll long long
#define PII pair <ll,int>
#define fr first
#define sc second
#define mp make_pair
int n,m,val[N];char ch[N];ll P,ans;
inline ll Read()
{
ll x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
ll Q_Multi(ll x,ll y)
{
ll z=false;
while (y) z=y&1?(z+x)%P:z,x=(x+x)%P,y >>= true;
return z;
}
ll Q_Power(ll x,ll y)
{
ll z=true;
while (y) z=y&1?Q_Multi(z,x):z,x=Q_Multi(x,x),y >>= true;
return z;
}
namespace Solve0
{
PII li[N];ll Inv,Pre,pre[N],_pre[N],Ans[N],ans;
int rt,st,_sg[N],Cnt[N],sg[N],qu[N][2];
void Pretreat()
{
for (int i=0;i<=n;i++) li[i]=mp(pre[i],i);
sort(li,li+n+1);pre[li[0].sc]=st=1;
for (int i=1;i<=n;i++)
pre[li[i].sc]=(st+=li[i].fr!=li[i-1].fr);
return;
}
inline bool cmp(int x,int y)
{return _sg[qu[x][0]]<_sg[qu[y][0]]||(_sg[qu[x][0]]==_sg[qu[y][0]]&&
qu[x][1]<qu[y][1]);}
inline void Add(int x) {ans+=Cnt[x]++;}
inline void Del(int x) {ans-=--Cnt[x];}
void Solve()
{
Inv=Pre=Q_Power(10,P-2);
for (int i=1;i<=n;i++)
_pre[i]=(10LL*_pre[i-1]+val[i])%P,
pre[i]=Q_Multi(Pre,_pre[i]),Pre=Q_Multi(Pre,Inv);
Pretreat();rt=(int)sqrt(n);
for (int i=1;i<=n;i++) _sg[i]=(i-1)/rt;
for (int i=1;i<=m;i++) qu[i][0]=Read(),qu[i][1]=Read();
for (int i=1;i<=m;i++) sg[i]=i;
sort(sg+1,sg+m+1,cmp);
for (int i=1;i<=m;)
{
memset(Cnt,false,sizeof Cnt);ans=false;int ri=i;
while (ri<m&&_sg[qu[sg[ri+1]][0]]==_sg[qu[sg[i]][0]]) ri++;
int bg=qu[sg[i]][0]-1,ed=qu[sg[i]][1];
for (int j=bg;j<=ed;j++) Add(pre[j]);
Ans[sg[i]]=ans;
for (;i<=ri;i++)
{
int _bg=qu[sg[i]][0]-1,_ed=qu[sg[i]][1];
while (bg>_bg) Add(pre[--bg]);
while (ed<_ed) Add(pre[++ed]);
while (bg<_bg) Del(pre[bg++]);
while (ed>_ed) Del(pre[ed--]);
Ans[sg[i]]=ans;
}
}
for (int i=1;i<=m;i++) printf("%lld\n",Ans[i]);
return;
}
}
namespace Solve1
{
ll pre[N],_pre[N];
void Solve()
{
for (int i=1;i<=n;i++)
{
pre[i]=pre[i-1];_pre[i]=_pre[i-1];
if (val[i]%P==0)
pre[i]+=i,_pre[i]++;
}
while (m--)
{
int k=Read(),l=Read();
printf("%lld\n",pre[l]-pre[k-1]+(_pre[l]-_pre[k-1])*(1-k));
}
return;
}
}
int main()
{
freopen("number.in","r",stdin);freopen("number.out","w",stdout);
P=Read();scanf("%s",ch+1);n=strlen(ch+1);
for (int i=1;i<=n;i++) val[i]=ch[i]-'0';
m=Read();
if (P==2||P==5) Solve1::Solve(); else
Solve0::Solve();
return 0;
}
总之完结了。。感觉day1还是太naive。。T2知道log^2不可写就要去想log^3的。。T3明明可以写出来但是对自己代码能力太没自信了。。不过我也不知道在考场那样的氛围下能不能写出来。。
但是还是感觉很虚啊。。day1好像有13、4个人A题的吧。。我这种渣渣暴力完全不能同台竞技啊。。
教训是能做的题还是要尽量做，考试的时候不要方就是干。纯暴力选手没有好下场。现在想想考试的时候自己明明写得出来但是没有写正解还是非常不爽的。
评论 (0)
