# A

# 题目大意

对于长度为 $n$ 的排列 $P$ ，我们定义了以下函数

$f(p)=\sum\limits_{i=1}^n |p_i - i|$

现在给你一个数字 $n$ ，你要计算，对于所有排列， $f(p)$ 有多少不同的值

# 数据范围

$1 \le t \le 100$
$1 \le n \le 500$

# 题解

打表找规律

C++

void solve () {
    for (int k = 1; k <= 10; k++) {
        vector<int> num;
        for (int t = 1; t <= k; t++)
            num.push_back(t);
        
        set<int> s;
   
        do {
            int res = 0;
            for (int i = 0; i < num.size(); i++)
                res += abs(i - num[i]);
            s.insert(res);
        } while (next_permutation(num.begin(), num.end()));

        cout << s.size() << endl;
    }
}

输出的数据为：

Data

观察有

Data

1 = 1
1 = 1
2 = 1 + 1
3 = 2 + 1
5 = 3 + 2
7 = 3 + 2
10 = 7 + 3
13 = 10 + 3
17 = 13 + 4
21 = 17 + 4
...

总结出规律，前两个是

1

，后面每两个都 "+1" ，故猜想出代码：

C++

void solve () {
	int t;	cin >> t;
	if (t == 1) {
		cout << t << endl;
		return; 
	}
	
	int res = 1;
	
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    res[1] = 1, res[2] = 1;
    
    int add = 1;
    for (int i = 3; i <= 510; i += 2) {
    	res[i] = res[i - 1] + add;
		res[i + 1] = res[i] + add;
		add++;
	}
	   
	int _;	cin >> _;
	while (_--) {
		int k;	cin >> k;
		cout << res[k + 1] << endl; 
	} 

    return 0;
}

# B

# 题目大意

给你一个 $n$ 和一个 $x$ ，你现在需要做的是，构造出 $a_1 \oplus a_2 \oplus ... \oplus a_n = x$ ，问 $MIN(\sum\limits_{i=1}^{n}a_i)$

# 数据范围

$1 \le t \le 10^4$
$1 \le n \le 10^9$
$0 \le x \le 10^9$

# 题解

x == 0
- n == 1 ：拼不出来
- n & 1 == 1 ， $n$ $n$ 是奇数
  - 选取 $n - 1$ 个，令 $2^0$ 位为 $1$
  - 剩下一个，令 $2^1$ 位为 $1$
  - 在 $n-1$ 个中，任选一个把 $2^1$ 位也改成 $1$
  - 故答案为 n - 1 + 2 + 2 = n + 3
- n & 1 == 0 ， $n$ $n$ 是偶数
  - 直接选取 $n$ 个，令 $2^0$ 位为 $1$ 即可
  - 故答案为 n
x == 1
- 同理上方 x == 0
- n & 1 == 0 时，答案为 n
- n & 1 == 1 时，答案为 n + 3

当 $x$ 为其他数时，计算 $x$ 的二进制表示中， $1$ 的个数，记为 $cnt$

cnt >= n ，有足够的 $1$ $1$ 可以给 $n$ $n$ 个数分配
- 故答案为 $x$
若分配完之后，还有剩余的，即 n > cnt ，则记 $n - cnt$ $n - c n t$ 为 $more$ $m o r e$
- 需要令 $more$ 个数，异或和为 $0$
- more & 1 == 1
  - 剩下奇数个数
    - 若采取之前的方法，则最后答案要先 $-1$ 再 $+4$ ，最后结果是 x + more + 3
    - 而不妨，从前面凑 $x$ 的 $cnt$ 个数中，任取一个 $2^0$ 位为 $0$ 的数，令其 $2^0$ 位为 $1$
    - 则可以实现剩下奇数个数和这个新来的 $1$ 异或和为 $0$ ，最后答案为 x + more + 1
- more & 1 == 0
  - 刚好剩下偶数个数，则令这偶数个数的 $2^0$ 位为 $1$ 即可
  - 故答案是 x + more

# 代码

C++

void solve () {
    cin >> n >> x;

    if (x == 0) {
        if (n == 1)
            cout << -1 << endl;
        else if (n & 1)
            cout << n + 3 << endl;
        else
            cout << n << endl;
        return;
    }
    else if (x == 1) {
        cout << (n & 1 ? n : n + 3) << endl;
        return;
    }

    int cnt = 0, tmp = x;
    while (tmp)
        cnt += (tmp & 1), tmp >>= 1;
    
    if (cnt >= n) {
        cout << x << endl;
        return;
    }

    int more = n - cnt;

    if (more & 1)
        cout << x + more + 1 << endl;
    else
        cout << x + more << endl;
}

预处理构造 Div2 打表找规律

# A

# 题目大意

# 数据范围

# 题解

# B

# 题目大意

# 数据范围

# 题解

# 代码

hhtp和https协议

第七届传智杯国赛