2023.8.31题目小记

1.费解的开关

1208. 翻硬币 - AcWing题库

1.使用位进制优化

2.由于第一行如果已经确定下来则后面的每一行都可以确定，可以将第一行的所有方法全部记录下来PS：32的二进制为100000一共六位，而此就已经可以使用位运算将五位开关全部枚举出来。此时枚举如果位运算当前位为1表示需要按开关，如果为0则不需要，注意此处不要和题目中的01亮灯是否的意思搞混

此处解释一下为什么第一行需要将所有安灯的方法枚举一遍：；因为第一行的灯的亮暗可以由自己决定也可以由第二行决定，只有第一行枚举所有方法时是以自己为中心改变按钮，后面的都是一下一行为中心改变按钮

3.最后将每一种枚举方法取最小值

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int t, cnt;
char g[N][N], ba[N][N];
int dx[5] = {-1, 0, 1, 0, 0};
int dy[5] = {0, 1, 0, -1, 0};
void turn(int x, int y)
{
	for(int i = 0; i < 5; i ++)
	{
		int a = x + dx[i];
		int b = y + dy[i];
		if(a >= 0 && a < 5 && b >= 0 && b < 5)
		{
			g[a][b] ^= 1;
		} 
	}
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> t;
	while(t --)
	{
		int res = 10;
		for(int i = 0; i < 5; i ++)cin >> ba[i];
		for(int op = 0; op < 32; op ++)
		{
			memcpy(g, ba, sizeof g);
			cnt = 0;
			for(int i = 0; i < 5; i ++)
			{
				if(op >> i & 1)
				{
					turn(0, i);
					cnt ++;
				}
			}
			for(int i = 0; i < 4; i ++)
			{
				for(int j = 0; j < 5; j ++)
				{
					if(g[i][j] == '0')
					{
						turn(i + 1, j);
						cnt ++;
					}
				}
			}
			int dark = 1;
			for(int i = 0; i < 5; i ++)
			{
				if(g[4][i] == '0')
				{
					dark = 0;
					break;
				}
			}
			if(dark)res = min(res, cnt);	
		}
		if(res > 6)res = -1;
		cout << res << '\n';
	}
	return 0;
}

2.翻硬币

1208. 翻硬币 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
string s, e;
int cnt;
void turn(int x)
{
	if(s[x] == '*')s[x] = 'o';
	else s[x] = '*';
}
int main()
{
	cin >> s >> e;
	for(int i = 0; i < s.size() - 1; i ++)
	{
		if(s[i] != e[i])
		{
			turn(i + 1);
			cnt ++;
		}
	}
	cout << cnt;
	return 0;
}

3.约数之和

97. 约数之和 - AcWing题库

采用分治

#include<bits/stdc++.h>
using namespace std;
const int mod = 9901;
int a, b;
int qmi(int p, int k)
{
	int res = 1;
	p %= mod;
	while(k)
	{
		if(k & 1)res = res * p % mod;
		p = p * p % mod;
		k >>= 1;
	}
	return res;
}
int sum(int p, int k)
{
	if(k == 1)return 1;
	if(k % 2 == 0)return (1 + qmi(p,k / 2)) * sum(p, k / 2) % mod;
	return (sum(p, k - 1) + qmi(p, k - 1)) % mod;
}
int main()
{
	cin >> a >> b;
	int res = 1;
	for(int i = 2; i <= a / i; i ++)
	{
		if(a % i == 0)
		{
			int s = 0;
			while(a % i == 0)
			{
				a /= i;
				s ++;
			}
			res = res * sum(i, b * s + 1) % mod;
		}
	}
	if(a > 1)res = res * sum(a, b + 1) % mod;
	if(a == 0)res = 0;
	cout << res;
	return 0;
}