USACO section 1.1 C++問題解
5972 ワード
USACO section1.1: DONE 2017.03.03 TEXT Submitting Solutions DONE 2017.03.04 PROB Your Ride Is Here [ANALYSIS] DONE 2017.03.04 TEXT Contest Problem Types DONE 2017.03.04 TEXT Ad Hoc Problems DONE 2017.03.04 PROB Greedy Gift Givers [ANALYSIS] DONE 2017.03.04 PROB Friday the Thirteenth [ANALYSIS] DONE 2017.03.04 PROB Broken Necklace [ANALYSIS]
上から見えるsection 1.1中国共産党には4つの問題があり、アルゴリズムを考察していないが、単純に思考が行き届いているかどうかと細心の注意を払う程度だ.
Prob 1:Your Ride Is Here(水題)
題意:inputは2つのすべての大文字からなる単語を与え、各アルファベットは1つの数字(A-1,B-2......)に対応し、2つの単語の中のアルファベットはそれぞれ乗算され、2つの数字を得て、この2つの数字%47の残数が等しいかどうかを判断する.
NOTE:データが小さいので、オーバーフローの心配はありませんが、念のため、演算のたびに余剰を取ります.(a%b)*(c%b) = (a*c)%b;
ソース:
Prob 2:Greedy Gift Givers(水題)
标题:n人がいて、誰も0元を持っていなくて、一人一人がxのお金を取り出して彼の指定したn人にプレゼントを買って、彼の指定した人は一人一人がx/n元を得て、もし(x%n)を除いて多く出た小銭は彼自身に帰ります.1ラウンドを出力した後の一人当たりの金額(マイナスでも...).
P.S:最初はmapで1つ1つマッピングしようとしたが、mapがソートして入力した順番がなくなったので、2つの配列でメンテナンスするしかなかった.
ソース:
Prob3:
Friday the Thirteenth(小さな穴があってWAの結果をもたらして、ACまで1つの数しか残っていません...)
标题:1900年1月1日が月曜日であることが知られており、1900年を含むN年間で毎月13日が月曜日-日曜日の回数となっている.
NOTE 1:得られた1900年1月13日は土曜日で、毎月の日数から次の月13日が曜日を算出し、閏年を注意して判断すればよい.
NOTE 2:毎年単位として一歩ずつ求めていくと、1年ごとに12回目の実际の计算は次の年の1月13日(+31は12月を过ごして1月になる)なので、最后の年のサイクルは特别です.
ソース:
Prob 4:Broken Necklace(面白い)題意:一連のネックレスには赤(r)、青(b)、白(w)の3色がある.真ん中のどこかから切り離して、折れた両側からそれぞれ同じ色のビーズ(両側の右の摘出可能数を取り、2つのシーケンスからa[i]+b[i+1]の最大値を見つけます(真ん中から折れた2川なので、必ず隣接して左がi番目、右が(i+1)%n番目).
一方、一つもない左区と右取の値を算出するのも簡単で、それぞれを計算する必要はありません.例えば、i番目を算出して左にm個を取ることができます.では、(i-1)番目、つまり彼の左は必ず(m!=1)個しか取れません.m=1は自分だけです.左の顔色が現在の色と異なる場合、再計算します.しかし、例外があります.
bbwbwrrwrwrの最初のbは5で、5番目のwは1であるべきだが、実際には5番目のbは7であるべきだ.右の赤にもつながっているからだ.だから私たちは特審を受けました
前が2で、現在が白(w)の場合、再計算する必要があります(すなわち、wはキューの末尾です).ソースコード:
これよりUSACO section 1.1で全部できました.
ジルコニアqi 2016.03.04
上から見えるsection 1.1中国共産党には4つの問題があり、アルゴリズムを考察していないが、単純に思考が行き届いているかどうかと細心の注意を払う程度だ.
Prob 1:Your Ride Is Here(水題)
題意:inputは2つのすべての大文字からなる単語を与え、各アルファベットは1つの数字(A-1,B-2......)に対応し、2つの単語の中のアルファベットはそれぞれ乗算され、2つの数字を得て、この2つの数字%47の残数が等しいかどうかを判断する.
NOTE:データが小さいので、オーバーフローの心配はありませんが、念のため、演算のたびに余剰を取ります.(a%b)*(c%b) = (a*c)%b;
ソース:
/*
ID:kongse_1
PROG:ride
LANG:C++
*/
#include
#include
#include
using namespace std;
const int MOD = 47;
string a, b;
int num1=1 ,num2=1;
int main()
{
freopen("ride.in", "r", stdin);
freopen("ride.out", "w", stdout);
cin >> a >> b;
for(int i = 0; i != a.size(); ++i)
num1 = (num1*(a[i]-'A'+1))%MOD;
for(int i = 0; i != b.size(); ++i)
num2 = (num2*(b[i]-'A'+1))%MOD;
if(num1 == num2) cout << "GO" << endl;
else cout << "STAY" << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
Prob 2:Greedy Gift Givers(水題)
标题:n人がいて、誰も0元を持っていなくて、一人一人がxのお金を取り出して彼の指定したn人にプレゼントを買って、彼の指定した人は一人一人がx/n元を得て、もし(x%n)を除いて多く出た小銭は彼自身に帰ります.1ラウンドを出力した後の一人当たりの金額(マイナスでも...).
P.S:最初はmapで1つ1つマッピングしようとしたが、mapがソートして入力した順番がなくなったので、2つの配列でメンテナンスするしかなかった.
ソース:
/*
ID:kongse_1
PROG:gift1
LANG:C++
*/
#include
#include
#include
#include
using namespace std;
const int maxn = 15;
string x[maxn], y[maxn], z;
int num, sum, n, money[maxn];
int find_(string curr)
{
for(int i = 0; i != num; ++i)
{
if(x[i] == curr) return i;
}
}
void calculate_(int a, int b)
{
money[a] -= b;
return ;
}
int main(){
freopen("gift1.in", "r", stdin);
freopen("gift1.out", "w", stdout);
cin >> num;
for(int i = 0; i != num; ++i)
{
cin >> x[i];
}
for(int i = 0; i != num; ++i)
{
cin >> z >> sum >> n;
if(n)
{
calculate_(find_(z), sum-sum%n);
for(int j = 0; j != n; ++j)
{
cin >> y[j];
calculate_(find_(y[j]), -sum/n);
}
}
}
for(int i = 0; i != num; ++i)
{
cout << x[i] << " " << money[i] << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
Prob3:
Friday the Thirteenth(小さな穴があってWAの結果をもたらして、ACまで1つの数しか残っていません...)
标题:1900年1月1日が月曜日であることが知られており、1900年を含むN年間で毎月13日が月曜日-日曜日の回数となっている.
NOTE 1:得られた1900年1月13日は土曜日で、毎月の日数から次の月13日が曜日を算出し、閏年を注意して判断すればよい.
NOTE 2:毎年単位として一歩ずつ求めていくと、1年ごとに12回目の実际の计算は次の年の1月13日(+31は12月を过ごして1月になる)なので、最后の年のサイクルは特别です.
ソース:
/*
ID:kongse_1
PROG:friday
LANG:C++
*/
#include
#include
#include
using namespace std;
const int maxn = 15;
int month[maxn]={0,31,28,31,30,31,30,31,31,30,31,30,31}, N, times[maxn], curr = 6;
int whether(int year)
{
if(year%400 == 0 || (year%4 == 0 && year%100 != 0)) return 1;
return 0;
}
void caculate_(int year)
{
if(year == 1900+N) return ;
if(whether(year)) month[2] = 29;
else month[2] = 28;
for(int i = 1; i != 13; ++i)
{
curr = (curr+month[i])%7;
if(i == 12 && year == 1900+N-1) break;
++times[curr];
}
caculate_(year+1);
}
int main()
{
freopen("friday.in", "r", stdin);
freopen("friday.out", "w", stdout);
cin >> N;
++times[6];
caculate_(1900);
cout << times[6] << " ";
for(int i = 0; i != 6; ++i)
{
cout << times[i];
if(i != 5) cout << " ";
}
cout << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
Prob 4:Broken Necklace(面白い)題意:一連のネックレスには赤(r)、青(b)、白(w)の3色がある.真ん中のどこかから切り離して、折れた両側からそれぞれ同じ色のビーズ(両側の右の摘出可能数を取り、2つのシーケンスからa[i]+b[i+1]の最大値を見つけます(真ん中から折れた2川なので、必ず隣接して左がi番目、右が(i+1)%n番目).
一方、一つもない左区と右取の値を算出するのも簡単で、それぞれを計算する必要はありません.例えば、i番目を算出して左にm個を取ることができます.では、(i-1)番目、つまり彼の左は必ず(m!=1)個しか取れません.m=1は自分だけです.左の顔色が現在の色と異なる場合、再計算します.しかし、例外があります.
bbwbwrrwrwrの最初のbは5で、5番目のwは1であるべきだが、実際には5番目のbは7であるべきだ.右の赤にもつながっているからだ.だから私たちは特審を受けました
前が2で、現在が白(w)の場合、再計算する必要があります(すなわち、wはキューの末尾です).ソースコード:
/*
ID:kongse_1
PROG:beads
LANG:C++
*/
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 505;
string x;
int n, num[2][maxn], max_;
int whether(char a, char b)
{
if(a+b == 'r'+'b') return 1;
return 0;
}
void calculate_(int curr, string y)
{
char last = x[curr];
if(y == "left")
{
int wh = 1;
num[wh][curr] = 1;
for(int i = (curr-1+n)%n;i != curr ; i = (i-1+n)%n)
{
if(x[i] == last || x[i] == 'w' || last == 'w')
{
if(last == 'w') last = x[i];
++num[wh][curr];
}
else break;
}
}
else
{
int wh = 0;
num[wh][curr] = 1;
for(int i = (curr+1)%n; i != curr ; i = (i+1+n)%n)
{
if(x[i] == last || x[i] == 'w' || last == 'w')
{
if(last == 'w') last = x[i];
++num[wh][curr];
}
else break;
}
}
return ;
}
int main()
{
freopen("beads.in", "r", stdin);
freopen("beads.out", "w", stdout);
cin >> n >> x;
for(int i = 0; i != n; ++i)
{
if( !i || (num[0][(i-1+n)%n] == 2 && x[i] == 'w') || whether(x[(i-1+n)%n],x[i]) )
calculate_(i, "right");
else num[0][i] = num[0][i-1]-1;
}
for(int i = n-1; i != -1; --i)
{
if( i == n-1 || (num[1][(i+1)%n] == 2 && x[i] == 'w') || whether(x[(i+1)%n],x[i]) )
calculate_(i, "left");
else num[1][i] = num[1][i+1]-1;
}
for(int i = 0; i != n; ++i){
max_ = max(max_, num[0][i]+num[1][(i-1+n)%n] );
}
cout <
. これよりUSACO section 1.1で全部できました.
ジルコニアqi 2016.03.04