paulzrm's blog

发表于 分类于

本文迁移自洛谷原文。

高精度对于 Python 来说不是个事。

思路与原版相同。

1
2
3
4
5
6
7
8
import math
n = int(input())
l = int(math.log(n - 1, 2)) + 1
res = n * l
res = res - 2 ** l
res = res + 1
t = n * (n - 1) // 2
print(min(res, t) % 100000007)

发表于 分类于

本文迁移自洛谷原文。

水题，直接暴力就能过

由于图很大，所以就不能直接连边最小生成树

所以我们可以换一个角度考虑:

求出所有可以用0边连成的联通块，那么将这些联通快连起来，就可以构造出一颗最小生成树

那么怎么求联通快呢?

直接dfs是可以的！

但是需要剪枝

最短代码

set s:还有哪些点没有被访问过
由于只有一些边是1边，所以几次下来，就几乎全访问过了

map<int,int> g[]: 存所有的1边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
map<int,int>g[200005];
set<int>s,ns;
inline void dfs(int x){
	vector<int>v;v.clear();ns.clear();
	for(set<int>::iterator it=s.begin();it!=s.end();it++)if(!g[x][*it])v.push_back(*it);else ns.insert(*it);  //只用在没有经过的点中找
	s=ns;//更新
  for(int i:v)dfs(i);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;++i)scanf("%d%d",&u,&v),g[u][v]=1,g[v][u]=1;
	for(int i=1;i<=n;++i)s.insert(i);
	for(;s.size();){++cnt;int t=*s.begin();s.erase(t);dfs(t);}
	printf("%d\n",cnt-1);
}

发表于 分类于

本文迁移自洛谷原文。

这是什么题目啊，竟然回爆long long…..

这里介绍一个不用压位的方法

思路：

分类讨论即可

1.直接加上所有的y-x

2.单独处理所有的|x-y|$\le$1的情况

复杂度:O(n)

map是O(n log n)

注意:对于爆long long 的情况，可以用long double

只不过会慢一点，而且精度只比long long 大一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define ld long double
#define ll long long
using namespace std;
const int mxn=200005;
map<ld,ld>cnt_m;
ld l_cnt[mxn],h_cnt[mxn],sum[mxn],ans,n,a[mxn];
int main(){
	cin>>n;
	for(ll i=1;i<=n;++i)cin>>a[i];
	for(ll i=n;i;--i){            //从后往前统计，就不用二分了
		++cnt_m[a[i]];
		l_cnt[i]=cnt_m[a[i]-1];
		h_cnt[i]=cnt_m[a[i]+1];
		sum[i]=sum[i+1]+a[i];
	}
	for(ll i=1;i<=n;++i)ans+=sum[i]-a[i]*(n-i+1)+l_cnt[i]-h_cnt[i];
	cout<<fixed<<setprecision(0)<<ans<<endl;  //一定要控制输出的小数位为0！否则会输出类似于1e9+09之类的东西
}
0%