写一下把我吊着打的离线赛总结 (?)

\(update\) \(2020.10.3\)

学会的东西：

struct p30
{

}p30;

什么的 （就可以完美地水暴力了

然后就50pts暴力写错了 胡的正解是对的23333

---

P1311 [NOIP2011 提高组] 选择客栈

丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0∼k−1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。

两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p 。

他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。

输入格式
共 n+1 行。

第一行三个整数 n, k, p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；

接下来的 n 行，第 i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色调 a[i]和 i 号客栈的咖啡店的最低消费 b[i]。

被欺骗了的50pts

其实k的范围并不大 刚好不会爆空间

然后暴力就错了。 错了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N= 200005, N2= 1005, K= 55;

int t[N], w[N];
ll cnt[N][K]; int M[N2][N2];
int n, k, p; 
int ne[N];

void init()         //预处理出的ne数组表示最前面可以放到哪
{
	memset(ne, -1, sizeof ne);
	for(int i=1; i<=n; i++) 
		if(w[i]<= p) ne[i]= i;

	for(int i=n- 1; i>=1; i--) 
	{
		if(ne[i]== i) continue;
		ne[i]= ne[i+ 1]; 
	}
	return ;
}

struct p50
{
	void get()
	{
		memset(M, 0x3f, sizeof M);
		for(int i=1; i<=n; i++)
		   for(int j=i+ 1; j<=n; j++) M[i][j]= min(M[i][j- 1], w[j]);    //是这里错了啊 应该是for(int j=i; j<=n; j++)  事实证明大样例拉胯
		return ; 
	} 
	void solve()
	{
		get();
		ll cnt= 0;
		for(int i=1; i<=n; i++) 
		   for(int j=i+ 1; j<=n; j++) 
		      if(t[i]== t[j]&& M[i][j]<= p) cnt++ ;
		printf("%lld\n", cnt);
		exit(0);  
	}
}p50;

int main()
{
//	freopen("hotel.in", "r", stdin);
//	freopen("hotel.out", "w", stdout);
	cin>> n>> k>> p;
	for(int i=1; i<=n; i++) scanf("%d%d", &t[i], &w[i]);
//	if(n<= 1000) p50.solve();               //被注释掉就AC的东西
	for(int i=1; i<=n; i++) cnt[i][t[i]]++ ;
	
	for(int i=1; i<=n; i++)
	   for(int j=0; j<k; j++) cnt[i][j]+= cnt[i- 1][j];    //cnt[i][j]表示第i个位置之前的颜色j有多少种
    ll ans= 0;
    init();
    for(int i=1; i<=n; i++)
    {
    	if(ne[i]== -1) continue;
    	int j= ne[i];
    	ans+= (ll)cnt[n][t[i]]- cnt[j- 1][t[i]];
    	if(i== j&& (ll)cnt[n][t[i]]- cnt[j- 1][t[i]]!= 0) ans-- ;      //减去自身 当然不用特判后面那个条件    留下来做纪念qaq
	}
    
	cout<< ans<< endl;
    return 0;
}

赛后才发现我写得非常垃圾qaq

有一个加强版加强了k的范围 就是卡这个算法的

其实可以记last数组 枚举第二个

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N= 2* 1e6+ 5, K= 1e4+ 5;
int t[N], w[N], cnt[K], last[N];

int main()
{
	int n, k, p; cin>> n>> k>> p; 
	for(int i=1; i<=n; i++) scanf("%d%d", &t[i], &w[i]);
	memset(last, -1, sizeof last);
	for(int i=1; i<=n; i++) 
	{
		if(w[i]<= p) last[i]= i;
		else last[i]= last[i- 1];
	}
	
	int pre= 0; ll ans= 0;
	for(int i=1; i<=n; i++)
	{
		if(last[i]== -1) continue;
		for(int j=pre+ 1; j<=last[i]; j++) cnt[t[j]]++ ;
		ans+= cnt[t[i]]- (last[i]== i); pre= last[i];
	}
	cout<< ans<< endl;
	return 0;
}

当然也有更简单的 把last求的过程放在循环里面 因为好像优化不了什么就不写了

题外话：老师说这道题没A的同学好好想想这几年学了些什么23333

---

没完整版题目和代码谅解

题目大概就是说给定一个长度为n的序列， q次询问， 每次询问一个l[i], r[i]问区间中有没有重复的数

数据范围好像卡掉了 \(O(nlogn)\) 的东西qaq （关键是我 \(O(nlogn)\) 的也不会啊

被虐爆的一天 只会 \(O(qn)\) 的60pts 好在部分分给得很足

我们可以先离散化， 然后60pts到手， 跑路

正解： 我们可以存一个 pre[i] 表示第i个前面离第i个最近的和他相同的数是什么

每次询问就要求 max(pre[l[i]]——pre[r[i]])中有没有大于等于l[i]的

这时你就可以打一个st表 复杂度什么的应该是可以的

再看一下max(pre[l[i]]——pre[r[i]])可以转换成max(pre[1]——pre[r[i]])

然后就是前缀和了

然后这题最难的其实是排序， 需要 \(O(n)\) 的排序， 数的范围1e9

基数排序什么的手写一下就好了。https://www.luogu.com.cn/blog/lqt121720/ji-shuo-pai-xu

---

[https://www.luogu.com.cn/problem/P1314]([NOIP2011 提高组] 聪明的质监员)

明显（？）的二分题

然后被我搞成了三分23333

大概

while(l< r)
	{
		int mid= (l+ r+ 1)>> 1;
		if(check(mid)>= check(mid+ 1)) l= mid;
		else r= mid- 1; 
	}

这种

发现三分只能求答案可以多个但是不是答案的一定要是一个的东西 (错了拍醒我 我们这道题是不可能的满足的

所以我们可以二分求出一个小于等于s的最大的

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N= 200005;
int w[N], v[N];
int cnt[N], val[N];
int l1[N], r1[N]; 
int n, m; int s; 
int maxn= 0;

int check(int x)
{
	memset(cnt, 0, sizeof cnt);
	memset(val, 0, sizeof val);
	for(int i=1; i<=n; i++)
	{
		if(w[i]>= x) cnt[i]++ , val[i]+= v[i];
	}
	for(int i=1; i<=n; i++) cnt[i]+= cnt[i- 1], val[i]+= val[i- 1];
	int ans= 0;
	for(int i=1; i<=m; i++)
		ans+= (int)(cnt[r1[i]]- cnt[l1[i]- 1])* (val[r1[i]]- val[l1[i]- 1]);
	return ans;
}

signed main()
{
	cin>> n>> m>> s;
	for(int i=1; i<=n; i++) 
	{
		scanf("%lld%lld", &w[i], &v[i]);
		maxn= max(maxn, w[i]);
	}
    for(int i=1; i<=m; i++)
    	scanf("%lld%lld", &l1[i], &r1[i]);
    int l= 0, r= maxn+ 1;
	int ans= (int)1e18;
	while(l< r)
	{
		int mid= (l+ r)>> 1;
		int x= check(mid);
		ans= min(ans, abs(x- s));
		if(x> s) l= mid+ 1;
		else r= mid;
	}
	cout<< ans<< endl;
	
	return 0;
}