首页 algorithm 算法OJ Codeforces

# A. Find Minimum Operations

输入 n，k，不断用n−kxn-k^x 代替nn，直到 n 等于 0，问最少要多少步

快速幂计算，注意如果 k=1，直接加上 n，节省时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#define int long long
using namespace std;
const int N = 1e4 + 10;
int a[N];
int qmi(int c, int b)
{
	int ans = 1;
	while (b)
	{
		if (b & 1) ans = ans * c;
		b >>= 1;
		c = c * c;
	}
	return ans;
}
void solve()
{
	int n, k;
	cin >> n >> k;
	if (k == 1)
	{
		cout << n << '\n';
		return;
	}
	int i = 0;
	for (;i == 0 || a[i - 1] <= n; i++) a[i] = qmi(k, i);
	int step = 0;
	for(int j = i - 1; n > 0; j--)
	{
		if (a[j] == 1)
		{
			step += n;
			break;
		}
		while (a[j] <= n)
		{
			n -= a[j];
			step++;
		}
	}
	cout << step << '\n';
	return;
}
signed main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;

# B. Brightness Begins

输入 k，假设一开始有 n 盏灯，全部是开的状态，即a[i]=1,1≤i≤na[i]=1,1\leq i\leq n，从1∼n1\sim n 进行遍历，如果a[i]a[i] 可以被 i 整除，就改变状态（开边关，关变开），要求输出 n，保证 n 中有 k 盏灯亮着

我们不难发现，

  1. 如果 i 是素数，那么 i 只能被 1 和 i 整除，那么最后的状态一定是开
  2. 如果 i 的因子个数为偶数，那么最后的状态也是开

也就是说，除了 i 的因子个数为奇数的，最后状态都是开；而因子个数为奇数的数一定是平方数，而平方数的分布有规律性：1,4,9,16,… 依次隔了 3,5,7,… 所以可以按照 3,5,7,… 进行分组，除了第一个数状态是 0，其他都是 1，然后用二分查找即可

注意二分查找的边界条件！！！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#define int long long
using namespace std;
//每3 5 7 ...个数为1组
//前x组的01总数
int sum(int x)
{
	return (3 + (2 * x + 1)) * x / 2;
}
//计算前x组中1的个数
int sum1(int x)
{
	return sum(x) - x;
}
void solve()
{
	int k; cin >> k;
	int l = 0, r = 1e9, mid;
	while (l < r)
	{
		mid = l + r + 1 >> 1;
		int t = sum1(mid);
		if (t > k) r = mid - 1;
		else if(t < k) l = mid;
		else
		{
			cout << sum(mid) << '\n';
			return;
		}
	}
	cout << sum(l) + k - sum1(l) + 1 << '\n';
	

}
signed main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

# C. Bitwise Balancing

给定三个整数 b,c,d，要求求出一个 a，让(a∣d)−(a&c)=d(a|d)-(a\&c)=d

直接列举 a 的每一个二进制位即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cmath>
#define int long long
using namespace std;
const int N = 100;

void solve()
{
	int cnt = 0, a[N];
	int b, c, d;
	cin >> b >> c >> d;
	while (b || c || d)
	{
		int t1 = b & 1, t2 = c & 1;
		int ans1 = t1, ans2 = 1 - t2;
		if (ans2 == (d & 1)) a[cnt++] = 1; 
		else if (ans1 == (d & 1)) a[cnt++] = 0;
		else
		{
			cout << -1 << '\n';
			return;
		}
		b >>= 1, c >>= 1, d >>= 1;
	}
	int ans = 0;
	for (int i = 0; i < cnt; i++) if(a[i]) ans += pow(2, i);
	cout << ans << '\n';
}
signed main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

# D. Connect the Dots

输入三个整数 a,d,k，输入 m 条指令，每次将a,a+d,a+2d,...,a+kda,a+d,a+2d,...,a+kd 连接起来，问最后有多少个联通块，1≤k≤101\leq k\leq 10

一开始我没有注意到 k 的特殊性，直接用并查集做，然后 TLE 了；然后看了题解，它是巧妙地应用了一个数组，ma[i][j]ma[i][j]，表示以 i 为起点每次跳跃 j 步的次数，将同一个步数的进行归类，每跳一次步数减 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <set>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int p[N], ma[N][15];
int find(int x)
{
	if (x != p[x]) p[x] = find(p[x]);
	return p[x];
}
void solve()
{
	int n, m;	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		p[i] = i;
		for (int j = 1; j <= 10; j++)
			ma[i][j] = 0;
	}
	while (m--)
	{
		int a, d, k;
		cin >> a >> d >> k;
		ma[a][d] = max(ma[a][d], k);//以a为起点，d为步长最多能走k次
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= 10; j++)
		{
			if (i - j < 1) break;
			if (ma[i - j][j]) p[find(i - j)] = find(i);//如果可以从i - j跳到j
		}
		for (int j = 1; j <= 10; j++)
		{
			if(ma[i][j] > 1 && i + j <= n) ma[i + j][j] = max(ma[i + j][j], ma[i][j] - 1);//继承前面没跳完的次数
		}
	}
	set<int> s;
	for (int i = 1; i <= n; i++)
		s.emplace(find(i));//s中有该元素返回False，没有就加到s中返回true
	cout << s.size() << '\n';
}
signed main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}