文章目錄

• T1：等比數(shù)列三角形
• • 題目
  • 題解
  • 代碼實(shí)現(xiàn)
• T2：電報(bào)
• • 題目
  • 題解
  • 代碼實(shí)現(xiàn)

T1：等比數(shù)列三角形

題目

求三邊都是 ≤n 的整數(shù)，且成等比數(shù)列的三角形個(gè)數(shù)
注意三角形面積不能為 0
注意 oeis 中未收錄此數(shù)列，所以并不需要去搜了

輸入格式
一行一個(gè)整數(shù) n
輸出格式
一行一個(gè)整數(shù)表示答案

樣例
樣例輸入1
9
樣例輸出1
10
樣例解釋1
除去 9 個(gè)等邊三角形，還有 {4，6，9} 。

樣例輸入2
100
樣例輸出2
133

數(shù)據(jù)范圍與提示
一共有 4 個(gè)子任務(wù)，對(duì)于每一個(gè)子任務(wù)，你只有通過(guò)了該子任務(wù)的所有測(cè)試點(diǎn)，才能獲得此子任務(wù)的分?jǐn)?shù)
有 10pts，保證 n≤10
有 20pts，保證 n≤10⁵
有 20pts，保證 n≤10⁵
有 50pts，保證 n≤10¹²
對(duì)于所有數(shù)據(jù)，有1≤ n≤10¹²

題解

注意{4,6,9}，{6,4,9}，{9,6,4}算同一個(gè)三角形，所以不用管順序
設(shè)三條邊從小到大分別為$a,ak,a{k}^2$($k$為公比且為正整數(shù))
所以$1\le k$

---

就然要構(gòu)成三角形，必然要滿足
$a+ak>a{k}^2=>1+k>k^2=>k^2?k?1<0$
解得$k<\frac{\surd 5+1}{2}$

綜上$k\in [1,\frac{\surd 5+1}{2})$

---

接下來(lái)令$k=\frac{p}{q}$($q,p$互質(zhì))，最大邊就表示為$a?\frac{p^2}{q^2}$
最大邊$\le n$，故此$q\le \surd n$
因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$q=\frac{p}{k}$，那么

• 當(dāng)$k$取最大時(shí)，$q$取最小，把$k=\frac{\surd 5+1}{2}$帶入就解出了$q$的最小值，
  但因?yàn)閗取不到這個(gè)開(kāi)區(qū)間，q的這個(gè)最小值也是一個(gè)開(kāi)區(qū)間
• 當(dāng)k取最小時(shí)，$q$取最大，這是滿足$q=p$，$q$的這個(gè)最大值是一個(gè)閉區(qū)間

綜上$q\in (p?\frac{2}{\surd 5+1},p]$，在這里有個(gè)轉(zhuǎn)化思想，把$p$代換成$q$，得到$q\in (q?\frac{2}{\surd 5+1},q]$
我們就可以枚舉$p\in [1,\surd n]$，算出此時(shí)q的可取值個(gè)數(shù)
注意：其實(shí)理解成枚舉$q$也是說(shuō)得通的

---

當(dāng)這樣統(tǒng)計(jì)完后，會(huì)出現(xiàn)一個(gè)問(wèn)題
$\{2，3，6\},\{4，6，9\}$這種公比為$\frac{3}{2}$的三角形，會(huì)被重復(fù)計(jì)算進(jìn)公比為$\frac{6}{4}$
所以我們需要把這些排除掉，這也是為什么上面推導(dǎo)的時(shí)候$\frac{p}{q}$要保證互質(zhì)
這里就可以用類似埃篩的方法，把$x$的因數(shù)里面算過(guò)的三角形減掉

要正著減，如果倒著，公比為$\frac{12}{8}$會(huì)先減掉公比為$\frac{9}{6}$而這里面還包含著$\frac{3}{2}$
會(huì)導(dǎo)致$\frac{3}{2}$被重復(fù)減掉

---

代碼實(shí)現(xiàn)

#include <cstdio> #include <cmath> using namespace std; #define LL long long #define MAXN 1000005 LL n, result; int ok[MAXN]; int main() {scanf ( "%lld", &n );int sqt = sqrt ( n );for ( int i = 1;i <= sqt;i ++ ) {int t = i * ( 2 / ( sqrt ( 5 ) + 1 ) );ok[i] = i - t;}for ( LL i = 1;i <= sqt;i ++ )for ( LL j = i << 1;j <= sqt;j += i )ok[j] -= ok[i];for ( LL i = 1;i * i <= n;i ++ )result += ( n / ( i * i ) ) * ok[i];printf ( "%lld", result );return 0; }

T2：電報(bào)

題目

給出 n 個(gè)點(diǎn)，每個(gè)點(diǎn)的出度均為 1，給出這 n 個(gè)點(diǎn)初始指向的點(diǎn)A[i] ，和改變這個(gè)點(diǎn)指向的目標(biāo)所需要的價(jià)值 C[i]。
求讓所有點(diǎn)強(qiáng)連通的最小花費(fèi)。

輸入格式
第一行輸入一個(gè)數(shù) n 表示點(diǎn)的個(gè)數(shù)。
之后的 n 行每行兩個(gè)數(shù) A[i]，C[i] 表示第 i 個(gè)點(diǎn)指向第 A[i] 個(gè)點(diǎn)，更改該點(diǎn)指向的點(diǎn)花費(fèi)為 C[i]。
輸出格式
共一行，為讓所有點(diǎn)強(qiáng)連通的最小花費(fèi)。

樣例
樣例輸入 1
4
2 2
1 4
1 3
3 1
樣例輸出 1
4
樣例解釋 1

很顯然，把 1–>2 的這條邊改成 （花費(fèi) 4）的情況下構(gòu)成強(qiáng)連通分量花費(fèi)最小。

樣例輸入 2
4
2 2
1 6
1 3
3 1
樣例輸出 2
5
樣例解釋 2
很顯然把 1–>2 的這條邊改成 1–>4 花費(fèi) 2，把 3–>1 的這條邊改成 3–>2 花費(fèi) 3 的情況下構(gòu)成強(qiáng)連通分量花費(fèi)最小，總花費(fèi)為 5。

樣例輸入 3
4
2 2
1 3
4 2
3 3
樣例輸出 3
4

樣例輸入 4
3
2 1
3 1
1 1
樣例輸出 4
0

題解

首先為了能變成強(qiáng)連通，樹(shù)上的點(diǎn)彼此之間需要破掉，先不動(dòng)環(huán)上的點(diǎn)

如圖中：$7，8，9$和$10，11，12，13$就必須破掉，破成一條鏈

要么把$7\to 8$破掉，要么把$7\to 9$破掉，然后讓$7?8?9$連成一條鏈

可以用拓?fù)渑判蛘业讲皇黔h(huán)上的點(diǎn)，然后把這棵樹(shù)破成鏈，如果本身是鏈就不進(jìn)行操作

圖就變成多個(gè)環(huán)和多棵樹(shù)的形態(tài)

顯然，環(huán)彼此之間是相互獨(dú)立的，就可以掃一次先處理出所有的環(huán)

我們?cè)谏厦孢M(jìn)行樹(shù)上破成鏈的時(shí)候，把環(huán)延伸的鏈或樹(shù)也一起破掉

如圖中：就把$6\to 7$和$6\to 10$都給破掉

接著如果變成強(qiáng)連通，環(huán)與環(huán)之間必須相互有路去連通

就是復(fù)活環(huán)與之外連的某一條邊

意味著我們要把環(huán)破掉一條邊和外界相連

那么這個(gè)時(shí)候，對(duì)于環(huán)上的最佳答案點(diǎn)肯定滿足把它與它父親在環(huán)上的邊破掉，然后把它與自己延伸的鏈的點(diǎn)進(jìn)行相連的操作花費(fèi)最小

破環(huán)就是自己的$C$值，與鏈上的點(diǎn)保留一條邊，就是找鏈上點(diǎn)的$C$的最大值

如圖中：我們要把$6\to 1$破掉，復(fù)活$6\to 7$或者$6\to 10$任意一條邊

而且必須復(fù)活至少一條，這樣才能讓環(huán)與外面進(jìn)行連通

但是如果圖上有多個(gè)點(diǎn)的復(fù)活值是負(fù)數(shù)，那么肯定是全選上，使答案變得更小

在上面破 環(huán)與鏈的邊 的時(shí)候，我們就記錄最大值的$C$，復(fù)活的時(shí)候，肯定復(fù)活這一條邊，其他邊的消耗遠(yuǎn)小于這一條邊破掉的消耗

---

最后我們來(lái)解釋一下代碼的一些地方，旁邊的小姐姐問(wèn)了我很久

• 為什么是建反圖：
  想一想，如果我們建正圖，每個(gè)點(diǎn)都只會(huì)有一個(gè)指向點(diǎn)，即每個(gè)點(diǎn)的vector里面都只有$1$個(gè)點(diǎn)，怎么破鏈，復(fù)活等以上的操作呢？
  換言之，每個(gè)點(diǎn)要知道自己的后繼，才能知道破哪些邊

• flag||tot>1的問(wèn)題，我們要知道
  當(dāng)只有環(huán)的時(shí)候，如果環(huán)是多個(gè)，也需要破掉，使所有環(huán)彼此強(qiáng)連通
  當(dāng)只有一個(gè)環(huán)的時(shí)候，如果環(huán)上有鏈也需要破掉，不然環(huán)上的點(diǎn)無(wú)法走到鏈上的點(diǎn)
  所以這里是取或，當(dāng)且僅當(dāng)原圖本身就是一個(gè)環(huán)才不用考慮復(fù)活

---

代碼實(shí)現(xiàn)

這里定義isCircle[i]
1：表示這個(gè)點(diǎn)不在環(huán)上（PS：可能誤導(dǎo)了許多親故 ）
2：表示這個(gè)點(diǎn)在環(huán)上且已經(jīng)經(jīng)過(guò)了破樹(shù)或破鏈處理
0：表示這個(gè)點(diǎn)在環(huán)上但等待被處理

#include <queue> #include <cstdio> #include <vector> #include <cstring> #include <iostream> using namespace std; #define MAXN 100005 queue < int > q; vector < int > G[MAXN], circle[MAXN]; int n, tot; bool flag; int a[MAXN], c[MAXN]; int d[MAXN], g[MAXN], isCircle[MAXN]; long long result;int main() {scanf ( "%d", &n );for ( int i = 1;i <= n;i ++ ) {scanf ( "%d %d", &a[i], &c[i] );G[a[i]].push_back ( i );d[a[i]] ++;}for ( int i = 1;i <= n;i ++ )if ( ! d[i] ) {q.push ( i );isCircle[i] = 1;flag = 1;}while ( ! q.empty() ) {int t = q.front();q.pop();d[a[t]] --;if ( ! d[a[t]] ) {q.push ( a[t] );isCircle[a[t]] = 1;}}for ( int i = 1;i <= n;i ++ ) {if ( isCircle[i] == 1 ) {//破樹(shù)為鏈int Max = 0;for ( int j = 0;j < G[i].size();j ++ ) {Max = max ( Max, c[G[i][j]] );result += c[G[i][j]];}result -= Max;}else {for ( int j = 0;j < G[i].size();j ++ )if ( isCircle[G[i][j]] == 1 ) {//破環(huán)與外面延伸的鏈g[i] = max ( g[i], c[G[i][j]] );//記錄一條鏈的最大值result += c[G[i][j]];}if ( isCircle[i] == 0 )tot ++;int x = i;while ( isCircle[x] == 0 ) {//分離出環(huán)isCircle[x] = 2;circle[tot].push_back ( x );x = a[x];}}}if ( flag || tot > 1 ) {for ( int i = 1;i <= tot;i ++ ) {int Min = 0x3f3f3f3f;for ( int j = 0;j < circle[i].size();j ++ )//復(fù)活Min = min ( Min, c[circle[i][j]] - g[a[circle[i][j]]] );if ( Min >= 0 )//必須復(fù)活的一條邊result += Min;else {for ( int j = 0;j < circle[i].size();j ++ )if ( c[circle[i][j]] - g[a[circle[i][j]]] < 0 )//可多復(fù)活幾條邊result += c[circle[i][j]] - g[a[circle[i][j]]];//破掉i與fi的環(huán)上邊的時(shí)候，接的那一條邊肯定是接在fi上}}}printf ( "%lld", result );return 0; }

總結(jié)

以上是生活随笔為你收集整理的等比数列三角形 （数论 + 黄金分割点）+ JOISC 2016 Day3 T3 「电报」（基环树 + 拓扑排序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。