新疆大学ACM-ICPC程序设计竞赛五月月赛（同步赛） H XOR
链接：https://www.nowcoder.com/acm/contest/116/H
来源：牛客网
题目描述
Once there was a king called XOR, he had a lot of land. Because of his name, he likes to play XOR games.
One day, he whimpered and wanted to establish N cities on that vast expanse of land, numbered 0, 1, 2..., N-1. He wanted to connect all the cities. If city A can reach City B through zero or one or several cities, then A and B are connected. The cost of repairing a road in City A and City B is the XOR value of number of City A and number of City B. This King XOR wanted to figure out the minimum cost for connecting all of the N cities.
Of course, like a fairy tale read as a child, there will be corresponding rewards after helping the king. If you help the king solve his problems, he will improve your ranking in the competition.
输入描述:
There are multi test cases
each test cases contains an integer N (2 ≤N≤ 20000), the number of cities the king wants to establish.
输出描述:
For each test case, print the minimum cost for connecting all of the N cities in one line.
输入
4
输出
4
说明
The weightof the minimum cost is 1+2+1=4 In the Sample Example.
题目的原意应该是求一个最小生成树。两点之间的权值就是点编号的异或值。
直接按题目意思来肯定是不行的，建不了这么大的图。。
然后按照最小生成树的思想想一下就会发现，由于两点之间的权值是固定的，那么n个点得到最小生成树的结果其实就是在n-1个点的基础上加上n-1这个点连接0~n-2中的最小权值，由于连接的点都比n-1小，那么与n-1异或值最小的m，应满足 其二进制中除开n-1的二进制数中最后一个1的位置不同，其他位都相同。
毕竟异或是相同就为0，不同就为1。
emmmm 然后就直接打表处理~~
// Asimple #include <bits/stdc++.h> #define debug(a) cout<<#a<<" = "<<a<<endl using namespace std; typedef long long ll; const int maxn = 20000 + 5; ll T, n, sum, num, m, t, len, ans; ll fa[maxn]; ll qpow(ll n) { ll ans = 1; ll a = 2; while( n ) { if( n&1 ) ans *= a; a = a*a; n >>= 1; } return ans; } ll count(ll n) { ll ans = 0; while( n%2 == 0 ) { n /= 2; ans ++; } return ans; } void init() { fa[2] = 1; for(int i=3; i<maxn; i++) { fa[i] = fa[i-1] + qpow(count(i-1)); } } void input() { init(); while( ~scanf("%d", &n) ){ cout << fa[n] << endl; } } int main() { input(); return 0; }
字节跳动公司福利 1371人发布