20210922 题解
crf的noip模拟赛day1
T1：
题解：dp
设dp[i][j]表示右下角为（i，j)时最大正方形
初值：就是输入的那个矩阵。
转移：
if（dp[i][j]==0) continue;//什么也不干
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1;
下面这个东西什么意思？
min(dp[i][j-1],dp[i-1][j-1]表示从这个右下角向左拓展
的最长距离
min(dp[i-1][j],dp[i-1][j-1]表示从这个右下角向上拓展
的最长距离。
至于为什么？反证法，如果上限不如上述所言，
与dp的定义矛盾
由于求的是正方形，所以二者取小。
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
il int read()
{
int s=0,w=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') w=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+c-'0';c=getchar();
}return s*w;
}
const int N=2010;
int n,m,c[N][N],dp[N][N],maxx;
int main()
{
n=read(),m=read();
for(re int i=1;i<=n;i++) for(re int j=1;j<=m;j++) dp[i][j]=read();
maxx=0;
for(re int i=1;i<=n;i++){
for(re int j=1;j<=m;j++){
if(dp[i][j]==0) continue;
dp[i][j]=min( min(dp[i-1][j],dp[i][j-1]), dp[i-1][j-1])+1;
maxx=max(maxx,dp[i][j]);
}
}
printf("%d",maxx);
return 0;
}
T2:
先按照x,y单调递增双关键字排序
此题最小划分数=最长反链,也就是最长下降子序列
我们设每一排书为一组，每个组里最大值为组里最
后一个数（记为t[i])。
有这样的结论：一定有一种情况，
使得t[i]中i递增，t[i]递减
就是最大值下标递增，数值递减
因为当我们使数列单调上升后，从后往前贪心地
将每一个数字接在第一个数值大于它的数字的后面，
一定可以构造出一个最优解。此时，
所有不能接在前面数字之后的数字，必定构成
下降序列，而组数（设为h）就是该下降序列的长度。
由于下降序列长度不可能长于最长下降子序列
于是h>=f
同时，由于最长下降子序列的各个数字不能在同一组
里，于是至少分h组，h<=f
所以h=f
上面的结论得证
我感觉数据错了……所以这道题不放代码了
T3:
题干啰里巴嗦一大堆话，就最后一段有用……
70分：莫队暴力
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
il int read()
{
int s=0,w=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') w=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+c-'0';c=getchar();
}return s*w;
}
const int N=1000010;
int n,m,a[N];
int Block,num[N],summ,ans[N];
struct node{
int l,r,id;
}Q[N];
/*
m表示询问数量
*/
il bool cmp(node c,node d){
if(c.l/Block != d.l/Block) return (c.l/Block) < (d.l/Block);
else return c.r<d.r;
}
il void deal(int pos,int y)
{
if(num[a[pos]]==a[pos]) summ--;
else if((num[a[pos]]+y)==a[pos]) summ++;
num[a[pos]]+=y;
}
int main()
{
n=read(),m=read();
for(re int i=1;i<=n;i++) a[i]=read();
for(re int i=1;i<=m;i++){
Q[i].l=read(),Q[i].r=read(),Q[i].id=i;
}
Block=sqrt(n);
sort(Q+1,Q+1+m,cmp);
int ll=1,rr=0;
for(re int i=1;i<=m;i++){//关系要注意
while(rr<Q[i].r) deal(++rr,1);
while(ll>Q[i].l) deal(--ll,1);
while(ll<Q[i].l) deal(ll++,-1);
while(rr>Q[i].r) deal(rr--,-1);
ans[Q[i].id]=summ;
}
for(re int i=1;i<=m;i++){
printf("%d\n",ans[i]);
}
return 0;
}
100分：树状数组
首先将问题离线，按右端点排序
设num[i]表示数值为i的数字有多少个
然后右端点每次移动，都单点更新num，然后更新贡献，统计区间和就可以了
关键是：怎么统计贡献？
我们发现，对于每一个数字a[i],当num[a[i]（算上自己）恰好有a[i]个时，会对答案有贡献
因为是按照右端点排序，所以将贡献记在左端点上，如果记在别的地方就会多统计贡献
因为当每一个数字最后一次出现的下标发生变化之后，贡献标记的位置发生了变化，所以
还要移动贡献标记，为此我们用vector存前面数值相同的数字的下标
然鹅，这样做不够……
e.g.
设数值为3的数字的下标：
5 8 17 66 81 92 97
如果66是最后出现的3的位置，那66的贡献记在17上面。
而当右端点位于[66,80]时，左端点在[6,8]则答案+1，在[1,5]
里则答案不变，所以作为补偿，在5处打上补偿标记-1。
同样地，补偿标记也要移动。
当左端点移动到[81,91]时，-1要记在8头上，1要记在17头上
此时，5处+1,8处-1,17处+1
单点修改，区间查询-----> 树状数组
对于每一种值，需要存一个链表（或者队列）来索引下标
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
il int read()
{
int s=0,w=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') w=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+c-'0';c=getchar();
}
return s*w;
}
const int N=1e6+10;
int n,m,a[N],L[N],R[N],id[N],ans[N];
int TR[N];
vector<int> v[N];
il bool cmp(int x,int y){
if(R[x]!=R[y]) return R[x]<R[y];
else return L[x]<L[y];
}
il int lowbit(int x){ return x&(-x); }
il void upd(int x,int y)
{
while(x<=n){
TR[x]+=y;x+=lowbit(x);
}return ;
}
il int getsum(int x){
int res=0;
while(x>0){
res+=TR[x];
x-=lowbit(x);
}return res;
}
int main()
{
n=read(),m=read();
for(re int i=1;i<=n;i++) a[i]=read();
for(re int i=1;i<=m;i++){
L[i]=read(),R[i]=read(),id[i]=i;
}
sort(id+1,id+1+m,cmp);
int p=1;
for(re int i=1;i<=n;i++){
v[a[i]].push_back(i);
int sz=v[a[i]].size();
if(sz==a[i]) upd(v[a[i]][sz-a[i]],1);//打上贡献标记
else if(sz==a[i]+1){
upd(v[a[i]][sz-a[i]-1] , -2);//打上补偿标记
upd(v[a[i]][sz-a[i]],1);//移动贡献标记
}
else if(sz>a[i]+1){
upd(v[a[i]][sz-a[i]-2],1);
upd(v[a[i]][sz-a[i]-1],-2);//移动补偿标记
upd(v[a[i]][sz-a[i]],1);
}
while(p<=m && R[id[p]]==i){
ans[id[p]]=getsum(R[id[p]])-getsum(L[id[p]]-1);
p++;
}
}
for(re int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
排序没用结构体，这样应该常数会小一些。
end