2022安徽大学ACM实验室新生赛题解+标程

A. 灵魂之火 I

考虑每次打出灵魂之火后，如果剩余手牌内有不是灵魂之火的卡牌，那么从中选择一张弃掉是最优的，根据以上策略容易得到答案为 $\min (m,\lceil \frac{n}{2}\rceil )\times 4\backslash min(m,\backslash lceil\backslash frac\{n\}\{2\}\backslash rceil)\backslash times4$ 。

注意 C/C++ 要开 long long。

void solve()
{
	cout << min(M, (N + 1) / 2) * 4 << endl;
}

B. 灵魂之火 II

考虑期望 Dp，记 $f_{i,j}f\_\{i,j\}$ 为有 $ii$ 张手牌，其中 $jj$ 张为灵魂之火时造成伤害的期望值。如果 $j>0j>0$ ，我们会打出灵魂之火，在打出一张灵魂之火并造成 $44$ 点伤害后，此时还剩余 $i-1i-1$ 张手牌， $j-1j-1$ 张灵魂之火，此时弃掉一张灵魂之火的概率为 $p=\frac{j-1}{i-1}p=\backslash frac\{j-1\}\{i-1\}$ ，在此之后会剩余 $i-2i-2$ 张手牌和，$j-2j-2$ 张灵魂之火；未弃掉灵魂之火的概率为 $1-p1-p$ ，在此之后会剩余 $i-2i-2$ 张手牌， $j-1j-1$ 张灵魂之火。在 $i\ge 2i\backslash ge2$ 时，可以根据概率进行转移：

初始值 $f_{1,1}=4f\_\{1,1\}=4$ ，其他均为 $00$ ，对于单次询问， $f_{n,m}f\_\{n,m\}$ 即为答案。可以在 $O(nm)O(nm)$ 内Dp预处理出所有答案后再 $O(1)O(1)$ 回答每次询问，总的复杂度 $O(nm+T)O(nm+T)$ 。

#include<bits/stdc++.h>
#define N 2040
#define mod 1000000007
#define ri int
#define LL long long 
using namespace std;

int T, rev[N << 1];
int f[N][N];

int add(int a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

int mul(int a, int b) {
    return a * 1LL * b % mod;
}

int pow(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = mul(a, a)) if (b & 1) ret = mul(ret, a);
    return ret;
}

int main() {
    for (ri i = 1; i < (N << 1); i++) rev[i] = pow(i, mod - 2);
    f[0][0] = 0; f[1][0] = 4;
    for (ri i = 2; i < N; i++) f[i][0] = add(f[i][0], mul(1, add(f[i - 2][0], 4)));
    for (ri i = 1; i < N; i++)
        for (ri j = 1; j < N; j++) {
            if (i - 2 >= 0)
                f[i][j] = add(f[i][j], mul(mul(i - 1, rev[i - 1 + j]), add(f[i - 2][j], 4)));
            f[i][j] = add(f[i][j], mul(mul(j, rev[i - 1 + j]), add(f[i - 1][j - 1], 4)));
        }
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        printf("%d\n", f[m][n - m]);
    }
    return 0;
}

C. 文本转换

Tag：模拟、语言知识

1. 如何读入一整行字符串：（看看大家的信息检索能力）

   fgets(s,10240,stdin);
   

   或者使用 C++ 的 getline 也是可以的。

2. 剩下的部分就没有什么难度了：从前到后扫，扫到第奇数个 ** 就输出 \textbf{，扫到第偶数个就输出 } 即可。

3. 语言知识：C/C++ 输出 \ 要用转义字符，即输出 \\ 。

4. 本题理论上也可以用 Python 写出较为简洁的代码。

#include<bits/stdc++.h>
using namespace std;
const int N=10245;
char s[N];
int main()
{
    fgets(s,10240,stdin);
    bool f=true;
    for(int i=0;s[i];++i)
        if(s[i]=='*')
        {
            ++i;
            if(f) printf("\\textbf{");
            else printf("}");
            f^=1;
        }
        else putchar(s[i]);
}

D. 终末螺旋

根据输入的数据，可以计算出小D到达入口位置的时间，利用反三角函数（可以直接用 math.h 中的反三角函数）也可以计算出激光扫到入口位置的时间，进行计较并判断即可。本题精度要求较低，$epseps$ 不要设得太大就好。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second

using namespace std;

typedef double D;

const D pi = acos(0) * 2;
const D eps = 1e-9;

int main()
{
	int T;
	cin >> T;
	
	cout.setf(ios_base:: fixed);
	cout.precision(10);
	
	while (T --) {
	
		D x0, y0, x1, y1, w, v;
		cin >> x0 >> y0 >> x1 >> y1 >> w >> v;
				
		w = w / 180 * pi;
		//cout << w << endl;
		D t0, t1;
		t0 = sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)) / v;
		if (x1 >= 0) t1 = (pi / 2 - atan(y1 / x1)) / w;
		else t1 = (pi + pi / 2 - atan(y1 / x1)) / w; 
		
	//	cout << t0 << " " << t1 << endl;
		
		if (t0 + eps < t1) cout << "Yes" << endl;
		else cout << "No" << endl;	
	}
	
	return 0;
}

E. 三十六方

Tag：递归思想、模拟（、简单数论）

不难看出方阵的“方值”定义是以递归的方式定义的，而最终一定是将整个方阵分割成若干个相等的极小方阵。我们可以按照定义模拟，得到整个方阵最终能分割出的极小方阵的边长，然后对于子方阵的最大值求和即可。当然，你也可以直接看出这个极小的边长实际上就是 $nn$ 的最大质因子。

#include<bits/stdc++.h>
using namespace std;
const int N=2022+5;
int h[N][N],n;
int solve(int x, int y, int d)
{
    int mx=-1;
    for(int i=x;i<=x+d-1;++i)
        for(int j=y;j<=y+d-1;++j)
            mx=max(mx,h[i][j]);
    return mx;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            cin>>h[i][j];
    int p=1,x=n;
    for(int i=2;i*i<=x;++i)
        if(x%i==0)
        {
            p=i;
            while(x%i==0) x/=i;
        }
    if(x>1) p=x;
    long long ans=0;
    for(int i=1;i<=n;i+=p)
        for(int j=1;j<=n;j+=p)
            ans+=solve(i,j,p);
    cout<<ans<<endl;
}

F. 小丑扔球

题源：是cf上div2 A题 的改编。Problem - A - Codeforces

题目构造过程：

我们在军训期间接受了新生赛出题任务（这时候kunkun还在跟hhs，xl学怎么玩MC），在9月上旬我们已经构造好了一个考察贪心基础算法的简单题，后经过多方面验题，发现此题难度超出了预期，正解的复杂度和复杂性奇高无比，因此新生赛很遗憾的减少了一个简单题。

确认题目无解后，我们又经过四五天的时间，决定从cf上面改编一题，然后花费大概4，5天的时间确定题面和std, 通过cf不同分段选手的验题，我们可以确定《小丑扔球》可以作为决定新生是否能够进入实验室的区分题之一，我们相信能做出来这道题的选手基础贪心算法是过关的。

经过多名选手验题，我们收到不同的难度反馈，分别为div2的A,B,C题难度

感谢： 浙大城市学院 mhq， gu76h(zyf) 等选手的第一轮验证

AHU实验室内其他选手的第二轮验证

考点：思维（结论），贪心（个人感觉是对cf选手的福利？）

先说结论：设用例数列为 $AA$：

1. 数列最大值 $\max (A)>\frac{\mathrm{sum}(A)}{2}\backslash max(A)>\backslash frac\; \{\backslash operatorname\{sum\}\{(A)\}\}\; 2$，答案为1；
2. $\max (A)=\frac{\mathrm{sum}(A)}{2}\backslash max(A)=\backslash frac\; \{\backslash operatorname\{sum\}\{(A)\}\}\; 2$ ，答案为0（两个元素）or 1（三个元素）；
3. ，（此时必有至少三个元素）答案为n（sum为奇数），n-count(1)（sum为偶数）

设所有元素之和为 $SumSum$，元素最大值为 $maxmax$，当前元素为 $nownow$，剩余其它元素之和为 $othoth$，显然有

对于情况1，有：

显然不论如何操作，即使剩余所有元素与 $maxmax$ 相消去，$maxmax$ 也必然能留下来，故此时答案为 1。

对于情况2，有：

1. 只有两个元素，显然只能对这两个元素不停操作直至空集，答案为 0；
2. 至少三个元素。此时较小的元素可以通过内耗从而使得最大的元素可以留下来，答案为 1；

对于情况3，有：显然此时至少有三个元素。

显然最大的元素一定能被留下来，至于对于每种元素何为最优操作请看附件。

对于任一非最大元素 $nownow$ 对于其在全集为 $AA$ 意义下的补集 $A^{\mathrm{\prime }}=\{max,\{oth\}\}A\text{'}=\backslash \{max,\backslash \{oth\backslash \}\backslash \}$（此处 $othoth$ 指代所有其余元素的集合），由附件结论可得该集合的操作后剩余值为：

化简后可得：

显然，若元素$nownow$能被留下来，需同时满足 和

对于前者，由式(3)可知已满足条件。

对于后者，显见有 $now\ge 1now\backslash ge\; 1$且$(max+oth)\mathrm{mod}2\le 1(max+oth)\backslash operatorname\; \{mod\}2\backslash le\; 1$。显然只有 $now=1now=1$ 且 $(max+oth)\mathrm{mod}2=1(max+oth)\backslash operatorname\; \{mod\}2=1$时，$nownow$ 不能被留下来。注意到此时 $sum=max+oth+nowsum=max+oth+now$ ，易得 $sumsum$ 为偶数。

因此我们得出结论：对于 $sumsum$ 为偶数的情况，所有值为 $11$ 的元素都不能被留到最后。

与前面啰嗦的解释不同，代码显得格外简洁好懂：

#include <algorithm>
#include <iostream>
 
using namespace std;
typedef long long LL;
const int N=1e6+10;
LL a[N],ans,n,s;
void solve(){
    sort(a + 1, a + 1 + n);
	ans = 0;
	if(s % 2){
		if(a[n] > s / 2) ans = 1;
		else ans = n;
	}
	else {
		if(a[n] >= s / 2) ans = 1;
		else {
			ans = n;
			for(int i = 1; i <= n; i ++)
				if(a[i] == 1) ans --;
        }
	}
	cout <<  ans <<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        s=0;
        for(int i=1;i<=n;i++)
            cin>>a[i],s+=a[i-1];
        s+=a[n];
        solve();
    }
    return 0;
}

G. 神秘信号

题目大意：对给定的串 $ss$ 而言，每次操作可删除它一个 $s_i\mathrm{\ne }{s}_{j}s\_i\; \backslash neq\; s\_j$ 的子串 $s_i{s}_{i+1}\dots s_{j-1}{s}_{j}s\_is\_\{i+1\}\backslash dots\; s\_\{j-1\}s\_j$，问将它删空的最少操作数，或不可能将它删空。

这题是一道结论题。虽然结论十分好猜、且符合直觉，但是严谨的证明稍微有点小麻烦。

下面都记 $ss$ 的长度为 $nn$ .

• 如果 $s_1\mathrm{\ne }{s}_{n}s\_1\backslash neq\; s\_n$，只需一次操作便可删除 $i=1,j=ni=1,j=n$ 的整个串 $ss$ .
• 如果 $s_1=s_{n}s\_1=\; s\_n$，不妨记 $s_1=s_n=\mathtt{A}s\_1=s\_n=\backslash mathtt\{A\}$ . 此时
  • 若某个位置 $pp$ 满足 $s_p\mathrm{\ne }\mathtt{A},s_{p+1}\mathrm{\ne }\mathtt{A}s\_p\backslash neq\backslash mathtt\{A\},\; s\_\{p+1\}\backslash neq\; \backslash mathtt\{A\}$，那么两次操作分别选择 $i=1,j=pi=1,j=p$ 和 $i=p+1,j=ni=p+1,j=n$，便可删除整个串 $ss$ .
  • 若不存在上述的 $pp$，那么对每个连续的两个字符 $s_k{s}_{k+1}s\_ks\_\{k+1\}$ 都有：不然 $s_k=\mathtt{A}s\_k=\backslash mathtt\{A\}$，不然 $s_{k+1}=\mathtt{A}s\_\{k+1\}=\backslash mathtt\{A\}$ . 记 $ss$ 中不是 $\mathtt{A}\backslash mathtt\{A\}$ 的字符数为 $mm$ .下面我们用归纳法证明对任意的 $mm$ 都无法删空 $ss$ .
    • $m=0m=0$ 时，$ss$ 中仅含 $\mathtt{A}\backslash mathtt\{A\}$，无法删空 $ss$ .
    • $m>0m>0$ 时，无论以何种方法删除 $ss$ 的子串，$ss$ 都会变成另一个 $mm$ 值更小、且仍保持该性质的串 $s^{\mathrm{\prime }}s\text{'}$ . $s^{\mathrm{\prime }}s\text{'}$ 无法被删空，因此 $ss$ 也无法被删空。

至此我们得到了结论：若 $s_1\mathrm{\ne }{s}_{n}s\_1\backslash neq\; s\_n$，那么输出 $11$；若 $s_1=s_{n}s\_1=s\_n$ 且存在 $pp$ 满足 $s_p\mathrm{\ne }{s}_1,s_{p+1}\mathrm{\ne }{s}_{n}s\_p\backslash neq\; s\_1,\; s\_\{p+1\}\backslash neq\; s\_n$，那么输出 $22$；否则输出 $-1-1$ .

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    cout << [&]() {
        int n = s.size();
        if (s[0] != s[n-1]) return 1;
        for (int i = 2; i <= n-2; i++)
            if (s[0] != s[i-1] && s[i] != s[n-1])
                return 2;
        return -1;
    }();
}

顺便一提，原来的那个 SOS 团标志，已经由 Yuki 重新修改后传上去了。这次上传的又是个什么样的东西呢？今后上网观看的人最好睁大眼睛看仔细了，跟原来画的蹩脚图案几乎没多大差别，但只要你注意比较，应该就会发现上面写的是“ZOZ团”。只有这么一丁点的差别，就成为解决异界信息的关键。 我想把这次的教训定为——别轻易点击不熟悉的链接。

H. 轻松的数列题

Tag：贪心、思维

对于每一个数，可以发现使其数位和减小的最小代价是将其最低位消去 $11$ 的代价。 我们可以对所有数的每一位整体考虑， 记一下每一位的数字之和， 按位从低到高的顺序消去，消去第 $ii$ 位一个数的代价显然为 $10^{i}10^i$（个位为第 0 位，十位为第 1 位，以此类推）。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
int a[11];
int main()
{
    int n,k,ans=0,b=1,x;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        for(int j=1;x;++j) ans+=x%10, a[j]+=x%10, x/=10;
    }
    for(int i=1;i<=9;++i)
    {
        if(1ll*b*a[i]>=k)
        {
            ans-=k/b;
            break;
        }
        ans-=a[i], k-=b*a[i], b*=10;
    }
    printf("%d\n",ans);
}

I. 不难的数列题

Tag：二分、STL

将结构体元素 $(a_i,k_i)(a\_i,k\_i)$ 按 $aa$ 升序排序。枚举 $jj$，显然对于给定的 $jj$，合法的 $ii$ 一定是一段连续的区间。区间的上界很好确定，下界则为第一个满足 $a_i>\frac{a_j}{k_j}a\_i>\backslash frac\{a\_j\}\{k\_j\}$ 的 $ii$ 。可以二分找到这个位置，然后便可很方便的统计答案。二分可以使用 STL 中的 std::upper_bound() 函数，作用是在给定序列中找到第一个大于给定值的元素的位置。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
struct node
{
    int a,k;
} x[N];
bool operator < (node s, node t)
{
    return s.a<t.a;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>x[i].a;
    for(int i=1;i<=n;++i) cin>>x[i].k;
    sort(x+1,x+1+n);
    int l=0;
    long long ans=0;
    for(int i=2;i<=n;++i)
    {
        if(x[i-1].a!=x[i].a) l=i-1;
        int j=upper_bound(x+1,x+1+n,(node){x[i].a/x[i].k,0})-x;
        ans+=max(0,l-j+1);
    }
    cout<<ans<<endl;
}

J. 神明的迷思

题目要求计算模质数域下的多项式的根的和，由于题目没有保证根的个数，无法使用韦达定理直接计算 ，出题人还没有想到复杂度低于 $O(T\cdot n\cdot mod)O(T\backslash cdot\; n\backslash cdot\; mod)$ 暴力的做法，如果有人有复杂度更优秀的做法，欢迎联系出题人。

正确的解题思路是，发现题目本身难以求解，并且注意到本题的强制在线意义不明并且加密方式与一般题目略有不同，很多答案相关的信息会被这些加密数据泄露出来。 经过仔细观察输入可以发现，本题输入以加密前的 $101\; \backslash \; \backslash \; 0$ 结尾，而该组数据加密后的结果一定是 $an{s}_{last}+su{m}_{last}ans\_\{last\}\; +\; sum\_\{last\}$，$su{m}_{last}sum\_\{last\}$ ，其中 $an{s}_{last}ans\_\{last\}$ 为上一段碑文的答案，$su{m}_{last}sum\_\{last\}$ 为之前所有碑文答案的和，由此即可计算得到 $an{s}_{last}ans\_\{last\}$ 和 $su{m}_{last-1}sum\_\{last\; -\; 1\}$ 。 再观察上一段加密后的数据，第一个数字 $nn$ 被加密为 $n\cdot an{s}_{last-1}+su{m}_{last-1}n\; \backslash cdot\; ans\_\{last\; -\; 1\}\; +\; sum\_\{last\; -\; 1\}$，而 $nn$ 真实值可以通过该段剩余数字个数得知，$su{m}_{last-1}sum\_\{last\; -\; 1\}$也已经计算出来，即可解得 $an{s}_{last-1}ans\_\{last\; -\; 1\}$ 的真实值，并计算出 $su{m}_{last-2}sum\_\{last\; -\; 2\}$ 。 如此即可从后往前依次推算出所有的答案，时间按复杂度 $O(T\cdot n)O(T\; \backslash cdot\; n)$。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
 
#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
 
using namespace std;
 
const int N = 1100;
const int mod = 10007;
 
int num[N], ans[N], tn[N];
 
int qpow(int a, int b)
{
	int ret = 1, base = a;
	while (b) {
		if (b & 1) ret = ret * base % mod;
		base = base * base % mod, b >>= 1;
	}
	return ret;
}
 
int main()
{
	string s;
	int len, cnt = 0, sum = 0;
	while (getline(cin, s)) {
		len = s.length();
		cnt ++; 
		Rep0(i, len - 1) if (s[i] == ' ') tn[cnt] ++;
		Rep0(i, len - 1){
			if (s[i] < '0' || s[i] > '9') break;
			num[cnt] = num[cnt] * 10 + s[i] - '0';
		}
	}   
	int ti = 0; 
	while (s[ti] != ' ') ti ++;
	ti ++;
	while (ti < len) sum = sum * 10 + s[ti] - '0', ti ++;
	//cout << sum << endl;
	for (int i = cnt - 1; i; i --) {
		ans[i] = (num[i + 1] - sum + mod) % mod * qpow(tn[i + 1], mod - 2) % mod;
		sum = (sum - ans[i] + mod) % mod;
	}
	
	Rep(i, cnt - 1) cout << ans[i] << endl;
	
	return 0;
}

K. 赛尔号

Tag：模拟

本题考查题意理解+代码能力。注意到题目要求求小 C 100% 获胜的方案，所以在模拟的过程中速度相同时要让小 C 后手，在随机修正计算伤害时要让小 D 的 $RR$ 为 $11$，小 C 的 $RR$ 为 $\frac{217}{255}\backslash frac\{217\}\{255\}$，这样模拟得到的局面得到的即为小 C 的最劣局面。枚举分配哪两项学习力后模拟对战过程即可。

#include<bits/stdc++.h>
using namespace std;
int az[5],al[5],a[5],b[5],c;
//0:attack; 1:defense; 2:speed; 3:HP; 4:attack power
int hurt(int atk, int power, int def, bool r)
{
    double res=((42.0*power*atk)/(def*50)+2)*3/2;
    if(r) res=res*217/255;
    return (int)res;
}
bool check()
{
    bool now=(a[2]>b[2]);
    int hp_a=a[3],hp_b=b[3];
    while(true)
    {
        int res=(now?hurt(a[0],a[4],b[1],1):hurt(b[0],b[4],a[1],0));
        if(now)
        {
            hp_b-=res;
            if(hp_b<=0) return true;
        }
        else
        {
            hp_a-=res;
            if(hp_a<=0) return false;
        }
        now^=1;
    }
}
int main()
{
    int T; cin>>T;
    while(T--)
    {
        cin>>az[0]>>az[1]>>az[2]>>az[3];
        cin>>b[0]>>b[1]>>b[2]>>b[3];
        cin>>c>>a[4]>>b[4];
        bool win=false;
        for(int i=0;i<4;++i)
            for(int j=i+1;j<4;++j)
            {
                al[i]=al[j]=255;
                for(int k=0;k<4;++k)
                {
                    if(k<3) a[k]=2*az[k]+al[k]/4+c+5;
                    else a[k]=2*az[k]+al[k]/4+c+110;
                }
                if(check()) win=true;
                al[i]=al[j]=0;
            }
        puts(win?"Yes":"No");
    }
}