CH Round #55 - Streaming #6 (NOIP模拟赛day2)

时间：2024-01-04 13:50:08

A.九九归一

题目：http://ch.ezoj.tk/contest/CH%20Round%20%2355%20-%20Streaming%20%236%20(NOIP模拟赛day2)/九九归一

题解：题目意思就是问 a是不是n的一个原根

首先如果 gcd(a,n)!=1 显然不可能 输出0

然后我们有性质

若 gcd(a,n)==1 则 a模n的阶k|phi（n）

所以就可以枚举phi(n)的约数判定了

复杂度题解中说是 q*logn*logn*logn的。。。

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 100000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int n,tot,a[maxn];

 int power(int xx,int yy)

 {

     ll t=,x=xx,y=yy;

     for(;y;y>>=,x=(x*x)%n)

      if(y&)t=(t*x)%n;

     return t;

 }

 inline bool check(int m)

 {

     for1(i,tot)if(power(m,a[i])==)return ;

     return ;

 }

 inline int gcd(int x,int y){return y?gcd(y,x%y):x;}

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();

     int x=n,y=n;

     for2(i,,sqrt(n))

      if(x%i==)

       {

           y=(y/i)*(i-);

           while(x%i==)x/=i;

       }

     if(x!=)y=(y/x)*(x-);

     for1(i,y)if(y%i==)a[++tot]=i;tot--;

     int cs=read();

     while(cs--)

     {

      int m=read();

      if(gcd(m,n)!=)printf("");

      else if(check(m))printf("");

      else printf("");

     }

     printf("\n");

     return ;

 }

B.LCA的统计

题目：http://ch.ezoj.tk/contest/CH%20Round%20%2355%20-%20Streaming%20%236%20(NOIP模拟赛day2)/LCA的统计

题解：首先枚举是一定要的，我们枚举 lca(i,j)然后看一下什么样的i，j是我们枚举的这个值。

稍微想想会发现f[x]=w[x]*（(s[x]*s[x])-sigma（s[y]*s[y]）） y是x 的子树

然后防止爆long long 就行了

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 1500000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 struct edga{int go,next;}e[maxn];

 int n,tot,head[maxn];

 ll s[maxn],f[maxn],w[maxn];

 inline void insert(int x,int y)

 {

     e[++tot].go=y;e[tot].next=head[x];head[x]=tot;

 }

 void dfs(int x)

 {

     f[x]=;s[x]=w[x];

     for(int i=head[x],y;i;i=e[i].next)

      {

          dfs(y=e[i].go);

          f[x]=((f[x]-w[x]*(s[y]*s[y]%mod))%mod+mod)%mod;

          s[x]=(s[x]+s[y])%mod;

      }

     f[x]=(f[x]+w[x]*(s[x]*s[x]%mod))%mod;

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();w[]=read()%mod;

     for2(i,,n)insert(read(),i),w[i]=read()%mod;

     dfs();

     ll ans=;

     for1(i,n)ans=(ans+f[i])%mod;

     printf("%lld\n",ans);

     return ;

 }

C.四驱兄弟

题目：http://ch.ezoj.tk/contest/CH%20Round%20%2355%20-%20Streaming%20%236%20(NOIP模拟赛day2)/四驱兄弟

题解：猜想大概是MST，然后发现不会证，就打了弃疗了。结果A了。。。

出题人是这样说的：

考虑图连通的情况，那么假设最小生成树不是第k小边最小生成树，就可以把两个树各取一点变成一个更小的生成树，就矛盾了

没想到我用map+cin居然没T

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1100000000

 #define maxn 200000+1000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 typedef map<string,int>::const_iterator cit;

 typedef map<string,int>::value_type vt;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 map<string,int>mp;

 struct rec{int u,v,w;}e[maxn];

 int n,m,tot,a[maxn],fa[maxn];

 string s;

 inline bool cmp(rec a,rec b)

 {

     return a.w<b.w;

 }

 inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();m=read();

     for1(i,m)

     {

       e[i].w=read();

       cin>>s;

       cit j=mp.find(s);

       if(j!=mp.end())e[i].u=j->second;

        else

         {

          mp.insert(mp.begin(),vt(s,++tot));

          e[i].u=tot;

         }

       cin>>s;

       j=mp.find(s);

       if(j!=mp.end())e[i].v=j->second;

        else

         {

          mp.insert(mp.begin(),vt(s,++tot));

          e[i].v=tot;

         }

     }

     sort(e+,e+m+,cmp);

     for1(i,tot)fa[i]=i;

     int j=;

     for1(i,n)

     {

         while(j<=m&&find(e[j].u)==find(e[j].v))j++;

         if(j>m)a[i]=inf;

         else

          {

           a[i]=e[j].w;

           fa[find(e[j].u)]=find(e[j].v);

          }

         j++;

     }

     for1(i,n)

      if(a[i]==inf)printf("INF\n");else printf("%d\n",a[i]);

     return ;

 }

AK了好高兴，不过还是运气比较好的原因。jiry半小时AK实在不能再orz

相关文章