2021中国大学生程序设计竞赛（CCPC）网选赛（第一场）部分题解_ccpc原題

---

前言

随着8月28号下午5点一到，今年ccpc选拔赛落下帷幕，自闭的五小时也就这样结束了
首先，打完这场比赛我深刻认识到自己的菜鸡程度，突然感觉回家种田也许是个不错的选择…

其次，这次的比赛可以说是我打的最艰辛的一场了，杭电oj炸了5小时，为了看有没有过代码就在那蒽刷榜单，给人整麻了，然后举办方成功的发现这比赛得重开了…自闭完5小时没想到还有第二次…

---

1001 Cut The Wire

Problem Description：

In the country of Infinity , there is a strange road. This road only has a starting point, but no end. Since this road is infinite, there are also countless street lights. The street lights are numbered from 1(the starting point) to infinity. The street lights are connected by wires under a strange law:
For a street light x,

if x is even, then x is connected with x2 by a wire;
if x is odd, then x and 3x+1 is connected by a wire.

Now Kris is standing in the middle of street light n and n+1, and he is able to cut all wires passing by. That is, he will cut all wires connecting street lights a and b satisfying a≤n and b>n.

Now he wonders, how many wires he will cut. Please help him calculate.

Input：
This problem contains multiple test cases.
The first line contains an integer T(1≤T≤105) indicating the number of test cases.
The next T lines each contains one integer n(1≤n≤109).

Output：
For each test case, output one line of one integer indicating the answer.

Sample Input：
2
12
60

Sample Output：
10
50

题意：

有一个无限长的x正整数轴，轴上每个点都代表一个路灯，路灯由电线连着。
对于第x盏路灯，如果x是奇数，那么他（x）和第 3x+1 盏路灯相连；如果x是偶数，那么他（x）和第 x / 2 盏路灯相连。
你现在站在第n和n+1的路灯之间，经过你的电线你可以一刀切断，也就是说当两盏能够相连的路灯a，b满足a<=n且b>n就算做一条经过你的电线，求你能斩断多少条电线

思路：

其实理解了题意就会了，以n为界限，如果i<n，那么i就不可能是偶数（i和i/2必定小于n，电线过不来），如果i>n，那么i就不能是奇数（i和3i+1必大于n，电线也过不来）
那么，这题就是求当i<n时，i为奇数的最小值到n之间的奇数个数；当i>n时，i为偶数到i*2之间的偶数个数。两者相加就是答案

代码：

#include <iostream>
#include <cmath>
#include <algorithm>

#define ll long long
using namespace std;
const int INF=100000000;

int main()
{
   
    int t;

    cin>>t;
    while(t--)
    {
   
        int n;

        int ans=0;
        cin>>n;
        if(n%2==0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21