文章目錄

• T1:One-Dimensional
• • title
  • solution
  • code
• T2:【NOIP模擬賽】Freda的迷宮
• • title
  • solution
  • code
• T3:【NOIP模擬賽】一道防AK好題
• • title
  • solution
  • code

確實(shí)沒想到自己寫文章能隔這么久，鴿王預(yù)警

T1:One-Dimensional

title

考慮一個(gè)含有 N 個(gè)細(xì)胞的一維細(xì)胞自動(dòng)機(jī)。細(xì)胞從 0 到 N-1 標(biāo)號。

每個(gè)細(xì)胞有一個(gè)被表示成一個(gè)小于 M 的非負(fù)整數(shù)的狀態(tài)。細(xì)胞的狀態(tài)會在每個(gè)整數(shù)時(shí)刻發(fā)生驟變。

我們定義 S(i,t) 表示第 i 個(gè)細(xì)胞在時(shí)刻 t 的狀態(tài)。在時(shí)刻 t+1 的狀態(tài)被表示為 S(i,t+1)=(A×S(i-1,t)+B×S(i,t)+C×S(i+1,t) ) mod M ，

其中 A,B,C 是給定的非負(fù)整數(shù)。對于 i<0 或 N≤i ，我們定義 S(i,t)=0 。

給定一個(gè)自動(dòng)機(jī)的定義和其細(xì)胞在時(shí)刻 0 的初始狀態(tài)，你的任務(wù)是計(jì)算時(shí)刻 T 時(shí)每個(gè)細(xì)胞的狀態(tài)。

輸入格式
輸入包含多組測試數(shù)據(jù)。每組數(shù)據(jù)的第一行包含六個(gè)整數(shù) N,M,A,B,C,T 。

第二行包含 N 個(gè)小于 M 的非負(fù)整數(shù)，依次表示每個(gè)細(xì)胞在時(shí)刻 0 的狀態(tài)。輸入以六個(gè)零作為結(jié)束。

輸出格式
對于每組數(shù)據(jù)，輸出N個(gè)小于M的非負(fù)整數(shù)，每兩個(gè)相鄰的數(shù)字之間用一個(gè)空格隔開，表示每個(gè)細(xì)胞在時(shí)刻T的狀態(tài)。

樣例
樣例輸入
5 4 1 3 2 0
0 1 2 0 1
5 7 1 3 2 1
0 1 2 0 1
5 13 1 3 2 11
0 1 2 0 1
5 5 2 0 1 100
0 1 2 0 1
6 6 0 2 3 1000
0 1 2 0 1 4
20 1000 0 2 3 1000000000
0 1 2 0 1 0 1 2 0 1 0 1 2 0 1 0 1 2 0 1
30 2 1 0 1 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
30 2 1 1 1 1000000000
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
30 5 2 3 1 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0
樣例輸出
0 1 2 0 1
2 0 0 4 3
2 12 10 9 11
3 0 4 2 1
0 4 2 0 4 4
0 376 752 0 376 0 376 752 0 376 0 376 752 0 376 0 376 752 0 376
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 3 2 2 2 3 3 1 4 3 1 2 3 0 4 3 3 0 4 2 2 2 2 1 1 2 1 3 0
數(shù)據(jù)范圍與提示
$0<N\le 50,0<M\le 1000,0\le a,b,c<M,0\le t\le 10^9$

solution

其實(shí)是很裸的一個(gè)矩陣快速冪，當(dāng)我們畫出下面一組圖的時(shí)候
腦子里面就因該出現(xiàn)矩陣的婀娜多姿 加速矩陣的美貌了


已經(jīng)呼之欲出了，這里直接呈現(xiàn)(原矩陣是一行m列的加速矩陣，如果原矩陣是m行1列，請將加速矩陣沿左對角線一一對應(yīng)交換（翻折）)
$$?\begin{array}{ccccc}b& 0& 0& ...& 0\\ c& a& 0& ...& 0\\ 0& b& a& ...& 0\\ 0& c& b& ...& 0\\ .& .& .& .& .\\ 0& 0& 0& ...& a\\ 0& 0& 0& ...& b\end{array}?$$

code

#include <cstdio> #include <cstring> using namespace std; #define MAXN 55 #define LL long long int mod, n, a, b, c, t;struct Matrix {int n, m;int c[MAXN][MAXN];Matrix () {memset ( c, 0, sizeof ( c ) );}Matrix operator * ( const Matrix &a ) {Matrix ans;ans.n = n;ans.m = a.m;for ( int i = 1;i <= n;i ++ )for ( int k = 1;k <= m;k ++ )if ( c[i][k] )for ( int j = 1;j <= a.m;j ++ )ans.c[i][j] = ( ans.c[i][j] + c[i][k] * a.c[k][j] % mod ) % mod;return ans;}}A, B;int main() {while ( scanf ( "%d %d %d %d %d %d", &n, &mod, &a, &b, &c, &t ) != EOF ) {if ( ! n && ! mod && ! a && ! b && ! c && ! t )return 0;memset ( A.c, 0, sizeof ( A.c ) );memset ( B.c, 0, sizeof ( B.c ) );A.n = 1, A.m = B.n = B.m = n;for ( int i = 1;i <= n;i ++ ) {scanf ( "%d", &A.c[1][i] );if ( i > 1 )B.c[i - 1][i] = a;B.c[i][i] = b;if ( i < n )B.c[i + 1][i] = c;}while ( t ) {if ( t & 1 )A = A * B;B = B * B;t >>= 1;}for ( int i = 1;i <= n;i ++ )printf ( "%d ", A.c[1][i] );printf ( "\n" );}return 0; }

T2:【NOIP模擬賽】Freda的迷宮

title

Freda是一個(gè)迷宮愛好者，她利用業(yè)余時(shí)間建造了許多迷宮。每個(gè)迷宮都是由若干房間和走廊構(gòu)成的，每條走廊都連接著兩個(gè)不同的房間，兩個(gè)房間之間最多只有一條走廊直接相連，走廊都是雙向通過。
黃昏時(shí)候，Freda喜歡在迷宮當(dāng)中漫步。每天，Resodo都會為Freda設(shè)計(jì)一個(gè)挑戰(zhàn)方案。Resodo會指定起點(diǎn)和終點(diǎn)，請F(tuán)reda來找到一條從起點(diǎn)到終點(diǎn)的簡單路徑。一條簡單路徑定義為一個(gè)房間序列，每個(gè)房間至多在序列里出現(xiàn)一次，且序列中相鄰的兩個(gè)房間有走廊相連。當(dāng)起點(diǎn)和終點(diǎn)之間存在且僅存在一條簡單路徑的時(shí)候，Freda認(rèn)為這個(gè)挑戰(zhàn)方案是RD的。現(xiàn)在，請你幫幫Resodo來寫一個(gè)程序，判斷一個(gè)挑戰(zhàn)方案是否是RD的。

輸入格式
第一行三個(gè)整數(shù)N,M,Q.分別表示房間數(shù)，走廊數(shù)，詢問數(shù)。
接下來M行每行2個(gè)整數(shù)x,y, 0<x,y<=N, 表示x和y之間有一條走廊相連。
接下來Q行每行2個(gè)整數(shù)x,y, 表示詢問以x為起點(diǎn),y為終點(diǎn)的挑戰(zhàn)方案是否是RD的.

輸出格式
對于每個(gè)詢問，輸出一行”Y”或者”N”（不含引號）.Y表示該詢問所表示的挑戰(zhàn)方案是RD的,N表示該詢問所表示的挑戰(zhàn)方案不是RD的.

樣例
樣例輸入
6 5 3
1 2
2 3
2 4
2 5
4 5
1 3
1 5
2 6
樣例輸出
Y
N
N
數(shù)據(jù)范圍與提示
樣例解釋
1,3之間只有一條路徑 1->2->3
1,5之間有兩條路徑 1->2->5 ; 1->2->4->5
1,6之間沒有路徑
數(shù)據(jù)范圍與約定
對于30%的數(shù)據(jù)，N<=100， M<=1000, Q<=100.
對于50%的數(shù)據(jù)，N<=1000, M<=10000, Q<=1000.
對于100%的數(shù)據(jù)，N<=10000, M<=100000, Q<=10000.

solution

這道題，也挺裸的，要不是我當(dāng)時(shí)打爆了

其實(shí)就是把這一條路徑摳出來，然后康康這上面是不是都是由簡單路徑組成的
因?yàn)閮牲c(diǎn)之間有且僅有一條簡單路徑，所以路徑上的邊都是橋
若有不為橋的邊，則一定可以找到另一條路徑連接不為橋的邊的兩個(gè)結(jié)點(diǎn)。
因此我們可以用無向強(qiáng)連通分量跑出每一條橋，然后用并查集將其捆綁，最后直接判斷兩點(diǎn)是否在一個(gè)并查集里面就行了

code

#include <cstdio> #include <vector> #include <iostream> using namespace std; #define MAXN 10005 vector < int > G[MAXN]; int n, m, Q, cnt; int f[MAXN], dfn[MAXN], low[MAXN];void MakeSet () {for ( int i = 1;i <= n;i ++ )f[i] = i; }int FindSet ( int x ) {if ( x != f[x] )return f[x] = FindSet ( f[x] );return x; }void UnionSet ( int u, int v ) {int fu = FindSet ( u ), fv = FindSet ( v );if ( fu != fv )f[fu] = fv; }void tarjan ( int u, int fa ) {dfn[u] = low[u] = ++ cnt;for ( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if ( ! dfn[v] ) {tarjan ( v, u );low[u] = min ( low[u], low[v] );if ( low[v] > dfn[u] )UnionSet ( u, v );}else if ( dfn[u] > dfn[v] && v != fa )low[u] = min ( low[u], dfn[v] );} }int main() {scanf ( "%d %d %d", &n, &m, &Q );for ( int i = 1;i <= m;i ++ ) {int x, y;scanf ( "%d %d", &x, &y );G[x].push_back ( y );G[y].push_back ( x );}MakeSet ();tarjan ( 1, 0 );for ( int i = 1;i <= Q;i ++ ) {int x, y;scanf ( "%d %d", &x, &y );if ( FindSet ( x ) == FindSet ( y ) )printf ( "Y\n" );elseprintf ( "N\n" );}return 0; }

T3:【NOIP模擬賽】一道防AK好題

title

Lemon認(rèn)為在第一屆『Citric』杯模擬賽中出的題目太簡單了，于是他決定，這次要給參賽選手們一個(gè)下馬威！ ^_

Lemon手上有一個(gè)長度為n的數(shù)列，第i個(gè)數(shù)為xi。
他現(xiàn)在想知道，對于給定的a,b,c，他要找到一個(gè)i，使得$a?(i+1)?x{i}^2+(b+1)?i?xi+(c+i)=0$成立。
如果有多個(gè)i滿足，Lemon想要最小的那個(gè)i。
Lemon有很多很多組詢問需要你回答，多到他自己也不確定有多少組。所以在輸入數(shù)據(jù)中a=b=c=0標(biāo)志著Lemon的提問的結(jié)束。

更加糟糕的是，Lemon為了加大難度，決定對數(shù)據(jù)進(jìn)行加密以防止離線算法的出現(xiàn)。
假設(shè)你在輸入文件中讀到的三個(gè)數(shù)為a0,b0,c0，那么Lemon真正要詢問的a=a0+lastans,b=b0+lastans,c=c0+lastans.
lastans的值是你對Lemon的前一個(gè)詢問的回答。如果這是第一個(gè)詢問，那么lastans=0
所有的詢問都將會按上述方式進(jìn)行加密，包括標(biāo)志著詢問的結(jié)束的那個(gè)詢問也是這樣。

為提高讀入效率，請用scanf()，而不能用cin，即使加sync_with_stdio(false)也不行！

對于不確定數(shù)量的數(shù)據(jù)，當(dāng)讀入完最后一行數(shù)據(jù)后，再次調(diào)用scanf()，會返回-1，以此可判斷讀入是否結(jié)束。

輸入格式
輸入文件第一行包含一個(gè)正整數(shù)n，表示數(shù)列的長度。
輸入文件第二行包含n個(gè)整數(shù)，第i個(gè)數(shù)表示xi的值。
接下來若干行，每行三個(gè)數(shù)，表示加密后的a,b,c值（也就是上文所述的a0,b0,c0）

輸出格式
包含若干行，第i行的值是輸入文件中第i個(gè)詢問的答案。注意，你不需要對標(biāo)志著詢問結(jié)束的那個(gè)詢問作答。
同時(shí)，標(biāo)志著詢問結(jié)束的詢問一定是輸入文件的最后一行。也就是，輸入文件不會有多余的內(nèi)容。

樣例
樣例輸入
5
-2 3 1 -5 2
-5 -4 145
-1 -6 -509
-9 -14 40
-3 -13 21
-3 -3 -3
樣例輸出
5
4
3
3
數(shù)據(jù)范圍與提示
第一個(gè)詢問中，真實(shí)的a=-5+0=-5，b=-4+0=-4，c=145+0=145（第一個(gè)詢問中l(wèi)astans=0）
帶入發(fā)現(xiàn)，i=5時(shí)，-5*(5+1)*2^2+(-4+1)52+145+5=0，而其他的i均不符合條件。所以答案是5.
第二個(gè)詢問中，真實(shí)的a=-1+5=4,b=-6+5=-1,c=-509+5=-504（lastans是上一個(gè)詢問的答案的值，也就是5）
經(jīng)帶入發(fā)現(xiàn)，i=4時(shí)，$4?(4+1)?(?5{)}^2+(?1+1)?4?(?5)+(?504)+4=0$，滿足條件，而其他的i均不滿足條件，所以答案是4.
同理，第三個(gè)詢問中真實(shí)的a=-5,b=-10,c=44.答案i=3
第四個(gè)詢問中真實(shí)的a=0,b=-10,c=24，答案i=3
第五個(gè)詢問中真實(shí)的a=0,b=0,c=0，此時(shí)我們發(fā)現(xiàn)這是一個(gè)標(biāo)志著結(jié)束的詢問，這個(gè)詢問我們無需作出回答。

對于40%的數(shù)據(jù)，滿足N<=1000，需要作出回答的詢問個(gè)數(shù)不超過1000.
對于100%的數(shù)據(jù)，滿足N<=50000，需要作出回答的詢問個(gè)數(shù)不超過500000，xi的絕對值不超過30000，解密后的a的絕對值不超過50000，解密后的b的絕對值不超過10^8
解密后的c的絕對值不超過10^18.

solution

如果當(dāng)你康到有加密強(qiáng)制在線

一直抓住在線不放去思考一些$log$算法，那么恭喜你
你成功get到了出題者的心意，不僅為你點(diǎn)個(gè)贊，棒棒！！
其實(shí)這道題的突破點(diǎn)就是a=b=c=0標(biāo)志著Lemon的提問的結(jié)束
也就是說最后的加密出來的$a,b,c$一定都為零，而我又知道每一次加密前的
$a0,b0,c0$為什么不搞點(diǎn)顏色呢

---

假設(shè)上一次的答案是$lastans$，這一次的答案是$ans$
那么一定滿足$$(a+lastans)?(ans+1)?x_{ans}^2+(b+lastans+1)?ans?x_{ans}+ans+c=0$$
讓我們對上面式子進(jìn)行一些騷操作 化簡
$$a?(ans+1)?x_{ans}^2+lastans?x_{ans}^2?(ans+1)+(b+1)?ans?x_{ans}+ans+c=0$$
$$lastans=?\frac{a?(ans+1)?x_{ans}^2+(b+1)?ans?x_{ans}+ans+c}{x_{ans}^2?(ans+1)+x_{ans}?ans+1}$$
利用這個(gè)遞推式，我們可以先把所有輸入都存下來，從最后一個(gè)已知答案開始往前推，就能離線之前所有答案搞定

code

#include <cstdio> #define LL long long #define MAXN 500005 int n, cnt; LL a, b, c; LL ans[MAXN], x[MAXN], A[MAXN], B[MAXN], C[MAXN];int main() {scanf ( "%d", &n );for ( int i = 1;i <= n;i ++ )scanf ( "%lld", &x[i] );while ( ~ scanf ( "%lld %lld %lld", &a, &b, &c ) )++ cnt, A[cnt] = a, B[cnt] = b, C[cnt] = c;ans[cnt - 1] = - A[cnt]; for ( int i = cnt - 1;i > 1;i -- ) {LL temp1 = A[i] * ( ans[i] + 1 ) * x[ans[i]] * x[ans[i]] + ( B[i] + 1 ) * ans[i] * x[ans[i]] + ans[i] + C[i];LL temp2 = x[ans[i]] * x[ans[i]] * ( ans[i] + 1 ) + x[ans[i]] * ans[i] + 1;ans[i - 1] = - temp1 / temp2;}for ( int i = 1;i < cnt;i ++ )printf ( "%lld\n", ans[i] );return 0; }

家里的網(wǎng)速實(shí)在。。本來半個(gè)小時(shí)就搞定了，硬生生卡成了兩小時(shí)

接下來要做常更得飛鴿王！！！

總結(jié)

以上是生活随笔為你收集整理的[3.3训练赛]One-Dimensional(矩阵快速幂)，Freda的迷宫(无向图强连通分量+并查集)，一道防AK好题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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