本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-11 20:57:41

T1 病毒

这是一道签到题，考查数据类型和算术运算。 一个简单的除法，但是需要注意：$ 0 \leq m≤n≤2^{32} $，$ 2^{32} $正好是无符号长整型(unsigned (long int))的最大值加一，需要开超长整型((signed) long long (int)) 保留三位小数，有两种方法： 第一种：

#include<cstdio>
\/\/#include<stdio.h> 这两个头文件用其中一个即可

printf("%.3lf",ans);\/\/.3表示保留三位小数，lf表示double类型 

第二种：

#include<iomanip>

cout<<fixed<<setprecision(3)<<ans;\/\/3表示保留三位小数 

参考代码

#include<iostream>\/\/或者用万能头<bits\/stdc++.h>
#include<cstdio>
using namespace std;
int main()
{
	\/\/freopen("norovirus.in","r",stdin);
	\/\/freopen("norovirus.out","w",stdout);
	long long n,m;
	double ans;
	cin>>n>>m;
	ans=double(m*100)\/n;\/*处理百分号(%)，同时将m转换为double*\/
	\/\/输出可以使用以下三种方法其中之一。 
	\/\/方法1 
	printf("%.3lf%% ",ans);
	\/\/方法2
	cout<<fixed<<setprecision(3)<<ans<<"%";
	\/\/方法3 
	printf("%.3lf ",ans);
	cout<<"%"; 
	 
	return 0;
}

T2 四季

本题想考查分支结构，为了防止输出任意一种骗分，增加为四组数据。不会使用循环的同学可以将代码复制4次。

对有些同学来说，可能难点在提取月份上，有两种方法，一是通过整体读入整数取模，二是通过字符读入，只取最后两个，运算得出月份。

然后使用if语句或switch语句完成代码。

参考代码

#include<bits\/stdc++.h>
using namespace std;
int main() {
	int n;
	char a,b;
	for(int i = 1; i <= 4; i++) {
		\/*方法一 
		 
		cin >> n; \/\/输入
		int date = n % 100; \/\/取日期的后两位 月份
		*\/ 
		\/\/方法二 
		cin>>a>>a>>a>>a>>a>>b;
		int date= (a-'0')*10+b-'0'; 
		if(date == 0 || date > 12) { \/\/判断日期是否合法
			cout << "error" << endl;
			continue;
		}
		if(date >= 9 && date <= 11) { \/\/秋天
			cout << "autumn" << endl;
		} else if(date >= 3 && date <= 5) { \/\/春天
			cout << "spring" << endl;
		} else if(date >= 6 && date <= 8) { \/\/夏天
			cout << "summer" << endl;
		} else { \/\/冬天
			cout << "winter" << endl;
		}
	}
	return 0;
}

T3 二进制

本题考查了循环，进制转换，绝对值等。

参考代码

#include<bits\/stdc++.h>
using namespace std;
int n, ans;
long long a[200050];
short fun(long long x){
	int cnt[2] = {0};
	while(x){
		cnt[x&1] ++;
		x >>= 1;
	}
	return (cnt[1] > cnt[0]) ? 1 : -1;
}
int main(){
	
	freopen("binary.in","r",stdin);
	freopen("binary.out","w",stdout);
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++)
		ans += fun(abs(a[i]));
	cout << ans << endl;
	return 0;
}

T4 猜拳

本题考查了贪心算法。

思路

我们只讲述满分做法。

根据题意，对于小容出的每一个剪刀或石头或布，我们都尽量让他赢，得 $2$ 分。

所以我们尽量的让 $a_1$ 和 $b_2$ 匹配，$a_2$ 和 $b_3$ 匹配，$a_3$ 和 $b_1$ 匹配。

对于剩下的，我们尽量让他达成平局，得 $1$ 分。

因此尽量让剩下的 $a_1$ 和 $b_1$，$a_2$ 和 $b_2$，$a_3$ 和 $b_3$ 匹配。

剩下的只能输，不能得分。

可以证明，没有其他任何一种方法使得分数更高。

可结合代码理解。

参考代码

#include <bits\/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n;
int a[3],b[3]; 
int ans;
signed main()
{
    \/\/freopen(".in","r",stdin);
    \/\/freopen(".out","w",stdout);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<=2;i++) cin>>a[i];
    for(int i=0;i<=2;i++) cin>>b[i];
    int p=min(a[0],b[1]);
    ans+=2*p;
    a[0]-=p,b[1]-=p;
    p=min(a[1],b[2]);
    ans+=2*p;
    a[1]-=p,b[2]-=p;
    p=min(a[2],b[0]);
    ans+=2*p;
    a[2]-=p,b[0]-=p;
    ans+=min(a[0],b[0]);
    ans+=min(a[1],b[1]);
    ans+=min(a[2],b[2]);
    cout<<ans; 
    return 0;
}

还可以用循环优化下代码表达

参考代码二

#include<bits\/stdc++.h>
using namespace std;
int main(){
	int n,a[3],b[3],ans=0;
	cin>>n>>a[0]>>a[1]>>a[2]>>b[0]>>b[1]>>b[2];
	for(int i=0;i<3;i++)
	{
		int j=(i+1)%3;
		int k=min(a[i],b[j]);
		ans+=k*2;
		a[i]-=k;
		b[j]-=k;
	}
	for(int i=0;i<3;i++){
		int k=min(a[i],b[i]);
		ans+=k;
		a[i]-=k;
		b[i]-=k;
	}
	cout<<ans;
	return 0;
}

T5 写作业

本题考查了模拟和贪心算法，以及结构体排序等语法运用。

对于 $50\%$

考虑直接模拟这个过程，设立一个访问标记数组，每一轮找到没有选择过的最大值。因为答案最大为 $n$，所以时间复杂度 $O(n^2)$。

对于 $100\%$

考虑实际上要让最大的先拿，然后再让次大的拿，以此类推。

考虑最大的拿完后我们可能传到次大的，这样就可以在同一轮里拿多个，实际上就是如果他们的下标递增，那么就可以在同一轮里拿。

所以我们可以按照大小为第一关键字，从大到小排序，然后问题转化到了当前这个序列上，求有多少递增的连续段。

循环的同时我们判断当前的数是否比前面的数小，如果小的话那就说明不递增了，我们要新开一轮，然后就做完了。

参考代码

#include <bits\/stdc++.h>

using namespace std;

#define pii pair<int, int>

#define fi first
#define se second

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int N = 1e5 + 10;

int n;

pii a[N];

int main()
{
    fst
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].fi, a[i].se = i;
    sort (a + 1, a + n + 1, [] (pii x, pii y) { return x.fi > y.fi; });
    int res = 1;
    for (int i = 1; i <= n; i++) if (a[i - 1].se > a[i].se) res++;
    cout << res;
    return 0;
}

T6 迷宫

信息学的成长路上怎么能少了迷宫问题呢？

思路

首先判断迷宫内空地的连通性，如果本来就不连通，那么及直接输出“No”。如果连通，连通块中包含的格式数要减少 $s$ 个，原来有 $ t $ 个，现在需要有 $t-s$个。

方法一

那么从任意一个空地开始，可以直接通过 $dfs$ 或者 $bfs$ 遍历找到$ t-s $个空地格子打标记，那么没打标记的空地格子就转换位字符'X'。

方法二

先将所有的空的格子转化为'X',再遍历，将 $ t-s $个'X'变为空地'.'

参考代码 方法二

#include <bits\/stdc++.h>
using namespace std;
int n,m,k,sx,sy,cnt,tot;
int dx[4] = {0,1,-1,0},dy[4] = {1,0,0,-1};
char mp[505][505];
void dfs(int x,int y){
    if (cnt == tot - k){
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= m;j++) cout << mp[i][j];
            cout << '\n';
        }
        exit(0);
    }
    for (int i = 0;i < 4;i++){
        int nx = x + dx[i],ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m || mp[nx][ny] != 'X') continue;
        mp[nx][ny] = '.',cnt++;
        dfs(nx,ny);
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            cin >> mp[i][j];
            if (mp[i][j] == '.') mp[i][j] = 'X',sx = i,sy = j,tot++;
        }
    }
    cnt = 1,mp[sx][sy] = '.';
    dfs(sx,sy);
    cout << "No";
    return 0;
}

参考代码 方法一

#include <bits\/stdc++.h>
using namespace std;
const int N = 510, dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
char s[N][N];
bool vis[N][N];
int n, m, k, cnt = 0, nr = 0;

void dfs (int x, int y) {
	if (vis[x][y]) return;
	--cnt;
	vis[x][y] = true;
	for (int l=0; l<4; l++) {
		int dx=dir[l][0], dy= dir[l][1];
		int i = dx + x, j = dy + y;
		if (!cnt) return;
		if (1 <= i && i <= n && 1 <= j && j <= m && !vis[i][j] && s[i][j] == '.') dfs (i, j);
	}
}

void dfs1 (int x, int y) {
	if (vis[x][y]) return;
	vis[x][y] = true, ++nr;
	for (int l=0; l<4; l++) {
		int dx=dir[l][0], dy= dir[l][1];
		int i = dx + x, j = dy + y;
		if (1 <= i && i <= n && 1 <= j && j <= m && !vis[i][j] && s[i][j] == '.') dfs1 (i, j);
	}
}

int main (void) {
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	cin.tie (0)->sync_with_stdio (false);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) cin >> (s[i] + 1);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cnt += s[i][j] == '.';
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (s[i][j] == '.') {
				dfs1 (i, j);
				if (cnt != nr) {\/\/迷宫本来不连通 
					cout << "No\n";
					return 0;
				}
			}
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) vis[i][j] = false;

	cnt -= k;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
			if (s[i][j] == '.') {
				dfs (i, j);
				if (cnt) {\/\/空地不够 
					cout << "No\n";
					return 0;
				}
				for (int i = 1; i <= n; i++, cout << '\n') for (int j = 1; j <= m; j++)
						if (s[i][j] == '.') cout << (vis[i][j] ? '.' : 'X');
						else cout << s[i][j];
				return 0;
			}
	abort ();
}

T6 奏鸣曲

思路分析

Subtask1

枚举，数据分为 $ 4 $ 类 A\B\C 或者 D...Z,每个位置暴力枚举，时间复杂度 $O(4^{n}) $

Subtask2

要出现ABC三种符号，可以同个状态压缩枚举当前出现的符号类型转移，但我们只需要种类数，可以直接记录出现的类别，就不要状态压缩了。 设 $f[i][j]$ 为前 $i$ 个位置出现过几个ABC。初始状态为 $f[0][0]=1$ 。 那么可以设计线性转移方程，时间复杂度 $O(n)$. $$ f[i][0]=f[i-1][0] \times 23
$$ $$ f[i][1]=f[i-1][0] \times 3 +f[i-1][1] \times 24 $$ $$ f[i][2]=f[i-1][1] \times 2 +f[i-1][2]*25 $$ $$ f[i][3]=f[i-1][2] +f[i-1][3] \times 26 $$

动态规划优化了解多的同学可以发现，这个式子可以用 $4 \times 4$ 矩阵快速幂优化，时间复杂度降为 $O(64*log^n)$,也可以解决 $100\%$的数据。

Subtask3

这是一个计数类问题，设 包含字符A的集合设为集合A;包含字符B的集合设为集合B,包含字符C的集合设为集合C. 那么问题的答案就是 $A \cap B \cap C $.

根据组合计数原理， $$|A \cap B \cap C|=\sum_{i=1}^{n-3}C_n^i \sum_{j=1}^{n-i-1}C_{n-i}^j\sum_{k=1}^{n-i-j}C_{n-i-j}^k23^{n-i-j-k} $$

这一坨式子看起来就很难计算，我们换个思路。

计数类问题常见的一个方法是正难则反。设所有可能字符串的集合是全集 $U$ ,$|U|=26^n$ 。

从全集中扣除 同时不包含ABC的符号，剩下的就是同时包含ABC的诗句了。 $$ A \cap B \cap C =

U-A' \cup B' \cup C' $$ 我们求集合 $A$ 的补集 $A'$,就是不包含字符'A'的集合，也就是每个位置其他 $25$ 个字符可选,$|A'|=25^n$ 。 同样的原理计算 $|A'B'|=24^n$ , $|A'B'C'|=23^n$,

$A' \cup B' \cup C' $= $$ |A'|+|B'|+|C'|-|A' \cap B'|-|A' \cap C'|-|B' \cap C'|+|A' \cap B' \cap C'| $$

带入上面的公式可得$26^n-325^n+324^n-23^n$

#include <iostream>
using namespace std;
#define int long long

const int P = 1e9+7;

int qpow(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)
			res = res * a % P;
		b >>= 1;
		a = a * a % P;
	}
	return res;
}

int F(int x) { return (x % P + P) % P; }

signed main()
{
	freopen("sonata.in","r",stdin); 
	freopen("sonata.out","w",stdout); 
	int n; cin >> n;
	if(n < 3)
		return cout << 0, 0;
	int all = qpow(26, n);
	int xxy = qpow(25, n);
	int x   = qpow(24, n);
	int oth = qpow(23, n);
	int res = F(3 * xxy - 3 * x + oth);
	cout << F(all - res) << '\n';
	return 0;
}