1710A - Color the Picture
题意
给出n * m 的矩阵和k中颜色，每种颜色有\(a_i\)个，要求矩阵每个单元都可以被涂上颜色且每个颜色相邻单元都至少有三个相同颜色，问是否可能
思路
至少有三个相同颜色可以推断出矩阵只可能是每次涂必须要占一行多列，或者多行一列（多：>= 2）
这样就好办了，直接按行和按列枚举，模拟是否可能以以上推断完成要求即可
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(k + 1);
for (int i = 1; i <= k; i ++) {
cin >> a[i];
}
int x = n, y = m;
LL cnt = 0; //每次以最低消耗（2）填充，多的用cnt存起来
， for (int i = 1; i <= k; i ++) {
int tmp = a[i] / m; //枚举每个元素最多可以占几行
if (tmp <= 1) tmp = 0; //如果是小于等于1，那么不满足要求
if (tmp > 2) { //如果大于二，则将多的存起来
cnt += tmp - 2;
tmp = 2;
}
if (x > 0) //如果已经多了，那么不再填充
x -= tmp;
if (!x) { //如果恰好填充完成那么输出
cout << "Yes" << endl;
return ;
}
}
if (cnt >= abs(x)) { //如果没填充好，那么可能是多了或者少了，如果多余的可以填充那么选择用那个颜色就一定可以满足要求
cout << "Yes" << endl;
return ;
}
//按列枚举，和按行枚举相似
cnt = 0;
for (int i = 1; i <= k; i ++) {
int tmp = a[i] / n;
if (tmp <= 1) tmp = 0;
if (tmp > 2) {
cnt += tmp - 2;
tmp = 2;
}
if (y > 0)
y -= tmp;
if (!y) {
cout << "Yes" << endl;
return ;
}
}
if (cnt >= abs(y)) {
cout << "Yes" << endl;
return ;
}
cout << "No" << endl;
}
1614C - Divan and bitwise operations
题意
给出n，n表示有n个数字，m组数据，每组数据给出l，r中所有元素的或和x，求出该组数据所有子段异或和
思路
由于子段或和相等那么异或和一定相等的特性，还有0和x或和等于x的性质，可以将给出的或和全部或起来，然后将原数据的第一个数字命为x，剩下的n-1个数全为0。这样这组数据的异或和就为x * pow(2, n - 1)
因为有n个数字的子段有\(2^n - 1\)个，除开第一个x，剩下的子段一共有\(2^{n-1} - 1\)个，加上x后为\(2^{n-1}\)即为x * pow(2, n - 1)
int qmi(int a, int b) {
LL res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
b >>= 1;
a = (LL)a * a % MOD;
}
return res;
}
//注意观察N的大小
void solve() {
//计数类问题
int n, m;
cin >> n >> m;
LL sum = 0;
for (int i = 1; i <= m; i ++) {
int l, r, x;
cin >> l >> r >> x;
sum |= x;
}
sum = sum % MOD * qmi(2, n - 1) % MOD;
cout << sum << endl;
}
1671D - Insert a Progression
题意
给出序列a，和从1到x的共x个数字，要求将x个数字插入序列a中，使序列中相邻两个元素的差值总和最小
思路
由题可知，在两个元素之间插入他们区间范围内的数字时，差值不变。于是先将原序列总差值求出，然后再求插入后对答案的影响
插入其实只与1和x有关，中间的数字算重复贡献。即在数字a,b中间插入，实质上就是将两数字中间的差值移除，然后增添新得差值a - 1(x) + b - 1(x) - abs(a - b)
对于开头结尾只需要算1和x对于头尾的差值即可。
void solve() {
int n, x;
cin >> n >> x;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
LL sum = 0, l = INF, r = -INF;
for (int i = 1; i <= n; i ++) {
if (i > 1)
sum += abs(a[i] - a[i - 1]);
l = min(l, (LL)a[i]);
r = max(r, (LL)a[i]);
}
int tmp = min(abs(a[1] - 1), abs(a[n] - 1));
for (int i = 2; i <= n; i ++) {
tmp = min(tmp, abs(a[i] - 1) + abs(a[i - 1] - 1) - abs(a[i] - a[i - 1]));
}
sum += tmp;
if (x <= r) {
cout << sum << endl;
return ;
}
tmp = INF;
tmp = min(abs(x - a[1]), abs(x - a[n]));
for (int i = 2; i <= n; i ++) {
tmp = min(tmp, abs(a[i] - x) + abs(a[i - 1] - x) - abs(a[i] - a[i - 1]));
}
sum += tmp;
cout << sum << endl;
}
1646C - Factorials and Powers of Two
题意
给出一个数字x，你有小于等于1e12的2的幂次和阶乘。问最少用多少数字可以组成x，否则输出-1
思路
首先一定可以得到x，因为二进制可以表达任何数字，所以用2的幂次就一定可以表达。因此我们可以枚举小于x的阶乘和，然后剩下的数字用2的幂次补充即可
vector<LL> cnt;
//注意观察N的大小
void solve() {
int n = cnt.size();
LL x;
cin >> x;
LL ans = __builtin_popcountll(x); //找到所求数字二进制表示下有多少个1
for (int i = 1; i <= (1l << n); i ++) { //枚举在1e12的范围内，所有阶乘和的取值
LL tmp = x, sum = 0;
for (int j = 0; j < n; j ++) {
if ((i >> j) & 1) {
sum ++;
tmp -= cnt[j];
}
}
if (tmp < 0) sum = 1e9;
ans = min(sum + __builtin_popcountll(tmp), ans);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
LL tmp = 1, i = 2;
while (tmp <= 1e12) {
cnt.push_back(tmp);
tmp *= i;
i ++;
}
while (t--) {
solve();
}
return 0;
}