ZigZagK的博客
2020 CCPC 威海站 部分题解
2020年12月22日 18:53
CCPC
查看标签

比赛链接

我是代码工具人,打的都是代码题2333。

B. Labyrinth

如果终点起点构成的矩阵中没有黑洞,那么答案显然就是曼哈顿距离。否则最优解一定会贴着至少一个黑洞走。

把黑洞周围四个点都存下来,每个点做BFS求到网格其他点的距离,然后每次询问时暴力枚举贴着哪个点就行了。

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int dif[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
const int maxn=450,maxt=200000,maxk=42*4;

int n,m,K,te,X[maxk+5],Y[maxk+5];bool flip;
pair<int,int> p[maxk+5];bool gg[maxt+5];
vector<int> sum[maxn+5];
vector<int> dis[maxk+5][maxn+5];
pair<int,int> que[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline void Point(int &X,int &Y) {readi(X);readi(Y);if (flip) swap(X,Y);}
#define ID(x,y) (((x)-1)*m+(y))
inline bool check(int x,int y) {return 1<=x && x<=n && 1<=y && y<=m && !gg[ID(x,y)];}
void BFS(int i,int X,int Y){
    int Head=0,Tail=0;que[++Tail]=mp(X,Y);dis[i][X][Y]=0;
    while (Head!=Tail){
        Head++;int x=que[Head].fr,y=que[Head].sc,d=dis[i][x][y];
        for (int f=0,xx,yy;f<4;f++)
            if (check(xx=x+dif[f][0],yy=y+dif[f][1]) && dis[i][xx][yy]==1e9)
                dis[i][xx][yy]=d+1,que[++Tail]=mp(xx,yy);
    }
}
int Count(int A,int B,int C,int D) {return sum[C][D]-sum[A-1][D]-sum[C][B-1]+sum[A-1][B-1];}
inline int absi(int x) {return x<0?-x:x;}
int main(){
    freopen("B.in","r",stdin);freopen("B.out","w",stdout);
    readi(n);readi(m);if (n>m) swap(n,m),flip=true;readi(K);readi(te);
    for (int i=1;i<=K;i++) Point(X[i],Y[i]),gg[ID(X[i],Y[i])]=true;
    int tem=K;K=0;
    for (int i=1;i<=tem;i++)
        for (int f=0;f<4;f++)
            if (check(X[i]+dif[f][0],Y[i]+dif[f][1]))
                p[++K]=mp(X[i]+dif[f][0],Y[i]+dif[f][1]);
    sort(p+1,p+1+K);K=unique(p+1,p+1+K)-(p+1);
    for (int i=1;i<=K;i++){
        for (int j=0;j<=n;j++) dis[i][j].resize(m+1,1e9);
        BFS(i,p[i].fr,p[i].sc);
    }
    for (int i=0;i<=n;i++) sum[i].resize(m+1);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            sum[i][j]=sum[i][j-1]+gg[ID(i,j)];
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            sum[i][j]+=sum[i-1][j];
    for (int t=1;t<=te;t++){
        int A,B,C,D;Point(A,B);Point(C,D);
        if (!Count(min(A,C),min(B,D),max(A,C),max(B,D))) printf("%d\n",absi(A-C)+absi(B-D)); else {
            int ans=1e9;for (int i=1;i<=K;i++) ans=min(ans,dis[i][A][B]+dis[i][C][D]);
            ans==1e9?puts("-1"):printf("%d\n",ans);
        }
    }
    return 0;
}

D. ABC Conjecture

猜结论:如果 $rad(c)=c$ 则有解,否则无解。

证明:

  • $rad(c)=c$ 时,显然 $rad(abc)\ge rad(c)=c$ ,所以无解。
  • $rad(c)<c$ 时,则至少有一个素数 $p$ 是 $c$ 含有多个的,假设 $c=p^2q$ ,令 $a=pq,b=(p-1)pq$ ,那么 $rad(abc)=rad((p-1)c)\le (p-1)pq<p^2q=c$ ,所以有解。

用PR分解 $c$ 检查 $c$ 中每个素数是否只有一个就行了。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;typedef long double DB;
const int maxp=10000,prime[]={2,3,5,7,11,13,17,19};

int te,P;LL n,p[maxp+5];

inline LL Mul(LL x,LL y,LL MOD) {return ((x*y-(LL)((DB)x/MOD*y)*MOD)%MOD+MOD)%MOD;}
inline LL Pow(LL w,LL b,LL MOD) {LL s=1;for (;b;b>>=1,w=Mul(w,w,MOD)) if (b&1) s=Mul(s,w,MOD);return s;}
inline bool MR(LL n){
    for (int i=0;i<8;i++) if (!(n%prime[i])) return n==prime[i];
    for (int t=1;t<=10;t++){
        int k=0;LL x,s;for (x=n-1;!(x&1);x>>=1,k++);x=Pow(rand()%(n-2)+2,x,n);
        if (x==1) continue;
        for (;k;k--,x=s) {s=Mul(x,x,n);if (s==1) {if (x<n-1) return false;break;}}
        if (s>1) return false;
    }return true;
}
#define Abs(x) ((x)<0?-(x):(x))
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
inline LL lcm(LL a,LL b) {return a/gcd(a,b)*b;}
inline void AMOD(LL &x,LL tem,LL MOD) {if ((x+=tem)>=MOD) x-=MOD;}
inline LL FindD(LL n){
    LL x=rand()%(n-1)+1,y=x,r=rand()%(n-1)+1;
    for (int i=1,k=1;;i++){
        AMOD(x=Mul(x,x,n),r,n-1);x++;if (x==y) return -1;LL GCD=gcd(Abs(x-y),n);
        if (GCD>1) return GCD;if (i==k) k<<=1,y=x;
    }
}
void PR(LL n){
    if (n==1) return;if (MR(n)) {p[++P]=n;return;}
    LL D;for (D=FindD(n);D<0;D=FindD(n));PR(D);PR(n/D);
}
int main(){
    for (scanf("%d",&te);te;te--){
        scanf("%lld",&n);P=0;PR(n);
        sort(p+1,p+1+P);
        int m=unique(p+1,p+1+P)-(p+1);
        m!=P?puts("yes"):puts("no");
    }
    return 0;
}

G. Caesar Cipher

如果没有$\bmod65536$ ,就是个裸的线段树维护哈希值,需要支持区间 $+k$ 。

但是有了$\bmod65536$ ,就会导致 $65535+1$ 变成 $0$ ,这就没办法打标记了。

不过,我们不难发现,每个位置变成 $0$ 的次数最多为 ${500000\over 65536}\approx 8$ 次,所以我们可以在每次出现 $0$ 的时候暴力修改变成 $0$ 的位置,这样就不会导致打标记暴毙了。

#include<cstdio>
#include<cctype>
using namespace std;
typedef unsigned long long ULL;
const int maxn=500000,maxt=maxn<<2,BA=19260817,MOD=1e9+7;

int n,te,a[maxn+5];
int len[maxt+5],MIN[maxt+5],ID[maxt+5],tag[maxt+5];
ULL pw[maxn+5],ha[maxt+5],sum[maxn+5];
int MN,who;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
void Pushup(int p){
    ha[p]=(ha[p<<1]*pw[len[p<<1|1]]+ha[p<<1|1])%MOD;
    if (MIN[p<<1]<MIN[p<<1|1]) MIN[p]=MIN[p<<1],ID[p]=ID[p<<1];
    else MIN[p]=MIN[p<<1|1],ID[p]=ID[p<<1|1];
}
void Build(int L,int R,int p=1){
    len[p]=R-L+1;if (L==R) {MIN[p]=65536-a[L];ID[p]=L;ha[p]=a[L];return;}
    int mid=L+(R-L>>1);Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p);
}
void Addtag(int p,int k) {ha[p]=(ha[p]+sum[len[p]]*k)%MOD;MIN[p]-=k;tag[p]+=k;}
void Pushdown(int p) {if (tag[p]) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=0;}
void Insert(int L,int R,int k,int l=1,int r=n,int p=1){
    if (L==l && r==R) return Addtag(p,k);
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Insert(L,R,k,l,mid,p<<1); else if (L>mid) Insert(L,R,k,mid+1,r,p<<1|1);
    else Insert(L,mid,k,l,mid,p<<1),Insert(mid+1,R,k,mid+1,r,p<<1|1);
    Pushup(p);
}
void Askmin(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R) {if (MIN[p]<MN) MN=MIN[p],who=ID[p];return;}
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Askmin(L,R,l,mid,p<<1); else if (L>mid) Askmin(L,R,mid+1,r,p<<1|1);
    else Askmin(L,mid,l,mid,p<<1),Askmin(mid+1,R,mid+1,r,p<<1|1);
}
void Update(int pos,int l=1,int r=n,int p=1){
    if (l==r) {MIN[p]=65536;ha[p]=0;return;}
    int mid=l+(r-l>>1);Pushdown(p);
    if (pos<=mid) Update(pos,l,mid,p<<1); else Update(pos,mid+1,r,p<<1|1);
    Pushup(p);
}
ULL Hash(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R) return ha[p];
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Hash(L,R,l,mid,p<<1); else if (L>mid) return Hash(L,R,mid+1,r,p<<1|1);
    else return (Hash(L,mid,l,mid,p<<1)*pw[R-mid]+Hash(mid+1,R,mid+1,r,p<<1|1))%MOD;
}
int main(){
    freopen("G.in","r",stdin);freopen("G.out","w",stdout);
    readi(n);readi(te);
    pw[0]=1;for (int i=1;i<=n;i++) pw[i]=pw[i-1]*BA%MOD;
    for (int i=1;i<=n;i++) sum[i]=(sum[i-1]+pw[i-1])%MOD;
    for (int i=1;i<=n;i++) readi(a[i]);Build(1,n);
    for (int t=1;t<=te;t++){
        int tp;readi(tp);
        if (tp==1){
            int L,R;readi(L);readi(R);Insert(L,R,1);
            for (MN=2e9,Askmin(L,R);!MN;MN=2e9,Askmin(L,R)) Update(who);
        } else {
            int x,y,len;readi(x);readi(y);readi(len);
            Hash(x,x+len-1)==Hash(y,y+len-1)?puts("yes"):puts("no");
        }
    }
    return 0;
}

H. Message Bomb

利用动态开点线段树,对每个组 $j$ 维护一个数组 $ex_i$ 表示 $i$ 这个人当前在不在 $j$ 组里,每次线段树下传标记时,只给 $ex_i=true$ 的点加次数。当 $x$ 人在 $y$ 组里发信息时,就给 $y$ 组的线段树打 $+1$ 标记,并将 $x$ 收到的信息 $-1$ 。

最后把所有线段树都下传一遍就可以得到答案。

题解好像有更简单的做法……

#include<cstdio>
#include<cctype>
using namespace std;
const int maxn=100000,maxm=200000,maxt=2e7;

int n,m,te,ans[maxm+5],ro[maxn+5];
int si,ls[maxt+5],rs[maxt+5],tag[maxt+5],ID[maxt+5];bool ex[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline void Addtag(int p,int k) {if (!p) return;if (ex[p]) ans[ID[p]]+=k;tag[p]+=k;}
inline void Pushdown(int p) {if (tag[p]) Addtag(ls[p],tag[p]),Addtag(rs[p],tag[p]),tag[p]=0;}
void Insert(int &p,int pos,bool f,int l=1,int r=m){
    if (!p) p=++si;if (l==r) {ID[p]=pos;ex[p]=f;return;}
    int mid=l+(r-l>>1);Pushdown(p);
    if (pos<=mid) Insert(ls[p],pos,f,l,mid); else Insert(rs[p],pos,f,mid+1,r);
}
void Solve(int p) {if (!p) return;Pushdown(p);Solve(ls[p]);Solve(rs[p]);}
int main(){
    freopen("H.in","r",stdin);freopen("H.out","w",stdout);
    readi(n);readi(m);readi(te);
    for (int i=1;i<=te;i++){
        int tp,x,y;readi(tp);readi(x);readi(y);
        if (tp==1) Insert(ro[y],x,1); else
        if (tp==2) Insert(ro[y],x,0); else
        if (tp==3) tag[ro[y]]++,ans[x]--;
    }
    for (int i=1;i<=n;i++) Solve(ro[i]);
    for (int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!