1. 首页
  2. IT资讯

小学期acm训练第一发(简单数学题)

这一部分为刘汝佳的《算法竞赛入门经典》(第一版)第三章的数学杂题部分,知识点的确比较杂,但还是以模拟为主。

题目链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=43038#overview

题目分析:

A.UVA113 让你对一个高精度的数求开方,直接开高精模板好像会T,所以使用了JAVA(JAVA自带快速幂,所以算乘方的时候回比较快),在此基础上以1,p为边界进行二分查找。然而后来找了网上的题解才发现直接开double也是可以的(只考虑整数的时候精度误差可以忽略),看来以后还是大胆还是很重要的。

B.UVA10161 给你那个无限大的棋盘,再给你一个自然数n,问这个自然数在那个棋盘上第几行与第几列。方法是先判断n在哪两个完全平方数之间,这样可以大致确定n的范围,然后再分类讨论求出坐标即可。

C.UVA253 判断两个骰子是不是一样,那只需要判断其中一个骰子通过旋转是否能变得和另一个一样。又每个骰子有6个面,固定每个面朝上之后各有4种旋转方式(绕垂直的轴转一圈),酱紫共有4*6=24种情况,分别对比就好啦。

D.UVA621 简单模拟题,让你判断给你的字符串符合四种特征中的哪一个,注意按照顺序判断就行。

E.UVA10025 对1…n前加上正或负,使得结果为k。又给定整数k,求n的最小值,使得存在这样的等式。输入k时,如果k小于0,直接取相反数,因为所有正负号取反就可以得到原等式。然后假设所有的符号全部是正号,求出使得1+2+…+n>k的最小的n,然后判断奇偶性是否能满足条件(因为只要将若干个正号改成负号就相当于减去那些数的2倍),又因为是最小的n,所以这样的若干个数必定存在,再判断奇偶性就能解决了。最后不要忘记对0,1这样的边界数据特判。

F.UVA591 题意是让你算出最少移动多少次数可以把所有积木堆成同一高度,由于积木总数除以积木的堆数是整数,所以先把这个最后要达成的平均高度算出来,然后用所有比它高的积木堆的高度减去它,再求和即可。

G.UVA107 未AC

H.UVA573 传统的蜗牛爬井问题,白天向上爬U,晚上下滑D,每天向上爬的距离还要减去F%,井的高度是H,需要注意的地方除了第一天的临界情况外,还有蜗牛晚上向下滑,只有当绝对高度为负时,才算是failure。

I.UVA846 和E题有类似的思路,因为答案和起始的数字无关,只和两数之差有关,设两数之差为n,先求出最大的k,使得1+2+3+…+k<n,再贪心算出至少还需要加上多少步,注意分类讨论n=0的情况。

J.UVA10499 题目看起来很复杂,实际上就是让你算切成n块之后表面积增大的百分比,无坑,唯一难点在于看懂题目。

K.UVA10790 让你算完全二分图K_m,n的非边界的交点个数,可以枚举较小的情况猜,也可以直接根据边的条数找规律,注意多增加一条边会增加的交点的个数,具体规律见代码

L.UVA11044 题目大意:至少需要多少个3*3的纸片才能覆盖住所有除边界以外的所有点。方法:把边界去掉再向上整除。

M.UVA10719 未AC

N.UVA10177 直接找规律即可,求正方形与长方形的个数应该是小学的知识点,注意数据较大,需要开LL,不放心直接JAVA大数也是挺方便的

O.UVA10916 难点还是在于看懂题意,先根据年份可以推出对应的bit是多少,然后只需要求出最大的n,使得n!<2^bit数

P.UVA10970 题目大意:求出一块M*N的巧克力最少要切多少刀才能全部切开(不必考虑把两块巧克力叠起来再切的情况),数数就好啦,而且先切横着的还是先切竖着的最后结果都一样>_<

Q.UVA10014 给了一个递推式和若干已知量,让你求a_1。较为复杂的一个题,关键在于如何化简递推式。可以直接写成矩阵然后运用高斯消元求解。通过直接观察也可以发现将递推式全部写出来(令i=1,2,3,…,),然后分别将第一条式子*1,第二条式子*2,…,之后再累加可以得到a_n,再将所有递推式直接全部相加,又可以得到a_1和a_n的关系,解一下就好啦。


代码如下:

A.

import java.util.Scanner; import java.math.BigInteger; public class Main {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         while(in.hasNext())         {             BigInteger b,c,low,high,key,temp;             int a;             a = in.nextInt();             b = in.nextBigInteger();             low = BigInteger.ONE;             high = b;             key = low.add(high).shiftRight(1);             temp = key.pow(a);             while(temp.compareTo(b) != 0)             {                 if(temp.compareTo(b) == -1)                 {                     low = key.add(BigInteger.ONE);                     key = low.add(high).shiftRight(1);                     temp = key.pow(a);                 }                 else                 {                     high= key.subtract(BigInteger.ONE);                     key = low.add(high).shiftRight(1);                     temp = key.pow(a);                 }             }             System.out.println(key);         }     } }


B.

#include <iostream> #include <cmath> using namespace std; int main() {     int n;     cin >> n;     while(n)     {             int x,y,xs,ys;             if(abs(sqrt(n)-int(sqrt(n)))<1e-8)             {                 if(int(sqrt(n)) % 2 == 0) cout << int(sqrt(n)) << " 1" << endl;                 else cout << "1 " << int(sqrt(n)) << endl;                 cin >> n;                 continue;             }             else if(abs(sqrt(n-1)-int(sqrt(n-1)))<1e-8)             {                 if(int(sqrt(n-1)) % 2 == 0) cout << int(sqrt(n-1))+1 << " 1" << endl;                 else cout << "1 " << int(sqrt(n-1))+1 << endl;                 cin >> n;                 continue;             }             int p = int(sqrt(n));             int q = p*p+p+1;             //cout << p << " " << q << endl;             if(p%2 == 0)             {                    if(n<=q)                    cout << p+1 << " " << n-p*p << endl;                    else cout << (p+1)*(p+1)-n+1 << " " << p+1<< endl;             }             else              {                  if(n<=q)                  cout << n-p*p << " " << p+1 << endl;                  else cout << p+1 << " " << (p+1)*(p+1) << endl;             }             cin >> n;     }     return 0; }


C.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	string s[25]; 	while(cin >> s[1]) 	{ 		s[0] = s[1].substr(6,6); 		 		s[1] = s[1].substr(0,6); 		 		for (int i = 2;i<=24;i++) s[i] = s[1]; 		 		s[5][0] = s[1][1]; 		s[5][1] = s[1][5]; 		s[5][2] = s[1][2]; 		s[5][3] = s[1][3]; 		s[5][4] = s[1][0]; 		s[5][5] = s[1][4]; 		 		s[9][0] = s[5][1]; 		s[9][1] = s[5][5]; 		s[9][2] = s[5][2]; 		s[9][3] = s[5][3]; 		s[9][4] = s[5][0]; 		s[9][5] = s[5][4]; 		 		s[13][0] = s[9][1]; 		s[13][1] = s[9][5]; 		s[13][2] = s[9][2]; 		s[13][3] = s[9][3]; 		s[13][4] = s[9][0]; 		s[13][5] = s[9][4]; 		 		s[17][0] = s[1][2]; 		s[17][1] = s[1][1]; 		s[17][2] = s[1][5]; 		s[17][3] = s[1][0]; 		s[17][4] = s[1][4]; 		s[17][5] = s[1][3]; 		 		s[21][0] = s[1][3]; 		s[21][1] = s[1][1]; 		s[21][2] = s[1][0]; 		s[21][3] = s[1][5]; 		s[21][4] = s[1][4]; 		s[21][5] = s[1][2]; 		 		for (int i = 1;i<=21;i+=4) 		for (int j = 1;j<4;j++) 		{ 			s[i+j] = s[i+j-1]; 			s[i+j][0] = s[i+j-1][0]; 			s[i+j][1] = s[i+j-1][3]; 			s[i+j][2] = s[i+j-1][1]; 			s[i+j][3] = s[i+j-1][4]; 			s[i+j][4] = s[i+j-1][2]; 			s[i+j][5] = s[i+j-1][5]; 		} 		 		string result = "FALSE"; 		for (int i = 1;i<=24;i++)if(s[i] == s[0]) 		{ 			result = "TRUE"; 			break; 		} 		//for (int i = 1;i<=24;i++) cout << s[i] << endl; 		cout << result << endl; 	}      //fclose(stdin);     //fclose(stdout);      return 0; }


D.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	int n; 	cin >> n; 	for (int i = 0;i<n;i++) 	{ 		string s; 		cin >> s; 		if(s == "1"||s == "4"||s == "78")  		{ 			cout << "+" << endl; 			continue; 		} 		if(s.substr(s.length()-2,2) == "35") 		{ 			cout << "-" << endl; 			continue; 		} 		if(s[0] == '9' && s[s.length()-1] == '4') 		{ 			cout << "*" << endl; 			continue; 		} 		if(s.substr(0,3) == "190") 		{ 			cout << "?" << endl; 			continue; 		} 	}      //fclose(stdin);     //fclose(stdout);      return 0; }


E.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	LL t; 	cin >> t; 	for (int i1 = 0;i1<t;i1++) 	{ 		LL n; 		cin >> n; 		if(n<0) n = -n; 		if(!n) 		{ 			cout << "3" << endl; 			if(i1!=t-1) cout << endl; 			continue; 		} 		LL result = (1+int(sqrt(n)*sqrt(8)))/2; 		LL p = result*(result+1)/2; 		if(abs(p-n)%2 == 0)cout << result << endl; 		else 		{ 			if(result%2 == 0) cout << result+1 << endl; 			else cout << result+2 << endl; 		} 		if(i1!=t-1) cout << endl; 	}      //fclose(stdin);     //fclose(stdout);      return 0; }


F.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	int n,i1 = 1; 	cin >> n; 	while(n) 	{ 		int a[60] = {0},s = 0,result = 0; 		for (int i = 0;i<n;i++) 		{ 			cin >> a[i]; 			s+=a[i]; 		} 		s/=n; 		for (int i = 0;i<n;i++) 		if(a[i]>=s) 		result+=a[i]-s; 		cout << "Set #" << i1++ << endl; 		cout << "The minimum number of moves is " << result << "." << endl << endl; 		cin >> n; 	}      //fclose(stdin);     //fclose(stdout);      return 0; }

H.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	double h,u,d,f; 	cin >> h >> u >> d >> f; 	while(h) 	{ 		f/=100.0; 		double h1 = u,u1 = u; 		int day = 1; 		while(h1-0>=eps && h1-h<=eps) 		{ 			//cout << "OK" << endl; 			h1-=d; 			//cout << fixed << setprecision(3) << h1 << endl; 			if(h1<0) break; 			u = max(0.0,u-u1*f); 			h1+=u; 			//cout << "OK" << endl; 			//cout << fixed << setprecision(3) << h1 << endl; 			day++; 		} 		if(h1-0<eps) cout << "failure on day " << day << endl; 		else cout << "success on day " << day << endl; 		 		cin >> h >> u >> d >> f; 	}      //fclose(stdin);     //fclose(stdout);      return 0; }


I.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	int t; 	cin >> t; 	while(t--) 	{ 		LL a,b; 		cin >> a >> b; 		if(b-a <=3) 		{ 			cout << b-a << endl; 			continue; 		} 		int step = sqrt(b-a); 		int result = step*2-1; 		result+=(b-a-step*step+step-1)/step; 		cout << result << endl; 	}      //fclose(stdin);     //fclose(stdout);      return 0; }


J.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	LL n,x; 	cin >> n; 	while(n>=1) 	{ 		if(n == 1) x = 0; 		else x = n*25; 		cout << x << "%" << endl; 		cin >> n; 	}      //fclose(stdin);     //fclose(stdout);      return 0; }


L.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	int n,m,t; 	cin >> t; 	while(t--) 	{ 		cin >> n >> m; 		m-=2; 		n-=2; 		cout << ((n+2)/3)*((m+2)/3) << endl; 	}      //fclose(stdin);     //fclose(stdout);      return 0; }

N.

import java.util.Scanner; import java.math.*; public class Main {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         while(in.hasNext())         {             int n = in.nextInt();             BigInteger s2 = BigInteger.ZERO,s3 = BigInteger.ZERO,s4 = BigInteger.ZERO,p = BigInteger.ZERO,r2,r3,r4;             for (int i = 1;i<=n;i++)             {                 p = p.add(BigInteger.valueOf(i));                 s2 = s2.add(BigInteger.valueOf(i*i));                 s3 = s3.add(BigInteger.valueOf(i*i*i));                 s4 = s4.add(BigInteger.valueOf(i*i*i*i));             }             r2 = p.pow(2).subtract(s2);             r3 = p.pow(3).subtract(s3);             r4 = p.pow(4).subtract(s4);             System.out.println(s2+" "+r2+" "+s3+" "+r3+" "+s4+" "+r4);         }     }      }

O.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	int y; 	cin >> y; 	while(y) 	{ 		y = y-y%10; 		int s = y-1960; 		s/=10;s+=2; 		int t = 1; 		for (int i = 1;i<=s;i++)t*=2; 		//cout << t << endl; 		int result = 1; 		double x = 0; 		x+=log(result); 		while(log(2)*t-x>=eps) 		{ 			result++; 			x+=log(result); 		} 		cout << result-1 << endl; 		cin >> y; 	}      //fclose(stdin);     //fclose(stdout);      return 0; }


P.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	int n,m; 	while(cin >> n >>m) 	{ 		if(n>=m)swap(m,n); 		cout << m*n-1 << endl; 	}      //fclose(stdin);     //fclose(stdout);      return 0; }


Q.

#include <iostream> #include <stdio.h> #include <fstream> #include <iomanip> #include <cmath> #include <string> #include <string.h> #include <sstream> #include <cctype> #include <climits> #include <set> #include <map> #include <queue> #include <vector> #include <iterator> #include <algorithm> #include <stack> #include <functional> /*int类型最大值INT_MAX,short最大值为SHORT_MAX long long最大值为LONG_LONG_MAX*/ //cout << "OK" << endl; #define _clr(x) memset(x,0,sizeof(x)) using namespace std; const int INF = INT_MAX; const double eps = 1e-8; const double EULER = 0.577215664901532860; const double PI = 3.1415926535897932384626; const double E = 2.71828182845904523536028; typedef long long LL;  int main() {     //freopen("sample.in", "r", stdin); 	//freopen("sample.out", "w", stdout); 	 	int t; 	cin >> t; 	while(t--) 	{ 		 		int n; 		cin >> n; 		double a0,a1 = 0,an = 0,b,c[3020] = {0}; 		cin >> a0 >> b; 		for(int i = 1;i<=n;i++)cin >> c[i]; 		an+=n*b+a0; 		for(int i = 1;i<=n;i++) an-=2*i*c[i]; 		an/=(n+1); 		a1=a0+b-an; 		for(int i = 1;i<=n;i++) a1-=2*c[i]; 		cout << fixed << setprecision(2) << a1 << endl; 		if(t != 0) cout << endl; 	}      //fclose(stdin);     //fclose(stdout);      return 0; }
 

  • 点赞
  • 收藏
  • 分享

    • 文章举报

小学期acm训练第一发(简单数学题) 小学期acm训练第一发(简单数学题)
萌萌哒黑大帅
发布了31 篇原创文章 · 获赞 0 · 访问量 1万+

私信 关注

原文始发于:小学期acm训练第一发(简单数学题)

主题测试文章,只做测试使用。发布者:sys234,转转请注明出处:http://www.cxybcw.com/93702.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code