AcWing 101. 最高的牛
原题链接
简单
作者:
呼和
,
2019-09-12 00:41:05
,
所有人可见
,
阅读 1791
题目做法 差分
没有用到pair 敲代码,为了思路。搞懂思路,少用库函数。对你思维提高很大的。
面对noip的同学的一种解答。
/*****************************************
Problem Name :
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int f[N];
int head[N],to[N],ne[N],len = 0;
int n , p , h , m;
void add(int a, int b)
{
to[len] = b;
ne[len] = head[a];
head[a] = len++;
}
bool find(int a, int b)
{
for(int i = head[a] ; i ; i = ne[i])
{
if(to[i] == b)
return false;
}
return true;
}
int main()
{
cin >> n >> p >> h >> m;
for(int i = 0 ; i < m ; i++)
{
int a, b;
cin >> a >> b;
if(a > b)
swap(a,b);
if(find(a,b))
{
add(a,b);
f[a+1]--,f[b]++;
}
}
for(int i = 1 ; i <= n ; i++ )
{
f[i] = f[i-1] + f[i];
}
int x = h - f[p];
for(int i = 1 ; i <= n ;i++)
cout << f[i] + x << endl;
}
少用库函数为啥不敲平衡树,库就是为了简化程序
杠精