天河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