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 3 5 2 0

樣例輸出

100
首先我們用O(sqrt(n))的時間求出fai(n)，然后對于每一個數a，進行一次快速冪算出a^fai(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 printf 17 #define scafn scanf 18 #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 2 1 1

樣例輸出

17

怎么說呢。這道題我其實考試的時候想了很久，沒有想到什么好的算法，我的算法是O(n*deg²)其中deg表示這個樹的度。那么針對這個復雜度應該是很容易TLE的。但是由于題目數據淼，還是AC了。

然后我發現標程也是用的這個辦法。。。雖然不嚴謹，但是還是給出思路（記S_i為以i為祖先點的所有點的W和（包括i節點本身））

對于每一個節點k，統計以它為LCA的節點，分為三部分：

一、i=j=k ?ans+=w_k*w_k*w_k

二、i=k,j是i的孩子 ?ans+=2*(w_k*w_k*(S_k-W_k))

應該沒有問題吧由于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*S₂*S₃

最后*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 printf 17 #define scafn scanf 18 #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;//情況1 50 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;//情況2 55 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;//情況3 60 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 3 95 GP_1 GP_2 100 GP_1 gp@3 100 gp@3 GP_2

樣例輸出

95 100 INF

數據范圍與約定

對于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 printf 17 #define scafn scanf 18 #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代碼

?比賽網址：http://ch.ezoj.tk/contest/CH%20Round%20%2355%20-%20Streaming%20%236%20(NOIP%E6%A8%A1%E6%8B%9F%E8%B5%9Bday2)

轉載于:https://www.cnblogs.com/Houjikan/p/4006778.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CH Round #55 - Streaming #6 (NOIP模拟赛day2)解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。