Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) E~G 题解
CF1553E Permutation Shift
题面
容易发现,如果进行 \(m\) 次交换,最多有 \(2m\) 个数改变位置,即最少有 \(n-2m\) 个数没有改变位置。
因此,我们开一个桶 \(cnt_i\) 算出循环移位后 \(1\) 的位置在 \(i\) 时有多少个数没有改变位置,即 \([n-i,\dots,n,1,2,\dots,n-i+1]\) 和 原序列 位置相同且值相同的个数。只有当 \(cnt_i\ge n-2m\) 时 \(i\) 才可能作为循环移位后 \(1\) 的位置。
因为 \(0\le m\le \frac{n}{3}\),那么 \(\frac{n}{3}\le n-2m\le n\)。所以最多有 \(3\) 个位置可能作为答案,暴力即可。
#include
#define DC int T = gi (); while (T--)
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
typedef pair PLI;
typedef pair PLL;
template
inline T gi()
{
T x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
template inline T abs(T x) {return x < 0 ? -x : x;}
const int N = 300003, M = N << 1;
int n, m, p[N], cnt[N];
int fa[N], sz[N];
int getf(int u) {return fa[u] == u ? u : fa[u] = getf(fa[u]);}
inline bool check(int x)
{
for (int i = 1; i <= n; i+=1) fa[i] = i, sz[i] = 1;
for (int i = x; i <= n; i+=1)
{
int u = getf(i - x + 1), v = getf(p[i]);
if (u != v)
{
fa[u] = v;
sz[v] += sz[u];
}
}
for (int i = 1; i < x; i+=1)
{
int u = getf(n - x + 1 + i), v = getf(p[i]);
if (u != v)
{
fa[u] = v;
sz[v] += sz[u];
}
}
int cnt = 0;
for (int i = 1; i <= n; i+=1)
if (getf(i) == i) cnt += sz[getf(i)] - 1;
return cnt <= m;
}
inline void solve()
{
n = gi (), m = gi ();
for (int i = 1; i <= n; i+=1) cnt[i] = 0, p[i] = gi ();
for (int i = 1; i <= n; i+=1)
if (p[i] <= i) ++cnt[i - p[i] + 1];
else ++cnt[n - (p[i] - i) + 1];
vector ans;
for (int i = 1; i <= n; i+=1)
if (cnt[i] >= n - 2 * m)
if (check(i)) ans.pb(i - 1);
cout << ans.size() << ' ';
for (auto x : ans) cout << x << ' ';
puts("");
return;
}
int main()
{
DC solve();
return 0;
}
CF1553F Pairwise Modulo
题面
化简式子:
\[\begin{aligned} p_i-p_{i-1}&=\sum\limits_{j因为 \(a_i\) 互不相同,所以直接枚举倍数做复杂度是对的。
树状数组即可。
#include
#define DC int T = gi (); while (T--)
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
typedef pair PLI;
template
inline T gi()
{
T x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
template inline T abs(T x) {return x < 0 ? -x : x;}
const int N = 300003, M = N << 1;
int n, a[N];
struct BIT
{
LL tr[N];
#define lowbit(i) (i & (-i))
void add(int u, int x) {for (int i = u; i <= 300000; i += lowbit(i)) tr[i] += x;}
LL query(int x) {LL res = 0; for (int i = x; i; i -= lowbit(i)) res += tr[i]; return res;}
LL query(int l, int r) {return query(r) - query(l - 1);}
} t1, t2;
int main()
{
n = gi ();
for (int i = 1; i <= n; i+=1) a[i] = gi ();
int mx = *max_element(a + 1, a + 1 + n);
LL sum = 0, ps = 0;
for (int i = 1; i <= n; i+=1)
{
sum += ps + 1ll * a[i] * (i - 1) - t1.query(a[i]);
ps += a[i];
for (int j = a[i]; j <= mx; j+=a[i])
sum -= 1ll * a[i] * (j / a[i]) * t2.query(j, min(mx, j + a[i] - 1));
for (int j = a[i]; j <= mx; j+=a[i])
t1.add(j, a[i]);
printf("%lld ", sum);
t2.add(a[i], 1);
}
return 0;
}
CF1553G Common Divisor Graph
题面
结论:答案至多为 \(2\)。
证明:建两个新点 \(a_s\times(a_s+1)\) 和 \(a_t\times(a_t+1)\),它们都是 \(2\) 的倍数。得证。
用一个并查集,将每个数和它的质因子合并。那么属于同一个集合的都可以直接到达。
分类讨论:
- 答案为 \(0\):直接判断 \(a_s\) 和 \(a_t\) 是否在同一个集合内。
- 答案为 \(1\):对于每一个数 \(a_i\),记录 \(a_i+1\) 能到达的集合,压到一个 vector 里面。看 \(a_s\) 所在的集合与 \(a_t\) 所在的集合是否在 vector 中存在,即能否通过新建一个点到达。
- 其他情况答案为 \(2\)。
#include
#define DC int T = gi (); while (T--)
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
typedef pair PLI;
typedef pair PLL;
template
inline T gi()
{
T x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
template inline T abs(T x) {return x < 0 ? -x : x;}
const int N = 150003, M = N << 1;
int n, q, a[N];
int fa[1000003];
vector v;
int stk[N], tp;
int getf(int u) {return fa[u] == u ? u : fa[u] = getf(fa[u]);}
int main()
{
n = gi (), q = gi ();
for (int i = 1; i <= n; i+=1) a[i] = gi ();
for (int i = 1; i <= 1000000; i+=1) fa[i] = i;
for (int i = 1; i <= n; i+=1)
{
int tmp = a[i];
for (int j = 2; 1ll * j * j <= tmp; j+=1)
if (tmp % j == 0)
{
fa[getf(j)] = getf(a[i]);
while (tmp % j == 0) tmp /= j;
}
if (tmp > 1) fa[getf(tmp)] = getf(a[i]);
}
for (int i = 1; i <= n; i+=1)
{
int tmp = a[i] + 1;
tp = 0;
stk[++tp] = a[i];
for (int j = 2; 1ll * j * j <= tmp; j+=1)
if (tmp % j == 0)
{
stk[++tp] = j;
while (tmp % j == 0) tmp /= j;
}
if (tmp > 1) stk[++tp] = tmp;
for (int k = 1; k <= tp; k+=1) for (int j = k; j <= tp; j+=1) {int x = getf(stk[k]), y = getf(stk[j]); v.pb({min(x, y), max(x, y)});}
}
sort(v.begin(), v.end());
unique(v.begin(), v.end());
while (q--)
{
int s = gi (), t = gi ();
s = getf(a[s]), t = getf(a[t]);
if (s > t) swap(s, t);
if (s == t) puts("0");
else
{
auto it = lower_bound(v.begin(), v.end(), mp(s, t));
if (it != v.end() && (*it) == mp(s, t)) puts("1");
else puts("2");
}
}
return 0;
}