新生赛

1 数一数三角形

1.1 题目描述

在那遥远的角落三条边相拥相依它们相隔却又相连像爱情中的你我他
三角形有着神秘的力量让我们的爱情纯粹又完美无论相隔多远，相连多近爱，永远如三角形般美丽

你得到一个正 $N$ 边多边形。将任意一条边标记为边 $1$ ，然后按顺时针顺序将下一条边标记为边 $2$ 、 $3$ 、 $\dots$ 、 $N$ 。在 $i$ 侧有 $A_{i}$ 个特殊点。这些点的位置使得边 $i$ 被分成长度相等的 $A_{i} + 1$ 段。

您希望创建尽可能多的 满足条件的三角形，同时满足以下要求。

每个三角形由 3 个不同的特殊点组成（不一定来自不同的边）作为它的角。
每个特殊点只能成为最多 1 个三角形的角。
所有的三角形不能互相相交。
请你数一数可以创建的满足条件的三角形的最大数量。

1.2 输入

$\begin{matrix} N \\ A_{1} & A_{2} & \dots & A_{n} \end{matrix}$

数据范围:
$3 \leq N \leq 200 000$ , $1 \leq A_{i} \leq 2 \cdot 10^{9}$

1.3 输出

输出一个整数，表示可以创建的三角形的最大数量。

1.4 示例 1

输入

4
3 1 4 6

输出

1.5 示例 2

输入

3
1 1 1

输出

1.6 说明

例如样例一，有一个正四边形。假设最上面的一条边被标记为边 $1$ ，下图显示了当 $A = [3, 1, 4, 6]$ 时特殊点如何位于每一边内及一种可行的方案

1.7 代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, a[200010];
int main()
{
    cin >> n;
    ll cnt = 0, maxa = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], cnt += a[i], maxa = max(maxa, a[i]);
    cout << min(cnt / 3, cnt - maxa) << '\n';
}
/*
    ll ans = sum/3;
    if (mx > 2 * (sum - mx)) {
        ans = sum - mx;
    }
    
    cout << ans << endl;*/

2 字符串相约

2.1 题目描述

在无尽的二进制海洋中，邂逅了你。就像在复杂的计算机代码里，我找到了那一行的灵魂诗。
在你的眼睛里，我看到星光，像是一个完美的算法, 在你的笑容下，我的心跳加速，我知道我已经陷入你的陷阱。
无论数据流如何冲刷，无论代码多么艰难，我都会矢志不渝，因为，我爱你。
你是我的私钥，我是你的公钥，在这信息海洋里，相互加密，无人能解。
当所有的数字疯狂旋转，当所有的指针失去方向，我将在你的离散空间里，等待，直到时间指向永恒。
这不仅仅是爱情的密语，它还保存了我们共同的记忆，无论虚拟空间如何寒冷，只要有你，我就能找到温暖。
在这个充满机器语言的世界，你我找到了属于我们的诗篇。虽然我们只是两个二进制字符串，但我们的爱情，已经超越了生命的边界。
两个二进制字符串开始了甜甜的爱情, 随着时光的飞逝，岁月的冲刷，他们长得也越来越像彼此 $\dots$

有两个长度相等的字符串 $a, b$ ,它们只包含字符 $0$ 或 $1$ ; 两个字符串都以字符 $0$ 开始，以字符 $1$ 结束。

您可以执行以下操作任意次数（可能为零）：

选择其中一个字符串和两个相等的字符; 然后将它们之间的所有字符替换为这个字符。

即: 选择这两个字符串之一(假设为 $s$ )，然后选择两个整数 $l$ 和 $r$ ,满足 $1 \leq l < r <∣ s ∣$ 且 $s_{l} = s_{r}$ .然后替换在区间 $[l, r)$ 的所有字符 $s_{i}$ ,使得 $s_{i}$ 都替换为 $s_{l}$ 。( $\sum_{i = l}^{r - 1} s_{i} = s_{l}$ )

2.2 输入

$\begin{aligned} T \\ a_{1} & b_{1} \\ a_{2} & b_{2} \\ ⋮ & ⋮ \\ a_{T} & b_{T} \end{aligned}$

$T$ 为测试用例数量，每个测试用例由 $a, b$ 两行组成
$a, b$ 都以字符 $0$ 开始，以字符 $1$ 结束

数据范围

$2 \leq∣ a ∣=∣ b ∣\leq 5 000$ , $1 \leq T \leq 2 000$
$\sum_{i = 1}^{T} ∣ a_{i} ∣\leq 50 000$

2.3 输出

对于每个测试用例，如果可以使两个字符串相等，则打印 YES。否则，打印 NO。

2.4 示例

输入

输出

YES
YES
YES
NO
NO
NO
YES

2.5 说明

在第一个测试用例中，我们可以执行以下操作：

选择字符串 $a, l = 2, r = 4;$ 此操作后， $a$ 为 $01110001$ ， $b$ 为 $01110101$ ;
选择字符串 $b, l = 5, r = 7;$ 此操作后， $a$ 为 $01110001$ ， $b$ 为 $01110001$ 。
在第二个测试用例中，字符串已经相等。
在第三个测试用例中，我们可以执行以下操作：
选择字符串 $a, l = 4, r = 6;$ 此操作后， $a$ 为 $000111$ ， b 为 $010111$ ;
选择字符串 $b, l = 1, r = 3;$ 此操作后， $a$ 为 $000111$ ， b 为 $000111$ 。

2.6 代码

#include<bits/stdc++.h>
using namespace std;
int t;
string a,b;
int main()
{
    cin>>t;
    while(t--)
    {
        cin >> a >> b;
        int size = a.size(), flag = 0;
        for (int i = 0; i < size - 1;i++)
        if(a[i]==b[i]&&a[i]=='0'&&a[i+1]==b[i+1]&&a[i+1]=='1')
            flag = 1;
        if(flag)
            cout << "YES" << '\n';
        else
	        cout<<"NO"<<'\n';
    }
}

3

3.1 题目描述：

WZ 学长最近迷恋上了泡养生茶，他买了枸杞，决明子，菊花，栀子，桑葚，桑叶，蒲公英，金银花，茯苓，人参... 某天他突发奇想，是不是把两杯液体重量一样的养生茶倒到其中一个杯子里面再喝下去，就会获得双倍的效果还能少喝一杯茶！（智慧的眼神）
说干就干！假设 WZ 学长一共有 $n$ 杯养生茶，每个杯子无限大并且初始只有 $1$ 升养生茶。WZ 学长每次只会把两杯质量一样的茶倒进其中一个杯子（别问我为什么要一样多），而他每次最多只愿喝 $m$ 杯，那么他最少还需要再调配多少杯养生茶。
（放心如果要喝的养生茶超过 $1$ 升，那么 WZ 就会把多的都送给 Jiejie 学长并且看着他喝完！）

3.2 输入

$\begin{aligned} n & m \end{aligned}$
$n$ 为 WZ 已有的养生茶杯数， $m$ 为他愿意最多喝的养生茶数量

3.3 输出

输出一行最少还需要再买多少杯

3.4 样例

输入
3 1
输出
1
题解：二进制问题

#include<iostream>
using namespace std;
int n, m, ans;
int main() {
	cin>>n>>m;
	while(__builtin_popcount(n) > m) ans += n & -n, n += n & -n;
	cout<<ans;
}

4

4.1 题目描述：

WZ 最近想要学卷积神经网络了！但是因为这是他第一次做这种项目，于是乎，，，一个拥有数不清 bug 的屎山就诞生了! 虽心有余想要全部删了重构，然而项目就快要结题了，只好央求我们英俊潇洒风流倜傥的 Jiejie 学长来挽救于危难之间。Jiejie 虽然看不懂问题到底出在了哪里，但他发现 WZ 的 bug 出现的很有规律，每个 bug 只会影响当前行的代码，为了 debug 的舒服他决定数行数行的进行修改。于是他决定帮 WZ 重构 $m$ 个片段（即从一个 bug 到另一个 bug 算一个片段），于是想问 Jiejie 学长最少需要重构多少行代码。

4.2 输入

$\begin{aligned} x & n & m \\ a_{1} & a_{2} & \dots & a_{n} \end{aligned}$
第一行输入代码总长度 $x$ 和 $n$ 个 bug 以及 Jiejie 愿意重构 $m$ 个片段数
第二行一共有 $n$ 个数字代表每个 bug 的位置
数据范围：
$1 \leq a_{i} \leq x$
$1 \leq x, n, m \leq 1 000$

4.3 输出

Jiejie 学长最少需要更改的行数

4.4 样例

输入
11 5 2
2 4 6 9 10

输出
5

题解：排序＋贪心

#include<iostream>
#include<algorithm>
#define maxn 10050
using namespace std;
int x,n,m;
int a[maxn];
int b[maxn];
int ans;
int main(){
	cin>>x>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=2;i<=n;i++)
		b[i-1]=a[i]-a[i-1];
	sort(b+1,b+n);
	for(int i=n-m;i>=1;i--)
		ans+=b[i];
	cout<<ans;
}

5

5.1 题目描述：

“鲁迅说的话关我周树人什么事，文则打游戏关我高某人什么事。“

WZ 最近迷恋上了塔防益智小游戏，目标是尽可能多的净化敌方的区域，整个地图由“*”构成，敌方的地盘用“#”表示。每块敌方的地区 WZ 都需要派遣一位白骑士去净化，但是敌方为了保护自己的地盘建立了多个碉堡，每个碉堡用“!”表示。WZ 只能攻占一片敌方的区域，而这片区域每拥有一个碉堡 WZ 就需要多派一个白骑士去净化。问 WZ 想要尽可能多的净化敌方区域至少需要派遣多少个白骑士。

一曲忠诚的赞歌~

5.2 输入格式

$\begin{aligned} n m \\ c h_{11} c h_{12} \dots c h_{1 m} \\ c h_{21} c h_{22} \dots c h_{2 m} \\ ⋮ \\ c h_{n 1} c h_{n 2} \dots c h_{n m} \end{aligned}$
第一行，输入两个整数 $n$ 和 $m$ 代表整张地图的大小
接下来 $n$ 行，每行将输入 $m$ 个字符代表当前位置情况
$1 \leq n, m \leq 500$

5.3 输出格式

$\begin{aligned} x & y \end{aligned}$
$x$ 代表 WZ 可以占领的敌方区域大小， $y$ 代表 WZ 至少需要派遣多少个白骑士

5.4 样例

输入

3 3
#!**
!#**
*#*#
*#*!

输出

6 8

题解：宽搜/深搜

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define maxn 1060
using namespace std;
int n,m;
char c[maxn][maxn];
int ti[4]={1,-1,0,0};
int tj[4]={0,0,1,-1};
bool v[maxn][maxn];
int ans1=0,ans2=0;
struct node{
	int x,y;
};
void find(int a,int b){//搜索
	int nans1=1,nans2=1;
	if(c[a][b]=='!')nans2++;
	v[a][b]=false;
	queue<node> Q;
	node X;
	X.x=a,X.y=b;
	Q.push(X);
	while(!Q.empty()){
		node fi=Q.front();
		Q.pop();
		int x=fi.x,y=fi.y;
		for(int i=0;i<4;i++)
			if(v[x+ti[i]][y+tj[i]]){
				nans1++;nans2++;
				if(c[x+ti[i]][y+tj[i]]=='!')nans2++;
				node N;
				N.x=x+ti[i],N.y=y+tj[i];
				Q.push(N);
				v[x+ti[i]][y+tj[i]]=false;
			}
	}
	if(nans1>ans1){
		ans1=nans1;
		ans2=nans2;
	}
}
int main(){
	memset(v,false,sizeof(v));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
			if(c[i][j]=='*')v[i][j]=false;
			else v[i][j]=true;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(v[i][j])find(i,j);
	cout<<ans1<<" "<<ans2;
}