[NOIp2011] luogu P1311 选择客栈
2024-08-27 20:50:48
我妈的抽象歌曲真 nb。
题目描述
给你 nnn 个点,每个点有两个参数 ci,dic_i,d_ici,di,给你一个数 DDD。定义一种方案合法,当且仅当你选出整数 i,j∈[1,n],i<j,ci=cji,j\in[1,n],i<j,c_i=c_ji,j∈[1,n],i<j,ci=cj,且存在一个整数 k∈(i,j)k\in(i,j)k∈(i,j) 使得 dk≤Dd_k\leq Ddk≤D。求合法方案数。
Solution 1
这是我口胡的做法。
注意到 ccc 特别小。每次枚举一个 ccc,然后枚举一个 ck≤Dc_k\leq Dck≤D,如果 kkk 前面有 xxx 个 cx=cc_x=ccx=c, 后面有 yyy 个 cy=cc_y=ccy=c,那么就把答案加 xyxyxy。时间复杂度 O(nk)O(nk)O(nk)。
还有一种思路就是你看到 ppp 其实也很小,然后还是用类似的方法做,可能更优吧,我也没怎么想。能卡过。
Solution 2 (Idea From ShawnZhou)
#include<cstdio>
#include<cstdlib>
#include<cstring>
const int MAXC=60;
int n,k,p;
int c,d;
int now;
int last[MAXC]; //上一个相同颜色的点的位置
int sum[MAXC];
int cnt[MAXC];
int ans=0;
int main(){
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=n;++i){
scanf("%d%d",&c,&d);
if(d<=p) now=i;
if(now>=last[c])
sum[c]=cnt[c];
last[c]=i;
ans+=sum[c];
++cnt[c];
}
printf("%d",ans);
}
最新文章
- Intent传递对象的两种方法
- SVN与TortoiseSVN实战:冲突详解(一)
- nodejs调试工具node-inspector入门随笔
- DATE 使用
- PHP - session编码和解码
- C#访问ORALCE数据库
- Java8新特性第3章(Stream API)
- xml 制作 RSS 订阅源
- PEP8 - Python编码规范
- BOM 浏览器对象模型_不超过 4 KB 的 document.cookie 对象
- Array Queries CodeForces - 797E
- MySQL5.7 锁定用户【转】
- hadoop from rookie to ninja - 1. Basic Architecture(基础架构)
- Beta阶段——第5篇 Scrum 冲刺博客
- [原创]delphi一次性批量在TScrollBox中显示N个复选框TCheckBox的源码
- zookeeper单机版安装
- SQL Server 中为何拥有db_owner权限的账号删除不掉数据库
- (原)ubuntu下cadvisor+influxdb+grafana+supervisord监控主机和docker的containers
- 微软开放了.NET 4.5.1的源代码
- Sqlite 语句 记录