# 題目: UVa 1746 - String Theory
# 題目說明
巢狀引文不只適合寫文章,也適合寫程式,以下是說明:
1 層的引文 (1-quotation) 定義為一個字串的頭尾都有一個 '
例如: 'this is a string'
k 層的引文 (k-quotation) 定義為頭尾都有 k 個 '
,而裡面有 (k - 1) 層的引文
例如: ''All 'work' and no 'play'''
就是一個 2 層的引文
INPUT:
每筆測茲有兩行輸入
第一行為一個整數 N
,代表接下來有 N
個整數
第二行輸入 N
個整數,代表引號的數量
OUTPUT:
輸出測資為幾層的巢狀引文 (k)
若沒有 k
,則輸出 no quotation
# 解題方法
儲存資料之後,從頭尾之間比較小的數字開始爆破
從最左及最右開始每次減 tmp
,隨後 tmp - 1
,直到 tmp = 0
或不符合 while
條件
當 tmp = 0
時,若剩餘數字的合可以整除 2,則輸出答案
注意當 k = 1
時,只有兩種輸入會成立 1 2
及 2 1 1
,需要特別處理
# 參考程式碼
#include <iostream> | |
#include <vector> | |
using namespace std; | |
int main() | |
{ | |
// fast io | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int N, a; | |
while (cin >> N) | |
{ | |
// store data | |
vector<int> data; | |
for (int i = 0; i < N; ++i) cin >> a, data.emplace_back(a); | |
// i start with the smallest number | |
for (int i = min(data[0], data[N - 1]); i > 0; --i) | |
{ | |
// copy the original data | |
vector<int> cpy = data; | |
int left = 0, right = N - 1; | |
int tmp = i; | |
while (right >= 0 && left < N && cpy[left] >= tmp && cpy[right] >= tmp) | |
{ | |
if ((cpy[left] -= tmp) == 0) ++left; | |
if ((cpy[right] -= tmp--) == 0) --right; | |
if (tmp == 0) | |
{ | |
int sum = 0; | |
for (auto& j : cpy) sum += j; | |
// if i = 1, thete are only two cases: 1 2 and 2 1 1 | |
if (!(sum & 1) && i != 1 || sum == 0 && i == 1) cout << i << "\n"; | |
else cout << "no quotation\n"; | |
goto finish; | |
} | |
} | |
} | |
finish:; | |
} | |
return 0; | |
} |
# 參考資料
https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/1746.php