yNiazNhaoNng D5

Posted on By 陈麒润 yNiazNhaoNng D5无评论

A

显然去除平方因子后就是判重。

设 a=p^2q 则：

  • 如果 p\leq 1000 那就可以直接筛掉
  • 如果 p>1000 那么 q<1000，q 可以筛掉

所以就做完了。

#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define Y 1000
#define MX 100005
using namespace std;
const int CHECK=0,FIL=1;int read();
int n,m,a[MX],p[MX],pr[MX];
unordered_map<int,bool> w;
//0.3s
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    FRE freopen("prime.in","r",stdin);
    FRE freopen("prime.out","w",stdout);
    n=read();
    for(int i=2;i<=Y;i++){
        if(pr[i]) continue;
        p[++m]=i;
        for(int j=i*2;j<=Y;j+=i) pr[j]=1;
    }
    for(int i=1;i<=31623;i++) w[i*i]=1;
    for(int i=1;i<=n;i++){
        a[i]=read();
        int u=1;
        for(int j=1,k=p[1];j<=m;k=p[++j]){
            while(a[i]%(k*k)==0) a[i]/=(k*k);
            if(a[i]%k==0) a[i]/=k,u*=k;
        }
        if(!w[a[i]]) u*=a[i];
        a[i]=u;
    }
    sort(a+1,a+1+n);
    m=0;
    for(int i=1;i<=n;i++) if(a[i]!=a[i-1]) m++;
    printf("%d\n",m);
    return 0;
}
int read(){
    int Ca=0;char Cr=&#039; &#039;;int Cf=1;
    while(Cr<&#039;0&#039; || Cr>&#039;9&#039;){Cr=getchar();if(Cr==&#039;-&#039;){Cf=-1;}}
    while(Cr>=&#039;0&#039; && Cr<=&#039;9&#039;){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca*Cf;
}

B

显然是 0 在一起 1 在一起。

枚举断点，把 1 归到一个点，首推发现这个点一定是中间的那个 1。

#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define Y 1000
#define MX 100005
using namespace std;
const int CHECK=0,FIL=1;int read();
int n,m,a[MX],p[MX],pr[MX];
unordered_map<int,bool> w;
//0.3s
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    FRE freopen("prime.in","r",stdin);
    FRE freopen("prime.out","w",stdout);
    n=read();
    for(int i=2;i<=Y;i++){
        if(pr[i]) continue;
        p[++m]=i;
        for(int j=i*2;j<=Y;j+=i) pr[j]=1;
    }
    for(int i=1;i<=31623;i++) w[i*i]=1;
    for(int i=1;i<=n;i++){
        a[i]=read();
        int u=1;
        for(int j=1,k=p[1];j<=m;k=p[++j]){
            while(a[i]%(k*k)==0) a[i]/=(k*k);
            if(a[i]%k==0) a[i]/=k,u*=k;
        }
        if(!w[a[i]]) u*=a[i];
        a[i]=u;
    }
    sort(a+1,a+1+n);
    m=0;
    for(int i=1;i<=n;i++) if(a[i]!=a[i-1]) m++;
    printf("%d\n",m);
    return 0;
}
int read(){
    int Ca=0;char Cr=&#039; &#039;;int Cf=1;
    while(Cr<&#039;0&#039; || Cr>&#039;9&#039;){Cr=getchar();if(Cr==&#039;-&#039;){Cf=-1;}}
    while(Cr>=&#039;0&#039; && Cr<=&#039;9&#039;){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca*Cf;
}

C

从每个点开始跑 Dijk 跑到前 k 小就结束即可。

注意每个点只要枚举前 k 小的边。

#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define GP pair<int,int>
#define MP make_pair
#define INF 2000000000
#define MX 100005
#define MW 1500005
using namespace std;
const int CHECK=0,FIL=1;int read();
int n,m,k,dis[MX],r[MX];bool upd[MX];
GP g[MW];
priority_queue<GP,vector<GP>,greater<GP> > q;
int ocnt,olst[MX];
vector<GP> v[MX];
//2.10s
void Write(int t){
    if(!t) return;
    Write(t/10);
    putchar(&#039;0&#039;+(t%10));
}
void write(int t){
    if(!t) printf("0");
    Write(t);
} 
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    FRE freopen("city.in","r",stdin);
    FRE freopen("city.out","w",stdout);
    n=read();m=read();k=read();
    while(m--){
        int a=read();int b=read();int c=read();
        v[a].push_back(MP(c,b));
        v[b].push_back(MP(c,a));
    }
    for(int i=1;i<=n;i++){
        sort(v[i].begin(),v[i].end());
        int w=min(k,(int)v[i].size()),lst=r[i-1];
        r[i]=lst+w;
        for(int j=1;j<=w;j++) g[lst+j]=v[i][j-1];
    }
    for(int i=1;i<=n;i++) dis[i]=INF;
    for(int T=1;T<=n;T++){
        while(ocnt){
            int j=olst[ocnt--];
            dis[j]=INF,upd[j]=0;}
        olst[++ocnt]=T;dis[T]=0;upd[T]=1;
        while(q.size()){q.pop();}
        q.push(MP(0,T));
        for(int ooo=0;ooo<=k;ooo++){
            GP tp=q.top();q.pop();
            int t=tp.second,l=tp.first;
        //  cout<<t<<" "<<l<<&#039;\n&#039;;
            if(dis[t]<l){ooo--;continue;}
            //if(ooo){printf("%d ",l);}
            if(ooo){write(l);putchar(&#039; &#039;);}
            for(int j=r[t-1]+1;j<=r[t];j++){
                int i=g[j].second,d=g[j].first;
                if(l+d<dis[i]){
                    dis[i]=l+d;
                    if(!upd[i]) upd[i]=1,olst[++ocnt]=i;
                    q.push(MP(dis[i],i));
                }
            }
        }putchar(&#039;\n&#039;);
    }
    return 0;
}
int read(){
    int Ca=0;char Cr=getchar();
    while(Cr<&#039;0&#039; || Cr>&#039;9&#039;){Cr=getchar();}
    while(Cr>=&#039;0&#039; && Cr<=&#039;9&#039;){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca;
}

D

P9067.

每个连通块看成一个点的话显然还是一棵树。

每个连通块开一个 set 维护它的儿子连通块的颜色。

每次修改就先更新父亲的 set。

然后如果修改的连通块和儿子连通块有颜色相同的就合并。

最后再看要不要和父亲合并。

合并就是并查集，set 的信息则采用按秩合并的思想把小的移到大的。

所以一共是 O(n\log^2 n) 卡一卡原题就过了。

#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define GP pair<int,int>
#define MP make_pair
#define INF 2000000000
#define MX 100005
#define MW 1500005
using namespace std;
const int CHECK=0,FIL=1;int read();
int n,m,k,dis[MX],r[MX];bool upd[MX];
GP g[MW];
priority_queue<GP,vector<GP>,greater<GP> > q;
int ocnt,olst[MX];
vector<GP> v[MX];
//2.10s
void Write(int t){
    if(!t) return;
    Write(t/10);
    putchar(&#039;0&#039;+(t%10));
}
void write(int t){
    if(!t) printf("0");
    Write(t);
} 
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    FRE freopen("city.in","r",stdin);
    FRE freopen("city.out","w",stdout);
    n=read();m=read();k=read();
    while(m--){
        int a=read();int b=read();int c=read();
        v[a].push_back(MP(c,b));
        v[b].push_back(MP(c,a));
    }
    for(int i=1;i<=n;i++){
        sort(v[i].begin(),v[i].end());
        int w=min(k,(int)v[i].size()),lst=r[i-1];
        r[i]=lst+w;
        for(int j=1;j<=w;j++) g[lst+j]=v[i][j-1];
    }
    for(int i=1;i<=n;i++) dis[i]=INF;
    for(int T=1;T<=n;T++){
        while(ocnt){
            int j=olst[ocnt--];
            dis[j]=INF,upd[j]=0;}
        olst[++ocnt]=T;dis[T]=0;upd[T]=1;
        while(q.size()){q.pop();}
        q.push(MP(0,T));
        for(int ooo=0;ooo<=k;ooo++){
            GP tp=q.top();q.pop();
            int t=tp.second,l=tp.first;
        //  cout<<t<<" "<<l<<&#039;\n&#039;;
            if(dis[t]<l){ooo--;continue;}
            //if(ooo){printf("%d ",l);}
            if(ooo){write(l);putchar(&#039; &#039;);}
            for(int j=r[t-1]+1;j<=r[t];j++){
                int i=g[j].second,d=g[j].first;
                if(l+d<dis[i]){
                    dis[i]=l+d;
                    if(!upd[i]) upd[i]=1,olst[++ocnt]=i;
                    q.push(MP(dis[i],i));
                }
            }
        }putchar(&#039;\n&#039;);
    }
    return 0;
}
int read(){
    int Ca=0;char Cr=getchar();
    while(Cr<&#039;0&#039; || Cr>&#039;9&#039;){Cr=getchar();}
    while(Cr>=&#039;0&#039; && Cr<=&#039;9&#039;){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca;
}
训练日志

发表回复