T1
看到这时限和内存，连一个数组都开不下，更别说离散化了，考试的时候我用了一个栈来模拟，相同留、进，不同退，可以说是很接近正解了，但还是没继续往下想，也是爆零了。
正解的思路很简单，这里引出一个概念，摩尔投票法，适用于超过半数（不能等于）的众数，可以在常数的空间下、\(O(n)\)的时间复杂度下查询，这里就不多说了，看了代码就能理解。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,a;
int cnt,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
if(cnt==0) ans=a;
if(ans==a) cnt++;
else cnt--;
}
printf("%d",ans);
}
这里的摩尔投票法还可以进行拓展，用于查询超过\(1/k\)的的众数，我们可以把用几个变量（或开个较小的数组）把所有可以成为候选人的记录一下，如果出现相同的对应候选人加一票，如果都不同则全部减一，票为0则更换候选人。这样就可以在空间复杂度很小的情况下统计这种特殊性质的众数。
T2
1.比较裸的一道中途相遇法，但我考试时还根本不会。我们首先要处理每个数的相同的数的位置，即找前驱和后继。然后我们就可以开始跑中途相遇了，如果一个数的前驱和后继都不在所搜的区间，那这个区间就是合法的，我们就可以搜它的两边的区间，递归下去。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,v[N],h[N],top[N];
int pre[N],nxt[N];
bool solve(int l,int r)
{
if(l>=r) return 1;
int li=l,ri=r;
while(li<=ri)
{
if(pre[li]<l&&nxt[li]>r)
{
return solve(l,li-1)&&solve(li+1,r);
}
if(pre[ri]<l&&nxt[ri]>r)
{
return solve(l,ri-1)&&solve(ri+1,r);
}
++li,--ri;
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&h[i]),v[i]=h[i];
sort(h+1,h+1+n);
int len=unique(h+1,h+1+n)-h;
for(int i=1;i<=len;i++)
{
top[i]=0;
}
for(int i=1;i<=n;i++)
{
v[i]=lower_bound(h+1,h+len,v[i])-h;
pre[i]=top[v[i]];
top[v[i]]=i;
}
for(int i=1;i<=len;i++)
{
top[i]=n+1;
}
for(int i=n;i>=1;i--)
{
nxt[i]=top[v[i]];
top[v[i]]=i;
}
printf("%sboring\n",solve(1,n)?"non-":"");
}
return 0;
}
2.第二种思路我们可以直接跑一遍扫描线，看能不能所构建的矩形能覆盖整个区间。
对于一个数i,它的前驱为pre[i],它的后继为nxt[i],
那么对于\(l∈(pre[i],i],r∈[i,nxt[i])\),在[l,r]这个区间是存在独一无二的数，那我们用
\(x1=pre[i]+1,x2=i,y1=i,y2=nxt[i]-1\)来做矩形覆盖。
最后只需要判断是否完全覆盖，即面积\(s=n*(n+1)/2\)。为什么不是\(n^2\),因为\(l<=r\)(! ! ! 卡了很久没理解)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+20;
int n;
#define lson (rt<<1)
#define rson (rt<<1|1)
struct lmy
{
int tag;
int sum;
}tr[N<<2];
void pushup(int rt,int l,int r)
{
if(tr[rt].tag) tr[rt].sum=r-l+1;
else tr[rt].sum=tr[lson].sum+tr[rson].sum;
}
void insert(int rt,int l,int r,int v,int L,int R)
{
if(l<=L&&R<=r)
{
tr[rt].tag+=v;
pushup(rt,L,R);
return ;
}
int mid=(L+R)>>1;
if(l<=mid) insert(lson,l,r,v,L,mid);
if(r>mid) insert(rson,l,r,v,mid+1,R);
pushup(rt,L,R);
}
int ask()
{
return tr[1].sum;
}
void clear(int n)
{
for(int rt=0;rt<=n*4;rt++)
{
tr[rt].sum=tr[rt].tag=0;
}
}
struct line
{
int x,l,r;
bool flag;
}a[N<<2];
bool comp(line a,line b)
{
return a.x<b.x;
}
int v[N],h[N],top[N];
int pre[N],nxt[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
long long s=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&h[i]),v[i]=h[i];
sort(h+1,h+1+n);
int len=unique(h+1,h+1+n)-h;
clear(n);
for(int i=1;i<=len;i++)
{
top[i]=0;
}
for(int i=1;i<=n;i++)
{
v[i]=lower_bound(h+1,h+len,v[i])-h;
// cout<<v[i]<<endl;
pre[i]=top[v[i]];
top[v[i]]=i;
}
for(int i=1;i<=len;i++)
{
top[i]=n+1;
}
for(int i=n;i>=1;i--)
{
nxt[i]=top[v[i]];
top[v[i]]=i;
}
int x1,x2,y1,y2;
int cnt=0;
for(int i=1;i<=n;i++)
{
x1=pre[i]+1,x2=i;
y1=i,y2=nxt[i]-1;
a[++cnt]=line({x1,y1,y2,0});
a[++cnt]=line({x2+1,y1,y2,1});
}
sort(a+1,a+1+cnt,comp);
int j=1;
for(int i=1;i<=n;i++)
{
while(j<=cnt&&a[j].x<=i)
{
insert(1,a[j].l,a[j].r,a[j].flag?-1:1,1,n);
j++;
}
s+=ask();
}
if(s==(1ll+n)*n/2) printf("non-boring\n");
else printf("boring\n");
}
}
T3
线段树优化建图的一道裸题（为啥都我没听过）。
这个题就用来当板子了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e6+5;
const int K=3e5;
int n,m,s;
int a[N<<2],op;
#define lson (rt<<1)
#define rson (rt<<1|1)
int h[N],to[N],nxt[N],w[N],tot;
void add(int x,int y,int dt)
{
to[++tot]=y;
nxt[tot]=h[x];
w[tot]=dt;
h[x]=tot;
}
void build(int rt,int l,int r)
{
if(l==r)
{
a[l]=rt;
return ;
}
int mid=(l+r)>>1;
add(rt,lson,0),add(rt,rson,0);
add(lson+K,rt+K,0),add(rson+K,rt+K,0);
build(lson,l,mid);
build(rson,mid+1,r);
}
void update(int rt,int l,int r,int L,int R,int v,int w)
{
if(L<=l&&r<=R)
{
if(op==2) add(v+K,rt,w);
else add(rt+K,v,w);
return ;
}
int mid=(l+r)>>1;
if(L<=mid) update(lson,l,mid,L,R,v,w);
if(R>mid) update(rson,mid+1,r,L,R,v,w);
}
int dis[N],vis[N];
priority_queue< pair<int,int> >q;
void dij(int x)
{
memset(dis,0x3f,sizeof dis);
dis[x]=0;
q.push(make_pair(0,x));
while(!q.empty())
{
x=q.top().second;
q.pop();
vis[x]=1;
for(int i=h[x];i;i=nxt[i])
{
int y=to[i];
if(dis[y]>dis[x]+w[i])
{
dis[y]=dis[x]+w[i];
if(!vis[y]) q.push(make_pair(-dis[y],y));
}
}
}
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&s);
build(1,1,n);
for(int i=1;i<=n;i++)
{
add(a[i],a[i]+K,0);
add(a[i]+K,a[i],0);
}
for(int i=1;i<=m;i++)
{
int x,y,dt;
scanf("%lld",&op);
if(op==1)
{
scanf("%lld%lld%lld",&x,&y,&dt);
add(a[x]+K,a[y],dt);
}
else
{
int l,r;
scanf("%lld%lld%lld%lld",&x,&l,&r,&dt);
update(1,1,n,l,r,a[x],dt);
}
}
dij(a[s]+K);
for(int i=1;i<=n;i++)
{
printf("%lld ",dis[a[i]]!=0x3f3f3f3f3f3f3f3f?dis[a[i]]:-1);
}
}
T4
预设型DP，这题又是一道DP分讨（恶心）。
我们设f[i][j][k]表示填到i个数，还要填j个数，max和为k。
我们按从小到大进行填数。
那么对于任意一个数x显然有三种情况。
1.如果x左右目前都没数，那么说明它的左右两个数都比x大，此时x的贡献为0.
2.如果x左右有一个数，那么它的贡献为x。
3.如果x左右都有数，那么它的贡献为\(2*x\)。
那动态转移方程太麻烦了，回头有空在补上。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=60;
const int mod=998244353;
int n,m,ans;
int f[N][N][2540];
signed main()
{
scanf("%lld%lld",&n,&m);
f[1][0][0]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=n-i+1;j++)
{
for(int k=0;k<+m;k++)
{
f[i][j+1][k]=(f[i][j+1][k]+f[i-1][j][k]*2)%mod;
f[i][j][k+i]=(f[i][j][k+i]+f[i-1][j][k]*2)%mod;
if(j!=0)
{
f[i][j+1][k]=(f[i][j+1][k]+f[i-1][j][k]*j)%mod;
f[i][j][k+i]=(f[i][j][k+i]+f[i-1][j][k]*j*2)%mod;
f[i][j-1][k+i*2]=(f[i][j-1][k+i*2]+f[i-1][j][k]*j)%mod;
}
}
}
}
for(int i=0;i<=m;i++)
{
ans=(ans+f[n][0][i])%mod;
}
printf("%lld",ans);
}