九度OJ
题目1088:剩下的树
时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:929 解决:328
题目描述:
有一个长度为整数L(1<=L<=10000)的马路,可以想象成数轴上长度为L的一个线段,起点是坐标原点,在每个整数坐标点有一棵树,即在0,1,2,...,L共L+1个位置上有L+1棵树。
现在要移走一些树,移走的树的区间用一对数字表示,如 100 200表示移走从100到200之间(包括端点)所有的树。
可能有M(1<=M<=100)个区间,区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。
输入:
两个整数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; }
更新个更高效的解法(去年做有bug 今年一次就搞定了)
#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 兆 特殊判题:否 提交:1596 解决:382
题目描述:
输入n个整数,依次输出每个数的约数的个数
输入:
输入的第一行为N,即数组的个数(N<=1000)
接下来的1行包括N个整数,其中每个数的范围为(1<=Num<=1000000000)
当N=0时输入结束。
输出:
可能有多组输入数据,对于每组输入数据,
输出N行,其中每一行对应上面的一个数的约数的个数。
样例输入:
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 兆 特殊判题:否 提交:765 解决:121
题目描述:
在某条线路上有N个火车站,有三种距离的路程,L1,L2,L3,对应的价格为C1,C2,C3.其对应关系如下:
距离s 票价
0<S<=L1 C1
L1<S<=L2 C2
L2<S<=L3 C3
输入保证0<L1<L2<L3<10^9,0<C1<C2<C3<10^9。
每两个站之间的距离不超过L3。
当乘客要移动的两个站的距离大于L3的时候,可以选择从中间一个站下车,然后买票再上车,所以乘客整个过程中至少会买两张票。
现在给你一个 L1,L2,L3,C1,C2,C3。然后是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\n"); 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\n", dp[B] ); } //while(1);// return 0; }