显然横纵坐标我们可以分开考虑。
假设只考虑横坐标，若\(x_2\not ={x_1}\)，那么向左/向右走可以互相抵消，然后只能往一个方向走；若\(x_2=x_1\)，那么就不能向左/向右走。
纵坐标同理。
只需要check一下最终位置是否在矩形内即可。
赛场上写的代码有些复杂：
/*
* Author: heyuhhh
* Created Time: 2020/3/31 21:38:57
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << ‘\n‘; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ‘ ‘; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ‘ ‘; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
void run() {
int a, b, c, d; cin >> a >> b >> c >> d;
int x, y; cin >> x >> y;
int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
int w = r2 - r1, h = c2 - c1;
if(w) {
int t = min(a / w, b / w);
a -= t * w, b -= t * w;
int tt = min(a, b);
a -= tt, b -= tt;
}
if(a > x - r1 || b > r2 - x) {
cout << "NO" << ‘\n‘;
return;
}
if(h) {
int t = min(c / h, d / h);
c -= t * h, d -= t * h;
int tt = min(c, d);
c -= tt, d -= tt;
}
if(c > y - c1 || d > c2 - y) {
cout << "NO" << ‘\n‘;
return;
}
cout << "YES" << ‘\n‘;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T;
while(T--) run();
return 0;
}
因为\(a_i\leq 1000\)且为合数，容易证明只需要前面\(11\)个质数即可构造出所有的\(a_i\)。
染色的话随便染就行。
/*
* Author: heyuhhh
* Created Time: 2020/3/31 22:01:11
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << ‘\n‘; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ‘ ‘; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ‘ ‘; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1000 + 5;
int n;
int a[N], col[N];
int primes[N], tot;
bool vis[N];
void init() {
for(int i = 2; i < N; i++) {
if(!vis[i]) primes[++tot] = i;
for(int j = i * i; j < N; j += i) vis[j] = true;
}
}
void run() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
vector <vector <int>> c, p;
c.resize(12); p.resize(n + 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 11; j++) {
if(a[i] % primes[j] == 0) {
c[j].push_back(i);
p[i].push_back(j);
}
}
}
memset(col, -1, sizeof(col));
for(int i = 1; i <= 11; i++) {
for(auto it : c[i]) {
if(col[it] == -1) {
col[it] = i;
break;
}
}
}
for(int i = 1; i <= n; i++) if(col[i] == -1) col[i] = p[i][0];
map <int, int> mp; int num = 0;
for(int i = 1; i <= n; i++) {
if(!mp[col[i]]) mp[col[i]] = ++num;
col[i] = mp[col[i]];
}
cout << num << ‘\n‘;
for(int i = 1; i <= n; i++) cout << col[i] << " \n"[i == n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
init();
int T; cin >> T;
while(T--) run();
return 0;
}
贪心搞即可。
容易发现将长度为\(n\)的串划分为\(\displaystyle\frac{n}{k}\)个长度为\(k\)的串，并且每个串都相等且都为回文串。
那么对长度为\(k\)的串暴力找代价最小的回文串就行。
详见代码：
/*
* Author: heyuhhh
* Created Time: 2020/3/31 22:23:34
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << ‘\n‘; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ‘ ‘; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ‘ ‘; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;
int n, k;
int cnt[N][26];
char s[N];
void run() {
cin >> n >> k;
cin >> (s + 1);
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 26; j++) {
cnt[i][j] = 0;
}
}
for(int i = 1; i <= k; i++) {
for(int j = i; j <= n; j += k) {
++cnt[i][s[j] - ‘a‘];
}
}
int l = 1, r = k;
int ans = 0;
int d = n / k;
while(l < r) {
int res = INF;
for(int i = 0; i < 26; i++) {
res = min(res, 2 * d - cnt[l][i] - cnt[r][i]);
}
ans += res;
++l, --r;
}
if(l == r) {
int res = INF;
for(int i = 0; i < 26; i++) {
res = min(res, d - cnt[l][i]);
}
ans += res;
}
cout << ans << ‘\n‘;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T;
while(T--) run();
return 0;
}
题意：
假设现在有一个\(n\cdot m\)的矩阵，每个位置的权值为\(a_{i,j}\)。现在从\((1,1)\)出发要到达\((n,n)\)，每次只能往下走或者往右走，代价为：当前价值\(x\)与\(a_{i,j}\)的\(\&\)，即\(x\& a_{i,j}\)。
现在有个\(dp\)代码：
显然这个\(dp\)是不正确的。
现在要求构造一个矩阵，使得\(dp\)跑出来的结果与最大值相差为\(k\)。
限制条件为：\(n,m\leq 500,a_{i,j}\leq 3\cdot 10^5,k\leq 10^5\)。
思路：
代码如下：
/*
* Author: heyuhhh
* Created Time: 2020/3/31 22:49:29
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << ‘\n‘; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ‘ ‘; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ‘ ‘; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
int k;
int a[4][4];
void run() {
cin >> k;
if(k == 0) {
cout << 1 << ‘ ‘ << 1 << ‘\n‘ << 0 << ‘\n‘;
return;
}
int lim = 1;
while(lim < 3e5) lim <<= 1;
lim >>= 2;
int MAX = (lim << 1) - 1;
cout << 3 << ‘ ‘ << 3 << ‘\n‘;
a[1][1] = MAX;
a[2][1] = k;
a[1][2] = lim;
a[2][2] = lim + k;
a[2][3] = a[3][2] = (MAX ^ lim);
a[3][3] = MAX;
for(int i = 1; i <= 3; i++) {
for(int j = 1; j <= 3; j++) {
cout << a[i][j] << ‘ ‘;
} cout << ‘\n‘;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
题意：
现有大小为\(n\cdot m\)的矩阵，每个格子上可以任意选择一个\([L,R]\)的数。现在可以对该矩形执行任意次数以下两种操作：
如果最终能够使得所有格子上面数值相同，那么就称该矩阵为完美的。
现在问每个格子选择的数值在\([L,R]\)范围内时有多少完美矩阵。
思路：
现在回到这个题，假设\(x\)为\([L,R]\)中偶数的个数，\(y\)为奇数的个数。
因为我们选择的数在\([L,R]\)范围内，实际上通过思考我们发现只跟奇偶性相关。当\(n\cdot m\)为奇数时，我们随便放置就行；当\(n\cdot m\)为偶数时，我们必须放置偶数个奇数以及偶数个偶数，那么枚举放置偶数的个数:\(\displaystyle\sum_{i=0,2,\cdots,n\cdot m}x^iy^{n\cdot m-i}{nm\choose i}\)。
我们容易发现这跟牛顿二项式定理有关。赛场上脑袋短路，忘记如何求解这个式子。。
其实这个式子就等于\(\displaystyle ((x+y)^{n\cdot m}+(x-y)^{n\cdot m}) / 2\)。
这貌似是数学中常用的一个技巧。
代码如下：
/*
* Author: heyuhhh
* Created Time: 2020/3/31 23:52:41
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << ‘\n‘; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ‘ ‘; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ‘ ‘; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5, MOD = 998244353, inv2 = (MOD + 1) >> 1;
int qpow(ll a, ll b) {
ll res = 1;
a %= MOD;
while(b) {
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void run() {
ll n, m, L, R;
cin >> n >> m >> L >> R;
int even = R / 2, odd = (R + 1) / 2;
even -= (L - 1) / 2, odd -= L / 2;
int res = qpow(even + odd, n * m);
if((n * m) & 1) cout << res << ‘\n‘;
else {
res += qpow(max(even, odd) - min(even, odd), n * m);
res %= MOD;
res = 1ll * res * inv2 % MOD;
cout << res << ‘\n‘;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
赛场上貌似很多人直接矩阵快速幂过的，其实这个很好想，根据上面的思考，我们得出最后的结果只与放置奇数个奇数/偶数和放置偶数个奇数/偶数有关。
设\(dp[i][2]\)表示前\(i\)个数，放置了奇数个/偶数个奇数/偶数，不妨考虑放置的是奇数。那么转移为：
那么当\(n\cdot m\)为奇数时，答案为\(dp[n\cdot m][0]+dp[n\cdot m][1]\)；否则，答案为\(dp[n\cdot m][0]\)。
这个过程我们用矩阵快速幂进行优化即可。
代码略。
Codeforces Round #630 (Div. 2)
原文：https://www.cnblogs.com/heyuhhh/p/12612378.html