生活随笔
收集整理的這篇文章主要介紹了
8.13模拟：分治二分倍增快速幂
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
- 前言
- 考場
- 復盤
- T1 road
- T2 shop
- T3 run
- T4 stairs
- 總結
前言
240分
100+80+20+40
T3少取了一個模結果全掛掉了（好不容易推出來了…）
T2也因為各種奇怪的錯誤掛了分
qwq
吸取教訓吧
考場
今天先看題
T1第一眼看錯了題意覺得水的不行
T3YBT原題且很水
T2T4乍看不太可做
因為錯誤審題，決定先寫自以為很水的T1
寫完樣例不對，才發現自己審題完全審錯了
那個翻折的關鍵性質又沒有看出來（都看出來了嗎，我感覺并不顯然啊qwq）
分析了一會性質感覺打表或許可行
但可能是道搬磚題
此時大概8:40
于是轉T3穩一穩
此時心態有些不穩了
（我甚至覺得T3的3e7會炸）
把T3超級暴力的《正解》floyd敲完還不太放心
但是也沒有什么太好的方法
轉回T1死磕
9:30
T1走上了慢慢打表之路
打了30min終于把惡心的轉移數組敲完了
此時已經感覺藥丸
但是編譯結果有點驚喜
一遍過了樣例？？？
又測了幾個位置也對了
說實話那個搬磚代碼一個bug沒有真的挺神奇的
我本來已經做好了和它死磕的準備
結果就這么過了？
重新燃起希望
10:20
來到T2
很不錯的時我很快發現了它的關鍵性質
利用一半為分界點遞歸轉移
然后后面再跟個二分
check的地方遞歸求個數
很愉快的切掉了這道挺難的題
有一說一這道應該是我這幾次模擬做的最好的一道題
確實有邏輯分析在里面
遺憾的是我切掉的時候也有點激動
手一抖最后的一步乘法沒有取模
…
11:00
此時 我以為 我已經切了3題
心態就平和了起來
推了一會T4沒有任何思路
就決定寫個好一點的部分分下班
20分還是很好寫的
40分也不太難
（又開始暴力搬磚 ）
11:30
這次時間有些緊湊
T1和T3浪費了太多時間
我沒有很多的時間檢查了
（說不定再看看T2的沙雕錯誤就瞅出來了呢qwq）
最后就帶著那個bug走出了考場
qwq
復盤
T1 road
正解簡單的離譜
關鍵是回溯時對原圖進行一個神奇的反轉操作
就很easy了
但為了紀念還是附上打表代碼
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=1e6+100;
int n
;
int a
,b
;
int mi
[32];
int shunpl
[5][5]={{},{0,1,1,1,3},{0,4,2,2,2},{0,3,1,3,3},{0,4,4,2,4}};
int shundir
[5][5]={{},{0,2,1,1,2},{0,2,2,1,1},{0,1,2,2,1},{0,1,1,2,2}};
int shunid
[5][5]={{},{0,1,2,3,4},{0,4,1,2,3},{0,3,4,1,2},{0,2,3,4,1}};
int nipl
[5][5]={{},{0,1,3,1,1},{0,2,2,4,2},{0,3,3,3,1},{0,2,4,4,4}};
int nidir
[5][5]={{},{0,1,1,2,2},{0,2,1,1,2},{0,2,2,1,1},{0,1,2,2,1}};
int niid
[5][5]={{},{0,1,4,3,2},{0,2,1,4,3},{0,3,2,1,4},{0,4,3,2,1}};
int dx
[5]={0,0,0,1,1},dy
[5]={0,0,1,1,0};
int x2
,y2
,x3
,y3
;
void find(int k
,int pl
,int dir
,int id
,int x
,int y
){int ed
=id
+mi
[2*k
]-1;if((a
<id
||a
>ed
)&&(b
<id
||b
>ed
)) return;if(k
==0){if(id
==a
){x2
=x
;y2
=y
;}if(id
==b
){x3
=x
;y3
=y
;}return;}if(dir
==1){int len
=mi
[k
-1],tot
=mi
[(k
-1)*2];for(int i
=1;i
<=4;i
++){find(k
-1,shunpl
[pl
][i
],shundir
[pl
][i
],id
+(shunid
[pl
][i
]-1)*tot
,x
+dx
[i
]*len
,y
+dy
[i
]*len
);}return;}else{int len
=mi
[k
-1],tot
=mi
[(k
-1)*2];for(int i
=1;i
<=4;i
++){find(k
-1,nipl
[pl
][i
],nidir
[pl
][i
],id
+(niid
[pl
][i
]-1)*tot
,x
+dx
[i
]*len
,y
+dy
[i
]*len
);}return;}
}
int main(){
int t
;scanf("%d",&t
);mi
[0]=1;for(int i
=1;i
<=30;i
++) mi
[i
]=mi
[i
-1]<<1;while(t
--){scanf("%d%d%d",&n
,&a
,&b
);find(n
,1,1,1,1,1);printf("%.0lf\n",10.0*sqrt((x3
-x2
)*(x3
-x2
)+(y3
-y2
)*(y3
-y2
)));}return 0;
}
T2 shop
本題std的二分很神奇
類似于一個二分相對大小的最大值
然后硬限制一個范圍
就過了…
覺得還是我的代碼更好理解一寫qwq（所有人對自己的代碼都是這么想的）
不取模，見祖宗
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=105;
const int mod
=1e9+7;
int n
,k
;
int solve(int x
){if(x
==0) return 0;return x
+solve(x
/2);
}
int find(int l
,int r
){if(l
>r
) return 0;if(r
==0) return 0;return r
-l
+1 + find((l
+1)/2,r
/2);
}
ll
ksm(ll x
,int k
){ll ans
=1,res
=x
;while(k
){if(k
&1) ans
=ans
*res
%mod
;res
=res
*res
%mod
;k
>>=1;}return ans
;
}
void work(int k
,int n
){int tot
=solve(n
/2);if(k
<=tot
){work(k
,n
/2);return;}k
-=tot
;
int o
=k
/n
,p
=k
%n
;if(p
==0){printf("%lld\n",n
*ksm(2,o
-1)%mod
);return;}int st
=n
/2+1,ed
=n
;while(st
<ed
){int mid
=st
+ed
>>1;
if(find(n
/2+1,mid
)>=p
) ed
=mid
;else st
=mid
+1;}printf("%lld\n",st
*ksm(2,o
)%mod
);
}
int main(){
int t
;scanf("%d",&t
);while(t
--){scanf("%d%d",&k
,&n
);work(k
,n
);}return 0;
}
T3 run
YBT原題且很水
這也掛分就離譜
有一個是沒有特判m=1的情況
還有一個是因為int的范圍k只枚舉到30而不是31！
頭疼
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=105;
int n
,m
;
bool f
[33][N
][N
];
int dis
[N
][N
];
int main(){
int t
;scanf("%d",&t
);while(t
--){memset(f
,0,sizeof(f
));memset(dis
,0x3f,sizeof(dis
));
scanf("%d%d",&n
,&m
);for(int i
=1;i
<=m
;i
++){int x
,y
;scanf("%d%d",&x
,&y
);f
[0][x
][y
]=1;}for(int k
=1;k
<=30;k
++){for(int i
=1;i
<=n
;i
++){for(int j
=1;j
<=n
;j
++){for(int p
=1;p
<=n
;p
++){if(f
[k
-1][i
][p
]&&f
[k
-1][p
][j
]){f
[k
][i
][j
]=1;
break;}}
}}}for(int i
=1;i
<=n
;i
++){for(int j
=1;j
<=n
;j
++){for(int k
=0;k
<=30;k
++){if(f
[k
][i
][j
]){
dis
[i
][j
]=1;break;}}}dis
[i
][i
]=0;}for(int k
=1;k
<=n
;k
++){for(int i
=1;i
<=n
;i
++){for(int j
=1;j
<=n
;j
++){dis
[i
][j
]=min(dis
[i
][j
],dis
[i
][k
]+dis
[k
][j
]);}}}printf("%d\n",dis
[1][n
]);}return 0;
}
T4 stairs
這題考場確實不太可做
考后寫起來發現反而不難了
狀壓求出轉移矩陣再快速冪加速即可
一個重要的技巧是把0規定為有擋板
這樣不同高度之間可以無縫連接
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=105;
const int mod
=1e9+7;
int n
,k
;
int w
[8];
struct matrix{int x
,y
;ll a
[130][130];void clear(){for(int i
=0;i
<=x
;i
++)for(int j
=0;j
<=y
;j
++) a
[i
][j
]=0;}
};
int mi
[8];
void print(matrix o
){for(int i
=0;i
<=min(3,o
.x
);i
++){for(int j
=0;j
<=3;j
++) printf("%d ",o
.a
[i
][j
]);printf("\n");}return;
}
matrix
cheng(matrix a
,matrix b
){matrix o
;o
.x
=a
.x
;o
.y
=b
.y
;o
.clear();for(int i
=0;i
<=o
.x
;i
++){for(int j
=0;j
<=o
.y
;j
++){for(int k
=0;k
<=a
.y
;k
++){o
.a
[i
][j
]=(o
.a
[i
][j
]+a
.a
[i
][k
]*b
.a
[k
][j
])%mod
;}}}return o
;
}
int dp
[130][2];
matrix trans
[8];
void init(){mi
[0]=1;for(int i
=1;i
<=7;i
++) mi
[i
]=mi
[i
-1]<<1;for(int k
=1;k
<=7;k
++){trans
[k
].x
=trans
[k
].y
=mi
[7]-1;for(int i
=0;i
<mi
[k
];i
++){for(int j
=0;j
<mi
[k
];j
++){dp
[0][1]=1;dp
[0][0]=0;for(int p
=1;p
<=k
-1;p
++){if((i
|j
)&mi
[p
-1]){dp
[p
][1]=dp
[p
-1][0]+dp
[p
-1][1];dp
[p
][0]=dp
[p
-1][1]+dp
[p
-1][0];}else{dp
[p
][1]=dp
[p
-1][0];dp
[p
][0]=dp
[p
-1][1]+dp
[p
-1][0];}dp
[p
][0]%=mod
;dp
[p
][1]%=mod
;}if((i
|j
)&mi
[k
-1]) trans
[k
].a
[i
][j
]=dp
[k
-1][0]+dp
[k
-1][1];else trans
[k
].a
[i
][j
]=dp
[k
-1][0];}}}
}
matrix ans
;
int main(){for(int i
=1;i
<=7;i
++) scanf("%d",&w
[i
]);init();ans
.x
=0;ans
.y
=mi
[7]-1;ans
.a
[0][0]=1;for(int i
=1;i
<=ans
.y
;i
++) ans
.a
[0][i
]=0;for(int k
=1;k
<=7;k
++){while(w
[k
]){if(w
[k
]&1){ans
=cheng(ans
,trans
[k
]);}trans
[k
]=cheng(trans
[k
],trans
[k
]);w
[k
]>>=1;}}printf("%lld\n",ans
.a
[0][0]);return 0;
}
總結
爭取吃一塹長一智吧
以后檢查代碼注意的東西又多了一個：取模是否徹底！
明天：字符串 加油！awa
總結
以上是生活随笔為你收集整理的8.13模拟：分治二分倍增快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
