2013-5-7トレーニング試合まとめ
58250 ワード
タイトルソースThe 13 th Zhejiang University Programming Contest
リンク:http://openoj.awaysoft.com:8080/judge/contest/view.action?cid=421#overview
A - Alien's Organ
标题:イベント出現平均確率はaであり、出現回数がN以下である確率を問う
解法:ポアソン分布、公式に従って計算すればよい.
View Code
B - Bad-written Number
标题:LEDランプは1つの数字を表して、3*3行使って、今N個の数字があって、前の数字の第3列は後の数字の第1列と重なって、合法的な方案が現れる可能性があることを聞きますいくらあります.
解法:状態圧縮DP,dp(i,j)は、前のi個の数、最後の数の第3列の状態jを表す、合法的なシナリオ数である.移行方程式は次のとおりです.
dp(i+1,a[k][2])+=dp(i,j)のうち、a[k][0,1,2]は、数字kの1,2,3列目の状態を表す.
View Code
C - Carrot Fantasy
标题:ややこしいーー…タワーガードと同じです.的模拟题
解法:時間によるシミュレーション..でも気持ち悪い.
D - Dakar Rally
标题:N段路、各段路に長さLiがあり、単位燃費aiと、区間にガソリンスタンドがあり、ガソリン単価piがあり、順番にすべての路を歩き終え、最小費用を聞く.
解法:欲張りで、ガソリンスタンドを通って、油を全部満タンにして、単調な列で保存して、この油の数量と単価、ガソリンを給油する時、高いのを取り替えて、使う時、価格の低いのから使います.
費用を計算して、本当に使った油だけを計算します.
View Code
E - Ever Dream
題意:N行の文字を与え、単語の出現頻度を統計する.出力周波数が1より大きい、最も長い単語は、複数ある場合、最後から2番目の単語を出力する.
解法:シミュレーションに追随すればよい.STLで書きます.便利です.入力処理については、英語以外の文字をすべてスペースに変換するstrtokを再利用して分割する.これで便利です.
View Code
F - Fawful's Revenge
この問題はとても神だそうです....
G - Gibonacci number
題意:G(i)=G(i-1)+G(i-2)は、G(0)=1、G(i)、iを与える、G(j)を求め、G(1)>0、そうでなければ-1を出力する.
解法:G(i)=F(i-1)*G(1)+F(i-2)、計算に持ち込めばよい.合法か否かの判定に注意する.
View Code
H - Happy Programming Contest
題意:N個の題目、各題目は完成時間があって、価値があって、今時間Tを与えて、最大完成数量を求めて、最小完成時間、最大価値.
解法:01リュックサック、ただ少し条件が多いだけです
View Code
I - I am Nexus Master!
題意:フォーラムには10の等級があり、1人のユーザーの等級評定は、登録時間、ダウンロード量、アップロード量、アップロード/ダウンロード割合を使用することによって一定である.現在のユーザーの情報を与え、そのレベルをフィードバックします.
解法:シミュレーションに従えばよい.一応、直接0に降格するか否かを判定してから降格するか否かを判定し、アップグレードするか否かを判定しなければならない.
View Code
リンク:http://openoj.awaysoft.com:8080/judge/contest/view.action?cid=421#overview
A - Alien's Organ
标题:イベント出現平均確率はaであり、出現回数がN以下である確率を問う
解法:ポアソン分布、公式に従って計算すればよい.
View Code
// p(k) = e^(-ave) * ave^k / k!
#include<cstdio>
#include<cmath>
int main(){
double ave;
int T, n;
scanf("%d", &T);
while( T-- ){
scanf("%d %lf", &n,&ave);
double p = 0, a = 1, b = 1;
for(int i = 0; i <= n; i++){
p += exp(-ave)*a/b;
a *= ave;
b *= (i+1);
}
printf("%.3lf
", p );
}
return 0;
}B - Bad-written Number
标题:LEDランプは1つの数字を表して、3*3行使って、今N個の数字があって、前の数字の第3列は後の数字の第1列と重なって、合法的な方案が現れる可能性があることを聞きますいくらあります.
解法:状態圧縮DP,dp(i,j)は、前のi個の数、最後の数の第3列の状態jを表す、合法的なシナリオ数である.移行方程式は次のとおりです.
dp(i+1,a[k][2])+=dp(i,j)のうち、a[k][0,1,2]は、数字kの1,2,3列目の状態を表す.
View Code
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
typedef long long LL;
const int N = 20100;
const LL mod = (LL)1e9+7;
char str[3][N];
const char* tar[] = {
" _ | ||_|",
" | |",
" _ _||_ ",
" _ _| _|",
" |_| |",
" _ |_ _|",
" _ |_ |_|",
" _ | |",
" _ |_||_|",
" _ |_| _|"
};
int a[10][3], b[N], n;
LL dp[N][4];
void pre(){
memset( a, 0, sizeof(a) );
for(int i = 0; i <= 9; i++)
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++)
//a[i][j] |= (tar[i][j+3*k] != ' ') << k;
a[i][j] = (a[i][j]<<1) | (tar[i][j+3*k] != ' ');
//for(int i = 0; i < 10; i++)
// printf("%d: %d, %d, %d
", i, a[i][0], a[i][1], a[i][2] );
}
void init(){
memset( str, 0, sizeof(str));
memset( b, 0 , sizeof(b));
for(int i = 0; i < 3; i++){
gets( str[i] );
for(int j = strlen(str[i]); j < 2*n+1; j++)
str[i][j] = ' ';
}
for(int j = 0; j < 3; j++)
for(int i = 0; i < 2*n+1; i++)
//b[i] |= (str[j][i] != ' ') << j;
b[i] = (b[i]<<1) | (str[j][i]!=' ');
}
void solve(){
memset( dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 0; i < n; i++){
int idx = 2*i;
for(int j = 0; j < 4; j++){
if( dp[i][j] == 0 ) continue;
for(int k = 0; k < 10; k++){
if( (j | a[k][0]) != b[idx] ) continue;
if( a[k][1] != b[idx+1] ) continue;
if( (a[k][2] & b[idx+2]) != a[k][2] ) continue;
dp[i+1][ a[k][2] ] += dp[i][j];
dp[i+1][ a[k][2] ] %= mod;
}
}
}
printf("%lld
", dp[n][ b[2*n] ]);
}
int main(){
freopen("2.in","r",stdin);
pre();
int T;
scanf("%d", &T);
while( T-- ){
scanf("%d", &n); getchar();
init();
solve();
}
return 0;
}C - Carrot Fantasy
标题:ややこしいーー…タワーガードと同じです.的模拟题
解法:時間によるシミュレーション..でも気持ち悪い.
D - Dakar Rally
标题:N段路、各段路に長さLiがあり、単位燃費aiと、区間にガソリンスタンドがあり、ガソリン単価piがあり、順番にすべての路を歩き終え、最小費用を聞く.
解法:欲張りで、ガソリンスタンドを通って、油を全部満タンにして、単調な列で保存して、この油の数量と単価、ガソリンを給油する時、高いのを取り替えて、使う時、価格の低いのから使います.
費用を計算して、本当に使った油だけを計算します.
View Code
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = (int)1e5+100;
int n; LL k;
struct TMP{
LL a, b, c;
void input(){
scanf("%lld%lld%lld",&a,&b,&c);
}
}route[N];
struct node{
LL gap, c;
}Q[N<<1], pre;
bool init(){
for(int i = 0; i < n; i++)
route[i].input();
for(int i = 0; i < n; i++)
if( 1LL*route[i].a*route[i].b > k ) return false;
return true;
}
void solve(){
LL res = 0, s;
int l = 0, r = 0;
for(int i = 0; i < n; i++){
// clear and full the gap.
while( (r>l) && (Q[r-1].c > route[i].c) ) r--;
s = 0;
for(int j = l; j < r; j++) s += Q[j].gap;
pre.c = route[i].c; pre.gap = k-s;
Q[r++] = pre;
// use the gap from the cheapest.
s = 1LL*route[i].a*route[i].b;
while( (l<r) && (Q[l].gap <= s) ){
res += Q[l].gap*Q[l].c;
s -= Q[l++].gap;
}
if( s > 0 ){
res += s*Q[l].c;
Q[l].gap -= s;
}
}
printf("%lld
", res);
}
int main(){
int T;
scanf("%d", &T);
while( T-- ){
scanf("%d%lld", &n,&k);
if( init() ) solve();
else printf("Impossible
");
}
return 0;
}E - Ever Dream
題意:N行の文字を与え、単語の出現頻度を統計する.出力周波数が1より大きい、最も長い単語は、複数ある場合、最後から2番目の単語を出力する.
解法:シミュレーションに追随すればよい.STLで書きます.便利です.入力処理については、英語以外の文字をすべてスペースに変換するstrtokを再利用して分割する.これで便利です.
View Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
map<string,int> mp;
bool isletter( char ch ){
if( ( (ch>='a')&&(ch<='z') ) || ( (ch>='A')&&(ch<='Z') ) )
return true;
return false;
}
bool Upletter( char ch ){
if( (ch>='A') && (ch<='Z') )
return true;
return false;
}
struct node{
string s;
int len;
bool operator < (const node &tmp) const{
return (len>tmp.len)||((len==tmp.len)&&(s<tmp.s));
}
}nxt;
vector< node > Q[110];
void solve(){
int n;
char str[110];
scanf("%d", &n); getchar();
mp.clear();
for(int i = 0; i < n; i++){
memset(str, 0, sizeof(str));
gets( str );
int L = strlen(str);
for(int i = 0; str[i]; i++){
if( isletter( str[i] ) ){
if( Upletter( str[i] ) )
str[i] += 32;
}
else str[i] = ' ';
}
char *p = strtok( str, " " );
while( p ){
if( mp.count(p) == 0 ) mp[p] = 1;
else mp[p] += 1;
p = strtok( NULL, " " );
}
}
for(int i = 0; i <= 100; i++)
Q[i].clear();
for( map<string,int>::iterator it = mp.begin(); it != mp.end(); it++ ){
nxt.s = it->first;
nxt.len = (it->first).size();
Q[ it->second ].push_back( nxt );
}
for(int i = 0; i <= 100; i++)
sort( Q[i].begin(), Q[i].end() );
bool flag = true;
for(int i = 100; i > 1; i-- ){
if( (int)Q[i].size() == 0 ) continue;
/* printf("len = %d, size = %d
", i, Q[i].size() );
for(int j = 0; j < (int)Q[i].size(); j++ ){
printf("%s ", Q[i][j].s.c_str() );
} puts("");
*/
int cur = 1;
for(int j = 1; j < (int)Q[i].size(); j++ ){
if( Q[i][j].len == Q[i][j-1].len ) cur++;
else break;
}
if( flag ) flag = false;
else printf(" ");
if( cur == 1 ) printf("%s", Q[i][0].s.c_str() );
else printf("%s", Q[i][cur-2].s.c_str() );
}
puts("");
}
int main(){
freopen("1.in","r",stdin);
int T;
scanf("%d", &T);
while( T-- ){
solve();
}
return 0;
}F - Fawful's Revenge
この問題はとても神だそうです....
G - Gibonacci number
題意:G(i)=G(i-1)+G(i-2)は、G(0)=1、G(i)、iを与える、G(j)を求め、G(1)>0、そうでなければ-1を出力する.
解法:G(i)=F(i-1)*G(1)+F(i-2)、計算に持ち込めばよい.合法か否かの判定に注意する.
View Code
#include<cstdio>
typedef long long LL;
LL f[25], G[25];
int main(){
f[0] = f[1] = 1;
for(int i = 2; i <= 20; i++) f[i] = f[i-1]+f[i-2];
int T, i, gi, j;
scanf("%d", &T);
while( T-- ){
scanf("%d%d%d", &i,&gi,&j); // i, Gi, j
if( i == 1 ){
if( gi < 1 ){
printf("-1
"); continue;
}
if( j == 1 ) printf("%d
", gi );
else printf("%lld
", f[j-1]*gi+f[j-2] );
}
else{
if( (gi-f[i-2])%f[i-1] != 0 ) printf("-1
");
else{
LL g1 = (gi-f[i-2])/f[i-1];
if( g1 < 1 ){
printf("-1
"); continue;
}
if( j == 1 ) printf("%lld
", g1);
else printf("%lld
", f[j-1]*g1+f[j-2] );
}
}
}
return 0;
}H - Happy Programming Contest
題意:N個の題目、各題目は完成時間があって、価値があって、今時間Tを与えて、最大完成数量を求めて、最小完成時間、最大価値.
解法:01リュックサック、ただ少し条件が多いだけです
View Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int num[55][1010], dp[55][1100], time[55][1100], sum[55][1100];
int n, T;
struct node{
int t, c;
bool operator < (const node &tmp)const{
return (t<tmp.t)||(t==tmp.t&&c>tmp.c);
}
}p[55];
int main(){
int T, t;
scanf("%d", &t);
while( t-- ){
scanf("%d%d", &T, &n);
for(int i = 1; i <= n; i++)
scanf("%d", &p[i].t);
for(int i = 1; i <= n; i++)
scanf("%d", &p[i].c);
sort( p+1, p+n+1 );
memset( dp, 0, sizeof(dp));
memset( num, 0, sizeof(num));
memset( sum, 0, sizeof(sum));
for(int i = 1; i <= n; i++){
for(int j = 0; j <= T; j++){
// dp[i][j] = max( dp[i-1][j], dp[i-1][j-p[i].t]+p[i].c );
dp[i][j] = dp[i-1][j]; num[i][j] = num[i-1][j];
sum[i][j] = sum[i-1][j];
if( j >= p[i].t ){
if( dp[i][j] <= (dp[i-1][j-p[i].t]+p[i].c) ){
if( dp[i][j] < dp[i-1][j-p[i].t]+p[i].c ){
dp[i][j] = dp[i-1][j-p[i].t]+p[i].c;
num[i][j] = num[i-1][j-p[i].t]+1;
sum[i][j] = sum[i-1][j-p[i].t] + j;
}
else if( num[i][j] <= num[i-1][j-p[i].t]+1 ){
if( num[i][j] < num[i-1][j-p[i].t]+1 ){
num[i][j] = num[i-1][j-p[i].t]+1;
sum[i][j] = sum[i-1][j-p[i].t] + j;
}
else if( sum[i][j] > sum[i-1][j-p[i].t] + j ){
sum[i][j] = sum[i-1][j-p[i].t] + j;
}
}
}
}
}
}
int pc = 0, pn = 0, pt = 0;
for(int i = 0; i <= T; i++){
if( pc < dp[n][i] ){
pc = dp[n][i];pn = num[n][i];pt = sum[n][i];
}
else if( pc == dp[n][i] ){
if( pn < num[n][i] )
pn = num[n][i], pt = sum[n][i];
else if( pt > sum[n][i] )
pt = sum[n][i];
}
}
printf("%d %d %d
", pc, pn, pt );
}
return 0;
}I - I am Nexus Master!
題意:フォーラムには10の等級があり、1人のユーザーの等級評定は、登録時間、ダウンロード量、アップロード量、アップロード/ダウンロード割合を使用することによって一定である.現在のユーザーの情報を与え、そのレベルをフィードバックします.
解法:シミュレーションに従えばよい.一応、直接0に降格するか否かを判定してから降格するか否かを判定し、アップグレードするか否かを判定しなければならない.
View Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const double esp = 1e-8;
const string tar[] = {
"Peasant", // 0
"User", // 1
"Power_User", // 2
"Elite_User", // 3
"Crazy_User", // 4
"Insane_User", // 5
"Veteran_User", // 6
"Extreme_User", // 7
"Ultimate_User", // 8
"Nexus_Master" // 9
};
double A[10]={
0,0,50,120,300,500,750,1024,1.5*1024,3*1024
};
double B[10]={
0,0,1.05,1.55,2.05,2.55,3.05,3.55,4.05,4.55
};
int C[10]={
0,0,4,8,15,25,40,60,80,100
};
int sign(double x){
return x<-esp?-1:(x>esp);
}
string s;
int week, cur;
double down, up;
void input(){
char tmp[20];
scanf("%s %d %lf %lf", tmp, &week, &down, &up );
s = tmp;
for(int i = 0; i < 10; i++)
if( s == tar[i] ){
cur = i; break;
}
}
bool Clear(){
if( (sign(down-50 ) >= 0) && (sign(up-0.4*down) < 0) ) return true;
if( (sign(down-100) >= 0) && (sign(up-0.5*down) < 0) ) return true;
if( (sign(down-200) >= 0) && (sign(up-0.6*down) < 0) ) return true;
if( (sign(down-400) >= 0) && (sign(up-0.7*down) < 0) ) return true;
if( (sign(down-800) >= 0) && (sign(up-0.8*down) < 0) ) return true;
return false;
}
bool Down(){ //
bool flag = false;
while( (cur>1) && (sign(up - down*(B[cur]-0.1)) < 0) )
cur -= 1, flag = true;
return flag;
}
void Up(){ // ，
int x = 9;
for(int x = 9; x > cur; x-- ){
if( (x>cur) && (week>=C[x]) && (sign(down-A[x])>=0)
&& (sign(up-down*B[x])>=0) ){
cur = x; break;
}
}
}
int main(){
int T;
scanf("%d", &T);
while( T-- ){
input();
if( Clear() ) printf("%s
", tar[0].c_str() );
else{
if( Down() == false ) Up();
printf("%s
", tar[cur].c_str() );
}
}
return 0;
}