CF576
CF576A
CF576A题意
给定一个数字 \(n\)，现在 Vasya 要从 \(1\sim n\) 中想一个数字 \(x\)。
Petya 向 Vasya 询问 “\(x\) 是否能整除 \(y\)?” ，通过 Vasya 的回答来判断 \(x\) 的答案。
Petya 的问题一开始就已经准备好，他必须将所有问题都问一遍，不管他当前需不需要问。
他想知道无论 Vasya 想出任何的 \(x\)，
最少要准备多少次询问 \(y\) 的问题才能猜中 \(x\)，并输出一组具体方案。
\(n\leq 1000\)
简要题意：需要你构造一个序列 \(a\)，使得任意的 \(x\in[1,n]\)，由 \(a|x\) 的真假构成的 \(01\) 序列 \(b\) 独一无二。
CF576A题解
对于每一个数字 \(x\)，我们可以将其质因数分解变成 \(p_1^{x_1}p_2^{x_2}\dots p_k^{x_k}\)。
不难发现，对于数字 \(x\)，如果序列中有 \(p_1^{x_1}\) 和 \(p_1^{x_1+1}\)，那么就一定能够判定这个数字有 \(p_1^{x_1}\) 这个因数。
故构造一个序列满足 \(\{x|x=prime_i^k(prime_i^k \le n),prime_i为质数\}\) 就能满足条件。
没了。
CF576A代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1200;
int prime[maxn], tot;
bool book[maxn];
int n;
vector<int> vec;
signed main(){
n = read();
for(int i = 2;i <= n;i++){
if(!book[i])prime[++tot] = i;
for(int j = 1;j <= tot && prime[j] * i <= n;j++){
book[prime[j] * i] = 1;
if(i % prime[j] == 0)break;
}
}
for(int i = 1;i <= tot && prime[i] <= n;i++){
int tmp = prime[i];
while(tmp <= n){vec.push_back(tmp);tmp *= prime[i];}
}
printf("%d\n",vec.size());
for(int i : vec)printf("%d ",i);
puts("");
return 0;
}
CF576B
link
用时：1:14:51.25
CF576B题意
给定一个 \([1,n]\) 的排列 \(p\)，如果设一条边表示为 \((u,v)\)，则要求你构造一棵树 \(T\) 满足
\[\forall (u,v)\in T,(p_u,p_v)\in T \]给出构造方案或者报告无解。
CF576B题解
啥笔Eric被B题卡，好似
如果将 \(i\to p_i\)，不难发现这样的图有以下性质：
- 所有的点入度和出度都是 \(1\)。
- 第一条可以推出这个图一定是由若干个环构成的，证明显然。
- 如果在 \(T\) 中 \(\exists(u,v)\)，则 \(u,v\) 的后继节点也必须相连。
所以不难发现，以下两种情况都是一定有解的：
- 有一个环是自环，则所有点连向这个点一定满足所有条件。
- 有一个环只有两个点，剩下的所有环都有偶数个点。
其余情况一律无解。
构造？
- 有一个环是自环的情况，设这个点是 \(x\)，那么这个点的后继点也是 \(x\)，也就是说，当 \((x,i)\) 相连的时候，\((x,p_i)\) 也必须相连。而刚刚的构造是将所有 \((x,i),i\neq x\) 相连，而所有的 \(i\neq j\) 都不存在 \((i,j)\)，故一定满足条件。
- 有一个环只有两个点，设其为 \((x,p_x)\)，其余所有环都有偶数个点，那么从环上一个位置开始顺时针编号，让所有奇数编号连向 \(x\)，所有偶数编号连向 \(p_x\)，最后在连上 \((x,p_x)\)，那么一定可以满足所有条件。
证明显然，可以自己手玩一下，异或严谨证明都可。
CF576B代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10;
int n, p[maxn];
bool book[maxn];
vector<pair<int,int> > vec;
signed main(){
n = read();
for(int i = 1;i <= n;i++)p[i] = read();
int u = 0;for(int i = 1;i <= n;i++)if(p[i] == i){u = i;break;}
if(u){
puts("YES");
for(int i = 1;i <= n;i++)
if(i != u)printf("%d %d\n",i,u);
return 0;
}
u = 0;
for(int i = 1;i <= n;i++)if(p[p[i]] == i){u = i;book[p[u]] = book[u] = 1;break;}
if(!u){puts("NO");return 0;}
else{
for(int i = 1;i <= n;i++){
if(!book[i]){
int cnt = 0, v = p[i];book[i] = 1;
while(v != i){book[v] = 1;cnt++;v = p[v];}
if((cnt & 1) == 0){puts("NO");return 0;}
v = p[i];vec.push_back(make_pair(p[u],i));
while(v != i){vec.push_back(make_pair(u, v));v = p[v];u = p[u];}
}
}
vec.push_back(make_pair(u,p[u]));
puts("YES");
for(auto i : vec)printf("%d %d\n",i.first,i.second);
}
return 0;
}
CF576C
link
用时1:29:36.12
CF576C题意
在一个平面上有 \(n(n\le 10^6)\) 个点，每个点 \(i\) 有坐标 \((x_i,y_i)(0\le x_i,y_i\le10^6)\)。
现在要求你给出一个排列，使得按照排列顺序行进的曼哈顿距离总和小于 \(2.5\times10^9\)。
要求给出方案，保证有解。
CF576C题解
从未设想的道路
将坐标 \((x_i,y_i)\) 看做区间 \([x_i,y_i]\)，那么 \(i\to j\) 的曼哈顿距离就是在莫队上从 \([x_i,y_i]\) 转移到 \([x_j,y_j]\) 的最小步数。
莫队的奇偶排序就是干这个的，直接 \(sort\) 就完了。
CF576C代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e6 + 10;
int len, n;
struct node{
int l, r, id;
node(int l = 0,int r = 0,int id = 0):l(l),r(r),id(id){}
friend bool operator< (node a,node b){
if(a.l / len != b.l / len)return a.l < b.l;
return ((a.l / len) & 1) ? a.r < b.r : a.r > b.r;
}
}a[maxn];
signed main(){
len = sqrt(n = read());
for(int i = 1;i <= n;i++){
int x = read(), y =read();
a[i] = node(x,y,i);
}
sort(a + 1,a + 1 + n);
for(int i = 1;i <= n;i++)printf("%d ",a[i].id);
puts("");
return 0;
}
CF576D
link
用时：2:39:40.05
CF576D题意
给出一张 \(n\) 点 \(m\) 边的有向图。
每条边 \(i\) 可以经过多次，但是在此之前，必须经过 \(d_i\) 次边（重复经过算多次）才能经过这条边。
问最少经过多少条边才能从 \(1\to n\)，无解输出 Impossible。
\(1\le n,m\le 150,0\le d_i\le10^9\)
CF576D题解
需要对 Floyd 有较深的理解。
设矩阵 \(A^k\) 表示经过 \(k\) 条边 可以/不可以 从 \(i\to j\)。
设矩阵 \(B_k\) 表示由所有 \(d_i<k\) 的边组成的邻接矩阵。
不难发现，\(A^k=(B_k)^k\)，这东西可以矩阵快速幂搞。
然后思路就有了：先将边从小到大排序，然后枚举每条边，设这条边是 \(i\)，那么依次进行以下操作：
- 首先更新 \(A^{tim_{i-1}}\) 到 \(A^{time_i}\)。
- 然后将 \(B_{u_i,v_i}\) 标记为 \(1\)。
- 将所有 \(B_{1,i}=1\) 的 \(i\) 加入队列，跑 \(bfs\)。
- 更新答案 \(ans\gets dis_n+time_i\)
最后注意初始状态下 \(A\) 是单位矩阵，\(B\) 是全 \(0\) 矩阵。
CF576D代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 155;
int n, m;
struct edge{
int u, v, w;
edge(int u = 0,int v = 0,int w = 0):u(u),v(v),w(w){}
friend bool operator < (edge a,edge b){return a.w < b.w;}
}edg[maxn];
struct Matrix{
bitset<maxn> a[maxn];
Matrix(bool opt = 0){for(int i = 1;i <= n;i++){a[i].reset(n);a[i][i] = opt;}}
friend Matrix operator * (Matrix a,Matrix b){
Matrix c = Matrix();
for(int i = 1;i <= n;i++)
for(int k = 1;k <= n;k++)
if(a.a[i][k])
c.a[i] |= b.a[k];
return c;
}
friend Matrix operator ^ (Matrix a,int b){
Matrix res = Matrix(1);
while(b){
if(b & 1)res = res * a;
a = a * a;b >>= 1;
}
return res;
}
}A,B;
int dis[maxn];
queue<int> que;
void bfs(){
memset(dis,0x3f,sizeof(dis));
while(!que.empty())que.pop();
for(int i = 1;i <= n;i++)
if(A.a[1][i]){que.push(i);dis[i] = 0;}
if(!dis[n])return;
while(!que.empty()){
int u = que.front();que.pop();
for(int v = 1;v <= n;v++)
if(B.a[u][v] && dis[v] == 0x3f3f3f3f3f3f3f3f){
dis[v] = dis[u] + 1;que.push(v);
}
}
}
signed main(){
n = read(); m = read();int u, v, w;
for(int i = 1;i <= m;i++){
u = read(); v = read(); w = read();
edg[i] = edge(u, v, w);
}
sort(edg + 1,edg + 1 + m);
int tim = 0,ans = 0x3f3f3f3f;dis[n] = 0x3f3f3f3f;
A = Matrix(1);B = Matrix();edg[m + 1].w = -1;
for(int i = 1;i <= m;i++){
if(ans < edg[i].w)break;
int dif = edg[i].w - tim;tim = edg[i].w;
A = A * (B ^ dif); B.a[edg[i].u][edg[i].v] = 1;
if(edg[i].w != edg[i + 1].w)bfs();
ans = min(ans,tim + dis[n]);
}
if(ans == 0x3f3f3f3f)puts("Impossible");
else printf("%lld\n",ans);
return 0;
}
CF576E
CF576E题意
给定一张 \(n\) 个点 \(m\) 条边的无向图。
一共有 \(k\) 种颜色，一开始，每条边都没有颜色。
定义合法状态为仅保留染成 \(k\) 种颜色中的任何一种颜色的边，图都是一张二分图。
有 \(q\) 次操作，第 \(i\) 次操作将第 \(e_i\) 条边的颜色染成 \(c_i\)。
但并不是每次操作都会被执行，只有当执行后仍然合法，才会执行本次操作。
你需要判断每次操作是否会被执行。
\(n,m,q \le 5 \times 10^5\)，\(k \le 50\)。
CF576E题解
线段树分治现学的。
不会线段树分治的自行右转到线段树分治模板。
现在默认大家都会线段树分治。
考虑这道题怎么用。
首先开 \(k\) 个线段树维护这是肯定的了。
如果所有的执行都会成立，怎么做？
对于同一条边 \(i\)，对于两个相邻的染色操作 \(q_x=(i,a)\) 和 \(q_y=(i,b)\)，\(q_x\) 的生效区间是 \([x+1,y-1]\)，这个完全可以线段树分治搞。
但是现在有的操作不会执行，怎么办呢？
首先不难发现操作执行就是把 \([x+1,y-1]\) 赋值为新颜色，否则赋值为原来的颜色。
回忆一下线段树分治是怎么做的。
一定会先更新完 \(i\) 再去更新 \(x+1\) 对吧？
于是我们就会在下一个边加入之前确定这个边的颜色。
然后就没了。
不过需要注意下空间。
CF576E代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
bool st;
const int maxn = 5e5 + 10;
int n, m, k, q;
pair<int,int> edg[maxn];
int id[maxn], col[maxn];
int r[maxn];
struct DSU{
typedef pair<pair<int,int>,int> T;
struct Stack{
T s[maxn];int tp;
inline T top(){return s[tp];}
inline bool pop(){if(!tp)return false;tp--;return true;}
inline void push(T x){s[++tp] = x;}
Stack(){tp = 0;}
};
stack<T> opt;
int fa[maxn << 1], hei[maxn << 1];
int getf(int x){return fa[x] == x ? x : getf(fa[x]);}
void init(int x = 0){for(int i = 1;i <= x;i++)fa[i] = i, hei[i] = 1;}
void merge(int x,int y){
x = getf(x); y = getf(y);
if(x == y)return;
if(hei[x] > hei[y])swap(x, y);
opt.push(make_pair(make_pair(x, y),hei[x] == hei[y]));
fa[x] = y;hei[y] += hei[x] == hei[y];
}
void trace(){
if(!opt.size())return;
auto u = opt.top();opt.pop();
fa[u.first.first] = u.first.first;
hei[u.first.second] -= u.second;
}
void trace(int lsttop){
while(opt.size() != lsttop){
auto u = opt.top();opt.pop();
fa[u.first.first] = u.first.first;
hei[u.first.second] -= u.second;
}
}
inline int version(){return opt.size();}
};
DSU dsu[51];
int lst[maxn], ncol[maxn];
bool ans[maxn];
struct Seg_Tree{
typedef int T;
vector<T> d[maxn << 2];
void init(int x = 0,int y = 0){for(int i = 1;i <= x;i++)dsu[i].init(y * 2);}
void update(int l,int r,int s,int t,int p,T x){
if(s <= l && r <= t){d[p].push_back(x);return;}
int mid = l + r >> 1;
if(s <= mid)update(l,mid,s,t,p << 1,x);
if(mid < t)update(mid + 1,r,s,t,p << 1 | 1,x);
}
void getans(int l,int r,int p){
vector<int> lsttop;lsttop.clear();lsttop.push_back(0);
for(int i = 1;i <= k;i++){lsttop.push_back(dsu[i].version());}
for(T i : d[p]){
int pos = id[i], col = ::col[i];
int u = edg[pos].first, v = edg[pos].second;
if(col){
dsu[col].merge(u, v + n);
dsu[col].merge(u + n,v);
}
}
if(l == r){
int pos = id[l], col = ::col[l];
int u = edg[pos].first, v = edg[pos].second;
int fu = dsu[col].getf(u), fv = dsu[col].getf(v);
if(fu == fv)puts("NO"),::col[l] = ncol[pos];
else puts("YES"),ncol[pos] = ::col[l];
}
if(l != r){
int mid = l + r >> 1;
getans(l,mid,p << 1);
getans(mid + 1,r,p << 1 | 1);
}
for(int i = 1;i <= k;i++){dsu[i].trace(lsttop[i]);}
}
void update(int l,int r,T x){update(1,q,l,r,1,x);}
}tree;
bool ed;
signed main(){
// cerr << (&ed - &st) / 1024 / 1024 << " Mib" << endl;
n = read(); m = read(); k = read(); q = read();
tree.init(k,n);int u, v;
for(int i = 1;i <= m;i++){
u = read(); v = read();
edg[i] = make_pair(u, v);
}
for(int i = 1;i <= q;i++){id[i] = read(); col[i] = read();ans[i] = true;}
for(int i = 1;i <= m;i++){lst[i] = q + 1;ncol[i] = 0;}
for(int i = q;i;i--){
r[i] = lst[id[i]];lst[id[i]] = i;
if(i < r[i] - 1)tree.update(i + 1,r[i] - 1,i);
}
tree.getans(1,q,1);
return 0;
}