Div. 2
Multiplication Table (577A)
题意：
给定n行n列的方阵，第i行第j列的数就是i*j，问有多少个格子上的数恰为x。
1<=n<=10^5, 1<=x<=10^9
题解：
送分题…对于每一行，判断是否存在数x即可…也可以枚举x的因子判断是否出现在表内…
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstring>
inline int read()
{
int s = ; char c; while((c=getchar())<'0'||c>'9');
do{s=s*+c-'0';}while((c=getchar())>='0'&&c<='9');
return s;
}
int n,i,x,ans;
int main()
{
n = read(); x = read();
for(i=;i<=n;i++) if(x%i==) if(x/i<=n) ans++;
printf("%d\n",ans);
return ;
}
Modulo Sum (577B)
题意：
给定长度为n的数列，判断是否存在和可以被m整除的子序列
1<=n<=10^6, 2<=m<=10^3, 0<=ai<=10^9
题解：
其实我看到这个数据范围以为是暴力的…
结果确实很多人拿O(nm)的暴力过了（只能说CF的评测机太快了）
我一开始写的是用bitset压位暴力，
用b[i]表示可以得到余数i，那么加入一个新的数就可以把所有为1的b[i]转移到b[(i+a[x])%m]，
于是我就拿bitset的位运算来做…
（既然别人暴力都过了，我的暴力当然也能过去，其实复杂度上来看也是可以过的）
不过其实并不用考虑大数据…
考虑前缀和（这题求的是子序列而不是子段，但是显然子段也是一个子序列，存在子段也代表答案是YES）
我们知道模m的剩余系大小为m，根据抽屉原理，当n>=m+1时，必定有两个元素关于模m同余。
而如果前缀和中 sum[l] ≡ sum[r] (mod m)，说明子段(l,r]就是满足条件的子序列。
所以只要n>m，答案就是YES。
所以实际复杂度就降为O(m^2)了
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstring>
#include <bitset>
using namespace std;
inline int read()
{
int s = ; char c; while((c=getchar())<'0'||c>'9');
do{s=s*+c-'0';}while((c=getchar())>='0'&&c<='9');
return s;
}
int n,m,i,a[];
bitset<> bs,tmp;
bool sol()
{
if(n>m) return ;
for(i=;i<=n;i++)
{
tmp = bs<<a[i];
bs |= bs>>(m-a[i]);
bs |= tmp;
bs[a[i]] = ;
if(bs.test()) return ;
}
return ;
}
int main()
{
n = read(); m = read(); if(n<=m) for(i=;i<=n;i++) a[i] = read()%m;
printf(sol()?"YES\n":"NO\n");
return ;
}
Div. 1
Vasya and Petya's Game (576A) (577C)
题意：
未知整数x∈[1,n]，每次询问可以知道x是否被某数y整除，问最少需要问多少次才可以确定x的具体数值。
1<=n<=10^3
题解：
我自己的做法是，
从小到大遍历1~n里的每一个数，
如果它的因子中所有被询问的数的最小公倍数t不等于自身，则说明需要询问这个数。
因为如果t等于自身，所有询问结果都是“是”的情况就可以唯一确定这个数。
否则就无法区分t与当前数。
而官方题解的做法是，因为如果不询问p^k就无法区分p^(k-1)和p^k，所以每个p^k(k>0)都要询问。
后来我仔细想了一下，这两个做法其实是等价的。
因为因子中所有被询问的数的最小公倍数不等于自身的，只有底数为质数的幂。
具体来说的话，
1、显然质数是要询问的
2、当前数为合数，且是底数为质数的幂
如果当前数是p^a，因为只有形如p^b (b|a, b<a) 的因子，
所以它们的最小公倍数一定小于p^a，也就是说p^a要被询问。
3、当前数为合数，且不是底数为质数的幂
根据算术基本定理，合数n可以表示成 p1^a1 * p2^a2 * … * pk^ak，
显然 p1^a1、p2^a2…pk^ak 两两互质。
又因为所有pi^ai会被询问，所以这些数的最小公倍数一定就是n本身，
所以此时不用询问。
回到这题，只要筛出素数，并输出它的幂即可。
复杂度O(n)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstring>
int n,i,j,s,t,tt,a[],pr[],ps;
bool b[];
int main()
{
scanf("%d",&n); s = ;
for(i=;i<=n;i++)
{
if(!b[i])
{
pr[++ps] = i;
for(j=i;j<=n;j*=i) a[++s] = j;
}
for(j=;j<=ps&&i*pr[j]<=n;j++)
{
b[i*pr[j]] = ;
if(i%pr[j]==) break;
}
}
printf("%d\n",s);
for(i=;i<s;i++) printf("%d ",a[i]);
if(s) printf("%d\n",a[s]);
return ;
}
Invariance of Tree (576B) (577D)
题意：
给定长为n的序列p1..pn，要求输出一棵树满足：u与v相连 当且仅当 p[u]与p[v]相连
有解输出YES和任意一个解的树上的所有边，无解输出NO。
1<=n<=10^5
题解：
构造…
这题的突破口就是题目名字…
重点在于找到可行解中进行置换后不变的东西。
（不变的是一个点）如果存在一个数a=p[a]，那么把所有其它点连到这个点就是一个可行解。
（不变的是一条边）也就是说存在两个数，满足a=p[a]且b=p[b]。这个时候的情况会稍微复杂一点。
因为虽然这条边不动，但是两个端点交换了位置，如果边的两端点的子树不同，置换后就不满足要求。
所以同时要满足这条边两端子树中的节点也恰好交换位置。
所以可以找到每一个环，
把环上奇数位置的点连到a，偶数位置的连到b（置换后ab互换，同时这些点也互换位置）
不过这样做，在存在奇数个元素的环的时候就不行了，这时无法构造。
（注意这时如果存在第一种情况的构造就可以按照第一种情况来）
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstring>
inline int read()
{
int s = ; char c; while((c=getchar())<'0'||c>'9');
do{s=s*+c-'0';}while((c=getchar())>='0'&&c<='9');
return s;
}
const int N = ;
int n,i,j,nx[N],st,st2,l,tmp,ev;
bool b[N];
int main()
{
n = read();
for(i=;i<=n;i++) nx[i] = read();
l = -; ev = ;
for(i=;i<=n;i++)
{
for(j=i,tmp=;!b[j];j=nx[j],tmp++) b[j] = ;
if(l!=&&tmp==) st = i, l = ;
if(l==-&&tmp==) st = i, st2 = nx[i], l = ;
if(tmp&) ev = ;
}
if(l==-||(l==&&!ev)) printf("NO\n");
else{
printf("YES\n");
if(l==){ for(i=;i<=n;i++) if(i!=st) printf("%d %d\n",st,i); }
else{
printf("%d %d\n",st,st2);
memset(b,,sizeof b); tmp = ;
for(i=;i<=n;i++)
{
if(i==st||i==st2) continue;
for(j=i;!b[j];j=nx[j],tmp^=) b[j] = , printf("%d %d\n",j,tmp?st2:st);
}
}
}
return ;
}
Points on Plane (576C) (577E)
题意：
给定n个点，求一条经过所有点的路径，它的总曼哈顿距离<25*10^8
1<=n<=10^6, 0<=x,y<=10^6
题解：
完全的乱搞题…一开始感觉无从下手…样例也是用来搞笑的…
正确的做法是按照[x/1000]分块…每块中按照y坐标排序…
然后交替从高到低、从低到高地走，然后就构造出答案了。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long lint;
const int N = ;
lint x[N],y[N],i,j,n;
bool p;
vector<int> vct[];
vector<int>::iterator it;
vector<int>::reverse_iterator rit;
inline int read()
{
int s = ; char c; while((c=getchar())<'0'||c>'9');
do{s=s*+c-'0';}while((c=getchar())>='0'&&c<='9');
return s;
}
inline int abs(int a){ return a>?a:-a; }
bool cmp(const int &a,const int &b){ return y[a]<y[b]; }
int main()
{
n = read();
for(i=;i<=n;i++)
{
x[i] = read(), y[i] = read();
vct[x[i]/].push_back(i);
}
for(i=;i<=;i++)
{
if(vct[i].empty()) continue;
p^=;
sort(vct[i].begin(),vct[i].end(),cmp);
if(p) for(rit=vct[i].rbegin();rit!=vct[i].rend();rit++) printf("%d ",(*rit));
else for(it=vct[i].begin() ;it!=vct[i].end() ;it++ ) printf("%d ",(*it));
}
return ;
}
Flights for Regular Customers (576D)
题意：
给定一个有向图，图上的边有限制条件，必须满足经过的边数（包括相同）达到限制条件才可以同行。
存在自环。
2<=n<=150, 1<=m<=150
题解：
150…想想发现好像不是网络流…
嗯就DP好了。f[i][j]表示i步后能否在j这个点。
很显然这个DP可以用转移矩阵跑快速幂来弄…
然后对于从小到大的每个限制条件，
如果满足较大的条件时仍然不能到达，那么只满足较小的条件时也一定不能到达。
看到这种性质…我就直接二分了…然而因为转移时也有m的因子，所以二分没什么用…
于是写了从小到大枚举满足的条件，如果满足后能够到达，就在这一个条件和下一个条件之间二分…
然后就有了复杂度爆炸的解法…被卡了很多次…尽管是CF上的4s…
主要有两点优化，都是在矩阵乘法时优化，（因为矩阵是01矩阵所以可以优化）
一个是改变矩阵乘法时的循环顺序，改为i-k-j循环，那么如果a[i][k]==0，则所有a[i][k]&b[k][j]都是0，这时可以continue掉…
另一个是在上面加上bitset…等于直接压位然后位运算来算矩阵了…
（其实加上第一个之后我就已经1s内过了）
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
inline int read()
{
int s = ; char c; while((c=getchar())<'0'||c>'9');
do{s=s*+c-'0';}while((c=getchar())>='0'&&c<='9');
return s;
}
const int N = ;
typedef bitset<N> bs;
int n,m,i,j,po,l,r,mid,stp[N],dt,ie,ans,ymd;
struct eg{int aa,bb,d;}e[N];
struct mrx{
bs nu[];
void clr(){ memset(nu,,sizeof nu); }
friend mrx operator * (const mrx &a,const mrx &b)
{
mrx c; c.clr();
for(int i=;i<n;i++) for(int k=;k<n;k++) if(a.nu[i][k])
c.nu[i] |= b.nu[k];
return c;
}
}ym,tm,sm,tmp;
bool cmp(const eg &a,const eg &b){ return a.d<b.d; }
mrx powmrx(mrx a,int b)
{
mrx ans; ans.clr(); for(int i=;i<n;i++) ans.nu[i][i] = ;
for(;b;b>>=)
{
if(b&) ans = ans*a;
a = a*a;
}
return ans;
}
void sol(int curp)
{
l = ; r = e[stp[curp+]].d-e[stp[curp]].d-;
while(l<=r)
{
mid = (l+r)>>;
sm = ym*powmrx(tm,mid);
if(sm.nu[][n-])
ans = mid, r = mid-;
else
l = mid+;
}
}
int main()
{
n = read(); m = read();
for(i=;i<=m;i++) e[i].aa = read(), e[i].bb = read(), e[i].d = read();
std::sort(e+,e++m,cmp);
e[].d = -;
for(i=;i<=m;i++) if(e[i].d!=e[i-].d) stp[++dt] = i;
e[stp[dt+] = m+].d = +n;
po = ; tm.nu[n-][n-] = ; ym.nu[][] = ;
ans = -;
if(e[].d==)
for(i=;i<=dt;i++)
{
for(j=stp[i],ie=stp[i+];j<ie;j++) tm.nu[e[j].aa-][e[j].bb-] = ;
tmp = ym*powmrx(tm,e[stp[i+]].d-e[stp[i]].d);
if(tmp.nu[][n-])
{
sol(i);
if(ans!=-){ ans += e[stp[i]].d; break; }
}
ym = tmp;
}
if(ans==-) printf("Impossible\n");
else printf("%d\n",ans);
return ;
}
Painting Edges (576E)
题意：
给定n点m边的无向图，有q次询问，k种颜色。
对于每个询问，如果操作后对应颜色能够构成二分图，则改变颜色并输出YES
否则不改变颜色，并输出NO
2<=n<=10^5
1<=m,q<=10^5
1<=k<=50
题解：
线段树+暴力维护并查集…
并查集维护的方法就是维护奇偶性。在不同集合之间的边显然可以，同一集合内奇偶性不同的边也可以。
用线段树存所有的询问。题目最大的难点在于某种颜色对应的边被删除…
换一种角度看，就是这条边的颜色会保持到下次改变这条边之前。
所以拿线段树来暴力维护并查集状态就好了…
求答案就是按1~q在线段树的叶节点跑。
（这种维护并查集不能路径压缩，所以要按秩合并，否则超时非常严重）
（深深地体会到了这种差别）
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = ;
typedef pair<int,int> pii;
int n,m,i,j,k,Q,ql,qr,qc,qe,nx[N],tnx[N],rcol[N];
pii e[N],q[N];
vector<pii> mgv[];
struct revdt
{
int c,p,f,z,s;
revdt(int _c,int _p,int _f,int _z,int _s){c=_c,p=_p,f=_f,z=_z,s=_s;}
};
typedef vector<revdt> revvct;
struct revdsu
{
int f[N],z[N],s[N];
pii findf(int a){ int ss=; while(a!=f[a]) ss^= s[a], a = f[a]; return make_pair(a,ss); }
bool dis(int a,int b){ return findf(a)!=findf(b); }
void merge(int a,int b,int col,revvct &vct)
{
pii pa = findf(a), pb = findf(b);
int fa = pa.first, fb = pb.first;
if(fa==fb) return;
bool fl = ;
if(z[fa]==z[fb]) z[fa]++, fl = ;
if(z[fa]>z[fb]) swap(fa,fb);
vct.push_back(revdt(col,fa,f[fa],z[fa]-(fl?:),s[fa]));
f[fa] = fb; s[fa] = pa.second^pb.second^;
}
}osu[];
inline int read()
{
int s = ; char c; while((c=getchar())<'0'||c>'9');
do{s=s*+c-'0';}while((c=getchar())>='0'&&c<='9');
return s;
}
void add(int p,int l,int r)
{
if(ql<=l&&r<=qr)
{
mgv[p].push_back(make_pair(qc,qe));
return;
}
int m = (l+r)>>;
if(ql<=m) add(p+p,l,m);
if(qr>m) add(p+p+,m+,r);
}
void query(int p,int l,int r)
{
revvct vct;
for(vector<pii>::iterator it=mgv[p].begin();it!=mgv[p].end();it++)
osu[it->first].merge(e[it->second].first,e[it->second].second,it->first,vct);
if(l>=r)
{
qe = q[l].first;
int a = e[qe].first, b = e[qe].second, co = q[l].second;
if(osu[co].dis(a,b)) printf("YES\n"), rcol[qe] = co;
else printf("NO\n");
ql = l+, qr = nx[l]-, qc = rcol[qe];
if(rcol[qe]) add(,,Q);
}
else
{
int m = (l+r)>>;
query(p+p,l,m);
query(p+p+,m+,r);
}
while(!vct.empty())
{
revdt it = vct.back();
osu[it.c].f[it.p] = it.f;
osu[it.c].z[it.p] = it.z;
osu[it.c].s[it.p] = it.s;
vct.pop_back();
}
}
int main()
{
n = read(); m = read(); k = read(); Q = read();
for(i=;i<=n;i++) for(j=;j<=k;j++) osu[j].f[i] = i;
for(i=;i<=m;i++) e[i].first = read(), e[i].second = read(), tnx[i]=Q+;
for(i=;i<=Q;i++) q[i].first = read(), q[i].second = read();
for(i=Q;i;i--){ nx[i] = tnx[q[i].first]; tnx[q[i].first] = i; }
query(,,Q);
return ;
}