Fork me on GitHub

Codeforces Round #595 (Div. 3)

降智题真的可以为所欲为.

Yet Another Dividing into Teams

思路

因为题目中有个条件叫做每个$a_i$互不相同,所以我们可以先排序之后看一下$a_i$于$a_{i-1}$的差的绝对值是否为$1$.如果有的话答案就是$2$,否则答案显然为$1$.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

int n , ans;
int num[105];

int main ( void ) {
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++)
cin>>num[i];
sort(num+1,num+1+n);
ans=1;
for(int i=2;i<=n;i++)
if(abs(num[i]-num[i-1])==1)
ans=2;
cout<<ans<<endl;
}
return 0;
}

Books Exchange

思路

$B1$和$B2$就一起说了….首先如果$i$可以把他的信息传给$d_i$,那么我们由信息传递那道题的思路可知我们可以从$i$到$d_i$连一条边.而每个点要知道自己的信息,就是要在自己所在的强连通分量中走一圈.即每个点的答案就是每个点所在强连通分量的大小.
又因为题目保证一定有解,所以直接$Tarjan$缩点然后直接统计$size$即可,多测注意清空.

代码

1
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
#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n,t,idx,Bcnt;
int head[N];
struct Edge{
int to;
int next;
}e[N<<1];
int dfn[N],low[N];
int Belong[N],siz[N];

inline void add ( int x , int y ) {
e[++t].to = y;
e[t].next = head[x];
head[x] = t;
return;
}
stack < int > st;
bool instack[N];
void Tarjan ( int cur ) {
st.push ( cur );
dfn[cur] = low[cur] = ++idx;
instack[cur] = 1;
for ( int i = head[cur] ; i ; i = e[i].next ) {
int j = e[i].to;
if ( !dfn[j] ) {
Tarjan ( j );
low[cur] = min ( low[cur] , low[j] );
}
else if ( instack[j] )
low[cur] = min ( low[cur] , dfn[j] );
}
int k;
if ( dfn[cur] == low[cur] ) {
Bcnt++;
do {
k = st.top ();
instack[k] = 0;
st.pop ();
Belong[k] = Bcnt;
siz[Belong[k]]++;
} while ( k != cur );
}
return;
}

int main ( void ) {
ios :: sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--){
t=0;
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
cin>>n;
for(int i=1;i<=n;i++){
int to;
cin>>to;
add(i,to);
}
for(int i=1;i<=n;i++)
if (!dfn[i] ) {
while(!st.empty())
st.pop();
Tarjan(i);
}
//cout<<t<<endl;
for(int i=1;i<=n;i++)
cout<<siz[Belong[i]]<<" ";
cout<<endl;
}
return 0;
}

Good Numbers (easy version)

思路

我们发现在$3^i<=10000$的情况下$i$最大只到$10$,所以我们可以$2^{log_3n}$的时间复杂度枚举一下所有的$good$数,每次询问时$check$一下即可.

代码

1
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
#include<bits/stdc++.h>
using namespace std;
int n,idx;
int num[10004];
inline int ksm(int x,int y){
int res=1;
while(y){
if(y&1)
res*=x;
x=x*x;
y>>=1;
}
return res;
}
int main ( void ) {
ios :: sync_with_stdio(false);
cin.tie(0),cout.tie(0);
for(int i=1;i<=(1<<10)-1;i++){
int now=0;
for(int j=0;j<=10;j++)
if(i&(1<<j))
now=now+ksm(3,j);
num[++idx]=now;
}
sort(num+1,num+1+idx);
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=idx;i++)
if(num[i]>=n){
cout<<num[i]<<endl;
break;
}
}
return 0;
}

Good Numbers (hard version)

思路

考虑$C1$中的思路发现这样枚举的话太费事了.所以我们可以先找到一个小于$n$的$good$数,而这个数显然可以贪心的在$O(log_3n)$的复杂度内求出来.然后我们考虑怎么让这个数字增加.
我们用二进制表示每个$3^i$是否被加入到这个数字里,那么我们可以发现我们要做的就是找到一个二进制下最左边的右边是$0$的$1$,把$0$变成$1$,然后把前边的$1$都变成$0$然后统计新的数字是什么即可.

代码

1
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
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
bool used[42];
inline int ksm(int x,int y){
int res=1;
while(y){
if(y&1)
res*=x;
x=x*x;
y>>=1;
}
return res;
}
signed main ( void ) {
ios :: sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--){
memset(used,0,sizeof(used));
cin>>n;
int tmp=n,res=0;
int MAX=40,MAXX=-1;
while(tmp){
int sign=0;
if(MAX<=0)
break;
for(int i=0;i<MAX;i++){
if(ksm(3,i)>tmp){
MAXX=max(MAXX,i);
break;
}
sign=i;
}
used[sign]=1;
tmp-=ksm(3,sign);
res+=ksm(3,sign);
MAX=sign;
}
if(res==n)
cout<<res<<endl;
else{
int sign;
for(int i=40;i>=0;i--)
if(used[i]){
sign=i;
break;
}
int css=0;
for(int i=0;i<=sign;i++){
if(used[i]==1&&used[i+1]==0){
css = ksm ( 3 , i + 1 );
for ( int j = i + 2 ; j <= sign ; j++ )
if ( used[j] )
css = css + ksm ( 3 , j );
break;
}
}
cout <<css << endl;
}

}
return 0;
}

Too Many Segments (easy version)

思路

发现我们只需要每次找到一个被覆盖次数大于$k$的点,然后寻找一下覆盖了这个点的区间中右端点最靠右的贪心的删去即可.
时间复杂度$O(n^2)$.

代码

1
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
#include <bits/stdc++.h>
using namespace std;

const int N = 205;

int n , k;
struct Sen { int l,r,id; } se[N];
bool use[N];
int num[N];
int opt[N] , ans;

int main ( void ) {

ios :: sync_with_stdio ( false );
cin.tie ( 0 ) , cout.tie ( 0 );
cin >> n >> k;

int MinLim = 2147483647 , MaxLim = -1;

for ( int i = 1 ; i <= n ; i++ ) {
cin >> se[i].l >> se[i].r;
se[i].id = i;
MinLim = min ( MinLim , se[i].l ) , MaxLim = max ( MaxLim , se[i].r );}
for ( int i = 1 ; i <= n ; i++ )
for ( int j = se[i].l ; j <= se[i].r ;j++ )
num[j]++;
for ( int i = MinLim ; i <= MaxLim ; i++ ) {
while ( num[i] > k ) {
int MaxDisTanceR = -1 , MaxDisTanceSign = -1;
for ( int j = 1 ; j <= n ; j++ )
if ( se[j].l <= i && se[j].r >= i && !use[j] )
if ( MaxDisTanceR < se[j].r ) {
MaxDisTanceR = se[j].r , MaxDisTanceSign = j;}
use[MaxDisTanceSign] = 1;
opt[++ans] = MaxDisTanceSign;
for ( int j = se[MaxDisTanceSign].l ; j <= se[MaxDisTanceSign].r ; j++ )
num[j]--;
}
}
cout << ans << endl;
for ( int i = 1 ; i <= ans ; i++ )
cout << opt[i] << " ";
return 0;
}

Too Many Segments (hard version)

思路

我们发现按照右端点排序之后,对于每个区间,如果它即将要覆盖的这个区间的最大值小于$k$的话,那么直接覆盖是没有问题的.
否则考虑对后面的贡献的话,如果这个区间之前的区间不选择的话,那么前边的区间不选一定比不选现在的这个区间更劣.(因为删除排序后前边的节点对后面的贡献更小).
所以我们需要一个可以维护区间$MAX$和区间加的数据结构维护即可.(线段树).

代码

1
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
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=2e5+5;
int n,k;
struct node{
int x,y;
int id;
}sg[MAXN];
bool operator <(node a,node b){
return a.y<b.y;
}
#define lc k<<1
#define rc k<<1|1
#define ls lc,l,mid
#define rs rc,mid+1,r
int mx[MAXN<<2],tag[MAXN<<2];
inline void add(int k,int v){
mx[k]+=v;
tag[k]+=v;
}
inline void pushup(int k){
mx[k]=max(mx[lc],mx[rc]);
}
inline void pushdwn(int k){
add(lc,tag[k]);
add(rc,tag[k]);
tag[k]=0;
}
int Query(int k,int l,int r,int qx,int qy){
if(qx<=l&&r<=qy) return mx[k];
pushdwn(k);
int mid=l+r>>1,res=0;
if(qx<=mid) res=max(res,Query(ls,qx,qy));
if(mid<qy) res=max(res,Query(rs,qx,qy));
return res;
}
void Modify(int k,int l,int r,int qx,int qy){
if(qx<=l&&r<=qy) return add(k,1);
pushdwn(k);
int mid=l+r>>1;
if(qx<=mid) Modify(ls,qx,qy);
if(mid<qy) Modify(rs,qx,qy);
pushup(k);
return ;
}
int m;
bool vis[MAXN];
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d%d",&sg[i].x,&sg[i].y),sg[i].id=i;
sort(sg+1,sg+n+1);
m=n;
for(int i=1;i<=n;i++)
if(Query(1,1,2e5,sg[i].x,sg[i].y)<k)
Modify(1,1,2e5,sg[i].x,sg[i].y),m--,vis[i]=1;
printf("%d\n",m);
for(int i=1;i<=n;i++)
if(!vis[i]) printf("%d ",sg[i].id);
puts("");
return 0;
}

By Elevator or Stairs?

思路

可以发现在每一层时,你是在电梯上还是在楼梯上是影响继续向后转移的,所以我们可以开$f_{i,j}$表示现在位于第$i$层,在/不在楼梯上时最小的时间花费.
然后转移的话考虑是从上一层走楼梯来还是走电梯来即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,c;
int A[N],B[N],f[N][2];
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> c;
for(int i=2;i<=n;i++)
cin >> A[i];
for(int i=2;i<=n;i++)
cin >> B[i];
cout << 0 << " ";
memset(f,0x3f3f3f3f,sizeof(f));
f[1][1] = c;
f[1][0] = 0;
for(int i=2;i<=n;i++){
f[i][0] = min(f[i-1][0]+A[i], f[i-1][1]+A[i]);
f[i][1] = min(f[i-1][0]+B[i]+c, f[i-1][1]+B[i]);
cout << min(f[i][0], f[i][1]) << " " ;
}
return 0;
}

Maximum Weight Subset

思路

update:(官方题解.我反正还没懂)😂我们设$f_{i,j}$表示现在是以$i$为根的节点,选中的点最浅深度是$j$时划分出子集的最大权值.
初始化时显然$f_{i,0}=a_i$.显然这个是刚开始时没有子树的情况,然后我们一颗颗的添加子树.
考虑怎么转移:因为我们一定是从底向上转移的,所以我们对于每个子树的根节点$i$,枚举一下这个点是继承的哪一颗子树的$f$,同时我们还要考虑其他子树对答案的贡献值,显然,距离可以直接进行转移).
总的方程为:$f_{v,dep}=max(f_{v,dep},(dep==0?a_v:f_{v,dep-1})+\sum_{son_v}f_{son,max(dep-1,k-dep-1)})$.
最终答案即为$f_{0,0}$

代码

1
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
#include <bits/stdc++.h>

using namespace std;

const int N = 210;

int n, k;
vector<int> a;
vector<vector<int>> g, dp;

void dfs(int v, int p) {
dp[v][0] = a[v];
for (auto to : g[v])
if (to != p) \
dfs(to, v);
for (int dep = 0; dep < N; ++dep) {
if (dep == 0) {
for (auto to : g[v]) {
if (to == p)
continue;
dp[v][dep] += dp[to][max(0, k - dep - 1)];
}
}
else {
for (auto to : g[v]) {
if (to == p) continue;
int cur = dp[to][dep - 1];
for (auto other : g[v]) {
if (other == p || other == to)
continue;
cur += dp[other][max(dep - 1, k - dep - 1)];
}
dp[v][dep] = max(dp[v][dep], cur);
}
}
}
for (int dep = N - 1; dep > 0; --dep)
dp[v][dep - 1] = max(dp[v][dep - 1], dp[v][dep]);
return;
}

int main() {
cin >> n >> k;
++k;
a = vector<int>(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
g = vector<vector<int>>(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
dp = vector<vector<int>>(n, vector<int>(N));
dfs(0, -1);
cout << dp[0][0] << endl;
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:Codeforces Round #595 (Div. 3)

文章作者:KRrrrrrrrr

发布时间:2019年10月23日 - 10:10

最后更新:2019年10月23日 - 20:10

原始链接:http://krrrr.xyz/2019/10/23/Round595/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。