期望得分：100+30+60=190
实际得分：100+30+30=160
T1
最优方案跳的高度一定是单调的
所以先按高度排序
dp[i][j] 跳了i次跳到j
枚举从哪儿跳到j转移即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 51 struct node
{
int c,h;
}e[N]; int dp[N][N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool cmp(node p,node q)
{
return p.h<q.h;
} int main()
{
freopen("meet.in","r",stdin);
freopen("meet.out","w",stdout);
int n;
read(n);
for(int i=;i<=n;i++) read(e[i].c);
for(int i=;i<=n;i++) read(e[i].h);
sort(e+,e+n+,cmp);
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++) dp[][i]=e[i].c;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
for(int k=;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i-][k]+e[j].h-e[k].h);
dp[i][j]+=e[j].c;
}
int t;
read(t);
for(int i=n;i>=;i--)
for(int j=;j<=n;j++)
if(dp[i][j]<=t) { printf("%d",i+); return ; }
}
T2
设给出的数是b1，b2，……
解为a1，a2……
那么可以得到 b1=a1+a2，b2=a1+a3
如果再知道 a2+a3=X，就可以解出a1，a2，a3
在b中把b1 b2 X 删去
剩下的最小的一定是 a1+a4，解出a4
再把a2+a4 ，a2+a4 删去,剩下的最小的一定是a1+a5
以此类推，解出所有的a
即
每确定一个ai
就把 aj+ai j∈[1,i) 全删去
剩下的最小的一定是a1 和ai+1 的和
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; int n,m,tot; #define N 302 int b[N*N]; int ans[N*N][N],t[N]; bool use[N*N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void work(int x)
{
if((b[]+b[]+b[x])&) return;
t[]=b[]-b[]+b[x]>>;
t[]=b[]-t[];
t[]=b[]-t[];
memset(use,false,sizeof(use));
use[]=use[]=use[x]=true;
int r,pos;
for(int i=,k=;i<=m;++i)
{
if(use[i]) continue;
t[k]=b[i]-t[];
for(int j=;j<k;++j)
{
r=t[j]+t[k];
pos=lower_bound(b+,b+m+,r)-b;
if(b[pos]!=r) return;
while(pos<m && use[pos] && b[pos]==r) pos++;
if(b[pos]!=r) return;
use[pos]=true;
}
k++;
}
tot++;
for(int i=;i<=n;i++) ans[tot][i]=t[i];
} int main()
{
freopen("city.in","r",stdin);
freopen("city.out","w",stdout);
read(n);
m=n*(n-)/;
for(int i=;i<=m;++i) read(b[i]);
sort(b+,b+m+);
for(int i=;i<=m;++i)
{
if(i> && b[i]==b[i-]) continue;
work(i);
}
printf("%d\n",tot);
for(int i=;i<=tot;++i)
{
for(int j=;j<=n;++j) printf("%d ",ans[i][j]);
printf("\n");
}
}
T3
分块
因为街灯上的数不超过1e4，所以p最多有1e4个
用vector[i][j] 存下%i=j 的数的位置 i<=100
当p<=100 时，直接在vector[p][v] 里二分在区间[l,r]内的最左位置和最右位置
再用一个vector[i] 存下所有的街灯数位i的位置
当p>100 时，%p=v 的数 有v，v+p，v+2p……
直接枚举这些数，最多100个，在vector[i] 里 二分 在区间[l,r]内的最左位置和最右位置
#include<cstdio>
#include<vector>
#include<iostream> using namespace std; #define N 100001 int a[N]; vector<int>V1[][];
vector<int>V2[]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
freopen("light.in","r",stdin);
freopen("light.out","w",stdout);
int n,m;
read(n); read(m);
for(int i=;i<=n;++i) read(a[i]),V2[a[i]].push_back(i);
for(int i=;i<=;++i)
for(int j=;j<=n;++j)
V1[i][a[j]%i].push_back(j);
int l,r,p,v;
int L,R,MID,TMP1,TMP2;
int pos,tot;
while(m--)
{
read(l); read(r); read(p); read(v);
if(p<=)
{
L=; R=V1[p][v].size()-;
TMP1=TMP2=-;
while(L<=R)
{
MID=L+R>>;
if(V1[p][v][MID]>=l) TMP1=MID,R=MID-;
else L=MID+;
}
if(TMP1==-) { puts(""); continue; }
L=TMP1; R=V1[p][v].size()-;
while(L<=R)
{
MID=L+R>>;
if(V1[p][v][MID]<=r) TMP2=MID,L=MID+;
else R=MID-;
}
if(TMP2==-) { puts(""); continue; }
printf("%d\n",TMP2-TMP1+);
}
else
{
pos=v; tot=;
while(pos<=)
{
L=; R=V2[pos].size()-;
TMP1=TMP2=-;
while(L<=R)
{
MID=L+R>>;
if(V2[pos][MID]>=l) TMP1=MID,R=MID-;
else L=MID+;
}
if(TMP1==-) { pos+=p; continue; }
L=TMP1; R=V2[pos].size()-;
while(L<=R)
{
MID=L+R>>;
if(V2[pos][MID]<=r) TMP2=MID,L=MID+;
else R=MID-;
}
if(TMP2==-) { pos+=p; continue; }
tot+=TMP2-TMP1+;
pos+=p;
}
printf("%d\n",tot);
}
}
}
60分暴力
#include<vector>
#include<cstdio>
#include<iostream> using namespace std; #define N 100001 int n,m,a[N]; int P; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} namespace solve1
{
int l,r,p,v,ans;
void work()
{
while(m--)
{
read(l); read(r); read(p); read(v);
ans=;
for(int i=l;i<=r;i++)
if(a[i]%p==v) ans++;
printf("%d\n",ans);
} }
} namespace solve2
{
vector<int>V[];
void work()
{
int l,r,p,v;
int L,R,MID,TMP1,TMP2;
for(int o=;o<=m;o++)
{
read(l); read(r); read(p); read(v);
if(o==)
{
P=p;
for(int i=;i<=n;i++) V[a[i]%P].push_back(i);
}
if(v> || !V[v].size()) { puts(""); continue; }
L=,R=V[v].size()-; TMP1=-;
while(L<=R)
{
MID=L+R>>;
if(V[v][MID]>=l) TMP1=MID,R=MID-;
else L=MID+;
}
if(TMP1==- || V[v][TMP1]>r) { puts(""); continue; }
L=TMP1,R=V[v].size()-; TMP2=-;
while(L<=R)
{
MID=L+R>>;
if(V[v][MID]<=r) TMP2=MID,L=MID+;
else R=MID-;
}
if(TMP2==-) { puts(""); continue; }
printf("%d\n",TMP2-TMP1+);
}
}
} void init()
{
read(n); read(m);
for(int i=;i<=n;i++) read(a[i]);
if(1ll*n*m<=1e6) solve1::work();
else solve2::work();
} int main()
{
freopen("light.in","r",stdin);
freopen("light.out","w",stdout);
init();
}