树上的图
题目大意、
有正整数 n，给定起点 x 和终点 y（都在 1 到 n 之间 ），要通过最少操作把 x 转成 y。操作有两种：
- 找数
i（1≤i≤n），若x和i二进制里1的个数（count）相同，x可转成i。 - 找数
i（1≤i≤n），若x和i二进制里最低位1及后面0组成的数（lowbit）相同，x可转成i。
求x变y最少操作次数 。
数据范围
有多组测试数据，第一行输入 T（T 是 1 到 \(10^5\)) 的正整数 ），表示测试数据的组数 。每组测试数据占一行，包含三个正整数 n、x、y，满足 \(1 \leq x,y \leq n \leq 10^{15}\) ，n 是数值上界，x 是起点，y 是终点 。
思路
- x=y，则不需要操作
- count(x)=count(y) or lowbit(x)=lowbit(y)， 仅需要一次操作
- 先count()转化，再lowbit转化，两次操作
点击查看代码
//2025“钉耙编程”中国大学生算法设计暑期联赛（2）
#include <bits/stdc++.h>
using namespace std;
using ll = long long;ll lowbit(bitset<100> t) {return t._Find_first();//找到第一个1的位置
}void solve() {ll n, x, y;cin >> n >> x >> y;bitset<100>a(x),b(y);ll xx = a.count();ll yy = b.count();if (x == y) {cout << 0 << "\n";} else if (xx == yy || lowbit(x) == lowbit(y)) {cout << 1 << "\n";} else {cout << 2 << "\n";}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int _ = 1;cin >> _;while (_--) {solve();}return 0;
}
井
题目大意
有一个 ( n \times n ) 的网格，其中恰好有一行 或 一列全为 1，其余为 0。网格状态是从 2n 种可能（选一行或一列全置 1）中等概率随机选一种。
操作与目标
网格初始全部覆盖，你按策略依次翻格子。当所有 1 被翻出时结束，要找 最优策略，让翻开所有 1 的期望次数最小，并输出这个最小期望。
数据范围
- 第一行输入 T ( $1 \leq T \leq 100 $），表示测试用例组数。
- 每组用例输入一个 n （$ 2 \leq n \leq 10^9 $），即网格规模。
思路
最有策略，先翻对角线，再翻行或列，最少翻n次，最多翻2n次，取平均3n/2次
点击查看代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve() {double n;cin >> n;cout << fixed << setprecision(4) << n * 3 / 2 << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int _ = 1;cin >> _;while (_--) {solve();}return 0;
}
半
题目大意
- 有两场比赛，都有
n名选手（编号1~n），已知两场比赛各自的排名（a数组、b数组，均是1~n的排列，无并列）。 - 你作为其中一名选手（假设是
i），可以禁赛其他选手，禁赛后剩余选手相对排名不变。
对每个选手 i（1 ≤ i ≤ n ），计算让自己在两场比赛中都拿第一名，最少需要禁赛多少人。
数据范围
- 第一行输入
T（最多20组），表示测试用例数。 - 每组用例：
- 先输入
n（选手总数，最多 \(10^6\) ）。 - 再输入两场比赛的排名数组
a、b（都是1~n的排列 ）。
- 先输入
思路
思路是一目了然的，对于一个选手i找出，求出在a,b数组大于i排名的并集大小
先枚举a[i]，记录小于a[i]的数，算出在b中小于a[i]的数，但不属于前i个a[]，再加上i-1，
点击查看代码
//2025“钉耙编程”中国大学生算法设计暑期联赛（2）
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
const int maxn=1e6+100;
int a[maxn],b[maxn];
int tr[maxn<<1];
int ans[maxn];
int lowbit(int x){return x&-x;
}
void add(int x){while(x<n){tr[x]++;x+=lowbit(x);}return ;
}
int sum(int x){int res=0;while(x){res+=tr[x];x-=lowbit(x); }return res;}void solve() {cin>>n;for(int i=0;i<=n;++i) tr[i]=0;for(int i=1;i<=n;++i)cin>>a[i];for(int i=1;i<=n;++i){int x;cin>>x;b[x]=i;}for(int i=1;i<=n;++i){int x=a[i];int w=b[x]-1-sum(b[x]-1)+i-1;ans[x]=w;add(b[x]);}for(int i=1;i<=n;++i) cout<<ans[i]<<" ";cout<<endl;return ;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int _ = 1;cin >> _;while (_--) {solve();}return 0;
}