最近模拟赛神TM多
几场模拟赛乱搞记(?!)
最近模拟赛好像挺多？
让我想想，loli的一场，zyx学长的一场，舒老师的一场……zyx学长的那场险些爆零(明明是题太毒瘤)，剩下两场似乎还是有良心题目的。
3月5日
T1窗口的星星
这道题好像考试前一天被我押中了？但是由于太难只看了看正解思路，也懒得实现代码……结果考场上一波GG。还好loli的数据比较水，乱搞A掉了。
先讲一下思路。对于每个星星，我们把它作为一个矩形的重心，然后如果把窗口的重心放在两个矩形相交的地方，我们就可以覆盖这两颗星星。那么我们就把这个题转化成了一堆矩形，而我们要求的就是那些个矩形的交亮度最大。
由于数据范围恶心所以要先离散化。怎么离散化呢？我们先把所有的矩形竖边按照横坐标排序，这样就可以用扫描线压掉横坐标这一维，然后我们来扫这些竖边，竖边能重合的最多的次数就是我们要求的。所以我们可以把入边和出边做相反的标记，之后用纵坐标来建树。这里就要离散了，我们只需要把能用的纵坐标编一下号，建树按照编号建树就可以了。
每次扫到一条入边，就给线段树相应的一段加上星星的亮度，出边就减去。线段树维护区间max就可以搞定了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define inv inline void
#define inb inline bool
#define inl inline long long
#define rll register long long
#define ll long long
#define maxn 100010
#define mid (l+r>>1)
#define ls (num<<1)
#define rs (num<<1|1)
using namespace std;
long long t,n,w,h,s[maxn<<2],tot,tt,ans,sum[maxn<<3],tag[maxn<<3];
inl read()
{
char c;rll r=0,f=1;
c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
r=r*10+(c^48);
c=getchar();
}
return r*f;
}
struct node
{
long long u,d,x,f;
}line[maxn<<2];
inb cmp(node a,node b)
{
return a.x<b.x;
}
inl lb(ll x)
{
rll l=1,r=tt;
while (l<=r){
if (x==s[mid]) return mid;
if (x<s[mid]) r=mid-1;
else l=mid+1;
}
}
inv pushdown(ll num)
{
if (tag[num]!=0){
tag[ls]+=tag[num];tag[rs]+=tag[num];
sum[ls]+=tag[num];sum[rs]+=tag[num];
tag[num]=0;
}
}
inv pushup(ll num)
{
sum[num]=max(sum[ls],sum[rs]);
}
inv update(ll L,ll R,ll l,ll r,ll num,ll flag)
{
if (L<=l && r<=R){
sum[num]+=flag;
tag[num]+=flag;
return;
}
pushdown(num);
if (L<=mid) update(L,R,l,mid,ls,flag);
if (R>mid) update(L,R,mid+1,r,rs,flag);
pushup(num);
}
int main()
{
t=read();
while (t--){
n=read();w=read();h=read();
for (rll i=1;i<=n;i++){
rll xx,yy,x2,y2;
rll x=read(),y=read(),c=read();
xx=2*x-w+1;yy=2*y-h+1;
x2=2*x+w;y2=2*y+h;
line[++tot].x=xx;line[tot].f=c;
line[tot].d=yy;line[tot].u=y2;
s[tot]=yy;
line[++tot].x=x2;line[tot].f=-c;
line[tot].d=yy;line[tot].u=y2;
s[tot]=y2;
}
sort(s+1,s+tot+1);
tt=unique(s+1,s+tot+1)-(s+1);
sort(line+1,line+tot+1,cmp);
for (rll i=1;i<=tot;i++){
rll l=lb(line[i].d);
rll r=lb(line[i].u)-1;
update(l,r,1,tt,1,line[i].f);
ans=max(ans,sum[1]);
}
printf("%lld\n",ans);
ans=0;tot=0;
memset(sum,0,sizeof(sum));memset(tag,0,sizeof(tag));
memset(s,0,sizeof(s));memset(line,0,sizeof(line));
}
}
###T2 矩形周长
好像又让我押中一道？不过本懒又是只看了一下思想……
仿照上一题进行离散化，然后对于横纵坐标分别建树，分别扫描线，每次记录总长度变化的量的绝对值，最后都加起来就行了。至于加起来为什么是周长，网上都有，这里就不赘述了。
然后值得注意的一点就是如果一条入边和一条出边重合，我们排序的时候特判一下，先计算入边。因为如果先计算出边就会造成多变化一次——这么说太抽象，你可以画一个田字格的图自己理解一下……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define rint register int
#define inv inline void
#define ini inline int
#define inb inline bool
#define maxn 100010
#define mid (l+r>>1)
#define ls (num<<1)
#define rs (num<<1|1)
using namespace std;
int n,tot,tt1,tt2,sumh[maxn<<2],sums[maxn<<2],tagh[maxn<<2],tags[maxn<<2],h[maxn<<1],s[maxn<<1];
ini read()
{
char c;rint r=0,f=1;
c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
r=r*10+(c^48);
c=getchar();
}
return r*f;
}
struct LINEH
{
int l,r,y,f;
}lineh[maxn<<1];
struct LINES
{
int u,d,x,f;
}lines[maxn<<1];
inb cmph(LINEH a,LINEH b)
{
if (a.y==b.y) return a.f>b.f;
return a.y<b.y;
}
inb cmps(LINES a,LINES b)
{
if (a.x==b.x) return a.f>b.f;
return a.x<b.x;
}
ini lbh(int x)
{
int l=1,r=tt1;
while (l<=r){
if (x==h[mid]) return mid;
if (x<h[mid]) r=mid-1;
else l=mid+1;
}
}
int lbs(int x)
{
int l=1,r=tt2;
while (l<=r){
if (x==s[mid]) return mid;
if (x<s[mid]) r=mid-1;
else l=mid+1;
}
}
inv pushuph(int num,int l,int r)
{
if (tagh[num]){
sumh[num]=h[r+1]-h[l];
return;
}
if (l==r){
sumh[num]=0;
return;
}
sumh[num]=sumh[ls]+sumh[rs];
}
inv updateh(int L,int R,int l,int r,int num,int flag)
{
if (L<=l && r<=R){
tagh[num]+=flag;
pushuph(num,l,r);
return;
}
if (L<=mid) updateh(L,R,l,mid,ls,flag);
if (R>mid) updateh(L,R,mid+1,r,rs,flag);
pushuph(num,l,r);
}
inv pushups(int num,int l,int r)
{
if (tags[num]){
sums[num]=s[r+1]-s[l];
return;
}
if (l==r){
sums[num]=0;
return;
}
sums[num]=sums[ls]+sums[rs];
}
inv updates(int L,int R,int l,int r,int num,int flag)
{
if (L<=l && r<=R){
tags[num]+=flag;
pushups(num,l,r);
return;
}
if (L<=mid) updates(L,R,l,mid,ls,flag);
if (R>mid) updates(L,R,mid+1,r,rs,flag);
pushups(num,l,r);
}
int main()
{
n=read();
for (rint i=1;i<=n;i++){
rint xx,yy,x2,y2;
xx=read();yy=read();x2=read();y2=read();
lineh[++tot].y=yy;lineh[tot].f=1;
lineh[tot].l=xx;lineh[tot].r=x2;
lines[tot].x=xx;lines[tot].f=1;
lines[tot].d=yy;lines[tot].u=y2;
h[tot]=xx;s[tot]=yy;
lineh[++tot].y=y2;lineh[tot].f=-1;
lineh[tot].l=xx;lineh[tot].r=x2;
lines[tot].x=x2;lines[tot].f=-1;
lines[tot].d=yy;lines[tot].u=y2;
h[tot]=x2;s[tot]=y2;
}
sort(h+1,h+tot+1);
tt1=unique(h+1,h+tot+1)-(h+1);
sort(s+1,s+tot+1);
tt2=unique(s+1,s+tot+1)-(s+1);
sort(lineh+1,lineh+tot+1,cmph);
sort(lines+1,lines+tot+1,cmps);
int lst=0,ans=0;
for (rint i=1;i<=tot;i++){
int l=lbh(lineh[i].l);
int r=lbh(lineh[i].r)-1;
updateh(l,r,1,tt1,1,lineh[i].f);
ans+=abs(sumh[1]-lst); lst=sumh[1];
}
lst=0;
for (rint i=1;i<=tot;i++){
int l=lbs(lines[i].d);
int r=lbs(lines[i].u)-1;
updates(l,r,1,tt2,1,lines[i].f);
ans+=abs(sums[1]-lst); lst=sums[1];
}
printf("%d",ans);
}
T3 TET
这个由于考场时思路错了所以没搓出来……
由于我是考后抄的题解，所以大家可以去看黄学长博客。代码简单易懂，特别是树套树的写法很有灵性。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ls (num<<1)
#define rs (num<<1|1)
using namespace std;
int d,s,n,qu,qd,qr,ql;
int read(){
char c;int r=0,f=1;
c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
r=r*10+(c^48);
c=getchar();
}
return r*f;
}
struct treeX{
int sg[3005],cov[3005];
void change(int L,int R,int l,int r,int x,int num){
sg[num]=max(sg[num],x);
if (L<=l && r<=R){
cov[num]=max(cov[num],x);
return;
}
int mid=(l+r)>>1;
if (L<=mid) change(L,R,l,mid,x,ls);
if (R>mid) change(L,R,mid+1,r,x,rs);
}
int query(int L,int R,int l,int r,int num){
if (L<=l && r<=R) return sg[num];
int maxx=cov[num];
int mid=(l+r)>>1;
if (L<=mid) maxx=max(maxx,query(L,R,l,mid,ls));
if (R>mid) maxx=max(maxx,query(L,R,mid+1,r,rs));
return maxx;
}
};
struct treeY{
treeX sg[3005],cov[3005];
void change(int L,int R,int l,int r,int x,int num){
sg[num].change(qd,qu,1,s,x,1);
if (L<=l && r<=R){
cov[num].change(qd,qu,1,s,x,1);
return;
}
int mid=(l+r)>>1;
if (L<=mid) change(L,R,l,mid,x,ls);
if (R>mid) change(L,R,mid+1,r,x,rs);
}
int query(int L,int R,int l,int r,int num){
if (L<=l && r<=R) return sg[num].query(qd,qu,1,s,1);
int maxx=cov[num].query(qd,qu,1,s,1);
int mid=(l+r)>>1;
if (L<=mid) maxx=max(maxx,query(L,R,l,mid,ls));
if (R>mid) maxx=max(maxx,query(L,R,mid+1,r,rs));
return maxx;
}
}T;
int main(){
d=read();s=read();n=read();
for (int i=1;i<=n;i++){
int c=read(),k=read(),g=read(),x=read(),y=read();
++x;++y;ql=x,qr=x+c-1,qd=y,qu=y+k-1;
int ans=T.query(ql,qr,1,d,1);
T.change(ql,qr,1,d,ans+g,1);
}
qd=1;qu=s;
printf("%d",T.query(1,d,1,d,1));
}
3月10日
不想描述今天的比赛。zyx学长简直有毒。
前两道题分别是斜率优化DP和马拉车，都没学过
最后一道线段树+set贼恶心，学长都没有A掉的
这里要%一下ljx大佬，考后切掉了这三道题，大家可以去一下ljx的博客。
3月11日
舒老师出的比赛比较良心，起码有一道可做题。
T2T3一道黑题一道提答题，直接放弃。
不过学长们玩魔塔还真是欢脱，顺便%一下Asia大佬轻松通关无数次
唯一会做的一道题 misswalmart
给的链接是一道叫上升序列的题，这道题就是由上升序列改过来的。
但是毕竟是改过来的，所以不要当做一道题。上一下题面
题目背景
政府出了新政策，特邀 OI 落后的乡村的教师来南方学习。于是，副村长LX就带着S老师和Refun老师， 踏上了飞向南方的飞机。。。。。。
当然，他们是去学（颓）习（废）的。
迷失沃尔玛
题目描述
到南方的第一天晚上，副村长 LX 就坐不住了！看着繁华的街市，副村长 LX 兴冲冲地去逛街买东西。可是她不小心在一座大商场沃尔玛迷路了。然而副村长 LX 很镇定，毕竟她已经迷路过几万次了，也不差这一次了。
在逛沃尔玛的时候，副村长LX发现了一排n个美丽的商品。每个商品都有自己的价格。LX 想从左往右挑选 X 个商品，使得它们的价格从左往右看，是单调上升的。如果有多种选择，她希望这些商品的“商品价格序”最小。
但LX不想动脑子，她还想留点精力找回去的路呢！作为吃瓜群众
的你，自然是要帮她一把了对吧！
注： “最小商品价格序”是指：假设你选择了A1、A2、A3/A4….Ax 这些商品，那么你要确保 A1 的权值最小，若不唯一，再确保 A2的权值最小……（即以权值为关键字的字典序）
输入格式
输入的第一行为一个整数n——商品的个数。
下一行n个整数，表示1~n号商品的价格。
下一行一个整数Q，表示Q次询问
接下来Q行， 每行有一个整数X， 表示询问长度为X的上升序列。
输出格式
输出为 Q 行，对于每个询问，如果对应的序列存在，则输出，否则打印LXALWAYSMISS
输入样例
10
8531 21017 12567 86 19807 30631 16280 25238 23448 4947
3
3
2
6
输出样例
86 16280 23448
86 4947
LXALWAYSMISS
数据规模与约定
对于30%的数据，1≤n≤100，1≤Q≤100
对于100%的数据，1≤n≤10000, 1≤Q≤1000，1≤Ai≤10000000
这个题一开始我觉得是DP，结果死活推不出来……本着是自己太傻逼了的心态又去尝试了网络流的做法和平衡树的做法，不过似乎都失败了……
于是自暴自弃开始瞎搞，想用一个堆来xjb贪……贪着贪着慢慢完善思路忽然发现好像搓出了正解？
当然正解是不需要堆的。只需要建一个结构体p，对于p[i]我们包括三个变量：
p[i].id表示第i个数的下标
p[i].l表示以第i个数为开头的最长上升子序列的长度
p[i].z表示第i个数的值
这样就好办了。对于我们查询的任何长度的最长上升子序列，其中任意两个相邻的元素都能满足后者下标大于前者，值大于前者，以后者为开头的最长上升子序列的长度小于前者。然后把它看成一个堆，按照值为第一关键字，id为第二关键字排序，然后满足条件就往外取数就好了。
顺便吐槽一句，fread神TM好使，加了跑的贼快……
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 10010
#define re register
using namespace std;
int a[maxn],f[maxn],n,q,maxx;
inline char gc()
{
static char buff[1000000],*S=buff,*T=buff;
return S==T&&(T=(S=buff)+fread(buff,1,1000000,stdin),S==T)?EOF:*S++;
}
int read(){
re char c;re int r=0,f=1;
c=gc();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=gc();
}
while (c>='0' && c<='9'){
r=r*10+(c^48);
c=gc();
}
return r*f;
}
int po[30];
void putout(int x){
if (!x){
putchar(48);
return;
}
if (x<0) putchar('-'),x=-x;
re int wt=0;
while (x) po[++wt]=x%10,x/=10;
while (wt) putchar(po[wt--]+48);
}
struct node{
int id,l,z;
}p[maxn];
inline bool cmp(node a,node b){
if (a.z==b.z) return a.id<b.id;
return a.z<b.z;
}
int main(){
freopen("misswalmart.in","r",stdin);
freopen("misswalmart.out","w",stdout);
n=read();
for (re int i=1;i<=n;i++) a[i]=read();
for (re int i=n;i>=1;i--){
f[i]=1;
for (re int j=i+1;j<=n;j++)
if (a[i]<a[j] && f[i]<f[j]+1)
f[i]=f[j]+1;
maxx=max(maxx,f[i]);
p[i].id=i;p[i].l=f[i];p[i].z=a[i];
}
sort(p+1,p+n+1,cmp);
q=read();
for (re int i=1;i<=q;i++){
re int x=read();
if (x>maxx){
puts("LXALWAYSMISS");
continue;
}
re int dqz=-1,now=0,lst=0;
for (re int j=1;j<=n;j++){
if (p[j].l>=x-now && p[j].id>lst && p[j].z>dqz){
lst=p[j].id;
dqz=p[j].z;
now++;
putout(p[j].z);putchar(' ');
}
if (now==x) break;
}
putchar(10);
}
}
赞 赏
蒟蒻的邮箱:xmzl200201@126.com
