A

签到

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
void solve() {
	int n;
	cin >> n;
	if (n & 1)cout << (n + 1) / 2;
	else cout << n / 2;

}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t = 1;
	//cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}

B

如果存在连续两盏亮着的灯，就灭掉后面那盏

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int res = 0;
	for (int i = 1; i < n; i++) {
		if (s[i] == '1' && s[i - 1] == '1') {
			s[i] = '0';
			res++;
		}
	}
	cout << res;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t = 1;
	//cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}

C

每次可以灭掉连续的K盏灯，所以一共有ans=n-k+1种操作方式，因此会产生2的ans次方种灯的状态，数据较小，不需要快速幂。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

void solve() {
	int n, k, res = 1;
	cin >> n >> k;
	int ans = n - k + 1;
	for (int i = 1; i <= ans; i++) {
		res = res * 2 % mod;
	}
	cout << res;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t = 1;
	//cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}

D

与C题不同的是，每次操作可以改变任意K盏灯的状态，限制条件减少，重复情况过多，C题方法不适用。打表发现当k为奇数时，可以通过奇数次操作可以使得灭掉奇数盏灯，通过偶数次操作可以使得灭掉偶数盏灯，所有灯的状态都能被实现，即2的n次方种。而当k为偶数时，任意次操作都只能灭掉偶数盏灯，所有只能实现所有情况的一半。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
const int mod = 1e9 + 7;

void solve() {
	int n, k, res = 1;
	cin >> n >> k;
	if (k == n) {
		cout << 2;
		return;
	}
	int ans = n;
	if (k%2==0)ans--;
	for (int i = 1;i <= ans; i++) {
		res = res * 2 % mod;
	}
	cout << res;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t = 1;
	//cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}

E

每次操作都改变两盏灯的状态，因此如果初始时关闭的灯的个数如果为奇数则必然无解。由于不要求最小化操作次数所以直接暴力求解，先遍历每一行，碰的关闭的就直接打开，把需要开启的灯换到最右边，然后遍历最后一列，同样的方法从上到下。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105;
char a[N][N];

void solve() {
	int n, m, sum = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] == '0')sum++;
		}
	}
	if (sum & 1) {
		cout << -1;
		return;
	}
	int k = 0;
	vector<pair<int, int>>q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '0') {
				if (j != m) {
					a[i][j] = '1';
					a[i][j + 1] = (a[i][j + 1] == '0' ? '1' : '0');
					k++;
					q.push_back({ i,j });
					q.push_back({ i,j + 1 });
				}
			}
		}
	}
	bool qq = false;
	for (int i = 1; i <= n; i++) {
		if (a[i][m] == '0') {
			if (i != n) {
				a[i][m] = '1';
				a[i+1][m] = (a[i+1][m] == '0' ? '1' : '0');
				k++;
				q.push_back({ i,m });
				q.push_back({ i+1,m});
			}
			else {
				qq = true;
			}
		}
	}
	if (qq) {
		cout << -1;
		return;
	}
	else {
		cout << k << "\n";
		for (int i = 0; i < q.size(); i++) {
			cout << q[i].first << " " << q[i].second << " ";
			if (i%2== 1)cout << "\n";
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t = 1;
	//cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}

F和G

这个题的关键应该是不要开灯。对于每个节点来说，如果存在一个与之直连的子节点可以亮着，则该节点必须灭（如果该节点目前还亮着），有两种选择，首选肯定是跟父节点同时灭，其次是跟亮着的子节点同时灭。如果父节点已经灭了或已经没有父节点了，则选择子节点。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int a[N];
bool vis[N];//记录灯的状态，初始时为0，亮着
vector<int>p[N];
int res = 0;
vector<pair<int, int>>q;
void dfs(int x, int fa) {
	int sum = 0,pos=0;//pos用来记录可以亮着的子节点
	for (int i = 0; i < p[x].size(); i++) {
		if (p[x][i] == fa)continue;
		dfs(p[x][i], x);
		if (vis[p[x][i]]==0)pos=p[x][i],sum++;
	}
	if (sum&&vis[x]==0) {
		if (fa == 0||vis[fa]==1) {
			vis[x] = 1;
			vis[pos]=1;
			q.push_back({ x,pos});
			res++;
		}
		else {
			vis[x] = 1;
			vis[fa] = 1;
			q.push_back({ x,fa });
			res++;
		}
		
	}
}
void solve() {
	int n;
	cin >> n;
	int u, v;
	for (int i = 1; i < n; i++) {
		cin >> u >> v;
		p[u].push_back(v);
		p[v].push_back(u);
	}
	dfs(1, 0);
	cout << res << "\n";
	for (int i = 0; i < q.size(); i++) {
		cout << q[i].first << " " << q[i].second << "\n";
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t = 1;
	//cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}