清華大学の2011年の再試験の上で問題を解いて報告します
九度OJテーマ1088:残りの木
時間制限:1秒メモリ制限:32メガ特殊判題:No提出:929解決:328
タイトルの説明:
整数L(1<=L<=10000)の長さの道路があり、数軸上の長さLの線分を想像することができ、起点は座標原点であり、整数座標点ごとに木が1本、すなわち0,1,2,...、L共L+1箇所にL+1本の木がある.
次に、いくつかのツリーを移動します.移動したツリーの区間は、100から200までの間(端点を含む)すべてのツリーを移動するペアの数字で表されます.
M(1<=M<=100)区間があり、区間間が重複している可能性があります.すべての区間の木を移動した後に残った木の個数を要求します.
入力:
2つの整数L(1<=L<=10000)とM(1<=M<=100)である.
次にM組の整数があり、各組には数字のペアがあります.
出力:
複数組の入力データがある可能性があり、各組の入力データに対して、すべての区間のツリーを移動した後に残ったツリーの個数を表す数を出力します.
サンプル入力:
500 3
100 200
150 300
470 471
サンプル出力:
298
より効率的な解法(昨年バグがあったのは今年一度で済みました)
九度OJテーマ1087:約数の個数
時間制限:1秒メモリ制限:32メガ特殊判題:No提出:1596解決:382
タイトルの説明:
n個の整数を入力し、各数の約数の個数を順次出力する
入力:
入力される第1の動作N、すなわち配列の個数(N<=1000)
次の1行にはN個の整数が含まれ、各数の範囲は(1<=Num<=1億2000万)
N=0で入力が終了します.
出力:
複数組の入力データがあり、各組の入力データに対して、
N行が出力され、各行は上の1つの数の約数の個数に対応する.
サンプル入力:
5
1 3 4 6 12
サンプル出力:
1
2
3
4
6
九度OJテーマ1086:最小費用
時間制限:1秒メモリ制限:32メガ特殊判定:No提出:765解決:121
タイトルの説明:
ある路線にはNの駅があり、3つの距離の道のりがあり、L 1,L 2,L 3で、対応する価格はC 1,C 2,C 3である.対応関係は次のとおりです.
距離s運賃
0 L1 L2入力保証02つのステーション間の距離はL 3を超えない.
乗客が移動する2つの駅の距離がL 3より大きい場合、中間の1つの駅から降りて切符を買って乗車することができるので、乗客は全過程で少なくとも2枚の切符を買うことができます.
L 1,L 2,L 3,C 1,C 2,C 3をあげます.次に、乗客の旅の開始駅と終点駅であるA Bの値である.
次に、N,Nをその路線の合計駅数として入力し、N−1個の整数を入力し、その路線の最初の駅から2番目の駅、3番目の駅、・・・、N番目の駅までの距離を表す.
入力により、乗客がAからB駅までの最小費用を出力する.
入力:
次の形式でデータを入力します.
L1 L2 L3 C1 C2 C3
A B
N
a[2]
a[3]
……
a[N]
出力:
複数のテストデータがあり、各データに対して、
入力により、乗客がAからB駅までの最小費用を出力する.
サンプル入力:
1 2 3 1 2 3
1 2
2
2
サンプル出力:
2
時間制限:1秒メモリ制限:32メガ特殊判題:No提出:929解決:328
タイトルの説明:
整数L(1<=L<=10000)の長さの道路があり、数軸上の長さLの線分を想像することができ、起点は座標原点であり、整数座標点ごとに木が1本、すなわち0,1,2,...、L共L+1箇所にL+1本の木がある.
次に、いくつかのツリーを移動します.移動したツリーの区間は、100から200までの間(端点を含む)すべてのツリーを移動するペアの数字で表されます.
M(1<=M<=100)区間があり、区間間が重複している可能性があります.すべての区間の木を移動した後に残った木の個数を要求します.
入力:
2つの整数L(1<=L<=10000)とM(1<=M<=100)である.
次にM組の整数があり、各組には数字のペアがあります.
出力:
複数組の入力データがある可能性があり、各組の入力データに対して、すべての区間のツリーを移動した後に残ったツリーの個数を表す数を出力します.
サンプル入力:
500 3
100 200
150 300
470 471
サンプル出力:
298
// 2011: 1088:
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <fstream>
using namespace std;
struct TREE{
int x;
int y;
};
TREE t[100];
bool f[10001];
int main(){
int l, m,
i, j, k, n;
ifstream cin("THU_1088.txt");
while( cin >> l ){
memset( f, 0, sizeof(f) );
cin >> m;
for( i=0; i<m; i++ ){
cin >> t[i].x >> t[i].y;
if( t[i].x > t[i].y ){
int temp = t[i].x;
t[i].x = t[i].y;
t[i].y = temp;
}
for( j=t[i].x; j<=t[i].y; j++ )
f[j] = 1;
}
int num=0;
for( i=0; i<=l; i++ )
if( f[i]==1 )
num++;
cout << l+1-num << endl;
}
system("pause");
return 0;
}
更新個より効率的な解法(昨年バグがあったのは今年一度で済みました)
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;
struct TREE{int x,y;};
TREE t[100],f[100];
bool cmp( TREE a, TREE b ){ return a.x < b.x; };
int main(){
int i, j, k, l, n, m;
ifstream cin("THU_1088.txt"); //
while( cin >> l >> m ){
for( i=0; i<m; i++ ){
cin >> t[i].x >> t[i].y;
if( t[i].x > t[i].y ){
int temp = t[i].x;
t[i].x = t[i].y;
t[i].y = temp;
}
}
sort( t, t+m, cmp ); // y
f[0] = t[0];
for( i=1,j=0; i<m; i++ ){
//cout << t[i].x << " " << t[i].y << endl;
if( t[i].x - 2 < f[j].y ){ //
f[j].y = max( f[j].y, t[i].y );
}else{ //
f[++j] = t[i];
}
}
int num = 0;
for( i=0; i<=j; i++ ){
//cout << f[i].x << " " << f[i].y << endl;
num += ( f[i].y - f[i].x + 1 );
}
cout << l+1-num << endl;
}
return 0;
}
九度OJテーマ1087:約数の個数
時間制限:1秒メモリ制限:32メガ特殊判題:No提出:1596解決:382
タイトルの説明:
n個の整数を入力し、各数の約数の個数を順次出力する
入力:
入力される第1の動作N、すなわち配列の個数(N<=1000)
次の1行にはN個の整数が含まれ、各数の範囲は(1<=Num<=1億2000万)
N=0で入力が終了します.
出力:
複数組の入力データがあり、各組の入力データに対して、
N行が出力され、各行は上の1つの数の約数の個数に対応する.
サンプル入力:
5
1 3 4 6 12
サンプル出力:
1
2
3
4
6
// 2011: 1087:
#include <iostream>
using namespace std;
struct DIVISOR{
int x;
int y;
};
DIVISOR d[200];
int main(){
int i, j, k, n, m, t;
while( cin >> n && n!=0 ){
while( n-- ){
for( i=0; i<200; i++ ) //
d[i].x = d[i].y = 0;
cin >> m;
j = 0; // d[i]
for( i=2; i*i<=m || m!=1; ){
if( m%i == 0 ){
if( i != d[j].x ){
j++;
d[j].x = i;
}
d[j].y++;
m /= i;
}
else i++;
}
int result = 1;
for( i=1; d[i].x!=0; i++ ){
//cout << d[i].x << " " << d[i].y << endl;
result *= (d[i].y+1);
}
cout << result << endl;
}
}
//system("pause");
return 0;
}
九度OJテーマ1086:最小費用
時間制限:1秒メモリ制限:32メガ特殊判定:No提出:765解決:121
タイトルの説明:
ある路線にはNの駅があり、3つの距離の道のりがあり、L 1,L 2,L 3で、対応する価格はC 1,C 2,C 3である.対応関係は次のとおりです.
距離s運賃
0
乗客が移動する2つの駅の距離がL 3より大きい場合、中間の1つの駅から降りて切符を買って乗車することができるので、乗客は全過程で少なくとも2枚の切符を買うことができます.
L 1,L 2,L 3,C 1,C 2,C 3をあげます.次に、乗客の旅の開始駅と終点駅であるA Bの値である.
次に、N,Nをその路線の合計駅数として入力し、N−1個の整数を入力し、その路線の最初の駅から2番目の駅、3番目の駅、・・・、N番目の駅までの距離を表す.
入力により、乗客がAからB駅までの最小費用を出力する.
入力:
次の形式でデータを入力します.
L1 L2 L3 C1 C2 C3
A B
N
a[2]
a[3]
……
a[N]
出力:
複数のテストデータがあり、各データに対して、
入力により、乗客がAからB駅までの最小費用を出力する.
サンプル入力:
1 2 3 1 2 3
1 2
2
2
サンプル出力:
2
// 2011: 1086:
//0<L1<L2<L3<10^9 0<C1<C2<C3<10^9
// <=L3
//A-B - n a[] n-1 a[2]-a[n]
//a[] 1 , 2 , 3 ,……, N 。
// :
// L1 L2 L3 C1 C2 C3
// A B
// N
// a[2]
// a[3]
// ……
// a[N]
#include <fstream>
#include <cstdio>
#include <iostream>
#define T 100000
#define INT long long
using namespace std;
INT a[T], b[T], l[4], c[4]; //l[0]
INT dp[T], t[4];
int back[4]; //back[0]
int A, B;
void backward( int x, int index ){ //x
INT sum = 0;
back[index] = x+1;
for( int i=1; sum<=l[index]; i++ ){
sum = a[x] - a[x-i];
back[index]--;
if( back[index] < A )
back[index] = A;
}
};
int main()
{
int i, j, k, n;
freopen("THU_1086.txt","r",stdin);//
while( scanf("%d%d%d%d%d%d", &l[1],&l[2],&l[3],&c[1],&c[2],&c[3])!=EOF ){
scanf( "%d%d%d", &A, &B, &n );
a[0] = a[1] = 0;
for( i=2; i<=n; i++ )
scanf( "%d", &a[i]); //%f
if( A > B ){
int temp = A;
A = B;
B = temp;
}else if( A == B ){
printf("0
");
continue;
}
for( i=0; i<=A; i++ ) // dp[0]dp[1]
dp[i] = 0;
for( i=A+1; i<=B; i++ ){
k = 0; //k t[]
for( j=1; j<=3; j++ ){
backward( i, j );
if( back[j] != i )
{ k++; t[k] = dp[back[j]]+c[j]; }
}
for( j=1; j<=k-1; j++ )
t[1] = min( t[1], t[j+1] ); // t[1]
dp[i] = t[1];
}
printf( "%lld
", dp[B] );
}
//while(1);//
return 0;
}