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

Author： xzm2019
发布时间：August 18, 2019
3423views
No comments
1165字数
Categories：算法

## Problem A. 日麻计算器

- 当$x > 4$的时候，直接输出对应答案
- 当$x \leq 4$时，按照题目公式去计算，和$12\,000$取`max`。注意$z$向上保留到整百的一个比较快的写法是$z' = (z / 100 + !!(z\ \%\ 100)) \times 100$。

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

int main()
{
    int T;
    scanf("%d", &T);
	int a,b;
	while (T--)
    {
        scanf("%d%d", &a, &b);
    	if (a >= 13) printf("48000\n");
    	else if (a >= 11) printf("36000\n");
    	else if (a >= 8) printf("24000\n");
    	else if (a >= 6) printf("18000\n");
    	else if (a == 5) printf("12000\n");
    	else
    	{
    		int t = (1 << (2 + a)) * 6 * b;
    		t = (t / 100 + !!(t % 100)) * 100;
    		printf("%d\n",min(t,12000));
    	}
    }
    return 0;
}
```

## Problem B. 麻将桌绘制

由于$w \times h$最大为$40\,000$，我们可以暴力的判断每一个点是否符合以下两个条件之一。

- 对于圆形，直接带入圆的公式$(x - x_C)^2 + (y-y_C)^2 \leq r^2$即符合条件。
- 对于矩形，我们先通过题目中的两个点判断出$x$和$y$的合法上下界，对于每个点直接判断。

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

int main()
{
	int w,h,xc,yc,r,x1,x2,y1,y2,xmin,xmax,ymin,ymax;
	cin >> w >> h >> xc >> yc >> r >> x1 >> y1 >> x2 >> y2;
	if (y1 < y2)
	{
		xmin = x1; xmax = x1 + y2 - y1;
		ymin = y1; ymax = y2;
	}
	if (y1 > y2)
	{
		xmin = x2 - y1 + y2; xmax = x2;
		ymin = y2; ymax = y1;
	}
	if (x1 < x2)
	{
		xmin = x1; xmax = x2;
		ymin = y2 - x2 + x1; ymax = y1;
	}
	if (x1 > x2)
	{
		xmin = x2; xmax = x1;
		ymin = y1; ymax = y1 + x1 - x2;
	}
	assert(xmax - xmin == ymax - ymin && xmax > xmin && ymax > ymin);
	for (int i = 0; i < w; i++)
	{
		for (int j = 0; j < h; j++)
		{
			bool flag = false;
			flag = flag || ((i - xc) * (i - xc) + (j - yc) * (j - yc) <= r * r);
			flag = flag || ((xmin <= i && i <= xmax) && (ymin <= j && j <= ymax));
			if (flag) printf("/"); else printf("\\");
		}
		printf("\n");
	}
	return 0;
}
```

## Problem C. 雀士分麻将

### Solution A: 贪心

本题可以直接贪心的来做，正着按照题目要求扫一遍，然后反着用上一次的数据扫一遍取`max`即可。注意最后答案可能会超出`int`的范围。

```cpp
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll

const int INF = 0x3f3f3f3f;
const int MAXN = 100000+10;
int n;
int a[MAXN];
int b[MAXN];
void solve()
{
	a[0] = a[n+1] = INF;
	for(int i = 1; i <= n; i++ ){
		b[i] = 1;
	}
	for(int i = 1; i <= n; i++ ){
		if( a[i] > a[i-1] ) b[i] = max( b[i], b[i-1]+1 );
	}
	for(int i = n; i >= 1; i-- ){
		if( a[i] > a[i+1] ) b[i] = max( b[i], b[i+1]+1 );
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++ ){
		// printf("%d\n", b[i]);
		ans += 1ll*b[i];
	}
	printf("%lld\n", ans);
}
int main(int argc, char * argv[]) 
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++ ){
		scanf("%d", &a[i]);
	}
	solve();
    return 0;
}
```

### Solution B: 图论

我们可以根据相邻两个数的大小关系建立单向边，构成有向图。将所有入度为$0$的点设置为$1$个糖果，然后`bfs`向上递增。

```cpp
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct edge{
    int to,next;
}e[100010];
int head[100010],cnt;
int I[100010];
inline void ins(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    I[v]++;
}
int n,a[100010],tot[100010];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)scanf("%d",a+i);
    for (int i=1;i<n;i++)
    {
        if (a[i]>a[i+1])ins(i+1,i);
        if (a[i]<a[i+1])ins(i,i+1);
    }
    ll ans=0;
    queue<int>q;while (!q.empty())q.pop();
    for (int i=1;i<=n;i++)if (!I[i])q.push(i),ans+=(tot[i]=1);
    while(!q.empty())
    {
        int now=q.front(),d=tot[now]+1;q.pop();
        for (int i=head[now];i;i=e[i].next)
        {
            tot[e[i].to]=max(tot[e[i].to],d);
            I[e[i].to]--;
            if (!I[e[i].to])q.push(e[i].to),ans+=tot[e[i].to];
        }
    }
    printf("%lld\n",ans);
    return 0;
}
```

## Problem D. 牌河N对子

> 求给定的字符串有多少非空子序列，满足其是一个串加其本身。

由于$N \leq 200$，因此我们只需要$O(N^3)$的时间复杂度即可。

符合条件的子序列的第二部分可以从整个字符串的$s_1, s_2, \cdots, s_{|s| - 1}$开始，我们枚举这个起点$i$。

这样我们把字符串分割为两个部分$s[0:i]$和$s[i + 1: |s| - 1]$。

我们只需要求出其公共子序列的方案数即可，同时再减去$s[0:i]$和$s[i + 2: |s| - 1]$的公共子序列的方案数，就是该点的贡献。

求公共子序列的方案数可以在$O(n^2)$的时间复杂度内解决完毕，加上枚举分割点，整体时间复杂度为$O(n^3)$。

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

const int maxn = 210;
const int mod = 1000000007;

int ans[maxn][maxn];
int res, n;
char ss[maxn];

int work(int l) {
	memset(ans, 0, sizeof(ans));
	int n1 = l, n2 = n - l - 1;
	for(int i=1; i<=n1; ++i)
		ans[i][0] = ans[i-1][0] + (ss[i-1] == ss[l] ? 1 : 0);
	for(int i=1; i<=n1; ++i)
		for(int j=1; j<=n2; ++j) {
			ans[i][j] = (ans[i][j-1] + ans[i-1][j])%mod;
			if(ss[i-1] != ss[l+j])
				ans[i][j] = (ans[i][j] - ans[i-1][j-1] + mod)%mod;
		}
	return ans[n1][n2];
}
void solve() {
	res = 0;
	n = strlen(ss);
	for(int i=1; i<n; ++i)
		res = (res + work(i))%mod;
    printf("%d\n", res);
}
int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		scanf("%s", ss);
		solve();
	}
}
```

## Problem E. 牌墙的深坑

将矩阵周边的格子都放到堆里，这些格子上面是无法盛水的。

每次在堆里挑出一个高度最小的格子 cell，把周围的格子加入到堆里。

这些格子被加入堆的时候，计算他们上面的盛水量。

盛水量 = cell.height - 这个格子的高度

当然如果这个值是负数，盛水量就等于 0。

堆我们可以使用优先队列进行实现。

```cpp
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int h[MAXN][MAXN];
int vis[MAXN][MAXN];
int n, m;

struct node{
	int x, y;
	int height;
	node(){}
	node( int x, int y, int height): x(x), y(y), height(height) {}
};
struct cmp{
	bool operator()( node a, node b ){
		return a.height > b.height;
	}
};
priority_queue<node, vector<node>, cmp> q;
void solve()
{
	for(int i = 1; i <= n; i++ ){
		vis[i][1] = vis[i][m] = 1;
		q.push( node( i, 1, h[i][1]) );
		q.push( node( i, m, h[i][m]) );
	}
	for(int j = 2; j < m; j++ ){
		vis[1][j] = vis[n][j] = 1;
		q.push( node( 1, j, h[1][j]) );
		q.push( node( n, j, h[n][j]) );
	}
	ll ans = 0;
	while( !q.empty() ){
		node now = q.top();
		q.pop();
		int hh = now.height;
		for(int i = 0; i < 4; i++ ){
			int x = now.x+dx[i];
			int y = now.y+dy[i];
			if( x < 1 || x > n || y < 1 || y > m ) continue;
			if( vis[x][y] ) continue;
			vis[x][y] = 1;
			if( hh > h[x][y] ){
				ans += 1ll*(hh-h[x][y]);
				h[x][y] = hh;
			}
			q.push( node( x, y, h[x][y]) );
		}
	}
	printf("%lld\n", ans);
}
int main(int argc, char * argv[])
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++ ){
		for(int j = 1; j <= m; j++ ){
			scanf("%d", &h[i][j]);
		}
	}
	solve();
    return 0;
}
```

## Problem F. 麻将大乱斗

如果$k$含有$2,3,5,7$之外的质因数，答案一定为$0$。

否则问题变成数位之积中恰好有若干个$2,3,5,7$质因子。

直接需要数位dp需要五维状态，如果处理不当，可能会`MLE`。

考虑到可能出现的乘积不会很多，使用`map`或`unordered_map`维护即可。

注意最后输出总积分数时**不用**取模！

bonus：如果这题改为$n \leq 10\,000$，应该怎么做？

```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
int dp[105][66666];
ll k;
char A[105], B[105];
int a[105];
inline int get(ll x)
{
    static unordered_map<ll, int> dic;
    static int sz = 0;
    if (dic.count(x)) return dic[x];
    return dic[x] = sz++;
}
int dfs(int pos, ll mul, int lead, int flag)
{
    if (mul == 0) return 0;
    if (pos == -1) return mul == 1;
    int h = get(mul);
    if (!flag && !lead && ~dp[pos][h]) return dp[pos][h];
    int sum = 0;
    int up = flag ? a[pos] : 9;
    for (int i = 0; i <= up; i++)
    {
        if (i == 0 && !lead) continue;
        if (i == 0)
            sum += dfs(pos - 1, mul, lead && i == 0, flag && i == a[pos]);
        else if (mul % i == 0)
            sum += dfs(pos - 1, mul / i, lead && i == 0, flag && i == a[pos]);
        if (sum >= MOD) sum -= MOD;
    }
    if (!flag && !lead) dp[pos][h] = sum;
    return sum;
}
int solve(char* c)
{
    int len = strlen(c);
    int pos = 0;
    for (int i = 0; i < len; i++)
        a[pos++] = c[len - 1 - i] - '0';
    return dfs(pos - 1, k, 1, 1);
}
void _minus(char* c)
{
    int len = strlen(c);
    reverse(c, c + len);
    //	cout << c << endl;
    int flag = 1, len1 = 1;
    for (int i = 0; i < len; i++)
    {
        if (flag)
            if (c[i] == '0')
                c[i] = '9';
            else
                c[i]--, flag = 0;
        if (c[i] != '0') len1 = i + 1;
    }
    //	cout << "LEN: "<<len1 << endl;
    reverse(c, c + len1);
    c[len1] = '\0';
}
int fac[] = {2, 3, 5, 7};
int main()
{
    memset(dp, -1, sizeof(dp));
    int T;
    scanf("%d", &T);
	long long TT = 0;
    while (T--)
    {
        scanf("%s%s%lld", A, B, &k);
        ll K = k;
        for (int i = 0; i < 4; i++)
            while (K % fac[i] == 0) K /= fac[i];
        if (K != 1)
        {
            printf("0\n");
            continue;
        }
        _minus(A);
        int ans = solve(B) - solve(A);
        if (ans < 0) ans += MOD;
        printf("%d\n", ans);
		TT += ans;
    }
	cout << TT << endl;
}
```

Last modification：August 18th, 2019 at 01:26 pm

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

Comment *

私密评论

Name *

Email *

Site

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

xzm2019 • 2019 年 08 月 18 日

## Problem A. 日麻计算器

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

## Problem B. 麻将桌绘制

由于$w \times h$最大为$40\,000$，我们可以暴力的判断每一个点是否符合以下两个条件之一。

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

## Problem C. 雀士分麻将

### Solution A: 贪心

本题可以直接贪心的来做，正着按照题目要求扫一遍，然后反着用上一次的数据扫一遍取`max`即可。注意最后答案可能会超出`int`的范围。

```cpp
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll

### Solution B: 图论

我们可以根据相邻两个数的大小关系建立单向边，构成有向图。将所有入度为$0$的点设置为$1$个糖果，然后`bfs`向上递增。

## Problem D. 牌河N对子

> 求给定的字符串有多少非空子序列，满足其是一个串加其本身。

由于$N \leq 200$，因此我们只需要$O(N^3)$的时间复杂度即可。

符合条件的子序列的第二部分可以从整个字符串的$s_1, s_2, \cdots, s_{|s| - 1}$开始，我们枚举这个起点$i$。

这样我们把字符串分割为两个部分$s[0:i]$和$s[i + 1: |s| - 1]$。

我们只需要求出其公共子序列的方案数即可，同时再减去$s[0:i]$和$s[i + 2: |s| - 1]$的公共子序列的方案数，就是该点的贡献。

求公共子序列的方案数可以在$O(n^2)$的时间复杂度内解决完毕，加上枚举分割点，整体时间复杂度为$O(n^3)$。

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

const int maxn = 210;
const int mod = 1000000007;

int ans[maxn][maxn];
int res, n;
char ss[maxn];

## Problem E. 牌墙的深坑

将矩阵周边的格子都放到堆里，这些格子上面是无法盛水的。

每次在堆里挑出一个高度最小的格子 cell，把周围的格子加入到堆里。

这些格子被加入堆的时候，计算他们上面的盛水量。

盛水量 = cell.height - 这个格子的高度

当然如果这个值是负数，盛水量就等于 0。

堆我们可以使用优先队列进行实现。

```cpp
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int h[MAXN][MAXN];
int vis[MAXN][MAXN];
int n, m;

## Problem F. 麻将大乱斗

如果$k$含有$2,3,5,7$之外的质因数，答案一定为$0$。

否则问题变成数位之积中恰好有若干个$2,3,5,7$质因子。

直接需要数位dp需要五维状态，如果处理不当，可能会`MLE`。

考虑到可能出现的乘积不会很多，使用`map`或`unordered_map`维护即可。

注意最后输出总积分数时**不用**取模！

bonus：如果这题改为$n \leq 10\,000$，应该怎么做？

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

Leave a Comment

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

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

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

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

Beijing Institute of Technology 2019.6 Monthly Contest 题解

第十三届北邮校赛（2019）个人存档

HQ Trivia UK 20180914 9pm BST 题目瞎扯

【转】Prufer codes与Generalized Cayley's Formula

lintcode 384. 最长无重复字符的子串

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

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

Leave a Comment

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

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