http://domen111.github.io/UVa-Easy-Viewer/?907
在一趟路途中總共過了 $k$ 天晚上，也就是 $k+1$ 天
在 $n$ 個暫停點之間加上起點與終點共包含 $n+1$ 條路連接兩兩暫停點，每個路徑都有一個距離
求在經過 $k$ 天晚上的情況下，一天行走距離的最小值為多少

想法

如果說一日行走距離 $m$ 可以在 $k+1$ 天走完，那麼距離 $m+1$ 也一定可以
所以觀察到行走距離具有單調性
枚舉一天行走的距離，如果所需的時間超過 $k$ ，就將枚舉的上界調整，否則調整下界

Code

閱讀全文 »

TOJ274

發表於 2020-09-21 分類於 TOJ

題敘

https://toj.tfcis.org/oj/pro/274/
定義單錯誤迴文為一個字串中只除去一個字元後，剩下的字串為迴文
給一個字串，求該字串是否為單錯誤迴文

想法

對於一個字串 $s$ ，檢查其左右兩端 $L$ $R$
如果 $s[L] == s[R]$ 那麼就繼續檢查 $L+1$ 到 $R-1$
否則判斷 $L+1$ 到 $R$ 這個字串以及 $L$ 到 $R-1$ 這個字串誰是迴文
如果在這其中錯誤超過 $1$ 次，那就表示這不是單錯誤迴文

Code

閱讀全文 »

UVa374

發表於 2020-09-21 分類於 UVa

題敘

http://domen111.github.io/UVa-Easy-Viewer/?374
給定三個整數 $B$ $P$ $M$ ，求 $B^P mod M$

想法1 - 暴力解

從 $1$ 開始到 $P$ ，每次乘上 $B$ 再模 $M$ ，複雜度 $O(P)$
但是複雜度過高，會TLE

//By Koios1143
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
ll b,p,m;

int main(){
    while(cin>>b>>p>>m){
	    ll ans=1;
	    for(int i=1 ; i<=p ; i++){
	        ans = ans*b % m;
	    }
	    cout<<ans<<"\n";
	}
    
    return 0;
}

閱讀全文 »

TOJ 565

發表於 2020-09-18 更新於 2020-09-27 分類於 TOJ

TOJ 565

題敘

https://toj.tfcis.org/oj/pro/565/
給一張捷運的路線圖以及兩個整數 $A$ $B$ 和起點 $S$，從 $i$ 站到 $j$ 站所需要的花費為
$A經過路線數 + B經過路線權重總和$
求 $S$ 到各點所需的最小花費

想法

Dijkstra 模板題
如果點 $i$ 到點 $j$ 最短路徑為 $A$
則點 $i$ 到 $A$ 上的任一點的路徑也必定為最短路徑 (前提是邊權都是正的)
所以，我們可以每次都走距離最短的路，不斷更新起點到終點的距離，最終更新完必定會是最短距離

閱讀全文 »

TOJ 564

發表於 2020-09-18 更新於 2020-09-27 分類於 TOJ

TOJ 564

題敘

https://toj.tfcis.org/oj/pro/564/
給一個序列，如果求該敘列有多少種回文排列方式

想法

如果說序列中相同元素各數有一種以上是奇數，可以保證一定無解
因為要排成回文，我們可以只看一半，而另一半的答案會隨之確定
其他情況下，將所有相同數字的元素數量切半來看，排列好
最後將不同數字排列，就可以獲得答案

閱讀全文 »

codeforces 543A

發表於 2020-09-13 分類於 codeforces

codeforces 543A

題敘

今天有 $n$ 個程式設計師，要寫 $m$ 行程式碼
第 $i$ 個程式設計師每寫1行分別會有 $bug[i]$ 個bug
給定 $n$ $m$ $b$ $p$ $bug[]$
要求在總共不超過 $b$ 個bug的情況下， $n$ 個程式設計師完成 $m$ 行程式碼的方法數有多少種
由於結果可能很大，求總和模 $p$ 的值