USACO 1.2

Brief

本章節的題目也是沒有什麼特定演算法,有些可以使用DP來處理,有些則是根據題目敘述來解即可

Milking Cows

此提使用DP來解,思考過程如下

  • 將所有farmers的工作時間依據其起點由早到晚排序
1
2
3
4
5
6
for(int i=0;i<n;i++){
farmers* f = new farmers();
fin >> f->low >> f->high;
data.push_back(f);
}
sort(data.begin(),data.end(),compare);
  • 掃過所有farmers的工作時間,判斷當前的farmers是否有跟上一個farmers的時間有重疊,如果有重疊,就更新當前紀錄的工作時間,如果沒有重疊,就代表此時需要閒置,因此就要更新當前閒置時間,每次更新的同時,也順便紀錄最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
currLow = data[0]->low;
currHigh= data[0]->high;
maxMilked = currHigh - currLow;
maxNotMilked = 0;
for(int i=1;i<data.size();++i){
if(data[i]->low > currHigh){ //沒有重疊
maxNotMilked = max(maxNotMilked,data[i]->low - currHigh);
currLow = data[i]->low;
currHigh = data[i]->high;
maxMilked = max(maxMilked,currHigh-currLow);
}
else if (data[i]->high > currHigh){ //有重疊
currHigh = data[i]->high;
maxMilked = max(maxMilked,(currHigh - currLow));
}
}
  • 全部掃過一遍及可找到答案

Transformations

  • 此題不難,只要想好如何將一個矩陣給順時針旋轉90即可
1
2
3
4
5
6
7
8
9
10
11
void turn90(char* data,int n){
char *tmp = new char[n*n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
tmp[j*n+(n-i-1)] = data[i*n + j];
}
}
memcpy(data,tmp,n*n);
delete tmp;
return ;
}
  • 根據題目所規定的順序,每種都去嘗試,若符合就印出答案,不合就繼續嘗試下一種即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//#1
turn90(src,n);
if( 0 == memcmp(src,dst,n*n)){
fout <<"1"<<endl;
return 0;
}
//#2
turn90(src,n);
if( 0 == memcmp(src,dst,n*n)){
fout <<"2"<<endl;
return 0;
}
//#3
turn90(src,n);
if( 0 == memcmp(src,dst,n*n)){
fout <<"3"<<endl;
return 0;
}
//#4
turn90(src,n);
reflect(src,n);
if( 0 == memcmp(src,dst,n*n)){
fout <<"4"<<endl;
return 0;
}
//#5
for(int i=0;i<3;i++){
turn90(src,n);
if( 0 == memcmp(src,dst,n*n)){
fout <<5<<endl;
return 0;
}
}
//#6
turn90(src,n);
reflect(src,n);
if( 0 == memcmp(src,dst,n*n)){
fout <<"6"<<endl;
return 0;
}
//#7
fout<<"7"<<endl;

Name That Number

  • 一開始先讀取dict.txt,只將長度符合題目要求的單字給存起來
1
2
3
4
while(din >> tmp){
if(tmp.size() == input.size())
data.push_back(tmp);
}
  • 接下來依據位數來一個一個檢查。先針對單字內所有的第一位進行檢查是否符合規則,若不合就將其從字典內刪除,以此往下即可找到所有符合的答案
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for(int i=0;i<input.size();++i){
    for(list<string>::iterator itr = data.begin(); itr != data.end() ; ){
    if(check(input[i]-'0',(*itr)[i])){
    ++itr;
    }
    else{
    itr = data.erase(itr);
    }

    }
    }

Palindromic Squares

  • 對於1~300之間的每個數字都去進行驗證
  • 首先將先該數字給平方,接者去判斷是否迴文,若是就印出答案即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PalindromesSquare(int n,int base){
string baseString;
string squareString;
int tmp = n;
n = n *n;
while(n){ //計算平方後的字串
squareString.push_back(getBaseChar(n%base));
n/=base;
}
while(tmp){ //計算當前的字串
baseString.push_back(getBaseChar(tmp%base));
tmp/=base;
}
if ( checkPalin(squareString) ){
n = baseString.size();
for(int i=0;i<baseString.size();++i)
fout<<baseString[n-i-1];
fout<<" "<<squareString<<endl;
}

}

Dual Palindromes

  • 這題跟 Dual Palindromes非常類似,先根據題目的需求對每個數字去做處理
  • 每次處理都以2~10進位去試試看有沒有迴文,若能夠產生迴文的base數量超過兩個就直接印出結果,直接測是下一個數字即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
ifstream fin ("dualpal.in");
int limit;
int start;
int count;
fin >> limit >> start;
while(limit){
++start;
count =0;
for(int i=2;i<=10;++i){
if( PalindromesSquare(start,i)){
++count;
if( 2 == count){
fout<<start<<endl;
--limit;
break;
}
}
}
}
return 0;
}