Potyczki Algorytmiczne 2011

Trial Round：

Tulips

按題意模擬。

#include<cstdio>
const int N=15000;
int n,ans=N,x,v[N+1];
int main(){
  scanf("%d",&n);
  while(n--){
    scanf("%d",&x);
    if(!v[x])ans--,v[x]=1;
  }
  printf("%d",ans);
}

Round 1：

Rooks [B]

對于每個沒有車的行，隨便找一個沒有車的列配對。

#include<cstdio>
const int N=1005;
int n,i,j,a[N],b[N];char tmp[N];
int main(){
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%s",tmp+1);
    for(j=1;j<=n;j++)if(tmp[j]=='W')b[a[i]=j]=1;
  }
  for(i=1;i<=n;i++)if(!a[i])for(j=1;j<=n;j++)if(!b[j]){b[a[i]=j]=1;break;}
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++)tmp[j]='.';
    tmp[a[i]]='W';
    puts(tmp+1);
  }
}

Round 2：

Unlucky [A]

如果$w$不是$k$的倍數，那么先考慮從起點帶$w\bmod k$升水出發怎么處理，然后再依次考慮每次從起點帶$k$升水出發怎么處理。

假設目前已經推進到的右端點是$all$，算上這次一共要從起點出發$t$次，那么從$all$往右推進的這段路將被經過總計$2t-1$次。最優策略是將這次出發帶走的水平均分成$2t-1$份，從而得到本次推進的距離，注意距離要和到終點的距離取$\min$。

求出推進距離后，乘以經過的次數，就是這段路消耗的水量。

時間復雜度$O(\frac{w}{k})$。

#include<cstdio>
typedef double db;
int s,w,k,o;db sum,all;
inline void gao(db k){
  k/=o;
  if(k+all>=s)k=s-all;
  sum+=k*o;
  all+=k;
  o-=2;
}
int main(){
  scanf("%d%d%d",&s,&w,&k);
  o=(w/k)*2-1;
  if(w%k)o+=2,gao(w%k);
  while(o>0)gao(k);
  printf("%.3f",w-sum);
}

Climbing [B]

從左往右貪心，若一段區間能拼上則拼上，通過維護關于最左邊數的不等式組的解集來判斷。

時間復雜度$O(n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,i,ans,A,B;ll L,R,C,D;
inline bool check(ll K){
  if(C==1){
    L=max(L,-D);
    R=min(R,K-D);
  }else{
    L=max(L,D-K);
    R=min(R,D);
  }
  return L<=R;
}
int main(){
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d%d",&A,&B);
    A+=B;
    if(i>1&&check(A)){
      ans++;
      D=A-D;
      C=-C;
    }else{
      L=0,R=A;
      C=-1,D=A;
    }
  }
  printf("%d",ans);
}

Round 3：

Pedestrian Crossing [B]

在模$K$意義下做，每個白色段會禁掉起點位置的一個區間，注意這里區間端點不會被禁，所以引入$0.5$坐標。最后檢查是否$[0,K-0.5]$都被禁了即可。

時間復雜度$O(n\log n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;
const int N=500005;
int Case,n,m,i;
ll S,K,l,r,sum,len[N];
P e[N<<1];
inline void ban(ll l,ll r){
  if(l>r)return;
  e[++m]=P(l,r);
}
inline bool gao(ll l,ll r){
  if(l+K-S<r)return 0;
  l%=K,r%=K;
  if(l>r)r+=K;
  l+=K-S,r+=K;
  if(l/K==r/K)ban(l%K*2+1,r%K*2-1);
  else{
    ban(l%K*2+1,K*2-1);
    ban(0,r%K*2-1);
  }
  return 1;
}
bool check(){
  scanf("%lld%lld%d",&S,&K,&n);
  for(i=1;i<=n;i++)scanf("%lld",&len[i]),len[i]+=len[i-1];
  m=0;
  for(i=1;i<=n;i+=2)if(!gao(len[i-1],len[i]))return 0;
  sort(e+1,e+m+1);
  l=0,r=-5,sum=0;
  for(i=1;i<=m;i++){
    if(e[i].first>r+1){
      if(l<=r)sum+=r-l+1;
      l=e[i].first;
    }
    r=max(r,e[i].second);
  }
  if(l<=r)sum+=r-l+1;
  return sum<K*2;
}
int main(){
  scanf("%d",&Case);
  while(Case--)puts(check()?"TAK":"NIE");
}

Round 4：

Fuel [B]

找到一條樹直徑，令直徑上的點代價為$1$，剩下的點代價為$2$，注意起點代價為$0$，然后貪心選點即可。

時間復雜度$O(n)$。

#include<cstdio>
const int N=500005;
int n,m,i,x,y,g[N],v[N<<1],nxt[N<<1],ed,A,B,ans;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int y,int d){
  if(d>B)A=x,B=d;
  for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x,d+1);
}
int main(){
  scanf("%d%d",&n,&m);
  for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
  dfs(1,0,1);
  dfs(A,0,1);
  A=n-B;
  ans=1,B--;
  while(m&&B)m--,B--,ans++;
  while(m>1&&A)m-=2,A--,ans++;
  printf("%d",ans);
}

Round 5：

Declining Sequences [B]

求出$f[i][j]$表示有多少以$j$為起點長度為$i$的遞減序列。

對于一個有解的詢問，從第$1$層一直找到第$m$層，每層需要找到權值小于某數，且下標大于某數的部分里從左往右第$k$個方案所在的下標。

按照權值掃描線后，線段樹上維護區間$f$值的和，然后在線段樹上二分即可。

時間復雜度$O(nm\log n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100005,K=13,M=262155;
const ll inf=1000000000000000010LL;
int n,m,q,i,j,k,o,a[N],b[N],ans[N][K];ll f[K][N],bit[N],que[N],all;
int gn[N],gq[N],v[N<<1],nxt[N<<1],ed;
int pos[N],A,B;ll val[M],C;
inline void up(ll&a,ll b){a=a+b<inf?a+b:inf;}
inline void ins(int x,ll p){for(;x<=n;x+=x&-x)up(bit[x],p);}
inline ll ask(int x){ll t=0;for(;x;x-=x&-x)up(t,bit[x]);return t;}
inline void add(int&x,int y){v[++ed]=y;nxt[ed]=x;x=ed;}
void build(int x,int a,int b){
  val[x]=0;
  if(a==b){pos[a]=x;return;}
  int mid=(a+b)>>1;
  build(x<<1,a,mid),build(x<<1|1,mid+1,b);
}
inline void modify(int x,ll p){
  val[x=pos[x]]=p;
  for(x>>=1;x;x>>=1)val[x]=val[x<<1],up(val[x],val[x<<1|1]);
}
void query(int x,int a,int b){
  if(B)return;
  if(A<=a&&val[x]<C){C-=val[x];return;}
  if(a==b){B=a;return;}
  int mid=(a+b)>>1;
  if(A<=mid)query(x<<1,a,mid);
  query(x<<1|1,mid+1,b);
}
int main(){
  scanf("%d%d%d",&n,&m,&q);
  for(i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
  sort(b+1,b+n+1);
  for(i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
  for(i=1;i<=n;i++)f[m][i]=1;
  for(i=m-1;i;i--){
    for(j=1;j<=n;j++)bit[j]=0;
    for(j=n;j;j--){
      f[i][j]=ask(a[j]-1);
      ins(a[j],f[i+1][j]);
    }
  }
  for(i=1;i<=n;i++)up(all,f[1][i]);
  a[0]=n+1;
  for(i=1;i<=q;i++){
    scanf("%lld",&que[i]);
    if(que[i]>all)ans[i][0]=-1;
  }
  for(i=1;i<=n;i++)add(gn[a[i]],i);
  for(i=1;i<=m;i++){
    ed=n;
    for(j=0;j<=n;j++)gq[j]=0;
    for(j=1;j<=q;j++)if(~ans[j][0])add(gq[a[ans[j][i-1]]-1],j);
    build(1,1,n);
    for(j=0;j<=n;j++){
      for(k=gn[j];k;k=nxt[k]){
        o=v[k];
        modify(o,f[i][o]);
      }
      for(k=gq[j];k;k=nxt[k]){
        o=v[k];
        A=ans[o][i-1]+1;
        B=0;
        C=que[o];
        query(1,1,n);
        ans[o][i]=B;
        que[o]=C;
      }
    }
  }
  for(i=1;i<=q;i++){
    if(~ans[i][0])for(j=1;j<=m;j++)printf("%d%c",ans[i][j],j<m?' ':'\n');
    else puts("-1");
  }
}

Double Factorial [B]

$1!\times 2!\times3!\times\dots\times n!$里質因子$5$的個數即

\[\left(\lfloor\frac{1}{5^1}\rfloor+\lfloor\frac{2}{5^1}\rfloor+\dots+\lfloor\frac{n}{5^1}\rfloor\right)+\left(\lfloor\frac{1}{5^2}\rfloor+\lfloor\frac{2}{5^2}\rfloor+\dots+\lfloor\frac{n}{5^2}\rfloor\right)+\dots+\left(\lfloor\frac{1}{5^k}\rfloor+\lfloor\frac{2}{5^k}\rfloor+\dots+\lfloor\frac{n}{5^k}\rfloor\right)\]

枚舉$k$后推公式即可。

n=int(input())
ans=0
k=5
while k<=n:
  m=n//k
  ans+=(m-1)*m*k//2+m*(n-m*k+1)
  k*=5
print(ans)

Trails [A]

留坑。

Vacation [A]

當$k=2$時就是$a$和$b$的距離。

當$k=3$時，答案上界為$24n$，對于每個點向三個排列對應位置左右$15$個位置連負邊可以減小答案。建立二分圖，使用Dijkstra找增廣路求最小費用流。

優化1：

最短路不超過$24$，可以用桶代替堆，使得每次Dijkstra時間復雜度為$O(n+m)$，其中$m=nc$。

優化2：

Dijkstra求出源點到每個點的最短路后，在最短路圖上BFS得到每個點的層數。

沿著最短層進行多路增廣，不斷BFS多路增廣直到無法增廣。

那么每次Dijkstra求出的最小花費嚴格遞增，且BFS出來的最小層數嚴格遞增。

沿用Dinic的分析可得每次多路增廣次數不超過$O(\sqrt{n})$，所以一共$O(c\sqrt{n})$次多路增廣。

總時間復雜度$O(c\sqrt{n}(n+m))$=$O(c^2n^{1.5})$。

#include<cstdio>
const int N=5005,inf=10000000,K=30;
int n,k,i,j,ans,a[N],b[N],c[N],last[N];
int s,t,cnt=1;
int g[N<<1],d[N<<1],f[N<<1],vis[N<<1],h[N<<1];
int pool[K][N<<1],top[K],q[N<<1];
int cur[N<<1];
void read(int a[]){
  int i,x;
  for(i=1;i<=n;i++)scanf("%d",&x),a[x]=i;
}
inline int abs(int x){return x>0?x:-x;}
inline int min(int a,int b){return a<b?a:b;}
struct E{
  int v,f,c,nxt;
  E(){}
  E(int _v,int _f,int _c,int _nxt){v=_v,f=_f,c=_c,nxt=_nxt;}
}e[N*(15*3+2)*2];
inline void add(int u,int v,int f,int c){
  e[++cnt]=E(v,f,c,g[u]);
  g[u]=cnt;
  e[++cnt]=E(u,0,-c,g[v]);
  g[v]=cnt;
}
inline void addedge(int x,int y){
  if(y<1||y>n)return;
  if(last[y]==x)return;
  last[y]=x;
  int w=min(abs(y-a[x]),8)+min(abs(y-b[x]),8)+min(abs(y-c[x]),8);
  add(x,y+n,1,w-24);
}
inline void ext(int x,int y){
  if(y>=K)return;
  d[x]=y;
  pool[y][++top[y]]=x;
}
inline bool dijkstra(){
  int i,o;
  for(i=1;i<=t;i++)d[i]=inf,vis[i]=0;
  for(i=0;i<K;i++)top[i]=0;
  ext(s,0);
  for(o=0;o<K;o++)while(top[o]){
    int u=pool[o][top[o]--];
    if(vis[u])continue;
    vis[u]=1;
    for(i=g[u];i;i=e[i].nxt)if(e[i].f){
      int v=e[i].v,w=e[i].c+h[u]-h[v];
      if(d[v]>d[u]+w&&!vis[v])ext(v,d[u]+w);
    }
  }
  return d[t]!=inf;
}
inline bool bfs(){
  int head=1,tail=1,i,u,v,z;
  for(i=1;i<=t;i++)vis[i]=0;
  vis[s]=1;
  f[s]=0;
  q[1]=s;
  while(head<=tail){
    u=q[head++];
    z=f[u]+1;
    for(i=g[u];i;i=e[i].nxt)if(e[i].f){
      int v=e[i].v,w=e[i].c+h[u]-h[v];
      if(d[v]==d[u]+w&&!vis[v]){
        vis[v]=1;
        f[v]=z;
        q[++tail]=v;
      }
    }
  }
  return vis[t];
}
bool dfs(int u){
  if(u==t)return 1;
  vis[u]=1;
  for(int&i=cur[u];i;i=e[i].nxt){
    int v=e[i].v;
    if(!vis[v]&&e[i].f&&d[v]==d[u]+e[i].c+h[u]-h[v]&&f[v]==f[u]+1){
      int tmp=dfs(v);
      if(tmp){
        ans+=e[i].c;
        e[i].f--,e[i^1].f++;
        vis[u]=0;
        i=e[i].nxt;
        return 1;
      }
    }
  }
  return vis[u]=0;
}
int main(){
  scanf("%d%d",&n,&k);
  read(a);
  read(b);
  if(k==2){
    for(i=1;i<=n;i++)ans+=min(abs(a[i]-b[i]),8);
    return printf("%d",ans),0;
  }
  read(c);
  s=n*2+1;
  t=s+1;
  for(i=1;i<=n;i++)add(s,i,1,0),add(i+n,t,1,0);
  for(i=1;i<=n;i++){
    for(j=a[i]-7;j<=a[i]+7;j++)addedge(i,j);
    for(j=b[i]-7;j<=b[i]+7;j++)addedge(i,j);
    for(j=c[i]-7;j<=c[i]+7;j++)addedge(i,j);
  }
  for(i=1;i<=n;i++)for(j=g[i];j;j=e[j].nxt)h[e[j].v]=min(h[e[j].v],e[j].c);
  for(i=1;i<=n;i++)h[t]=min(h[t],h[i+n]);
  ans=n*24;
  while(dijkstra()){
    if(h[t]+d[t]>=0)break;
    while(bfs()){
      for(i=1;i<=t;i++)cur[i]=g[i],vis[i]=0;
      while(dfs(s));
    }
    for(i=1;i<=t;i++)h[i]+=d[i];
  }
  printf("%d",ans);
}

Round 6：

Automorphisms [B]

找重心作為根，如果兩個重心就拆了中間加個點作為根。

對于每個點，將兒子按hash值分組，對于每組，將答案乘以兒子數的階乘即可。

#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef vector<int>V;
const int N=500005,P=1000000007;
int n,m,cnt,i,x,y,A,B,ans,g[N],v[N<<1],nxt[N<<1],ed,fac[N],sz[N],f[N],q[N];
V tmp;map<V,int>T;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int y){
  sz[x]=1;
  for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x),sz[x]+=sz[v[i]];
  if(sz[x]>n-sz[x]&&!A)A=x;
  if(sz[x]==n-sz[x])A=x,B=y;
}
void cal(int x,int y){
  for(int i=g[x];i;i=nxt[i]){
    int u=v[i];
    if(u==y)continue;
    cal(u,x);
  }
  cnt=0;
  for(int i=g[x];i;i=nxt[i]){
    int u=v[i];
    if(u==y)continue;
    q[cnt++]=f[u];
  }
  sort(q,q+cnt);
  for(int i=0,j;i<cnt;i=j){
    for(j=i;j<cnt&&q[i]==q[j];j++);
    ans=1LL*ans*fac[j-i]%P;
  }
  tmp.resize(cnt);
  for(int i=0;i<cnt;i++)tmp[i]=q[i];
  int&o=T[tmp];
  if(!o)o=++m;
  f[x]=o;
}
int main(){
  scanf("%d",&n);
  for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
  for(fac[0]=i=1;i<=n;i++)fac[i]=1LL*fac[i-1]*i%P;
  dfs(1,0);
  ans=1;
  cal(A,B);
  if(B){
    cal(B,A);
    if(f[A]==f[B])ans=ans*2%P;
  }
  printf("%d",ans);
}

Kangaroos [A]

兩個區間$[x_1,y_1][x_2,y_2]$相交等價于$x_1\leq y_2$且$y_1\geq x_2$。

考慮離線，把所有區間看成二維的點建立K-D Tree。

然后從$1$到$n$依次加入每個區間，每次加入一個區間時，把所有與它相交的詢問的值$+1$，把所有與它不相交的詢問的值設為$0$。

在K-D Tree上打標記，最后每個詢問的答案為其值的歷史最大值，時間復雜度$O(n\sqrt{m})$。

#include<cstdio>
#include<algorithm>
const int N=200010,inf=-1,BUF=6000000;
int n,m,i,id[N],root,cmp_d,X,Y;struct P{int x,y;}a[N];char Buf[BUF],*buf=Buf;
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
struct node{
  int D[2],l,r,Max[2],Min[2];
  int m,d,e,hm,hd,he;
}t[N];
inline bool cmp(const node&a,const node&b){return a.D[cmp_d]<b.D[cmp_d];}
inline void Max(int&a,int b){if(a<b)a=b;}
inline void Min(int&a,int b){if(a>b)a=b;}
inline void up(int x){
  id[t[x].e]=x,t[x].e=t[x].he=inf;
  if(t[x].l){
    Max(t[x].Max[0],t[t[x].l].Max[0]);
    Min(t[x].Min[0],t[t[x].l].Min[0]);
    Max(t[x].Max[1],t[t[x].l].Max[1]);
    Min(t[x].Min[1],t[t[x].l].Min[1]);
  }
  if(t[x].r){
    Max(t[x].Max[0],t[t[x].r].Max[0]);
    Min(t[x].Min[0],t[t[x].r].Min[0]);
    Max(t[x].Max[1],t[t[x].r].Max[1]);
    Min(t[x].Min[1],t[t[x].r].Min[1]);
  }
}
int build(int l,int r,int D){
  int mid=(l+r)>>1;
  cmp_d=D,std::nth_element(t+l+1,t+mid+1,t+r+1,cmp);
  t[mid].Max[0]=t[mid].Min[0]=t[mid].D[0];
  t[mid].Max[1]=t[mid].Min[1]=t[mid].D[1];
  if(l!=mid)t[mid].l=build(l,mid-1,!D);
  if(r!=mid)t[mid].r=build(mid+1,r,!D);
  return up(mid),mid;
}
inline void hdoa(node&x,int v){
  Max(x.hm,x.m+v);
  if(x.e>inf)Max(x.he,x.e+v);else Max(x.hd,x.d+v);
}
inline void hdoc(node&x,int v){Max(x.hm,v);Max(x.he,v);}
inline void doa(node&x,int v){
  Max(x.hm,x.m+=v);
  if(x.e>inf)Max(x.he,x.e+=v);else Max(x.hd,x.d+=v);
}
inline void doc(node&x,int v){Max(x.hm,x.m=v);Max(x.he,x.e=v);x.d=0;}
inline void pb(node&x){
  if(x.hd){
    if(x.l)hdoa(t[x.l],x.hd);
    if(x.r)hdoa(t[x.r],x.hd);x.hd=0;
  }
  if(x.he>inf){
    if(x.l)hdoc(t[x.l],x.he);
    if(x.r)hdoc(t[x.r],x.he);
    x.he=inf;
  }
  if(x.d){
    if(x.l)doa(t[x.l],x.d);
    if(x.r)doa(t[x.r],x.d);
    x.d=0;
  }else if(x.e>inf){
    if(x.l)doc(t[x.l],x.e);
    if(x.r)doc(t[x.r],x.e);
    x.e=inf;
  }
}
void change(node&x){
  if(x.Min[0]>X||x.Max[1]<Y){doc(x,0);return;}
  if(x.Max[0]<=X&&x.Min[1]>=Y){doa(x,1);return;}
  pb(x);
  if(x.D[0]<=X&&x.D[1]>=Y)Max(x.hm,++x.m);else x.m=0;
  if(x.l)change(t[x.l]);
  if(x.r)change(t[x.r]);
}
void dfs(node&x){
  pb(x);
  if(x.l)dfs(t[x.l]);
  if(x.r)dfs(t[x.r]);
}
int main(){
  fread(Buf,1,BUF,stdin),read(n),read(m);
  for(i=1;i<=n;i++)read(a[i].x),read(a[i].y);
  for(i=1;i<=m;i++)read(t[i].D[0]),read(t[i].D[1]),t[i].e=i;
  root=build(1,m,0);
  for(i=1;i<=n;i++)X=a[i].y,Y=a[i].x,change(t[root]);
  dfs(t[root]);
  for(i=1;i<=m;i++)printf("%d\n",t[id[i]].hm);
}

Laser Pool [A]

與橫線以及豎線的交點個數很容易求，那么只要求出橫線豎線交點與運動軌跡的交點數即可。

運動軌跡可以劃分成若干條貫穿邊界的斜線，對于第一條和最后一條，可以用bitset暴力統計。

對于中間的部分，斜線都是完整的，可以FFT預處理。

時間復雜度$O(n\log n+\frac{nq}{32})$。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef unsigned int U;
const int N=100010,M=10010,L=262150;
int n,m,cb,ce,i,j,ab[N*2],arb[N*2],rab[N*2],rarb[N*2],g[65540];
char a[N],b[N];
struct Que{int x,y,vx,vy,t,ans;}e[M];
inline int popcount(U x){return g[x>>16]+g[x&65535];}
struct BIT{
  U v[N/32+5];
  void clr(){for(int i=0;i<=cb;i++)v[i]=0;}
  U get(int x){return v[x>>5]>>(x&31)&1;}
  void set(int x,U y){if((v[x>>5]>>(x&31)&1)^y)v[x>>5]^=1U<<(x&31);}
  void shl(int x,int y){
    int A=y>>5,B=y&31,C=(32-B)&31,D=x>>5,E=(D<<5)+31;
    for(int i=x;i<=E;i++)set(i,get(i+y));
    for(int i=D+1;i<=cb;i++){
      v[i]=v[i+A]>>B;
      if(C)v[i]|=v[i+A+1]<<C;
    }
  }
  void copy(int x,int y,const BIT&p){for(int i=x;i<=y;i++)v[i]=p.v[i];}
  void And(int x,int y,const BIT&p){for(int i=x;i<=y;i++)v[i]&=p.v[i];}
  int count(int x,int y){
    int A=x>>5,B=y>>5,C,ret=0;
    if(A==B){
      for(int i=x;i<=y;i++)if(v[A]>>(i&31)&1)ret++;
      return ret;
    }
    for(int i=A+1;i<B;i++)ret+=popcount(v[i]);
    C=(A<<5)+31;
    for(int i=x;i<=C;i++)if(v[A]>>(i&31)&1)ret++;
    C=B<<5;
    for(int i=C;i<=y;i++)if(v[B]>>(i&31)&1)ret++;
    return ret;
  }
}bA,bB,brA,brB,tA,tB;
inline void read(int&a){
  char c;bool f=0;a=0;
  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));
  if(c!='-')a=c-'0';else f=1;
  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';
  if(f)a=-a;
}
namespace FFT{
int k,j,pos[L];
const double pi=acos(-1.0);
struct comp{
  double r,i;comp(double _r=0,double _i=0){r=_r,i=_i;}
  comp operator+(const comp&x){return comp(r+x.r,i+x.i);}
  comp operator-(const comp&x){return comp(r-x.r,i-x.i);}
  comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}
}a[L],ra[L],b[L],rb[L],c[L];
void FFT(comp a[],int n,int t){
  for(int i=1;i<n;i++)if(i<pos[i])swap(a[i],a[pos[i]]);
  for(int d=0;(1<<d)<n;d++){
    int m=1<<d,m2=m<<1;
    double o=pi*2/m2*t;comp _w(cos(o),sin(o));
    for(int i=0;i<n;i+=m2){
      comp w(1,0);
      for(int j=0;j<m;j++){
        comp&A=a[i+j+m],&B=a[i+j],t=w*A;
        A=B-t;B=B+t;w=w*_w;
      }
    }
  }
  if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;
}
void work(){
  for(k=1;k<=n||k<=m;k<<=1);k<<=1;
  j=__builtin_ctz(k)-1;
  for(i=0;i<k;i++)pos[i]=pos[i>>1]>>1|((i&1)<<j);
  for(i=1;i<=n;i++)a[i].r=ra[n-i+1].r=::a[i];
  for(i=1;i<=m;i++)b[i].r=rb[m-i+1].r=::b[i];
  FFT(a,k,1),FFT(ra,k,1),FFT(b,k,1),FFT(rb,k,1);
  for(i=0;i<k;i++)c[i]=a[i]*b[i];
  FFT(c,k,-1);
  for(i=1;i<=n+m;i++)ab[i]=(int)(c[i].r+0.5);
  for(i=0;i<k;i++)c[i]=a[i]*rb[i];
  FFT(c,k,-1);
  for(i=1;i<=n+m;i++)arb[i]=(int)(c[i].r+0.5);
  for(i=0;i<k;i++)c[i]=ra[i]*b[i];
  FFT(c,k,-1);
  for(i=1;i<=n+m;i++)rab[i]=(int)(c[i].r+0.5);
  for(i=0;i<k;i++)c[i]=ra[i]*rb[i];
  FFT(c,k,-1);
  for(i=1;i<=n+m;i++)rarb[i]=(int)(c[i].r+0.5);
}
}
namespace Solve{
bool a[N],b[N];
int sa[N],sb[N];
int cnt,idx[4][N],idy[4][N];
int tot,st[N*8],en[N*8],v[N*8],pos[N*8],cur,q[N*8],sw[N*8];long long sl[N*8];
struct E{int sx,sy,ex,ey,len,w,d,nxt;}f[N*8];
inline bool check(int x,int y){return b[x]&&a[y];}
inline int abs(int x){return x>0?x:-x;}
inline int&getid(int x,int y,int d){
  if(y==1||y==n)return idx[d][x];
  return idy[d][y];
}
inline void makerev(int x){
  f[x].sx=f[x-1].ex;
  f[x].sy=f[x-1].ey;
  f[x].ex=f[x-1].sx;
  f[x].ey=f[x-1].sy;
  f[x].w=f[x-1].w;
  f[x].d=(f[x-1].d+2)&3;
}
inline int getnxt(int x,int y,int d){
  if(d==0){
    if(x<m&&y==n)return getid(x,y,(d+1)&3);
    if(y==n)return getid(x,y,(d+2)&3);
    return getid(x,y,(d+3)&3);
  }
  if(d==2){
    if(x>1&&y==1)return getid(x,y,(d+1)&3);
    if(y==1)return getid(x,y,(d+2)&3);
    return getid(x,y,(d+3)&3);
  }
  if(d==1){
    if(x<m&&y==1)return getid(x,y,(d+3)&3);
    if(y==1)return getid(x,y,(d+2)&3);
    return getid(x,y,(d+1)&3);
  }
  if(x>1&&y==n)return getid(x,y,(d+3)&3);
  if(y==n)return getid(x,y,(d+2)&3);
  return getid(x,y,(d+1)&3);
}
inline int cal(int x,int t,int n,int*s){
  if(x+t<=n)return s[x+t]-s[x-1];
  t-=n-x;
  int ret=s[n-1]-s[x-1];
  ret+=t/(n+n-2)*(s[n]+s[n-1]-s[1]);
  t%=n+n-2;
  if(t<n)return ret+s[n]-s[n-t-1];
  return ret+s[n]-s[1]+s[t-n+2];
}
inline int search(int L,int r,int x){
  int l=L,t=L-1,mid;
  while(l<=r)if(sl[mid=(l+r)>>1]-sl[L-1]<=x)l=(t=mid)+1;else r=mid-1;
  return t;
}
inline void ask(int x,int y,int t,int p){
  int&ans=e[p].ans;
  ans=cal(x,t,m,sb)+cal(y,t,n,sa);
  int ex=m,ey=y-x+m;
  if(ey>n)ey=n,ex=x-y+n;
  int d=ex-x;
  if(t<=d){
    tA.copy(y>>5,cb,bA);
    tB.copy(x>>5,cb,bB);
    tB.shl(0,x);
    tA.shl(0,y);
    tA.And(0,t>>5,tB);
    ans-=tA.count(0,t);
    return;
  }
  if(d){
    tA.copy(y>>5,cb,bA);
    tB.copy(x>>5,cb,bB);
    tB.shl(0,x);
    tA.shl(0,y);
    tA.And(0,(d-1)>>5,tB);
    ans-=tA.count(0,d-1);
  }
  t-=d;
  int o=getnxt(ex,ey,0);
  int l=st[v[o]],r=en[v[o]];
  o=pos[o];
  int u=search(o,r,t);
  ans-=sw[u]-sw[o-1];
  t-=sl[u]-sl[o-1];
  o=u+1;
  if(o>r){
    ans-=t/(sl[r]-sl[l-1])*(sw[r]-sw[l-1]);
    t%=sl[r]-sl[l-1];
    u=search(l,r,t);
    ans-=sw[u]-sw[l-1];
    t-=sl[u]-sl[l-1];
    o=u+1;
  }
  o=q[o];
  x=f[o].sx,y=f[o].sy;
  if(f[o].d==0){
    tA.copy(y>>5,cb,bA);
    tB.copy(x>>5,cb,bB);
  }
  if(f[o].d==1){
    y=n-y+1;
    tA.copy(y>>5,cb,brA);
    tB.copy(x>>5,cb,bB);
  }
  if(f[o].d==2){
    x=m-x+1;
    y=n-y+1;
    tA.copy(y>>5,cb,brA);
    tB.copy(x>>5,cb,brB);
  }
  if(f[o].d==3){
    x=m-x+1;
    tA.copy(y>>5,cb,bA);
    tB.copy(x>>5,cb,brB);
  }
  tB.shl(0,x);
  tA.shl(0,y);
  tA.And(0,t>>5,tB);
  ans-=tA.count(0,t);
}
void work(int*A,int*B){
  for(i=1;i<=n;i++)sa[i]=sa[i-1]+a[i],bA.set(i,a[i]),brA.set(n-i+1,a[i]);
  for(i=1;i<=m;i++)sb[i]=sb[i-1]+b[i],bB.set(i,b[i]),brB.set(m-i+1,b[i]);
  cnt=0;
  for(i=1;i<m;i++){
    cnt++;
    f[cnt].sx=i,f[cnt].sy=1;
    f[cnt].ex=m,f[cnt].ey=m-i+1;
    if(f[cnt].ey>n)f[cnt].ey=n,f[cnt].ex=n-1+i;
    f[cnt].w=B[m-i+2];
    f[cnt].d=0;
    makerev(++cnt);
  }
  for(i=2;i<n;i++){
    cnt++;
    f[cnt].sx=1,f[cnt].sy=i;
    f[cnt].ex=m,f[cnt].ey=m-1+i;
    if(f[cnt].ey>n)f[cnt].ey=n,f[cnt].ex=n-i+1;
    f[cnt].w=B[m+i];
    f[cnt].d=0;
    makerev(++cnt);
  }
  for(i=2;i<=m;i++){
    cnt++;
    f[cnt].sx=i,f[cnt].sy=1;
    f[cnt].ex=1,f[cnt].ey=i;
    if(f[cnt].ey>n)f[cnt].ey=n,f[cnt].ex=i+1-n;
    f[cnt].w=A[i+1];
    f[cnt].d=3;
    makerev(++cnt);
  }
  for(i=2;i<n;i++){
    cnt++;
    f[cnt].sx=m,f[cnt].sy=i;
    f[cnt].ex=1,f[cnt].ey=m+i-1;
    if(f[cnt].ey>n)f[cnt].ey=n,f[cnt].ex=m+i-n;
    f[cnt].w=A[i+m];
    f[cnt].d=3;
    makerev(++cnt);
  }
  for(i=1;i<=cnt;i++){
    f[i].len=abs(f[i].sx-f[i].ex);
    f[i].w-=check(f[i].ex,f[i].ey);
    getid(f[i].sx,f[i].sy,f[i].d)=i;
  }
  for(i=1;i<=cnt;i++)f[i].nxt=getnxt(f[i].ex,f[i].ey,f[i].d);
  cur=tot=0;
  for(i=1;i<=cnt;i++)v[i]=0;
  for(i=1;i<=cnt;i++)if(!v[i]){
    st[++tot]=cur+1;
    for(j=i;!v[j];j=f[j].nxt)v[q[++cur]=j]=tot;
    en[tot]=cur;
  }
  for(i=1;i<=cnt;i++)sl[i]=sl[i-1]+f[q[i]].len,sw[i]=sw[i-1]+f[q[i]].w,pos[q[i]]=i;
}
}
int main(){
  for(i=1;i<65536;i++)g[i]=g[i>>1]+(i&1);
  read(n),read(m);
  scanf("%s%s",a+1,b+1);
  for(i=1;i<=n;i++)a[i]-='0';
  for(i=1;i<=m;i++)b[i]-='0';
  read(ce);
  for(i=1;i<=ce;i++)read(e[i].x),read(e[i].y),read(e[i].vx),read(e[i].vy),read(e[i].t);
  FFT::work();
  cb=(n>m?n:m)>>5;
  for(i=1;i<=n;i++)Solve::a[i]=a[i];
  for(i=1;i<=m;i++)Solve::b[i]=b[i];
  Solve::work(ab,arb);
  for(i=1;i<=ce;i++)if(e[i].vx==1&&e[i].vy==1)Solve::ask(e[i].x,e[i].y,e[i].t,i);
  for(i=1;i<=n;i++)Solve::a[i]=a[n-i+1];
  for(i=1;i<=m;i++)Solve::b[i]=b[i];
  Solve::work(rab,rarb);
  for(i=1;i<=ce;i++)if(e[i].vx==1&&e[i].vy==-1)Solve::ask(e[i].x,n-e[i].y+1,e[i].t,i);
  for(i=1;i<=n;i++)Solve::a[i]=a[i];
  for(i=1;i<=m;i++)Solve::b[i]=b[m-i+1];
  Solve::work(arb,ab);
  for(i=1;i<=ce;i++)if(e[i].vx==-1&&e[i].vy==1)Solve::ask(m-e[i].x+1,e[i].y,e[i].t,i);
  for(i=1;i<=n;i++)Solve::a[i]=a[n-i+1];
  for(i=1;i<=m;i++)Solve::b[i]=b[m-i+1];
  Solve::work(rarb,rab);
  for(i=1;i<=ce;i++)if(e[i].vx==-1&&e[i].vy==-1)Solve::ask(m-e[i].x+1,n-e[i].y+1,e[i].t,i);
  for(i=1;i<=ce;i++)printf("%d\n",e[i].ans);
}

The Shortest Period [B]

枚舉答案長度$L$，設$A$和$B$分別為第一個循環節和反串的第一個循環節：

1. 壞點不在$A$，那么可以暴力匹配檢驗。

2. 壞點不在$B$，那么把串翻轉后不在$A$中，轉化為$1$。

3. 壞點在$A$和$B$的交里面，那么只要長度為$N-L+1$的前后綴相同，那么就存在長度為$L$的循環節。

通過擴展KMP和Hash快速判斷即可，時間復雜度$O(dn\log n)$。

#include<cstdio>
const int N=200010,P=233;
int T,n,i,j,t,k,p,l,ans,g[N];char a[N];unsigned int pow[N],f[N];
inline void swap(char&a,char&b){char c=a;a=b;b=c;}
inline unsigned int hash(int l,int r){return f[r]-f[l-1]*pow[r-l+1];}
inline int min(int a,int b){return a<b?a:b;}
void solve(){
  for(i=1;i<=n;i++)f[i]=f[i-1]*P+a[i];
  for(g[i=0]=n;i<n-1&&a[i+1]==a[i+2];i++);
  for(g[t=1]=i,k=2;k<n;k++){
    p=t+g[t]-1,l=g[k-t];
    if(k+l>p){
      j=(p-k+1)>0?(p-k+1):0;
      while(k+j<n&&a[k+j+1]==a[j+1])j++;
      g[k]=j,t=k;
    }else g[k]=l;
  }
  for(i=n;i;i--)g[i]=g[i-1];
  for(i=1;i<ans;i++){
    j=g[i+1];
    if(j==n-i||g[i+2]>=n-i+1)ans=i;else{
      j+=i+2,k=(j-2)/i*i+1,t=k+i;
      if(t>n)t=n;
      if(hash(j,t)!=hash(j-k,t-k)||g[t+1]<n-t)continue;
      for(t++;t<=n;t+=i)if(g[t]<min(i,n-t+1))break;
      if(t>n)ans=i;
    }
  }
}
int main(){
  for(pow[0]=i=1;i<N;i++)pow[i]=pow[i-1]*P;
  scanf("%d",&T);
  while(T--){
    scanf("%d%s",&n,a+1);
    ans=n-1;
    solve();
    for(i=1;i<n-i+1;i++)swap(a[i],a[n-i+1]);
    solve();
    printf("%d\n",ans);
  }
}

Trial Finals：

Wyznaczanie planu sieci drogowej 2

前$n-2$次每次取出一個度數$=1$的點和一個度數$>1$的點連邊；最后一次取出兩個度數$=1$的點連邊。

#include<cstdio>
#include<cstdlib>
const int N=2000005;
int n,i,x,y,ca,cb,a[N],b[N],f[N],d[N],deg[N];
void NIE(){
  puts("BRAK");
  std::exit(0);
}
int main(){
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&deg[i]);
    if(deg[i]==1)a[++ca]=i;else b[++cb]=i;
  }
  for(i=1;i<n-1;i++){
    if(!ca)NIE();
    if(!cb)NIE();
    x=a[ca--];
    y=b[cb--];
    f[x]=y;
    d[x]++;
    d[y]++;
    if(d[y]+1<deg[y])b[++cb]=y;else a[++ca]=y;
  }
  if(!ca)NIE();
  x=a[ca--];
  if(!ca)NIE();
  y=a[ca--];
  f[x]=y;
  d[x]++;
  d[y]++;
  for(i=1;i<=n;i++)if(d[i]!=deg[i])NIE();
  for(i=1;i<=n;i++)if(f[i])printf("%d %d\n",i,f[i]);
}

Finals：

Computational Biology

對于每個長度為$m$的子串，由其向循環移一位的字符串hash連邊，找最大環即可。

時間復雜度$O(qn\log n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
typedef pair<ull,ull>P;
const int N=500005,S=233;
int n,q,m,ce,i,j,f[N],vis[N],ans,now;
char a[N];
ull p[N],tmp,base;
P e[N];
int main(){
  scanf("%d%d%s",&n,&q,a+1);
  for(p[0]=i=1;i<=n;i++)p[i]=p[i-1]*S;
  while(q--){
    scanf("%d",&m);
    tmp=ce=0,base=p[m];
    for(i=1;i<=n;i++){
      tmp=tmp*S+a[i];
      if(i>m)tmp-=base*a[i-m];
      e[++ce]=P(tmp,tmp*S-(base-1)*a[i-m+1]);
    }
    sort(e+1,e+ce+1);
    ans=0;
    for(i=1;i<=ce;i++)f[i]=0;
    for(i=1;i<=ce;i=j){
      for(j=i;j<=ce&&e[i]==e[j];j++);
      f[i]=j-i;
    }
    for(i=1;i<=ce;i++)if(f[i]){
      tmp=e[i].second;
      now=0;
      while(1){
        j=lower_bound(e+1,e+ce+1,P(tmp,0))-e;
        if(j<1||j>ce||e[j].first!=tmp||!f[j])break;
        now+=f[j];
        f[j]=0;
        if(j==i){
          if(now>ans)ans=now;
          break;
        }
        tmp=e[j].second;
      }
    }
    printf("%d\n",ans);
  }
}

Byteland Worldbeat Publishers

不妨設$n=m$，考慮一個完美匹配：

對于每條匹配邊$(左u,右v,w)$，連邊$左 u\rightarrow 右 v$，邊權$w$。
對于每條非匹配邊$(左u,右v,w)$，連邊$右 v\rightarrow 左 u$，邊權$-w$。

那么每個完美匹配權值和相同當且僅當每個環的邊權和都是$0$。

注意到所有環都可以由$左u\rightarrow 右 v\rightarrow 左 u+1\rightarrow 右 v+1\rightarrow 左 u$拼成，于是對于所有$(u,v)$檢查這樣的環邊權和是否是$0$即可。

將信息排序后雙指針即可完成檢查。

時間復雜度$O(k\log k+n+m)$。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005,M=300005;
int Case,n,m,i,j,k,o,nxt,A,B,C,D,st[N],en[N];
struct E{int x,l,r,v;}e[M];
inline bool cmp(const E&a,const E&b){return a.x==b.x?a.l<b.l:a.x<b.x;}
inline void up(int x){
  if(x<o||x>nxt)return;
  nxt=x;
}
bool check(){
  scanf("%d%d",&n,&m);
  if(n<m)n=m;
  scanf("%d",&m);
  for(i=1;i<=m;i++)scanf("%d%d%d%d",&e[i].x,&e[i].l,&e[i].r,&e[i].v);
  sort(e+1,e+m+1,cmp);
  for(i=1;i<=n;i++)st[i]=m+1,en[i]=0;
  for(i=1;i<=m;i++)en[e[i].x]=i;
  for(i=m;i;i--)st[e[i].x]=i;
  for(i=1;i<n;i++){
    j=st[i],k=st[i+1],o=1;
    while(o<n){
      while(j<=en[i]&&e[j].r<o)j++;
      while(k<=en[i+1]&&e[k].r<o)k++;
      A=0;
      if(j<=en[i]&&e[j].l<=o)A=e[j].v;
      B=0;
      if(k<=en[i+1]&&e[k].l<=o)B=e[k].v;
      o++;
      while(j<=en[i]&&e[j].r<o)j++;
      while(k<=en[i+1]&&e[k].r<o)k++;
      C=0;
      if(j<=en[i]&&e[j].l<=o)C=e[j].v;
      D=0;
      if(k<=en[i+1]&&e[k].l<=o)D=e[k].v;
      if(A+D!=B+C)return 0;
      nxt=n;
      up(n-1);
      if(j<=en[i]){
        up(e[j].l-2);
        up(e[j].l-1);
        up(e[j].r-1);
        up(e[j].r);
      }
      if(k<=en[i+1]){
        up(e[k].l-2);
        up(e[k].l-1);
        up(e[k].r-1);
        up(e[k].r);
      }
      o=nxt;
    }
  }
  return 1;
}
int main(){
  scanf("%d",&Case);
  while(Case--)puts(check()?"TAK":"NIE");
}

Exam

即求出與每個矩形有交的編號最大的矩形$f[i]$，若$f[i]\leq i$則矩形$i$處于頂層。

枚舉矩形$i$和矩形$j$的形狀，那么詢問范圍是二維滑窗，對著$x$掃描線，對著$y$維護線段樹即可。

時間復雜度$O(n\log n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010,M=262150;
int n,m,A,B,i,j,k,tmp,q[N],id[N],pos[N],v[M],f[N],ans,fin[N];
struct E{int x,y,r,t;}e[N];
inline bool cmpe(const E&a,const E&b){return a.x<b.x;}
inline bool cmp(int x,int y){return e[x].y<e[y].y;}
void build(int x,int a,int b){
  v[x]=0;
  if(a==b){pos[a]=x;return;}
  int mid=(a+b)>>1;
  build(x<<1,a,mid),build(x<<1|1,mid+1,b);
}
inline void change(int x,int p){
  v[x=pos[x]]=p;
  for(x>>=1;x;x>>=1)v[x]=max(v[x<<1],v[x<<1|1]);
}
inline void up(int&a,int b){a<b?(a=b):0;}
void ask(int x,int a,int b,int c,int d){
  if(e[q[a]].y>=d||e[q[b]].y<=c||!v[x])return;
  if(e[q[a]].y>c&&e[q[b]].y<d){up(tmp,v[x]);return;}
  if(a==b)return;
  int mid=(a+b)>>1;
  ask(x<<1,a,mid,c,d);
  ask(x<<1|1,mid+1,b,c,d);
}
void gao(int me,int him,int xl,int xr,int yl,int yr){
  for(m=0,i=1;i<=n;i++)if(e[i].r==him)q[++m]=i;
  if(!m)return;
  sort(q+1,q+m+1,cmp);
  for(i=1;i<=m;i++)id[q[i]]=i;
  build(1,1,m);
  for(i=j=k=1;i<=n;i++)if(e[i].r==me){
    while(j<=n&&e[j].x<e[i].x+xr){
      if(e[j].r==him)change(id[j],e[j].t);
      j++;
    }
    while(k<=n&&e[k].x<=e[i].x+xl){
      if(e[k].r==him)change(id[k],0);
      k++;
    }
    tmp=0;
    ask(1,1,m,e[i].y+yl,e[i].y+yr);
    up(f[e[i].t],tmp);
  }
}
int main(){
  scanf("%d%d%d",&n,&A,&B);
  for(i=1;i<=n;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].r),e[i].t=i;
  sort(e+1,e+n+1,cmpe);
  gao(0,0,-B,B,-A,A);
  gao(1,1,-A,A,-B,B);
  gao(0,1,-A,B,-B,A);
  gao(1,0,-B,A,-A,B);
  for(i=1;i<=n;i++)if(f[i]<=i)fin[++ans]=i;
  printf("%d\n",ans);
  for(i=1;i<=ans;i++)printf("%d ",fin[i]);
}

Computational Geometry

$n$為奇數則無解，否則$n$的方案可以由$n-2$的方案右邊拼上$1\times 2$或$2\times 1$的矩形得到。

#include<cstdio>
int n,i,o,x;
int main(){
  scanf("%d",&n);
  if(n&1)return puts("NIE"),0;
  puts("0 0");
  puts("0 2");
  puts("2 2");
  for(i=4,x=2;i<n;i+=2,o^=1){
    if(!o){
      printf("%d 1\n",x);
      printf("%d 1\n",x+=2);
    }else{
      printf("%d 2\n",x);
      printf("%d 2\n",x+=1);
    }
  }
  printf("%d 0",x);
}

Coprime Numbers

設$g_i$表示數字$i$倍數的出現次數，$f_i$表示有多少對數字的最大公約數是$i$的倍數，則$f_i=C(g_i,2)-f_{2i}-f_{3i}-\dots$。

時間復雜度$O(a\log a)$。

#include<cstdio>
const int M=3000005;
int n,m,i,j,x,c[M];long long f[M];
int main(){
  scanf("%d",&n);
  while(n--){
    scanf("%d",&x);
    c[x]++;
    if(x>m)m=x;
  }
  for(i=m;i;i--){
    for(j=i;j<=m;j+=i)f[i]+=c[j];
    f[i]=1LL*f[i]*(f[i]-1);
    for(j=i+i;j<=m;j+=i)f[i]-=f[j];
  }
  printf("%lld",f[1]/2);
}

Prime prime power

對于$a^b$，如果$b=2$，那么在$[\sqrt{n},\sqrt{n}+k\log k]$內必定能找到$k$個質數作為$a$。

篩出$n^{\frac{1}{4}}$內的所有質數，暴力枚舉所有落在該區間內的倍數，將其篩掉，即可判斷每個數是否是質數。

然后以最大的質數的平方作為上界，枚舉更大的$a$和$b$，這里方案數指數級下降，故暴力即可。

最后排序輸出第$k$小的值即可。

時間復雜度$O(n^{\frac{1}{3}}+k\log^2k)$。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1050010;
ll n,lim,t,o,b[66],q[N*2];int cnt,k,m,i,j,a[66],p[N],tot;bool v[N],vis[N*2];
inline ll pow(ll a,int b){
  ll t=1;
  while(b--){
    if(a>lim/t)return lim+1;
    t*=a;
  }
  return t;
}
inline ll powfast(ll a,int b){ll t=1;for(;b;b>>=1,a*=a)if(b&1)t*=a;return t;}
void sieve(ll n){
  int i,j;
  for(tot=0,i=2;i<=n;i++){
    if(!v[i])p[tot++]=i;
    for(j=0;j<tot&&i*p[j]<=n;j++){
      v[i*p[j]]=1;
      if(i%p[j]==0)break;
    }
  }
}
inline void check(int x){for(ll i=max(t/x*x,2LL*x);i<=lim;i+=x)if(i>=t)vis[i-t]=1;}
int main(){
  scanf("%lld%d",&n,&k);
  t=max((ll)sqrt(n)-10,2LL);
  while(t*t<=n)t++;
  sieve((ll)sqrt(lim=t+max(k,10)*21)+5);
  for(i=0;i<tot;i++)check(p[i]);
  for(o=t;o<=lim&&cnt<k;o++)if(!vis[o-t])q[++cnt]=o*o;
  lim=q[cnt];
  for(i=3;;a[++m]=i++)if((1LL<<i)>lim)break;
  for(b[1]=2;(b[1]+1)*(b[1]+1)*(b[1]+1)<=lim;b[1]++);
  for(i=2;i<=m;i++)for(b[i]=b[i-1];pow(b[i],a[i])>lim;b[i]--);
  sieve(max(b[1],1LL*a[m]));
  for(i=1;i<=m;i++)if(!v[a[i]]){
    for(j=0;j<tot&&powfast(p[j],a[i])<=n;j++);
    for(;j<tot&&p[j]<=b[i];j++)q[++cnt]=powfast(p[j],a[i]);
  }
  sort(q+1,q+cnt+1);
  printf("%lld",q[k]);
}

Hard Choice

在每條邊兩個點中間加上一個虛擬點代表這條邊權，就可以化邊權為點權。

把沒刪掉的邊用LCT維護一棵生成樹，樹邊都是橋。

對于一條非樹邊，把樹上對應路徑上所有邊的權值都修改為$0$，表示都不是橋。

然后倒著處理詢問，對于每次刪掉的邊，把兩點路徑上邊權都修改為$0$。

詢問等價于查詢兩點間邊權和，若兩點連通且路徑上不存在橋，則有解。

#include<cstdio>
#include<map>
const int N=200010,BUF=5000000;
char Buf[BUF],*buf=Buf;
int a[N],n,m,i,x,fa[N],edge[N][2],ask[N][4],q;
struct LCT{int f,son[2],sum,data;bool rev,tag;}T[N];
int father(int x){return fa[x]==x?x:fa[x]=father(fa[x]);}
std::map<int,bool>del[N>>1];
inline void swap(int&a,int&b){int c=a;a=b;b=c;}
inline bool isroot(int x){return !T[x].f||T[T[x].f].son[0]!=x&&T[T[x].f].son[1]!=x;}
inline void rev1(int x){if(!x)return;swap(T[x].son[0],T[x].son[1]),T[x].rev^=1;}
inline void makezero1(int x){if(!x)return;T[x].sum=T[x].data=0;T[x].tag=1;}
inline void pb(int x){
  if(T[x].rev)rev1(T[x].son[0]),rev1(T[x].son[1]),T[x].rev=0;
  if(T[x].tag)makezero1(T[x].son[0]),makezero1(T[x].son[1]),T[x].tag=0;
}
inline void up(int x){T[x].sum=T[x].data|T[T[x].son[0]].sum|T[T[x].son[1]].sum;}
inline void rotate(int x){
  int y=T[x].f,w=T[y].son[1]==x;
  T[y].son[w]=T[x].son[w^1];
  if(T[x].son[w^1])T[T[x].son[w^1]].f=y;
  if(T[y].f){
    int z=T[y].f;
    if(T[z].son[0]==y)T[z].son[0]=x;else if(T[z].son[1]==y)T[z].son[1]=x;
  }
  T[x].f=T[y].f;T[x].son[w^1]=y;T[y].f=x;up(y);
}
inline void splay(int x){
  int s=1,i=x,y;a[1]=i;
  while(!isroot(i))a[++s]=i=T[i].f;
  while(s)pb(a[s--]);
  while(!isroot(x)){
    y=T[x].f;
    if(!isroot(y)){if((T[T[y].f].son[0]==y)^(T[y].son[0]==x))rotate(x);else rotate(y);}
    rotate(x);
  }
  up(x);
}
inline void access(int x){for(int y=0;x;y=x,x=T[x].f)splay(x),T[x].son[1]=y,up(x);}
inline void makeroot(int x){access(x);splay(x);rev1(x);}
inline void link(int x,int y){makeroot(x);T[x].f=y;access(x);}
inline void makezero(int x,int y){
  if(father(x)!=father(y)){
    fa[father(x)]=father(y);
    n++;
    T[n].sum=T[n].data=1;
    link(x,n);link(n,y);
    return;
  }
  makeroot(x);
  access(y);
  splay(x);
  makezero1(x);
}
inline int getsum(int x,int y){
  if(father(x)!=father(y))return 1;
  makeroot(x);
  access(y);
  splay(x);
  return T[x].sum;
}
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
int main(){
  fread(Buf,1,BUF,stdin);read(n);read(m);read(q);
  for(i=1;i<=n;i++)fa[i]=i;
  for(i=1;i<=m;i++){
    read(edge[i][0]);read(edge[i][1]);
    if(edge[i][0]>edge[i][1])swap(edge[i][0],edge[i][1]);
  }
  for(i=1;i<=q;i++){
    while(*buf!='Z'&&*buf!='P')buf++;
    ask[i][0]=x=*buf=='P',buf++;
    read(ask[i][1]);read(ask[i][2]);
    if(ask[i][1]>ask[i][2])swap(ask[i][1],ask[i][2]);
    if(!x)del[ask[i][1]][ask[i][2]]=1;
  }
  for(i=1;i<=m;i++)if(!del[edge[i][0]][edge[i][1]])if(father(edge[i][0])!=father(edge[i][1])){
    fa[father(edge[i][0])]=father(edge[i][1]);
    n++;
    T[n].sum=T[n].data=1;
    link(edge[i][0],n);link(n,edge[i][1]);
    del[edge[i][0]][edge[i][1]]=1;
  }
  for(i=1;i<=m;i++)if(!del[edge[i][0]][edge[i][1]])makezero(edge[i][0],edge[i][1]);
  for(i=q;i;i--)if(!ask[i][0])makezero(ask[i][1],ask[i][2]);else ask[i][3]=getsum(ask[i][1],ask[i][2]);
  for(i=1;i<=q;i++)if(ask[i][0])puts(ask[i][3]?"NIE":"TAK");
}

posted @ 2022-10-16 17:26 Claris 閱讀(189) 評論(0) 收藏舉報

刷新頁面返回頂部

Claris' Blog

Potyczki Algorytmiczne 2011

公告