北京理工大学2019年计算机学院小学期程序设计方法与实践 - 热身赛题解

Author： xzm2019
发布时间：August 15, 2019
2784views
No comments
3530字数
Categories：算法

## Problem A. A + B Problem

I don't know I need to say what. But I know there are many teams using `BigInteger`. They get `Time Limit Exceeded` and some people get `Wrong Answer` or `Runtime Error` because they didn't deal negative numbers well.

However, $-10^{18} \leq a,b \leq 10^{18}$, which means $-2 \times 10^{18} \leq a + b \leq 2 * 10^{18}$. That's ok for `long long`.

```cpp
#include <bits/stdc++.h>

using namespace std;

int main() {
    long long a, b;
    while (scanf("%lld%lld", &a, &b) == 2)
        printf("%lld\n", a + b);
}
```

## Problem B. 谁是助教

何(he)金(jin)岷(min) 和 马(ma)泽(ze)航(hang)是你们的助教。请认准哦，一开始题面的确有一点点表述的不太清楚，没有说明白是按照姓名的顺序输出。

本题主要是为了测试`Special Judge`在oj的正常使用。

```cpp
#include <bits/stdc++.h>
using namespace std;

int ans1[3], ans2[3];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		if (s == "he") ans1[0] = i;
		if (s == "jin") ans1[1] = i;
		if (s == "min") ans1[2] = i;
		if (s == "ma") ans2[0] = i;
		if (s == "ze") ans2[1] = i;
		if (s == "hang") ans2[2] = i;
	}
	bool flag = true;
	for (int i = 0; i < 3; i++) 
		if (!ans1[i]) flag = false;
	if (flag)
		return printf("3\n%d %d %d\n",ans1[0],ans1[1],ans1[2]),0;
	flag = true;
	for (int i = 0; i < 3; i++) 
		if (!ans2[i]) flag = false;
	if (flag)
		return printf("3\n%d %d %d\n",ans2[0],ans2[1],ans2[2]),0;
	return printf("-1\n"), 0;
}

```

## Problem C. 助教的麻将

原题解：

> 显而易见就是在一个空间里面尽可能装长度为 $3$ 的金条，然后再将剩下的空间装满长度为 $2$ 的金条就可以了。然后特判一下剩余空间仅为 $1 \times 1 \times 1$ 时，可以抽出一根长度为 $3$ 的放下两根长度为 $2$ 的。显然这种情况更优。
再考虑箱子大小只有 $1 \times 1 \times 1$ 时无法塞下金条就可以了。

然而忘记考虑在 $5 \times 5 \times 2$ 的情况下，最优解其实可以螺旋摆放的，放$16$根 $1 \times 3$ 的然后在中间插入一根 $1 \times 2$ 的，这样总价值是$83$。 然而原来的方法总价值是$82$。

注意多考虑这种情况即可。

本题经过rejudge以后，有$8$个提交由`Accepted`变为了`Wrong Answer`，同时有$3$个提交从`Wrong Answer`变为了`Accepted`。

PS：由于这一题实际最后通过人数并不多，助教~~就不~~想默默的改正式赛的题了。

```cpp
void solve()
{
	ll all = 1ll*a*b*c;
	if( a == 1 && b == 1 && c == 1 ){
		printf("0\n");
		return;
	}
	if( a%3 == 0 || b%3 == 0 || c%3 == 0 ){
		printf("%lld\n", all/3*5);
	}
	else if( a%3 == 1 && b%3 == 1 && c%3 == 1 ){
		printf("%lld\n", (all/3-1)*5+6); 
	}
	else if( a%3 == 2 && b%3 == 2 && c%3 == 2 ){
	    if( a+b+c >= 12 ) printf("%lld\n", (all-50)/3*5+83);
		else printf("%lld\n", (all/3-2)*5+12);
	}
	else if( all%3 == 1 ){
		printf("%lld\n", (all/3-1)*5+6);
	}else{
		printf("%lld\n", all/3*5+3);
	}
}
```

## Problem D. 助教的血流成河

大！模！拟！

蛮力法作为程序设计中最经典也是最古老的的一种算法，为什么大家都不想去接触呢？

这里有很多的方法判断胡牌。单纯的谈心在清一色的情况下可能要考虑很多，希望大家可以考虑如何使用别的姿势判断胡牌，拓展题目：[Jongmah](http://codeforces.com/contest/1110/problem/D)
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
#define PI acos(-1)
#define eps 1e-9
#define mp(x,y) make_pair(x,y)
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
#define LOCAL
char s[30];
int cnt[3][10], tmp[3][10], tmp2[3][10];
int qingyise;
int yitiaolong;
int anqidui;
int longqidui;
int duiduihu;
int pinghu;
int gen;
int jiang;
void init(){
	memset( cnt, 0, sizeof( cnt ));
	pinghu = 0;
	qingyise = 0;
	yitiaolong = 0;
	anqidui = 0;
	longqidui = 0;
	duiduihu = 0;
	gen = 0;
	jiang = 0;
}
void check_anqidui(){
	for(int i = 0; i < 3; i++ ){
		for(int j = 1; j < 10; j++ ){
			if( cnt[i][j] ){
				if( cnt[i][j] != 2 && cnt[i][j] != 4 ){
					anqidui = 0;
					return;
				}
			}
		}
	}
	anqidui = 1;
}
void check_longqidui(){
	for(int i = 0; i < 3; i++ ){
		for(int j = 1; j <= 9; j++ ){
			if( cnt[i][j] == 4 ){
				longqidui = 1;
				return;
			}
		}
	}
}
bool check( ){
	memcpy( tmp2, tmp, sizeof(tmp) );
	int count = 4;
	// for(int i = 0; i < 3; i++ ){
	// 	for(int j = 1; j < 10; j++ ){
	// 		printf("%d ", tmp2[i][j]);
	// 	}
	// 	printf("\n");
	// }
	for(int i = 0; i < 3; i++ ){
		for(int j = 1; j <= 9; j++ ){
			if( tmp2[i][j] >= 3 ){
				tmp2[i][j] -= 3;
				count--;
			}
			while( tmp2[i][j] && j <= 7 ){
				if( !tmp2[i][j+1] || !tmp2[i][j+2] ) return 0;
				tmp2[i][j]--;
				tmp2[i][j+1]--;
				tmp2[i][j+2]--;
				count--;
			}
		}
	}
	// for(int i = 0; i < 3; i++ ){
	// 	for(int j = 1; j < 10; j++ ){
	// 		printf("%d ", tmp2[i][j]);
	// 	}
	// 	printf("\n");
	// }
	// printf("%d\n", count);
	if( count == 0 ) return 1;
	else return 0;
}
void check_duiduihu( int jian ){
	for(int i = 0; i < 3; i++ ){
		for(int j = 1; j < 10; j++ ){
			if( cnt[i][j] ){
				if( jian == i*10+j ){
					if( cnt[i][j] > 2 ){
						duiduihu = 0;
						return;
					}
				}else if( cnt[i][j] <= 2 ){
					duiduihu = 0;
					return;
				}
			}
		}
	}
	duiduihu = 1;
}
void check_pinghu(){
	memcpy( tmp, cnt, sizeof(tmp));
	for(int i = 0; i < 3; i++ ){
		for(int j = 1; j < 10; j++ ){
			if( tmp[i][j] >= 2 ){
				tmp[i][j] -= 2;
				if( check() ){
					// printf("####\n");
					pinghu = 1;
					// printf("pinghu %d %d\n", pinghu, &pinghu);
					if( !jiang ) jiang = i*10+j;
					check_duiduihu( i*10+j );
					if( duiduihu ){
						jiang = i*10+j;
						return;
					}
				}
				tmp[i][j] += 2;
			}
		}
	}
}
void check_qingyise(){
	int count = 0;
	for(int i = 0; i < 3; i++ ){
		count += cnt[i][0];
	}
	if( count == 1 ) qingyise = 1;
}
void check_yitiaolong(){
	for(int i = 0; i < 3; i++ ){
		int flag = 1;
		for(int j = 1; j <= 9; j++ ){
			if( !cnt[i][j] ){
				flag = 0;
				break;
			}
		}
		if( flag ){
			yitiaolong = 1;
			return;
		}
	}
}
void count_gen(){
	for(int i = 0; i < 3; i++ ){
		for(int j = 1; j <= 9; j++ ){
			if( cnt[i][j] == 4 ){
				gen++;
			}
		}
	}
	if( longqidui ) gen--;
}
void print_anqidui(){
	char huase;
	for(int i = 0; i < 3; i++ ){
		if( i == 0 ) huase = 'm';
		else if( i == 1 ) huase = 'p';
		else huase = 't';
		for(int j = 1; j <= 9; j++ ){
			while( cnt[i][j] ){
				printf("%d%c%d%c\n", j, huase, j, huase );
				cnt[i][j] -= 2;
			}
		}
	}
}
void print_pinghu(){
	char huase;
	for(int i = 0; i < 3; i++ ){
		for(int j = 1; j <= 9; j++ ){
			if( jiang == i*10+j ) cnt[i][j] -= 2;
			if( i == 0 ) huase = 'm';
			else if( i == 1 ) huase = 'p';
			else huase = 't';
			while( cnt[i][j] >= 3 ){
				printf("%d%c%d%c%d%c\n", j, huase, j, huase, j, huase );
				cnt[i][j] -= 3;
			}
			while( cnt[i][j] ){
				printf("%d%c%d%c%d%c\n", j, huase, j+1, huase, j+2, huase );
				cnt[i][j]--;
				cnt[i][j+1]--;
				cnt[i][j+2]--;
			}
		}
	}
	int op = jiang/10;
	if( op == 0 ) huase = 'm';
	else if( op == 1 ) huase = 'p';
	else huase = 't';
	int num = jiang%10;
	printf("%d%c%d%c\n", num, huase, num, huase );
}
void get_ans(){
	int ans;
	int op;
	if( qingyise && longqidui ) {ans = 32; op = 1;}
	else if( qingyise && anqidui ) {ans = 16; op = 2;}
	else if( qingyise && yitiaolong ) {ans = 8; op = 3;}
	else if( longqidui ) {ans = 8; op = 4;}
	else if( qingyise && duiduihu ) {ans = 8; op = 5;}
	else if( qingyise ) {ans = 4; op = 6;}
	else if( anqidui ) {ans = 4; op = 7;}
	else if( yitiaolong ) {ans = 2; op = 8;}
	else if( duiduihu ) {ans = 2; op = 9;}
	else {ans = 1; op = 10;}
	while( gen-- ) ans *= 2;
	if( anqidui ) print_anqidui();
	else print_pinghu();
	if( op == 1 ) printf("QingLongQiDui");
	else if( op == 2 ) printf("QingQiDui");
	else if( op == 3 ) printf("QingYiSeYiTiaoLong");
	else if( op == 4 ) printf("LongQiDui");
	else if( op == 5 ) printf("QingYiSeDuiDuiHu");
	else if( op == 6 ) printf("QingYiSe");
	else if( op == 7 ) printf("AnQiDui");
	else if( op == 8 ) printf("YiTiaoLong");
	else if( op == 9 ) printf("DuiDuiHu");
	else if( op == 10 ) printf("PingHu");
	printf(" *%d\n", ans);
}
void solve()
{
	char huase;
	int num;
	init();
	for(int i = 0; i < 28; i += 2 ){
		num = s[i]-'0';
		huase = s[i+1];
		// printf("%d%c\n", num, huase);
		if( huase == 'm' ){
			cnt[0][0] = 1;
			cnt[0][num] ++;
		}else if( huase == 'p' ){
			cnt[1][0] = 1;
			cnt[1][num]++;
		}else{
			cnt[2][0] = 1;
			cnt[2][num]++;
		}
	}
	if( cnt[0][0] && cnt[1][0] && cnt[2][0] ){
		printf("ZhaHu\nHuaZhu\n");
		return;
	}
	check_anqidui();
	if( !anqidui ) check_pinghu();
	else check_longqidui();
	// printf("pinghu %d %d\nanqidui %d\n", pinghu, &pinghu, anqidui);
	if( !pinghu && !anqidui ){
		printf("ZhaHu\n");
		return;
	}
	check_qingyise();
	check_yitiaolong();
	count_gen();
	get_ans();
}
int main(int argc, char * argv[]) 
{
    #ifdef LOCAL
    //freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    #endif
	while( ~scanf("%s", s) ){
		solve();
	}
    return 0;
}
```

Last modification：August 14th, 2019 at 11:57 pm

If you think my article is useful to you, please feel free to appreciate

Comment *

私密评论

Name *

Email *

Site

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 热身赛题解

xzm2019 • 2019 年 08 月 15 日

## Problem A. A + B Problem

However, $-10^{18} \leq a,b \leq 10^{18}$, which means $-2 \times 10^{18} \leq a + b \leq 2 * 10^{18}$. That's ok for `long long`.

```cpp
#include <bits/stdc++.h>

using namespace std;

int main() {
    long long a, b;
    while (scanf("%lld%lld", &a, &b) == 2)
        printf("%lld\n", a + b);
}
```

## Problem B. 谁是助教

何(he)金(jin)岷(min) 和 马(ma)泽(ze)航(hang)是你们的助教。请认准哦，一开始题面的确有一点点表述的不太清楚，没有说明白是按照姓名的顺序输出。

本题主要是为了测试`Special Judge`在oj的正常使用。

```cpp
#include <bits/stdc++.h>
using namespace std;

```

## Problem C. 助教的麻将

原题解：

注意多考虑这种情况即可。

本题经过rejudge以后，有$8$个提交由`Accepted`变为了`Wrong Answer`，同时有$3$个提交从`Wrong Answer`变为了`Accepted`。

PS：由于这一题实际最后通过人数并不多，助教~~就不~~想默默的改正式赛的题了。

## Problem D. 助教的血流成河

大！模！拟！

蛮力法作为程序设计中最经典也是最古老的的一种算法，为什么大家都不想去接触呢？

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 热身赛题解

Leave a Comment

2019南昌邀请赛网络赛个人记录（附官方题解）

北京理工大学第七届程序设计新生赛题解（unofficial）

第 43 届 ACM/ICPC 亚洲区域赛（南京）总结

北京理工大学第八届程序设计新生赛题解

Beijing Institute of Technology 2019.6 Monthly Contest 题解

2019 西安邀请赛D Miku and Generals

BITSS 2018 寒假集训算法总结赛题解（Unofficial）

OI~XCPC流水账

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 热身赛题解

北京理工大学第八届程序设计新生赛题解

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 热身赛题解

Leave a Comment

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 热身赛 题解

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 热身赛题解