T1 數列（sequence）
比賽時
我自以為是地打了簡簡單單一個判斷～～～
之后
Waiting……
T2 2753. 樹（tree）
比賽時
這題我居然比賽時也想了很久，可能是因為我太懶，我很早意識到lca的思想可以做，但是我還是想有什么辦法更簡單，如一個玄學的DFS、詭異的樹形DP（顯然時間會炸），浪費了我很多時間，最終我沒有想到，我就來講講lca的做法吧，由于路徑中節點的深度必須是升序的，可以知道一條路徑，它的起點必定是終點的祖先，符合lca，\(n \leq 100000\)，那么列舉終點，設兩個陣列：\(fa[i][j]\)表示編號為i的節點向上跳\(2^j\)次的節點，\(a[i][j]\)表示編號為i的節點向上跳\(2^j\)次途中遇到的節點價值總和，原汁原味的lca判斷的是深度，這里改一改就可以了，設變數\(sum=b[x]\)（x表示終點），每次向上跳時判斷\(sum+a[x][j] < s\)，跳的時候加一下就可以了，時間復雜度為\(O(20n)\)，顯然這個20非常小，可以不寫，
之后
有同學用了暴力居然都過了，這卡常居然能過，不公平呀，資料也太水了吧，
總結
不能太懶，想到一個AC的方法，如果在短時間內沒有想到更簡單的方法，則打，
T3 2754. 【2012東莞市選】時間流逝（flow）
比賽時
一看到概率，我就幾乎想放棄，我不知道因為概率的存在期望天數怎么算（但其實很簡單，我太蒟了～～）
之后
沒有之后～～～沒幾個人做對，聽不懂，
T4 3858. 挖掘機技術哪家強 shoberu
題目描述
給出n，求出n的每個因數x的難挖指數的和，難挖指數是所有與x互質的數y的和（包括1，\(1 \leq y \leq x\)）
比賽時
一看到這是偏數學題，就泄了氣，n太大了，1000000000，而且多組資料，1000組，我就想，可以列舉x，時間復雜度約為\(O(3000)\)，那么處理x的難挖指數的時間復雜度最多用\(O(10)\)，沒有想到高效求的方法，想來想去，并沒有想到什么規律，放棄～
之后
正解：歐拉函式，可惜我還沒學，歐拉函式可以求出對于一個x，y有多少個，和本題題意極其相似，我們發現：對于一個x，y總是成對出現（證明是顯然的，若 p 與 x 互質，那么p 與 x-p 也互質，我們把 p 與 x-p 結成一對），且一對和為x；如\(x=14\),y有\(1,3,5,9,11,13\)，每組和都\(=x\)，于是我們可以用歐拉函式求出x的y有多少個，就可以求出難挖指數是多少，一個x時間復雜度為\(O(\log n)\)，常數級別，那么整個的時間復雜度為\(O(t \sqrt{n})\)，完全可以過，注意有特殊情況：x=1,x=2，
#include<cstdio>
int t,n;
long long ans;
inline int euler(int x){
int ans=x;
for(int i=2;i*i<=x;i++){
if(x%i==0) ans-=ans/i;
while(x%i==0) x/=i;
}
if(x>1) ans-=ans/x;
return ans;
}
inline long long func(int x){
if(x==1||x==2){
return 1;
}else{
int g=euler(x);
return (long long)g*x/2;
}
}
int main(){
scanf("%d",&t);
for(int l=0;l<t;l++){
scanf("%d",&n);
ans=0;
for(int i=1;i*i<=n;i++)
if(n%i==0){
ans+=func(i);
if(n/i!=i) ans+=func(n/i);
}
printf("%lld\n",ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93584.html
標籤：其他
上一篇：2020.01.19【NOIP提高組】模擬比賽-1.水池,2.數字排序,3.球星,4.鉆石交易 總結反思
下一篇：紀中集訓2020.02.03【NOIP提高組】模擬B 組總結反思——登機(board)，游戲(game)，分組(group)