首页 > 代码库 > CH Round #55 - Streaming #6 (NOIP模拟赛day2)解题报告

CH Round #55 - Streaming #6 (NOIP模拟赛day2)解题报告

T1九九归一

描述

萌蛋在练习模n意义下的乘法时发现,总有一些数,在自乘若干次以后,会变成1。例如n=7,那么5×5 mod 7=4,4×5 mod 7=6,6×5 mod 7=2,2×5 mod 7=3,3×5 mod 7=1。如果继续乘下去,就会陷入循环当中。
萌蛋还发现,这个循环的长度经常会是φ(n),即小于n且与n互质的正整数的个数。例如,φ(7)=6,而上述循环的长度也是6,因为5,4,6,2,3,1共有6个数。
再如n=6,那么5×5 mod 6=1。这个循环的长度很短,只有2,而恰好φ(6)=2。
然而,对于某些情况,虽然循环的长度可以是φ(n),但存在比φ(n)更小的长度:例如n=7,而2×2 mod 7=4,4×2 mod 7=1,循环的长度只有3。当然,6也可以是一个循环的长度。
假设已知了n,我们称数a神奇的,当且仅当关于数a的循环长度可以是φ(n),而且不存在比φ(n)更小长度的循环。例如对于n=7,5是神奇的,而2不是神奇的。
现在给出n和q次询问,每次询问给出a,问a是否是神奇的。

输入格式

第一行两个整数n q。n≤10,000,000,q≤100,000,0≤a<n。
第二行有q个整数,每个表示一个a。

输出格式

输出q个字符,1表示这个数是神奇的,0表示这个数不是神奇的。

样例输入

7 35 2 0

样例输出

100
首先我们用O(sqrt(n))的时间求出fai(n),然后对于每一个数a,进行一次快速幂算出afai(n)Mod n是否为1,不为1则直接输出0即可。
题目中已经告知循环的长度必定为fai(n)的因数,那么我们事先用sqrt(n)的时间求出fai(n)的所有因数,那么一个数的因数是log(n)级别的,于是对于每一个因数进行快速幂判断是否神奇,总复杂度loglogn

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <map>10 #include <set>11 #include <list>12 #include <vector>13 #include <ctime>14 #include <iterator>15 #include <functional>16 #define pritnf printf17 #define scafn scanf18 #define For(i,j,k) for(int i=(j);i<=(k);(i)++)19 using namespace std;20 typedef long long LL;21 typedef unsigned int Uint; 22 const int INF=0x7ffffff;23 //==============struct declaration==============24 25 //==============var declaration=================26 LL bound;27 vector <LL> fact;28 int siz;29 //==============function declaration============30 int fai(LL x);31 int gcd(LL a,LL b){return a%b==0?b:gcd(b,a%b);}32 bool loop(LL x,LL Mod);33 void divide(LL x);34 LL quickpow(int x,int Exp,LL Mod);35 //==============main code=======================36 int main()37 {  38   LL Mod,q;39   scanf("%lld%lld",&Mod,&q);40   bound=fai(Mod);divide(bound);41   while (q--){42     LL query;43     scanf("%lld",&query);44     if (gcd(query,Mod)!=1)//可以证明如果不互质是不可能循环的45                                      //此处用quickpow亦可,时间复杂度均为log(n)46       putchar(0);47     else if (loop(query,Mod))48       putchar(1);49     else 50       putchar(0);51   }52   return 0;53 }54 //================fuction code====================55 int fai(LL x)//欧拉函数56 {57    LL res=x;58    LL m=sqrt(x+0.5);59    for(LL i=2;i<=m;i++){60      if (x%i==0){61        res=res/i*(i-1);62        while (x%i==0)63          x/=i;64      }65    }  66    if (x!=1)67      res=res/x*(x-1);68    return res;69 }70 bool loop(LL x,LL Mod)//判断是否神奇71 {72   for(int i=0;i<=siz;i++)73     if (quickpow(x,fact[i],Mod)==1)74       return false;75   return true;76 }77 void divide(LL x)//分解因数78 {79   int m=sqrt(x+0.5);80   For(i,2,m)81     if (x%i==0){82       fact.push_back(i);83       fact.push_back(x/i);84     }85   sort(fact.begin(),fact.end());86   siz=fact.size()-1;87 }88 LL quickpow(int x,int Exp,LL Mod)//快速幂89 {90   if (Exp==0)91     return 1;92   if (Exp==1)93     return x;94   LL t=quickpow(x,Exp/2,Mod);95   t=(t*t)%Mod;96   if (Exp&1)97     t=(t*x)%Mod;98   return t;99 }
T1代码

 

 

 

T2 LCA的统计

描述

萌蛋有一棵n个节点的有根树,其根节点为1。除此之外,节点i的父节点为p_i。每个点上都有一个权值,节点i的权值是w_i。
萌蛋知道你一定知道什么叫做祖先(从根到某个点的路径上的每个点都是这个点的祖先,包括它本身),也一定知道什么叫做最近公共祖先(两个点的最近公共祖先是某个点,这个点同时是两个点的祖先,且离根最远)。
现在给出这棵树,你需要求出:

其中LCA(i,j)表示点i与点j的最近公共祖先。
由于答案可能很大,你只需要输出它对1,000,000,007取模的结果。

输入格式

第一行为两个整数n w_1。1≤n≤100,000,0≤w_i≤1,000,000,000,1≤p_i<i
第二行到第n行,第i行有两个整数p_i  w_i。

输出格式

输出只有一行,为一个整数,表示所求答案对1,000,000,007取模的结果。

样例输入

2 21 1

样例输出

17

怎么说呢。这道题我其实考试的时候想了很久,没有想到什么好的算法,我的算法是O(n*deg2)其中deg表示这个树的度。那么针对这个复杂度应该是很容易TLE的。但是由于题目数据淼,还是AC了。

然后我发现标程也是用的这个办法。。。虽然不严谨,但是还是给出思路(记Si为以i为祖先点的所有点的W和(包括i节点本身))

对于每一个节点k,统计以它为LCA的节点,分为三部分:

一、i=j=k  ans+=wk*wk*wk

二、i=k,j是i的孩子  ans+=2*(wk*wk*(Sk-Wk))

应该没有问题吧由于i,j可以互换,所以*2

三、i,j分别位于k的两个不同的子树中

我们先来看只有两个子节点的情况(圈圈内数字是节点编号)

 

对于1号节点进行统计i,j分别在左右子树的情况

w1*w2w3  w1*w2w6 w1*w2w7 

w1*w4w3  w1*w4w6 w1*w4w7

w1*w5w3  w1*w5w7 w1*w5w7

以上加起来就是:

w1*(w2+w4+w5)(w3+w6+w7)=w1*S2*S3

最后*2,因为i,j可以调换

三叉、四叉直到n叉数都可以对每两个子树进行分别统计。

然后。。做完了吧。。记得对1,000,000,007取模就行

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <map>10 #include <set>11 #include <list>12 #include <vector>13 #include <ctime>14 #include <iterator>15 #include <functional>16 #define pritnf printf17 #define scafn scanf18 #define For(i,j,k) for(int i=(j);i<=(k);(i)++)19 using namespace std;20 typedef long long LL;21 typedef unsigned int Uint; 22 const int INF=0x7ffffff;23 //==============struct declaration==============24 25 //==============var declaration=================26 const int MAXN=100010;27 const int MOD=1000000007;28 vector <int> Edge[MAXN];29 LL w[MAXN],S[MAXN],res=0;30 int n;31 //==============function declaration============32 void Count(int x);//计算以x为LCA的答案33 //==============main code=======================34 int main()35 {  36   scanf("%d%lld",&n,&w[1]);37   For(i,2,n){38     int pa;39     scanf("%d%lld",&pa,&w[i]);40     Edge[pa].push_back(i);41   }42   Count(1);43   printf("%lld\n",res%MOD);44   return 0;45 } 46 //================fuction code====================47 void Count(int x)48 {49   res=(res+(((w[x]*w[x])%MOD)*w[x])%MOD)%MOD;//情况150   S[x]=w[x];51   int siz=Edge[x].size()-1;52   For(i,0,siz){53     Count(Edge[x][i]);//对子节点递归处理54     res=(res+((w[x]*w[x])%MOD*(S[Edge[x][i]]*2)%MOD)%MOD)%MOD;//情况255     S[x]=(S[x]+S[Edge[x][i]])%MOD;//累加S值56   }57   For(i,0,siz)58     For(j,i+1,siz)59       res=(res+((((w[x]*S[Edge[x][i]])%MOD*S[Edge[x][j]])%MOD)*2)%MOD)%MOD;//情况360   return;61 }
T2代码

T3 四驱兄弟

描述

如果你和萌蛋一样,也看过《四驱兄弟》,你或许会记得,有一局比赛十分特别,只按照5个人中的第4名计算成绩。
现在我们将问题扩展一下:一共有n个队员,只按照其中的第k名计算成绩。而赛车的规则也有所不同:一共有m个赛车,每个赛车装配着2个GP晶片的终端,且第i个赛车预期到达终点的时间为a_i。(注:不同赛车上的终端可以对应着相同的GP晶片,但不会2个都相同;任何赛车上的2个终端对应的GP晶片都是不同的)
比赛开始时,n个队员依次选择自己的赛车。对于每个队员,他可以选择开启GP晶片功能或不开启。如果开启,那么2个终端对应的GP晶片就会建立连接,且这个赛车的比赛用时就是预期时间a_i;如果不开启,那么GP晶片不会建立连接,但是这个赛车的比赛用时将会非常长(可以认为是无穷)。甚至,他可以放弃比赛,这样他不会占用任何赛车,但是当然比赛用时也会被认为是无穷。
任何时候,一旦存在若干个(至少3个)晶片A,B,C,…,X满足:A与B建立了连接,B与C建立了连接,……,X与A建立了连接(即形成了循环连接的情况),那么处理系统就会崩溃。这是非常可怕的,我们宁可让比赛用时变为无穷也不能让系统崩溃。
现在给出队员和赛车的信息,请输出最优情况下的成绩(即第k小的比赛时间的最小值)。为了增大难度,k并不是给出的,而是你需要对于1≤k≤n的所有的k输出答案。

输入格式

第一行为两个整数n m。
接下来m行,每行描述了一个赛车,格式为空格隔开的一个整数和两个字符串,分别是a_i和它的两个终端对应的GP晶片名。

输出格式

n行,每行一个整数,第i行表示i=k时的答案。特别地,如果答案是无穷,输出INF。

样例输入

3 395 GP_1 GP_2100 GP_1 gp@3100 gp@3 GP_2

样例输出

95100INF

数据范围与约定

对于20%的数据,n,m≤3,GP晶片名称的长度均为1。
对于40%的数据,n,m≤6,GP晶片名称的长度均为1。
对于60%的数据,n,m≤1,000,GP晶片的长度不会超过3。
对于100%的数据,0<n,m≤100,000,0<a_i≤1,000,000,000,GP晶片的名称只包含大小写字母、数字、“@” 、“_”共64种字符且长度不会超过5且非空。

样例解释

以下是一种最优方案(方案可能不唯一):
首先,3人各自选择了1辆赛车。(都没有放弃参赛)
如果k=1,那么让赛车1开启GP晶片,其余不开启,此时3个赛车的比赛时间分别为95,INF,INF,第1名的成绩是95。
如果k=2,那么让赛车2和3开启GP晶片,而赛车1不开启,此时3个赛车的比赛时间分别为100,100,INF,第2名的成绩是100。
如果k=3,那么由于3辆赛车不可能都开启GP晶片(因为假设都开启,那么3个GP晶片会出现循环连接的情况,这是不允许的),所以总有赛车没有开启GP晶片,那么第3名的成绩一定是INF。

iostream害人啊!!本来可以AK的就是因为cin超时了。。。最后一题只有80分。我还写了ios::sync_with_stdio(false)都超时。。等等测试一下不开有多少分。

很简单的一个模型。将一辆赛车看成一条边,连接两个不同的芯片,边长为速度,那么这一题就改成了选n条边,使得图中不出现环,且对于k∈[1,n]来说,第k大的边最小。

那么。。最小生成树。。

证明自行搜索克鲁斯卡尔算法的证明,基本类似。

 

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <map>10 #include <set>11 #include <list>12 #include <vector>13 #include <ctime>14 #include <iterator>15 #include <functional>16 #define pritnf printf17 #define scafn scanf18 #define For(i,j,k) for(int i=(j);i<=(k);(i)++)19 using namespace std;20 typedef long long LL;21 typedef unsigned int Uint; 22 const int INF=0x7ffffff;23 //==============struct declaration==============24 struct adj{25   int s,e,len;26   bool operator <(const adj &rhs)const {27     return len<rhs.len;28   }29 };30 //==============var declaration=================31 map <string,int> id;32 const int MAXN=100010;33 adj Edge[MAXN];34 int n,m,tot=0;35 int root[MAXN*2];36 //==============function declaration============37 int findr(int x){return root[x]==x?x:root[x]=findr(root[x]);}38 //==============main code=======================39 int main()40 {  41   id.clear();42   scanf("%d%d",&n,&m); 43   For(i,1,m){44     char str1[20],str2[20];45     string str;46     scanf("%d%s%s",&Edge[i].len,str1,str2);47     str=string(str1);48     if (id[str]==0)49       id[str]=++tot;50     Edge[i].s=id[str];51     str=string(str2);52     if (id[str]==0)53       id[str]=++tot;54     Edge[i].e=id[str];55   }56   sort(Edge+1,Edge+1+m);57   For(i,1,tot)58     root[i]=i;59   for(int i=1;i<=m&&n>0;i++){60     adj &e=Edge[i];61     if (findr(e.s)!=findr(e.e)){62       printf("%d\n",e.len);63       n--;64       root[findr(e.s)]=findr(e.e);65     }                            66   }67   while (n--)68     printf("INF\n");69   return 0;70 }71 //================fuction code====================
T3代码

 

CH Round #55 - Streaming #6 (NOIP模拟赛day2)解题报告