ZR2020提高组十连测day3
锅是锅了,但是还是有本质很好的题目的...
出锅原因:
- 数据和题面不符
- 二三题数据随机,导致暴力与正解一样
A
有毒
我们会发现,本质上就是求一个图的染色方案,使得异色边数最大....大于m/2
做法很简单,直接dfs实现二分图染色即可,然后如果一遍不行我们randomshuffle存图顺序多dfs几遍
其实有个结论是如果我们二分图染色能做到每个奇环只有一条边是没有用的...
而奇环最小三个边
而且这样我们就有重复的边,如果选了一个包含了多个奇环就能变得很优....
当然这个最优化是NPh的
code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
const int MAXM = 2e6 + 7;
int n, m, ccnt, ans;
int home[MAXN], nxt[MAXM], to[MAXM];
int eu[MAXM], ev[MAXM], col[MAXN];
struct rec {
int u, v;
} e[MAXM];
inline void ct(int x, int y) {
ccnt++;
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = y;
}
inline void dfs(int u) {
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
if(!col[v]) {
col[v] = -col[u];
dfs(v);
}
}
}
inline void solve() {
ccnt = 0;
memset(home, 0, sizeof(home));
for(int i = 1; i <= m; ++i) {
ct(e[i].u, e[i].v);
ct(e[i].v, e[i].u);
}
memset(col, 0, sizeof(col));
for(int i = 1; i <= n; ++i) {
if(!col[i]) {
col[i] = 1;
dfs(i);
}
}
int cnt = 0;
for(int i = 1; i <= m; ++i) {
if(col[e[i].u] != col[e[i].v]) {
cnt++;
}
}
if(cnt > m / 2) {
// for(int i = 1; i <= n; ++i) {
// printf("%d %d\n", i, col[i]);
// }
ans = 1;
}
return ;
}
int main() {
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
scanf("%d%d", &n, &m);
if(m == 0) {
puts("No");
return 0;
}
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &e[i].u, &e[i].v);
}
for(int i = 1; i <= 17; ++i) {
random_shuffle(e + 1, e + m + 1);
solve();
if(ans)break;
}
if(ans)
printf("Yes\n");
else printf("No\n");
return 0;
}
B
不需要构造方案不够妙啊!
但是本质上还是很妙的
我们观察一下,交换更简化的是什么
k=3
000101
->
101000
可以通过把错位k来把有些1搞过去,操作前提是我们有连续k个空格0
啊!你会发现这个相当于一个翻转操作啊
所以说我们一定可以把连续长为k的一段相同的和然后把一段长度小于等于k的随意位置搞到前面去
所以我们可以先把所有的空白段移动到最后然后看前面那些不是空白段的是不是完全匹配
因为如果不一样我们没法动就暴毙了
做法很简单,我们开一个栈然后把长度等于k的平移消除掉就好了,因为他们相当于没用了
code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int T, n, k;
char s1[MAXN], s[MAXN], t1[MAXN], t[MAXN];
inline void init(char *str, char *res, int &x) {
static int len[MAXN], st[MAXN];
x = 0;
st[0] = -1;
len[0] = 0;
for(int i = 1; i <= n; ++i) {
++x;
res[x] = str[i];
if(str[i] - 'a' == st[x - 1]) {
len[x] = len[x - 1] + 1;
st[x] = st[x - 1];
} else {
len[x] = 1;
st[x] = str[i] - 'a';
}
while(x > 0 && len[x] == k) {
x -= k;
}
}
}
inline void solve() {
scanf("%d%d", &n, &k);
scanf("%s%s", s + 1, t + 1);
int sl = 0, tl = 0;
init(s, s1, sl);
init(t, t1, tl);
bool flg = sl == tl;
for(int i = 1; i <= tl; ++i) {
flg &= (s1[i] == t1[i]);
}
if(flg)puts("Yes");
else puts("No");
}
int main() {
// freopen("test.in", "r", stdin);
scanf("%d", &T);
while(T-- > 0) {
solve();
}
return 0;
}
C
考虑直接计数
你会发现只有两两之间的差一起取gcd,然后得到的d的所有的因数可能成为答案
然后要判断这个约数可不可以合法,就是能不能过被卡的位置
首先但凡中间的一定不行,因为我们就不能同时过开头和结尾了
判断条件是->
然后两边的就有毒,他会限制我们合法序列的数量....
仔细思考一下应该可
如果两个数同余就能限制
那么就是
暴力实现上面的
复杂度显然是
std:
复杂度在两个方面,计算合法的序列,判断合法的约数
对于第一步,我们可以lowerbound!
对于第二步,我们可以压所有的质因数指数然后dp,因为一个不合法他的子集就都不合法....
具体的:我们可以用一个dfs类似的东西传导一下我们的限制和前后limit
std:
code:
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= int(b); i++)
#define per(i, a, b) for (int i = (a); i >= int(b); i--)
#define fir first
#define sec second
#define tct template<class type>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 1e5, maxm = 2e6, mod = 1e9 + 7;
int m, c, q[maxn + 5], S[maxn + 5], T, C[maxm + 5];
ll N, K, p[maxn + 5], lst[maxn + 5], nxt[maxn + 5], A[maxm + 5], B[maxm + 5], Num[maxm + 5];
inline void red(int &x) {
x += x >> 31 & mod;
}
tct inline void cmax(type &x, type y) {
x < y ? x = y : 0;
}
tct inline void cmin(type &x, type y) {
x > y ? x = y : 0;
}
struct event {
int t; ll x;
bool operator < (const event &o) const {
return x < o.x;
}
} ev[maxn + 5];
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
void work(ll N) {
for (ll i = 2; i * i <= N; i++) if (N % i == 0) {
p[++c] = i;
while (N % i == 0) N /= i, q[c]++;
}
if (N > 1) p[++c] = N, q[c] = 1;
}
map<ll, int> M;
void dfs(int x, ll y, int z) {
if (x == c + 1) {//预处理所有约数
M[y] = z;
Num[z] = y;
return;
}
z *= q[x] + 1;
dfs(x + 1, y, z);
rep(i, 1, q[x]) {
y *= p[x];
dfs(x + 1, y, z + i);
}
}
void dfs0(int x, int z, int y) {
if (x == c + 1) {//传导
cmax(A[z], A[z + S[y]]);
cmin(B[z], B[z + S[y]]);
C[z] |= C[z + S[y]];
return;
}
z *= q[x] + 1;
per(i, q[x], 0) {
if (i == q[x] && x == y) continue;
dfs0(x + 1, z + i, y);
}
}
int main() {
scanf("%lld %d", &N, &m);
rep(i, 1, m) scanf("%d %lld", &ev[i].t, &ev[i].x);
sort(ev + 1, ev + m + 1);
ll x = 0, mx = 0, mn = N + 1;
rep(i, 1, m) if (ev[i].t == 1) {
if (x) K = gcd(K, ev[i].x - x);
x = ev[i].x;
cmax(mx, ev[i].x), cmin(mn, ev[i].x);
}
x = 0;
rep(i, 1, m) {
if (ev[i].t == 0) lst[i] = x;
else x = ev[i].x;
}
x = N + 1;
per(i, m, 1) {
if (ev[i].t == 0) nxt[i] = x;
else x = ev[i].x;
}
work(K);
dfs(1, 1, 0);
S[c] = 1;
per(i, c, 1) S[i - 1] = S[i] * (q[i] + 1);
T = S[0];
fill(B, B + T, N + 1);
rep(i, 1, m) if (ev[i].t == 0) {
if (!lst[i]) {
cmax(A[M[gcd(K, nxt[i] - ev[i].x)]], ev[i].x);
} else if (nxt[i] == N + 1) {
cmin(B[M[gcd(K, ev[i].x - lst[i])]], ev[i].x);
} else {
C[M[gcd(K, gcd(nxt[i] - ev[i].x, ev[i].x - lst[i]))]] = 1;
}
}
rep(i, 1, c) dfs0(1, 0, i);
int res = 0;
rep(i, 0, T - 1) if (!C[i]) {
ll x = (mn - A[i] - 1) / Num[i] + 1;
ll y = (B[i] - 1 - mx) / Num[i] + 1;
res = (res + x % mod * y % mod) % mod;
}
printf("%d\n", res);
return 0;
}
数据太水了
code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6 + 7;
const int P = 1e9 + 7;
int m, T1, T2;
ll N, ans, tot, cnt[MAXN];
struct rec {
ll id, x;
bool operator<(const rec &w)const {
return x < w.x;
}
} a[MAXN], b[MAXN], c[MAXN];
int vis[MAXN];
inline ll gcd(ll x, ll y) {
return y == 0 ? x : gcd(y, x % y);
}
inline void solve(ll x) {
ll rc1 = 0, rc2 = 0;
// for(int i = 0; i <= x; ++i)vvis[i] = 0;
ll tmp1 = 0;
for(int i = 1; i <= T1; ++i) {
if(b[i].x > c[1].x) {
break;
} else {
if(b[i].x % x == c[1].x % x)
tmp1 = b[i].x;
}
}
// printf("c1 %lld\n", tmp1);
rc1 = (c[1].x - tmp1 - 1) / x + 1;
ll tmp2 = N + 1;
for(int i = T1; i >= 1; --i) {
if(b[i].x < c[T2].x) {
break;
} else {
if(b[i].x % x == c[T2].x % x)
tmp2 = b[i].x;
}
}
// printf("c2 %lld\n", tmp2);
rc2 = (tmp2 - c[T2].x - 1) / x + 1;
if(tmp2 == N - N % x + c[1].x % x)rc2 += ((N - c[T2].x) % x == 0);
// printf("QAQ%lld??%lld %lld %lld %lld\n", x, rc1, rc2, c[1].x / x + 1, ((N - c[T2].x) / x + 1));
ans += rc1 * rc2 % P;
ans %= P;
}
inline void build(ll x) {
for(ll i = 1; i * i <= x; ++i) {
if(x % i == 0) {
cnt[++tot] = i;
if(i * i != x) {
cnt[++tot] = x / i;
}
}
}
sort(cnt + 1, cnt + tot + 1);
for(int i = 1; i <= tot; ++i) {
bool flg = 1;
if(vis[i])continue;
// printf("%lld??\n", cnt[i]);
for(int k = 1; k <= m; ++k) {
if((a[k].id == 1) && ((a[k].x % cnt[i] != c[1].x % cnt[i]) || (c[1].x > a[k].x))) {
// printf("%d?\n", k);
flg = 0;
}
if((a[k].id == 0) && (a[k].x % cnt[i] == c[1].x % cnt[i]) && ((c[1].x < a[k].x) && (c[T2].x > a[k].x))) {
// printf("%d!%lld %lld\n", k, c[1].x, a[k].x);
flg = 0;
}
if(!flg)break;
}
if(flg) {
// printf("qwq\n");
for(int j = i; j <= tot; ++j) {
if(cnt[j] % cnt[i] == 0 && !vis[j]) {
solve(cnt[j]);
vis[j] = 1;
}
}
}
}
return ;
}
int main() {
// freopen("test.in", "r", stdin);
// freopen("test1.out", "w", stdout);
scanf("%lld%d", &N, &m);
for(int i = 1; i <= m; ++i) {
scanf("%lld%lld", &a[i].id, &a[i].x);
if(a[i].id == 0) {
b[++T1] = a[i];
} else {
c[++T2] = a[i];
}
}
sort(a + 1, a + m + 1);
// for(int i = 1; i <= m; ++i) {
// printf("%lld %lld\n", a[i].id, a[i].x);
// }
sort(b + 1, b + T1 + 1);
sort(c + 1, c + T2 + 1);
ll tmp1 = 1;
tmp1 = c[2].x - c[1].x;
for(int i = 2; i < T2; ++i) {
// printf("%lld %lld\n", tmp1, c[i + 1].x - c[i].x);
tmp1 = gcd(tmp1, c[i + 1].x - c[i].x);
//预处理
}
// printf("%lld\n", tmp1);
build(tmp1);//建图
printf("%lld\n", ans);
return 0;
}