模拟赛
T1 立大功。
T1 yyy loves Maths VI (mode)
摩尔投票法。
既然有一个人出现次数 \(\gt \frac{n}{2}\)，那么我们可以用两两抵消的思路。最坏的情况就是每一个不是答案的都消掉了一个答案，但这样也会剩下正确答案。
for(int i=1;i<=n;++i)
{
int x; scanf("%d",&x);
if(cnt==0) a=x;
if(a==x) cnt++;
else cnt--;
}
最炸裂的是用 CRT！！！取几个质数求模，每个都找出模数出现次数最多的那个，然后解。
复习CRT。（如果不证明还挺简单的？）
code
#include<bits/stdc++.h>
using namespace std;
int n,prime[3][1030],a[3]={1009,1019,1021},mx[3],ans[3];
int exgcd(int a,int b,int &x,int &y)
{
if(b==0) {x=1; y=0; return a;}
int gcd=exgcd(b,a%b,x,y),t=x;
x=y; y=t-y*(a/b);
return gcd;
}
int u,v;
int crt()
{
int x,y,res=0;long long ck=1,m;
for(int i=0;i<3;i++) ck*=a[i];
for(int i=0;i<3;i++)
{
m=ck/a[i];
exgcd(a[i],m,x,y);
res=(res+y*m*ans[i])%ck;
}
return res>0?res:res+ck;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
int x; scanf("%d",&x);
for(int j=0;j<3;j++) prime[j][x%a[j]]++;
}
for(int j=0;j<3;j++)
for(int i=0;i<a[j];i++)
if(mx[j]<prime[j][i]) mx[j]=prime[j][i],ans[j]=i;
printf("%d\n",crt());
return 0;
}
T2 Non-boring sequences
赛时半小时打完，最后十分钟发现假了。。。
正解两种：
一、 分治
思路出奇的简单，我们考虑如果一个数在目前的区间中只出现一次，那么所有跨过它的子区间一定都满足，所以我们只需要对它左右的两个子区间递归求解就好了。
如何判断一个数在某个区间中是否只出现一次呢？可以预处理每个数上一次出现的位置和下一次出现的位置，判断是否在区间内就好了。
大概长这样：
for(int i=1;i<=n;i++)
{
nxt[i]=1e9;
int x; scanf("%d",&x);
pre[i]=mp[x]; nxt[lst[i]]=i;
mp[x]=i;//map离散化
}
这样我们还需要遍历每个区间，极限情况可以卡。
这里用到一个 trick：启发式分裂！！！
启发式分裂（中途相遇法）：从两边同时遍历，最坏情况在中间 \(\frac{len}{2}\)。
名字依旧很高级，其实就是每次分成两半，同时进行，防止被卡。用处挺大的。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int t;
int n,nxt[N],pre[N];
unordered_map<int,int> mp;
bool dfs(int l,int r)
{
if(l>=r) return 1;
int ll=l,rr=r;
while(ll<=rr)
{
if(pre[ll]<l&&nxt[ll]>r)
return dfs(l,ll-1)&&dfs(ll+1,r);
if(pre[rr]<l&&nxt[rr]>r)
return dfs(l,rr-1)&&dfs(rr+1,r);
ll++,rr--;
}
return 0;
}
int main()
{
scanf("%d",&t);
while(t--)
{
mp.clear();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
nxt[i]=1e9;
int x; scanf("%d",&x);
pre[i]=mp[x]; nxt[lst[i]]=i;
mp[x]=i;
}
if(dfs(1,n)) printf("non-boring\n");
else printf("boring\n");
}
return 0;
}
二、 扫描线
咕咕咕。。。
标签：return,rr,2024.7,19,ll,dfs,int,区间,模拟 From： https://www.cnblogs.com/ppllxx-9G/p/18312440