当前位置 博文首页 > xiongyuqing的博客:2019上海网络赛icpc
?B. Light bulbs:
?
思路:对前端点排序,然后取前两个区间进行分析,分别为L1,R1,L2,R2。分L1==L2,R1<L2,R1>=L2,L1<L2&&R2<=R1,四种情况。每种情况去掉区间重复的,把剩下合法的区间压入队列中,注意剩下的区间是左区间减一,右区间加一后放入队列。
优先队列知识:
头文件:#include<queue>
创建一个优先队列priority_queue<数据类型,容器(必须数组实现),元素比较方式> ? [变量名]? 。后两个参数可不写
升序队列:priority_queue <int,vector<int>,greater<int> > q;
降序队列:priority_queue <int,vector<int>,greater<int> > q;
top访问队头元素,size 返回队列内元素个数,push 插入元素到队尾(并排序)
队友代码:
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
typedef pair<int, int> pp;
int main() {
int cas, n, m;
scanf("%d", &cas);
for (int i = 1; i <= cas; ++i) {
scanf("%d%d", &n, &m);
priority_queue<pp> que;
for (int i = 0; i < m; ++i) {
int l, r;
scanf("%d%d", &l, &r);
que.push(pp(-l, r));
}
int ans = 0;
while (!que.empty()) {
if (que.size() == 1)
break;
pp x = que.top();
que.pop();
pp y = que.top();
int l1 = -x.first, r1 = x.second;
int l2 = -y.first, r2 = y.second;
if (l1 == l2) {
que.pop();
if (r1 == r2)
continue;
int t1 = 0, t2 = 0;
if (r1 < r2) {
t1 = r1 + 1;
t2 = r2;
}
else {
t1 = r2 + 1;
t2 = r1;
}
if (t2 >= t1)
que.push(pp(-t1, t2));
}
else if (l2 > r1) {
ans += r1 - l1 + 1;
}
else if (l1<l2&&r1>=r2) {
int t = l2;
l2 = r2 + 1;
r2 = r1;
r1 = t - 1;
que.pop();
if (r1 >= l1)
que.push(pp(-l1, r1));
if (r2 >= l2)
que.push(pp(-l2, r2));
}
else if (l1 != l2 && r1 >= l2) {
int t = l2;
l2 = r1 + 1;
r1 = t - 1;
que.pop();
if (r1 >= l1)
que.push(pp(-l1, r1));
if (r2 >= l2)
que.push(pp(-l2, r2));
}
}
if (!que.empty()) {
pp p = que.top();
ans += p.first + p.second + 1;
}
printf("Case #%d: %d\n", i, ans);
}
return 0;
}
方法二:差分:https://blog.csdn.net/weixin_43705195/article/details/88370758
?概念:
如果有一数列 a[1],a[2],.…a[n]
且令 b[i]=a[i]-a[i-1],b[1]=a[1]
那么就有
a[i]=b[1]+b[2]+.…+b[i]
=a[1]+a[2]-a[1]+a[3]-a[2]+.…+a[i]-a[i-1]
此时b数组称作a数组的差分数组
换句话来说a数组就是b数组的前缀和数组 例:
原始数组a:9 3 6 2 6 8
差分数组b:9 -6 3 -4 4 2
可以看到a数组是b的前缀和
分析:首先我们得到一个原数组a,然后
设d[i]=a[i]-a[i-1] (1<i≤n,d[1]=a[1]);//差分数组
设f[i]=f[i-1]+d[i] (1<i≤n,f[1]=d[1]=a[1]);
设sum[i]=sum[i-1]+f[i] (1<i≤n,sum[1]=f[1]=d[1]=a[1])。//区间求和
那么现在有一个任务:
在区间[left,right]上加一个常数c。
我们可以利用原数组就是差分数组的前缀和这个特性,来解决这个问题。显然可得出公式:b[left]+=c,b[right+1]?=c
同样如果通过以上问题让求某一区间的和,那么前缀和也同样能够完成,但是如果操作的次数过大
那么前缀和显然会超时,但是同样有解决的方式例如 树状数组,线段树。
相对于代码长度而言,使用差分的思想求解会变得异常简单。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<functional>
#include<cmath>
using namespace std;
const int N = 1010;
int a[N], sum[N],f[N];//即b数组
int main(){
int n, m, q;
cin >> n >> m>>q;//n个数,m个操作,q次询问
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = n; i > 1; i--)//需要从大到小求
a[i] -= a[i - 1];//此时a[i]数组表示的是a的差分数组
for (int i = 1,x,y,k; i <= m; i++){
cin >> x >> y >> k;//在区间[x,y]内的每个数加上k
a[x] += k, a[y+1] -= k;//对区间两端的值进行修改
}
for (int i = 1; i <= n; i++){
f[i] = f[i - 1] + a[i];//就跟b数组一样,f[i]表示a[i]
sum[i] = sum[i - 1] + f[i];//自己理解为相当于前缀和
}
for (int i = 1,x,y; i <= q; i++){
cin >> x >> y;
cout << sum[y] - sum[x - 1] << endl;
}
return 0;
}
?代码转自:https://blog.csdn.net/Harington/article/details/100879278
思路:将前后端点记录在数组p.first中,p.second记录操作区间结尾,如果前缀和为奇数,说明此开关为开,直到下一个操作前,之间的开关都是开的,若为偶数则说明反复开了又关,不记录。
#include<iostream>
#include<cstring>
#include<math.h>
#include<algorithm>
#include<stdio.h>
#include<map>
using namespace std;
const int maxn = 2e3 + 10;
int N, M;
pair<int, int> p[maxn];
int main() {
int T, Case = 0;
scanf("%d", &T);
int Cnt = 0;
while(T--) {
Cnt = 0;
scanf("%d%d", &N, &M);
int L, R;
for(int i = 1; i <= M; ++i) {
scanf("%d%d", &L, &R);
p[Cnt++] = make_pair(L, 1);
p[Cnt++] = make_pair(R + 1, -1);
}
sort(p, p + Cnt);
int Ans = 0;
int Sum = 0;
for(int i = 0; i < Cnt; ++i) {
Sum += p[i].second;
if(Sum & 1)//如果这个开关是开的 ,那到下个最近的灯泡操作前灯都是开的
Ans += p[i + 1].first - p[i].first;
}
printf("Case #%d: %d\n", ++Case, Ans);
}
return 0;
}
?
?
?
?
?
cs