挖土机周赛R1

比赛地址：http://acm.mangata.ltd/contest/65ab7517b13e94c4785969f9

T1 A+B=B

思路

先将字母转化为对应的数字，很显然(0->A、1->B、2->C ……)

因为字母只有A~J，说明加法最多是两位长度，那么分类输出一下即可

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    char a, b;
    cin >> a >> b;
    int ans = (a - 'A') + (b - 'A');
    if (ans < 10)
        cout << (char)('A' + ans);
    else
        cout << (char)('A' + ans / 10)
             << (char)('A' + ans % 10);
    return 0;
}

T2 ABBA

思路

一个简单的数学分类讨论

为了分类简单，我们假设A是较小的那一个（如果 B 小的话我们就交换，并且进行标记方便后续输出答案，如果A和B相等，那也不用比较了）

比较 $a^b$ 和 $b^a$ 大小的话我们判断 $\frac{a^b}{b^a}$ 的大小即可，于是我们构造函数 $f(x) = \frac{a^x}{x^a} （X>0）$ ，于是问题转变为了研究 $f(x)$ 在区间 $[a,∞]$ 的单调性

$$f'(x) = \frac{a^x \times ln_a \times x^a - a^x \times ax^{a-1}}{x^{2a}} \\ =\frac{a^x\times x^{a-1} (xln_a-a)}{x^{2a}} \\ = \frac{a^x\times x^{a-1} \times ln_a(x-\frac{a}{ln_a})}{x^{2a}} $$

1. 当 $0<a<1$ 时，因为 $ln(a) < 0$ ，所以 $f'(x) < 0$ ，所以 $f(x)$ 在区间 $[a,∞]$ 内是减函数，所以 $f(a) > f(b)$ ，即 $\frac{a^a}{a^a} > \frac{a^b}{b^a}$ ，即 $\frac{a^b}{b^a} < 1$ ，所以 $a^b<b^a$ (实际上数据 a,b>=1，可以忽略这一条)

2. 当 $a = 1$ 时，如果 $b = 1$ ，则 $a^b = b^a$ ，否则 $a^b < b^a$

3. 当 $1<a<e$ 时，因为 $0<ln_a<1$ ，所以 $\frac{1}{ln_a} > 1$ ，所以 $\frac{a}{ln_a}$ ，所以当 $a<x<\frac{a}{ln_a}$ 时， $f'(x) < 0$ 。当 $x>\frac{a}{ln_a}$ 时，$f'(x) > 0$ ，所以 $f(x)$ 在区间 $[a,\frac{a}{ln_a}]$ 内是递减的，在 $[\frac{a}{ln_a}, +∞]$ 区间内是递增的。但是我们不用考虑太多，因为 $a$ 是整数，那么 $a = 2$ 的情况单独列一下即可，即当 $b < 4$ ，则 $a^b < b^a$ ，如果 $b = 4$ 则 $a^b = b^a$ ，如果 $b > 4$ 则 $a^b > b^a$

4. 当 $a>=e$ 时，因为 $ln(a) >= 1$ ，所以 $0<=\frac{1}{ln_a}<=1$ ，$0<\frac{a}{ln_a} <= a$ ，所以当 $x > a$ 时 $f'(x) > 0$ 即 $f(x)$ 在区间 $[a,+∞]$ 内是增函数，所以 $f(a) < f(b)$ 即 $a^b>b^a$

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
	int a, b;
	bool fg = false;
	int ans;//0 表示 a^b > b^a ; 1 表示 a^b < b^a; -1 表示 a^b = b^a
	cin >> a >> b;
	if (a == b) {
		ans = -1;
	} else {
		if (a > b) {
			swap(a, b);
			fg = true;
		}
		if (a == 1) {
			ans = 1;
		} else if (a == 2) {
			if (b < 4)
				ans = 1;
			else if (b == 4)
				ans = -1;
			else
				ans = 0;
		} else {
			ans = 0;
		}
	}
	if (fg)
		ans = !ans;
	if (ans == -1)
		cout << "same" << endl;
	else if (ans == 0)
		cout << "first" << endl;
	else
		cout << "second" << endl;
	return 0;
}

T3 环状字符串

思路

简单一点的思路就是循环去模拟，但是我们其实可以直接计算出环开始的位置的

假设环的长度为 $len$ ，需要我们输出的是 第 $n$ 个字符开始的长度为 $m$ 的子串（字符串是环形），那么我们不难知道子串开始的位置为 $(n-1) \% (len)$ ，然后循环 $m$ 次去取子串即可（注意这里的子串长度可能是环的几倍）

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	int n,m;
	cin >> s;
	cin >> n >> m;
	int len = s.length();
	int start = (n - 1) % len;
	int idx = 0;
	while(idx < m) {
		cout<<s[start];
		++start;
		if (start == len) 
			start = 0;
		++idx;
	}
	cout<<endl;
	return 0;
}

有个偷懒的写法（会占用较多空间）：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s, t;
    int n, m;
    cin >> s;
    cin >> n >> m;
    t = "";
    while (t.length() < n + m - 1)
        t += s;
    for (int i = n; i <= n + m - 1; i++)
        cout << t[i - 1];
    return 0;
}

T4 照明

思路

读入地图后扫描所有的* 即灯塔位置，然后从四个方向去扫描，碰到墙 # 前，每到一个. 空地就进行标记，最后统计一下所有的标记点和灯塔的数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
char g[35][35];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int main()
{
    cin >> n;
    memset(g, '#', sizeof(g));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (g[i][j] == '*')
            {
                for (int k = 0; k < 4; k++)
                {
                    int x = i;
                    int y = j;
                    while (g[x][y] != '#')
                    {
                        if (g[x][y] == '.')
                            g[x][y] = 'o';
                        x += dx[k];
                        y += dy[k];
                    }
                }
            }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (g[i][j] == 'o' || g[i][j] == '*')
                ans++;
    cout << ans << "\n";
    return 0;
}

T5 算法提高 邮票面值设计

思路

我们深搜枚举第 $i$ 张邮票的价格为 $i\_value$ ，显然我们应该从 $dfs(1,1)$ 开始，因为我们必须要一张 $1$ 分的邮票作为开始

• 那我们思考这个dfs的出口在哪，如果说我们第 $i$ 张邮票的位置大于种类 $k$ 那就说明超出预算种类了

• 现在出口找到了，我们就要思考数据更新的问题了，这里我们假设有一个函数 $dp(x)$ 可以算出当前的 $val$ 列表能得到的连续最大面值，又由于 $val$ 列表是递增的，所以我们能推断出下一个位置 $i+1$ 的 $val[i+1]$ 的值应该是 $[val[i]+1,dp[i] + 1]$ 这个区间范围内的。

• 现在我们来处理函数 $dp(x)$ ，我们设 $f(x)$ 为面值为 $x$ 的最少邮票组成数量，初始条件显然是 $f[0] = 0,f[1] = 1$ ，其余 $f[x]$则为 INF 。 $f[x]$ 的状态只能通过 $f[x - val[i]]$ 和 $f[x]$ 推断过来，于是状态转移方程则为： $f[x] = min(f[x],f[x-val[i]])$ ， $x$ 的范围为： $[2,n\times val[len(val)]]$ ， $i$ 的范围则是 $[1,len(val)]$

代码

#include<bits/stdc++.h>
 
using namespace std;
 
int n, k, ans = 0;
int val[15];//面值表,长度k,from 1
int result[15];//最大面值的表
 
int dp(int len) {
    //由当前面值表得到连续最大面值
    //表长自定
    int f[200] = {0};//f[面值]=最少张数
    f[0] = 0;
    f[1] = 1;
    int this_max = 1;
    for (int i = 2; i <= (val[len] * n); ++i) {
        //面值最大值为
        ++this_max;
        f[i] = 100000;
        for (int j = 1; j <= len; ++j) {
            if ((i - val[j]) < 0) {
                break;
            }
            f[i] = min(f[i], f[i - val[j]] + 1);
        }
        if (f[i] > n) {
            --this_max;
            break;
        }
    }
 
    return this_max;
}
 
void dfs(int i, int i_value) {
    //第i个，面值i_value
    if (i > k) {
        return;
    }
 
    //更新
    val[i] = i_value;
    int now_value = dp(i);
    if (now_value > ans) {
        for (int j = 1; j <= k; ++j) {
            result[j] = val[j];
        }
        ans = now_value;
    }
 
    //子树
    for (int j = (i_value + 1); j <= (now_value + 1); ++j) {
        dfs(i + 1, j);
    }
}
 
int main() {
 
    cin >> n >> k;
    dfs(1, 1);
    for (int i = 1; i <= k; ++i) {
        cout << result[i] << ' ';
    }
    cout << endl << "MAX=" << ans;
    return 0;
}