天河C-OI赛制首测

Done OI Start at: 2025-4-8 18:35 1.5 hour(s) Host: 12

认真想了下大家代码,还是进步很大的,其实都接近正解了👍👍👍差点测试/打表小技巧

前两题文件IO,后两题洛谷远端测评没有文件IO

j0,j1,jn,y0,y1,yn,这种都是Bessel函数,在不同的C std lib中名字不同,不要写这类变量名

要自己出测试用例啊啊啊

y=x%mod这种函数不单调,想二分是好事,但本题不能用,5>3,5%4<3%4,数据量1E6够打表的

同余的知识见一本通,5%4-3%4会出现负数

C题O(n)处理示例(end、first这种名字也别取,这里便于理解写了first)


//翻译题目:求cnt(G)==cnt(R)俩宝石数量相等的 最大区间长度
//对两个元素分别计数略麻烦cnt(G)==cnt(R),考虑cnt(G)-cnt(R)==0,记G为1,R为-1,算前缀和,找最大区间和为0的区间长度
#include<iostream>
#include<cstring>
// #include<map>//nlogn排序、logn查找,适合数据个数1E5范围内,数据值范围超过数组索引的情况
// #include<unordered_map>//O(1)查找,相当于帮忙做了hash的桶排,适合键非int/ll的情况
using namespace std;
const int maxn=2E6+20, offset=1E6+10;//由于存在-1运算,过程中可能有负数,如果用first数组得加个偏移量,注意加了偏移量数组也得相应开大 
char brilliants[maxn];
int pre[maxn], first[maxn]={0}, max_len=0;//pre为宝石±1相加的前缀和结果,first为第一次出现的
int main(){
	cin>>brilliants+1;//元素索引从1开始计数能简化很多代码 
	pre[0]=offset;
	for(int i=1; i<=strlen(brilliants+1); i++){
		pre[i]= pre[i-1] + (brilliants[i]=='G' ? 1 : -1);
		if(!first[pre[i]])	first[pre[i]]=i;
		if(pre[i]==offset)	max_len=i;//如果前缀和为0(->offset)那最优左端点必为起始	
		else if(first[pre[i]])	max_len=max(max_len, i-first[pre[i]]);
	}
	cout<<max_len;
	return 0;
}


//不想折腾偏移量的直接unordered_map吧,这题前缀和-索引得存着,即使省了字符串等数组也有map在,空间优化了个寂寞(只能算常数系数级别的优化) 
#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;
const int maxn=1E6+10;
char brilliant;
int pre, max_len=0;
unordered_map<int,int> first; 
int main(){
	for(int i=1; cin>>brilliant; i++){
		pre= pre + (brilliant=='G' ? 1 : -1);
		if(first.find(pre)==first.end())	first[pre]=i;
		if(pre==0)	max_len=i;	
		else if(first[pre])	max_len=max(max_len, i-first[pre]);
	}
	cout<<max_len;
	return 0;
} 


Status
Done
Rule
OI
Problem
4
Start at
2025-4-8 18:35
End at
2025-4-8 20:02
Duration
1.5 hour(s)
Host
Partic.
12