文章目錄

• T1
• • 題目
  • 題解
  • code
• T2
• • 題目
  • 題解
  • code
• T3
• • 題目
  • 題解
  • code

T1

題目

七夕節(jié)因牛郎織女的傳說而被扣上了「情人節(jié)」的帽子。于是TYVJ今年舉辦了一次線下七夕祭。Vani同學(xué)今年成功邀請到了cl同學(xué)陪他來共度七夕，于是他們決定去TYVJ七夕祭游玩。

TYVJ七夕祭和11區(qū)的夏祭的形式很像。矩形的祭典會場由N排M列共計N×M個攤點組成。雖然攤點種類繁多，不過cl只對其中的一部分?jǐn)傸c感興趣，比如章魚燒、蘋果糖、棉花糖、射的屋……什么的。Vani預(yù)先聯(lián)系了七夕祭的負(fù)責(zé)人zhq，希望能夠通過恰當(dāng)?shù)夭贾脮?#xff0c;使得各行中cl感興趣的攤點數(shù)一樣多，并且各列中cl感興趣的攤點數(shù)也一樣多。
　　不過zhq告訴Vani，攤點已經(jīng)隨意布置完畢了，如果想滿足cl的要求，唯一的調(diào)整方式就是交換兩個相鄰的攤點。兩個攤點相鄰，當(dāng)且僅當(dāng)他們處在同一行或者同一列的相鄰位置上。由于zhq率領(lǐng)的TYVJ開發(fā)小組成功地扭曲了空間，每一行或每一列的第一個位置和最后一個位置也算作相鄰。現(xiàn)在Vani想知道他的兩個要求最多能滿足多少個。在此前提下，至少需要交換多少次攤點。

輸入格式
第一行包含三個整數(shù)N和M和T。T表示cl對多少個攤點感興趣。
接下來T行，每行兩個整數(shù)x, y，表示cl對處在第x行第y列的攤點感興趣。

輸出格式
首先輸出一個字符串。如果能滿足Vani的全部兩個要求，輸出both；如果通過調(diào)整只能使得各行中cl感興趣的攤點數(shù)一樣多，輸出row；如果只能使各列中cl感興趣的攤點數(shù)一樣多，輸出column；如果均不能滿足，輸出impossible。
如果輸出的字符串不是impossible， 接下來輸出最小交換次數(shù)，與字符串之間用一個空格隔開。

樣例
樣例輸入1
2 3 4
1 3
2 1
2 2
2 3
樣例輸出1
row 1
樣例輸入2
3 3 3
1 3
2 2
2 3
樣例輸出2
both 2
數(shù)據(jù)范圍與提示
對于30% 的數(shù)據(jù)，N, M≤100。
對于70% 的數(shù)據(jù)，N, M≤1000。
對于100% 的數(shù)據(jù)，1≤N, M≤100000，0≤T≤min(NM, 100000)，1≤x≤N，1≤y≤M

題解

這道題先初級均分紙牌，后中級糖果傳遞，然后這題就變成水題了

我們知道如果要滿足每一行或者每一列的攤點數(shù)一樣，感興趣的攤點數(shù)一定能整除行或列
這道題的行與列操作是彼此獨立的，接下來以行為例，大家類比列
考慮糖果怎么寫的，把這$n$行，每一行看成一個人，那么一共就有$n$個人，圍成一圈，每個人手上的糖果就是該行感興趣的攤點數(shù)，設(shè)平均數(shù)$aver=T/n$，每一個人都會向右邊的人傳遞糖果然后接受左邊的人傳來的糖果，最后手上均有$aver$個，設(shè)原本手上就有$p_i$顆糖果，$X_i$表示第$i$個人給了第$i?1$人$X_i$顆糖，特殊的$X_1$表示第一個人給第$n$個人，如果值為負(fù)則表示$i?1$給$i$

然后就可以寫出$n$個方程
$$?\begin{array}{l}{p}_1?X_1+X_2=aver??>X_2=aver?p_1+X_1(令pre[i]={\sum }_{j=1}^{i}aver?X_j)\\ p_2?X_2+X_3=aver??>X_3=aver?p_2+X_2??>X_3\\ =aver?p_2+aver?p_1+X_1=X_1+pre[i]\\ ...\\ p_n?X_n+X_1=aver??>X_n=X_1+pre[n]\end{array}$$
這里我們翻轉(zhuǎn)$pre$的定義，$pre[i]={\sum }_{j=1}^i{X}_j?aver$
那么最后的答案則是$min(|X_1|+|X_1?pre[1]|+|X_1?pre[2]|...|X_1?pre[n]|)$
注意這個絕對值可以用數(shù)軸的含義來表示，$|X_1?Y|$表示在數(shù)軸上$X_1$與$Y$之間的距離
然后我們就可以把$pre[i]$對應(yīng)到數(shù)軸上面，然后調(diào)用初中知識，當(dāng)$X_1$取之中位數(shù)時，距離和最小

code

#include <cmath> #include <cstdio> #include <algorithm> using namespace std; #define MAXN 100005 #define int long long int N, M, T, result; int row[MAXN], col[MAXN], pre[MAXN];int cal ( int *p, int n ) {int ans = 0, average = T / n;for ( int i = 1;i <= n;i ++ )pre[i] = pre[i - 1] - p[i] + average;sort ( pre + 1, pre + n + 1 );int mid = pre[( n + 1) >> 1];for ( int i = 1;i <= n;i ++ )ans += fabs ( mid - pre[i] );return ans; }signed main() {scanf ( "%lld %lld %lld", &N, &M, &T );for ( int i = 1;i <= T;i ++ ) {int x, y;scanf ( "%lld %lld", &x, &y );row[x] ++;col[y] ++;}if ( T % N && T % M )printf ( "impossible" );else if ( T % N == 0 && T % M == 0 ) {result += cal ( row, N );result += cal ( col, M );printf ( "both %lld", result );} else if ( T % N == 0 ) {result = cal ( row, N );printf ( "row %lld", result );} else {result = cal ( col, M );printf ( "column %lld", result );}return 0; }

T2

題目

現(xiàn)有一個傳動系統(tǒng)，包含了$N$個組合齒輪和$M$個鏈條。每一個鏈條連接了兩個組合齒輪$u$和$v$，并提供了一個傳動比$x:y$ 。即如果只考慮這兩個組合齒輪，編號為$u$的齒輪轉(zhuǎn)動$x$圈，編號為$v$的齒輪會轉(zhuǎn)動$y$圈。傳動比為正表示若編號為$u$的齒輪順時針轉(zhuǎn)動，則編號為$v$的齒輪也順時針轉(zhuǎn)動。傳動比為負(fù)表示若編號為$u$的齒輪順時針轉(zhuǎn)動，則編號為$v$的齒輪會逆時針轉(zhuǎn)動。若不同鏈條的傳動比不相容，則有些齒輪無法轉(zhuǎn)動。我們希望知道，系統(tǒng)中的這$N$個組合齒輪能否同時轉(zhuǎn)動。

輸入格式
有多組數(shù)據(jù)，第一行給定整數(shù)$T$，表示總的數(shù)據(jù)組數(shù)，之后依次給出$T$組數(shù)據(jù)。
每一組數(shù)據(jù)的第一行給定整數(shù)$N$和$M$，表示齒輪總數(shù)和鏈條總數(shù)。
之后有$M$行，依次描述了每一個鏈條，其中每一行給定四個整數(shù) $u$，$v$，$x$ 和$y$，表示只考慮這一組聯(lián)動關(guān)系的情況下，編號為$u$的齒輪轉(zhuǎn)動$x$圈，編號為$v$的齒輪會轉(zhuǎn)動$y$圈。請注意， $x$為正整數(shù)，而$y$為非零整數(shù)，但是$y$有可能為負(fù)數(shù)。

輸出格式
輸出$T$行，對應(yīng)每一組數(shù)據(jù)。首先應(yīng)該輸出標(biāo)識這是第幾組數(shù)據(jù)，參見樣例輸出。之后輸出判定結(jié)果，如果$N$個組合齒輪可以同時正常運行，則輸出 Yes，否則輸出 No。

樣例
樣例輸入
2
3 3
1 2 3 5
2 3 5 -7
1 3 3 -7
3 3
1 2 3 5
2 3 5 -7
1 3 3 7
樣例輸出
Case #1: Yes
Case #2: No
數(shù)據(jù)范圍與提示
對于所有的數(shù)據(jù)，$T\le 32,N\le 1000,M\le 10000,|x|,|y|\le 100$

題解

這里其實理解了相容是什么意思就可以了
無非就是每一個齒輪因為我們按的鏈條有了一定的旋轉(zhuǎn)速度
然后保證這些鏈條所涉及的齒輪彼此間的旋轉(zhuǎn)速度是永恒的

那么我們就可以用$dfs$判斷即可：
以單位"1"的旋轉(zhuǎn)速度開始，當(dāng)$u$點以單位"1"旋轉(zhuǎn)，那么$v$點就會以$\frac{y}{x}$速度旋轉(zhuǎn)

當(dāng)這個齒輪沒有被訪問過就更新它的旋轉(zhuǎn)速度
反之則判斷此時它的旋轉(zhuǎn)速度跟之前的速度是否一致
這道題比較良心不會卡精度

code

#include <cmath> #include <cstdio> #include <vector> using namespace std; #define MAXN 1005 #define eps 1e-5 struct node {int v;double w;node () {}node ( int V, double W ) {v = V;w = W;} }; vector < node > G[MAXN]; int T, n, m; bool flag; bool vis[MAXN]; double speed[MAXN];bool check ( int u, double now ) {vis[u] = 1;speed[u] = now;for ( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].v;double w = G[u][i].w;if ( ! vis[v] ) {if ( ! check ( v, now * w ) )return 0;}else {if ( fabs ( now * w - speed[v] ) > eps )return 0;}}return 1; }int main() {scanf ( "%d", &T );for ( int t = 1;t <= T;t ++ ) {scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ ) {G[i].clear();vis[i] = 0;}for ( int i = 1;i <= m;i ++ ) {int u, v, x, y;scanf ( "%d %d %d %d", &u, &v, &x, &y );G[u].push_back( node ( v, y * 1.0 / x ) );G[v].push_back( node ( u, x * 1.0 / y ) );}flag = 1;for ( int i = 1;i <= n;i ++ )if ( ! vis[i] ) {if ( ! check ( i, 1 ) ) {flag = 0;break;}}if ( flag )printf ( "Case #%d: Yes\n", t );elseprintf ( "Case #%d: No\n", t );}return 0; }

T3

題目

SD0062 號選手小 Q 同學(xué)為了偷到 SDOI7012 的試題，利用高超的黑客技術(shù)潛入了 SDOI 出題組的內(nèi)聯(lián)網(wǎng)的中央控制系統(tǒng)，然而這個內(nèi)聯(lián)網(wǎng)除了配備有中央控制系統(tǒng)，還為內(nèi)聯(lián)網(wǎng)中的每條單向網(wǎng)線設(shè)定了特殊的通信口令，這里通信口令是一個字符串，不同網(wǎng)線的口令可能不同。這讓小 Q 同學(xué)感覺有些棘手， 不過這根本難不倒他，很快他就分析出了整個內(nèi)聯(lián)網(wǎng)的結(jié)構(gòu)。

內(nèi)聯(lián)網(wǎng)中有$n$個節(jié)點（從$1$到$n$標(biāo)號）和$m$條單向網(wǎng)線，中央控制系統(tǒng)在第$1$個節(jié)點上，每條網(wǎng)線單向連接內(nèi)聯(lián)網(wǎng)中的某兩個節(jié)點，從$1$號節(jié)點出發(fā)經(jīng)過若干條網(wǎng)線總能到達(dá)其他任意一個節(jié)點。每個節(jié)點都可以運行任意的應(yīng)用程序，應(yīng)用程序會攜帶一條通信口令，當(dāng)且僅當(dāng)程序的口令與網(wǎng)線的口令相同時，程序才能通過這條網(wǎng)線到達(dá)另一端的節(jié)點繼續(xù)運行，并且通過每條網(wǎng)線都需要花費一定的時間。

每個應(yīng)用程序可以在任意一個節(jié)點修改通信口令，修改通信口令花費的時間可以忽略不計，但是為了減小修改量，需要先調(diào)用一個子程序來計算當(dāng)前程序的口令和網(wǎng)線的口令的最長公共前綴（記其長度為 $len$），由于獲取網(wǎng)線的口令的某個字符會比較耗時，調(diào)用一次這個子程序需要花費$len$個單位時間。

除此之外，小 Q 同學(xué)還在中央控制系統(tǒng)中發(fā)現(xiàn)了一個字典，每條網(wǎng)線的口令都是字典中的某個字符串。具體來說，這個字典是一棵$k$個節(jié)點（從 1 到 k 標(biāo)號）的有根樹，其中根是第$1$個節(jié)點，每條邊上有一個字符，字符串$S$在字典中當(dāng)且僅當(dāng)存在某個點 $u$使得從根節(jié)點出發(fā)往下走到$v$的這條路徑上的字符順次拼接構(gòu)成$S$。

現(xiàn)在小 Q 同學(xué)在$1$號節(jié)點同時開啟了$n?1$個應(yīng)用程序，這些應(yīng)用程序同時運行且互不干擾，每個程序的通信口令都為空，他希望用最短的時間把這些程序分別發(fā)送到其他節(jié)點上，你需要幫小 Q 同學(xué)分別計算出發(fā)送到第$i(=2,3,...n)$個節(jié)點的程序完成任務(wù)的最短時間。

題解

首先我們把一條邊拆成四個點，這條邊的發(fā)起者（出點）和這條邊的接受者（入點）以及各自再建一個虛點，彼此之間的權(quán)還是以前的邊權(quán)

建一個源點s，然后向所有入點是1的點建一條邊權(quán)為0的邊
然后枚舉每一個點u，將所有形如<i,u>和<u,j>的邊彼此之間建一條邊，邊權(quán)就是他們的lcp(最長公共前綴)
跑一次原圖對于源點而言的最短路
最后，對于一個點u，枚舉所有<i,u>的邊，取它們中出點最小的dis
但是一個點的入邊和出邊會有很多，別人都說連出的邊數(shù)大概是$O(n^2)$的GG了

---

所以我們考慮優(yōu)化建圖：
一條邊被拆成四個點，兩個入點兩個出點，分別用來處理前綴和后綴
對于一個點，我們以前綴為例子，后綴與之類似以下略過 ：
1.按照每條邊對應(yīng)字符串在Trie樹上的dfs序排序，上面是入邊，下面是出邊
2.上下分別按照順序連邊權(quán)為0的有向邊(灰色邊)
3.考慮到一個性質(zhì)$lcp(a_1,a_n)=mi{n}_{i=1}^{n?1}lcp(a_i,a_{i+1})$
4.考慮dfs序相鄰的兩點$x_i,x_{i+1}$（有可能都是入點或出點），計算出$lcp(x_i,x_{i+1})$
考慮它們的影響范圍，顯然，我們找到序號最大且小于等于$i$的入邊$c_k$和序號大于等于$i+1$的出邊$r_j$，連邊$<c_k,r_j>$，長度為$lcp(x_i,x_{i+1})$（圖中省略了$lcp$）
這樣，就可以滿足一個序號小的入邊到任意一個序號比它大的出邊之間的最短路就是它們的lcp值

---

對于步驟4，其實是一種虛樹的思想吧
經(jīng)典的就是為什么按$dfn$序排序后兩兩之間的$lca$會覆蓋任意兩個點之間的$lca$
接下來給出簡單證明，假設(shè)$a,b,c$是排序后緊挨著的三個點且$df{n}_a<df{n}_b<df{n}_c$
因此$b$不可能成為$lca(a,b)$，$c$不可能成為$lca(b,c),lca(a,c)$
那么會有幾種情況呢？
情況1：當(dāng)$b,c$的$lca$在$a,b$的$b?lca(a,b)$路徑上($c$可以是$b$的兒子，是一樣的情況)，顯然$lca(a,c)=lca(a,b)$

情況2：$lca(a,b)=lca(b,c)$那么也很簡單$lca(a,c)=lca(a,b)=lca(b,c)$

情況3：$lca(b,c)$在$lca(a,b)$的子樹外，那么$lca(a,b)$一定是$lca(b,c)$子樹內(nèi)的一點
因此$lca(a,c)=lca(b,c)$

情況4：$lca(a,c)$在$a?lca(a,b)$路徑上，這個時候好像出了問題別急往下看


根據(jù)$dfn$的定義，我們得把$lca(a,c)$的子樹遍歷完了才能去$b$那一邊
那么按道理$df{n}_c<df{n}_b$與我們之前的前提矛盾，因此此情況并不存在

code

#include <queue> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define MAXN 20005 #define MAXM 200005 #define LL long long #define inf ( 1ll << 60 ) struct noded {int u;LL w;noded () {}noded ( int U, int W ) {u = U;w = W;}bool operator < ( const noded &t ) const {return w > t.w;} }; struct node {int v, next, w;node () {}node ( int V, int W, int Next ) {v = V;next = Next;w = W;} }edge[MAXM * 10]; priority_queue < noded > q; vector < int > G[MAXM], Redge[MAXM], Cedge[MAXM];//R入邊,C出邊 int T, n, m, k, a, b, c, d, id, tot, cnt, idx; int pos[MAXM], head[MAXM], dfn[MAXN], dep[MAXN], flag[MAXM]; int f[MAXN][20]; LL dp[MAXM];int Fabs ( int x ) {return ( x < 0 ? ( - x ) : x ); }void init () {id = tot = cnt = idx = 0;memset ( head, 0, sizeof ( head ) );for ( int i = 1;i <= k;i ++ )G[i].clear();for ( int i = 1;i <= n;i ++ ) {Redge[i].clear();Cedge[i].clear();} }void addEdge ( int u, int v, int w ) {edge[++ cnt] = node ( v, w, head[u] );head[u] = cnt; }void insert ( int a, int b, int c, int d ) {pos[++ id] = d;//1/3出 2/4入 addEdge ( tot + 1, tot + 2, c );addEdge ( tot + 1, tot + 4, c );addEdge ( tot + 3, tot + 2, c );addEdge ( tot + 3, tot + 4, c );Redge[b].push_back( id );Cedge[a].push_back( id );tot += 4; }bool cmp ( int x, int y ) {return dfn[pos[Fabs ( x )]] < dfn[pos[Fabs ( y )]]; }void dfs ( int u, int fa ) {dfn[u] = ++ idx;f[u][0] = fa;dep[u] = dep[fa] + 1;for ( int i = 1;i < 20;i ++ )f[u][i] = f[f[u][i - 1]][i - 1];for ( int i = 0;i < G[u].size();i ++ )if ( G[u][i] != fa )dfs ( G[u][i], u ); }int lca ( int u, int v ) {if ( dep[u] <= dep[v] )swap ( u, v );for ( int i = 19;i >= 0;i -- )if ( dep[f[u][i]] >= dep[v] )u = f[u][i];if ( u == v )return u;for ( int i = 19;i >= 0;i -- )if ( f[u][i] != f[v][i] ) {u = f[u][i];v = f[v][i];}return f[u][0]; }int getlca ( int u, int v ) {//因為點1的深度是1,因此邊的個數(shù)是點的深度-1 return dep[lca ( u, v )] - 1; }void build ( int x ) {if ( Redge[x].empty() || Cedge[x].empty() )return;sort ( Redge[x].begin(), Redge[x].end(), cmp );sort ( Cedge[x].begin(), Cedge[x].end(), cmp );for ( int i = 0;i < Redge[x].size() - 1;i ++ ) {addEdge ( Redge[x][i] * 4 - 2, Redge[x][i + 1] * 4 - 2, 0 );addEdge ( Redge[x][i + 1] * 4, Redge[x][i] * 4, 0 );}for ( int i = 0;i < Cedge[x].size() - 1;i ++ ) {addEdge ( Cedge[x][i] * 4 - 3, Cedge[x][i + 1] * 4 - 3, 0 );addEdge ( Cedge[x][i + 1] * 4 - 1, Cedge[x][i] * 4 - 1, 0 );}int len = 0;for ( int i = 0;i < Redge[x].size();i ++ )flag[++ len] = Redge[x][i];for ( int i = 0;i < Cedge[x].size();i ++ )flag[++ len] = - Cedge[x][i];sort ( flag + 1, flag + len + 1, cmp );for ( int p = 1, i = 0, j = 0;p < len;p ++ ) {if ( flag[p] < 0 ) {flag[p] = - flag[p];j ++;}else i ++;//我們只能保證當(dāng)前p的flag是正數(shù)但無法保證p+1int lca = getlca ( pos[flag[p]], pos[Fabs ( flag[p + 1] )] );if ( i && j < Cedge[x].size() )addEdge ( Redge[x][i - 1] * 4 - 2, Cedge[x][j] * 4 - 3, lca );if ( j && i < Redge[x].size() )addEdge ( Redge[x][i] * 4, Cedge[x][j - 1] * 4 - 1, lca );} }void Dijkstra () {while ( ! q.empty() )q.pop();tot ++;for ( int i = Cedge[1].size() - 1;i >= 0;i -- ) {addEdge ( tot, Cedge[1][i] * 4 - 1, 0 );addEdge ( tot, Cedge[1][i] * 4 - 3, 0 );}memset ( dp, 0x7f, sizeof ( dp ) );dp[tot] = 0;q.push( noded ( tot, 0 ) );while ( ! q.empty() ) {noded t = q.top();q.pop();if ( t.w > dp[t.u] )continue;for ( int i = head[t.u];i;i = edge[i].next ) {int v = edge[i].v, w = edge[i].w;if ( dp[v] > dp[t.u] + w ) {dp[v] = dp[t.u] + w;q.push( noded ( v, dp[v] ) );}}}for ( int i = 2;i <= n;i ++ ) {LL ans = inf;for ( int j = 0;j < Redge[i].size();j ++ )ans = min ( ans, dp[Redge[i][j] * 4] );printf ( "%lld\n", ans );} }int main() {scanf ( "%d", &T );while ( T -- ) {scanf ( "%d %d %d", &n, &m, &k );init ();for ( int i = 1;i <= m;i ++ ) {scanf ( "%d %d %d %d", &a, &b, &c, &d );insert ( a, b, c, d );}for ( int i = 1;i < k;i ++ ) {scanf ( "%d %d %d", &a, &b, &c );G[a].push_back( b );G[b].push_back( a );}dfs ( 1, 0 );for ( int i = 2;i <= n;i ++ )build ( i );Dijkstra ();}return 0; }

終于把拖了的坑填完了

有任何問題歡迎評論，我看見會回復(fù)大家的，Thanks?(･ω･)ﾉ

總結(jié)

以上是生活随笔為你收集整理的【周末狂欢赛7】【NOIP模拟赛】七夕祭，齿轮(dfs)，天才黑客的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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