Rain_chr @ 2023-01-15 15:52:58
众所周知，离散化+暴力乱搞是没有办法过这道题的，因为他会将中间的可见部分抹去。但是，我在中间随机选了一百个点，也加入离散化，就可以通过了。
显然，还是不能让这种暴力乱搞通过的，所以建议加强数据。
哦对了，如果有人证明这是正解的一种，那就当我没说。
贴代码
#include<bits/stdc++.h>
using namespace std;
struct node
{
int start,end;
}bill[1010];
map<int,int> num;
bool wall[100010];
int main()
{
srand(time(0));
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&bill[i].start,&bill[i].end);
for(int i=1;i<=m;i++)
{
num[bill[i].start]=0;
for(int j=1;j<100;j++)
num[rand()%(bill[i].end-bill[i].start+1)+bill[i].start]=0;
num[bill[i].end]=0;
}
int cnt=0;
map<int,int>::iterator it;
it=num.begin();
while(it!=num.end())
{
it->second=++cnt;
it++;
}
for(int i=1;i<=m;i++)
{
bill[i].start=num[bill[i].start];
bill[i].end=num[bill[i].end];
}
int ans=0;
for(int i=m;i;i--)
{
bool flag=0;
for(int j=bill[i].start;j<=bill[i].end;j++)
{
flag|=!wall[j];
wall[j]=1;
}
ans+=flag;
}
cout<<ans;
return 0;
}by liangbowen @ 2023-01-15 15:55:11
太菜了。直接暴力就可以过掉。
#include <iostream>
#include <cstdio>
using namespace std;
int read() {char op = getchar(); int x = 0; while (op < 48 || op > 57) op = getchar(); while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar(); return x;}
const int N = 1e7 + 5;
int a[N];
bool vis[N];
int main()
{
int n = read(), m = read();
for (int x = 1; x <= m; x++)
{
int u = read(), v = read();
for (int i = u; i <= v; i++) a[i] = x;
}
int ans = 0;
for (int i = 1; i <= n; i++)
if (a[i] && !vis[a[i]])
ans++, vis[a[i]] = true;
cout << ans;
return 0;
}by AKPC @ 2023-01-15 16:26:36
@liangbowen bushi，lz是我们集训队的巨佬
by AKPC @ 2023-01-15 16:29:44
诶嘿嘿，赶紧写个暴力
by liangbowen @ 2023-01-15 20:15:38
@A_Passing_Creeper 太菜了指的是不需要这么复杂的乱搞，因为暴力就能过（
by PNNNN @ 2023-02-05 19:17:26
@违规用户名684254 这道题就真离谱，m太小了，暴力枚举都能过
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,tot=0,id=0,cnt[1000005];
struct poster{
int l,r,k;
};
vector <poster> a;
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
id++;
cnt[id]++;
tot++;
for(int j=0;j<a.size();j++){
if(a[j].l>r||a[j].r<l)continue;
if(l<=a[j].l&&r>=a[j].r){
cnt[a[j].k]--;
if(cnt[a[j].k]==0){
tot--;
}
}else if(a[j].l<l&&a[j].r<=r) {
a[j].r=l-1;
}else if(a[j].l>=l&&a[j].r>r){
a[j].l=r+1;
}else if(a[j].l<l&&a[j].r>r){
cnt[a[j].k]++;
a.push_back((poster){r+1,a[j].r,a[j].k});
a[j].r=l-1;
}
}
a.push_back((poster){l,r,id});
//cout<<tot<<endl;
}
cout<<tot;
return 0;
}by Rain_chr @ 2023-02-05 22:06:34
@PNNNN 就我后来真补了一个线段树 （
by PNNNN @ 2023-02-09 19:38:33
@违规用户名684254 期末考有说法吗
by Rain_chr @ 2023-02-10 20:29:41
@PNNNN 作文题目是路上，我当时就想上路
by AKPC @ 2023-02-16 22:12:15
@违规用户名684254 @PNNNN
所以数据加强了吗
by corrupted_random @ 2023-02-19 18:52:14
没，暴力还是能过