清華大学の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
//  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    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
//  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; }