Hello 2024

实时

A.

alice先操作bob后操作

全部如果是奇数就是alice最后操作，如果是偶数bob最后操作

1.ac

B.

s[i]= -?ans--;

s[i]=+ ans++;

cout<<ans；

1.ac

C.

构造2个数组从a[i]中

尽可能按照从大到小排序，不能改变相对位置

选一个小选一个大就是最优解

第一个元素很重要

枚举一下第一个索引

还得再找一下比第一个索引元素小的数

超时？

无论如果第一个元素是必须在第一个的

我们只需要找那个第一个元素所在的数组就可以了

找的这个数组是不会存在贡献的

因此枚举那个数组的变化

还有如果不在就是全部都在一个数组里

找ai<ai+1的就可以计算ans

两者比较一下即可

多个例子初始化

1.re2数组开小了

2.wa2

3335333

333 + 5333

貌似是ans没有++

所以例子才是0

cnt没有++

353应该cnt=1;

cp输出方式的问题。。

要空格

3 5 3

没思路

题解

A.

// Problem: A. Wallet Exchange
// Contest: Codeforces - Hello 2024
// URL: https://codeforces.com/contest/1919/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//	　　＞―r￣￣`ｰ―＿
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
void solve() {
	int a,b;
	cin>>a>>b;
	int sum=a+b;
	if(sum&1){
		cout<<"Alice"<<'\n';
	}else{
		cout<<"Bob"<<'\n';
	}


}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}

	return 0;
}

B.

// Problem: B. Plus-Minus Split
// Contest: Codeforces - Hello 2024
// URL: https://codeforces.com/contest/1919/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//	　　＞―r￣￣`ｰ―＿
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
void solve() {
	int n;
	cin>>n;
	string s;
	cin>>s;
	int ans=0;
	for(int i=0;i<n;i++){
		if(s[i]=='-'){
			ans--;
		}else{
			ans++;
		}
	}
	if(ans>=0){
		cout<<ans<<'\n';
	}else{
		cout<<-ans<<'\n';
	}
	

}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}

	return 0;
}

C.

贪心

我贪心思路有问题

先找一下代码实现是否错误

如果wa了就应该开始找反例去证明这个贪心不是最优解

最优解应该是

模拟出两个数组来存放元素

当然还是可以先存放第一个索引在一组里，因为相对位置不变，所以前面不会存在元素

那还是得考虑一下只有一组的情况

然后遍历一边a数组

遍历到的元素记作x

把x,b.back(),c.back()的九种关系都考虑一遍即可

大致情况

1.x<b.back() && x<c.back();

那应该放在最后一个元素比较的小的数组里，简单举个例子证明一下（x=3,b.back()=4,c.back()=5,因此我们应该放在b数组后面,如果放在c数组后就留了一个4，如果遍历到4的话就会多一些亏损)

2.x<b.back() && x>c.back();

放在b数组后不会亏损

3.x>b.back() && x<c.back();

放在c数组后不会亏损

4.x>b.back() && x>c.back();

那应该放在最后一个元素比较小的数组里，同理例子（x=8,b.back()=4,c.back()=5,c数组还可以容纳（4321）而b数组只能容纳（321）,原本最大容纳量是7,加到b数组后可以容纳（7654321），加入b数组最大容纳量是12，加入c数组可以容纳(7654321)加入c数组最大容纳量是11）(如果理想化（不亏损）可以容纳的元素量）

13（27种不矛盾的）种关系讨论(x,b,c)

1.x>b && x>c && b>c

加入c

2.x<b && x>c && b>c

加入b

3.x>b && x>c && b>c

加入c

4.x>b && x>c && b<c

加入b

5.x>b && x>c && b=c

加入b

6.x>b && x<c && b<c

加入c

7.x<b && x<c && b>c

加入c

8.x=b && x=c && b=c

加入b

9.x<b && x=c && b>c

加入c

10.x>b && x=c && b<c

加入c

11.x<b && x<c && b<c

加入b

12.x<b && x<c && b=c

加入b

13.x=b && x<c && b<c

加入b

还是wa2 1196个例子

正规解法：

模拟一下2个数组加入元素

b数组末尾为x,c数组末尾为y

这次我们始终让x<=y

就不用判断太多大小关系

1.y>=a[i]>x

加入c

2.a[i]>y

加入b,ans++

3.x>=a[i]

加入b

一开始可以让x=INF,y=INF（最大值）

就可以直接判断一个数组没有元素，一个数组全是元素的情况

// Problem: C. Grouping Increases
// Contest: Codeforces - Hello 2024
// URL: https://codeforces.com/contest/1919/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//	　　＞―r￣￣`ｰ―＿
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
void solve() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int x=INF,y=INF;
	int ans=0;
	for(int i=1;i<=n;i++){
		if(x>y){
			swap(x,y);
		}
		if(x>=a[i]){
			x=a[i];
		}else if(y>=a[i] && x<a[i]){
			y=a[i];
		}else{
			x=a[i];
			ans++;
		}
	}
	cout<<ans<<'\n';
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}
	return 0;
}