\[Codeforces Round \#321 (Div. 2)\]

传送门 >> http://codeforces.com/contest/580
很久没写过codeforces相关了…期间一路打到紫名又掉回蓝名…
欸…昨晚cf水出新高度,没想到自己竟然没有起得来…五点惊醒打了下virtual contest,两小时还是切了四题的…
下面是题解↓

A. Kefa and First Steps

[Description]

给一个$10^5$的数组,求最长连续不降序列的长度。

[Solution]

$O(n)$

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=1e5;
int a[maxn];

int main(){
int n,ans=0,now=1; scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(i && a[i]>=a[i-1]) now++;
else ans=max(ans,now),now=1;
}
ans=max(ans,now);
printf("%d",ans);
}

B. Kefa and Company

[Description]

不超过$10^5$个物品,每个物品两个描述值a,b,给定一个整数d。现在要求选出一些物品使得,任意集合内的物品a的差值不超过小于d,且b的总和最大。

[Solution]

单调队列。

[Code]

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
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const int maxn=1e5;
struct P{
int a,s;
bool operator < (const P pp) const{
return a<pp.a;
}
}p[maxn];
ll sum[maxn];

int main(){
int n,d; scanf("%d%d",&n,&d);
for(int i=0;i<n;i++) scanf("%d%d",&p[i].a,&p[i].s);
sort(p,p+n);
sum[0]=p[0].s;
for(int i=1;i<n;i++) sum[i]=sum[i-1]+p[i].s;
int l=0,r=0; ll ans=0;
while(l<n){
while(r<n-1 && p[r+1].a-p[l].a<d) r++;
if(!l) ans=max(ans,sum[r]);
else ans=max(ans,sum[r]-sum[l-1]);
l++;
}
printf("%lld",ans);
}

C. Kefa and Park

[Description]

给定一个结点不超过$10^5$的树,每个结点的权值为0或1,对于每个叶结点,若它到根结点的路径上有连续权值为1且长度≥d的一条链,对答案无贡献,否则答案+1。输出答案。

[Solution]

DFS.

[Code]

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=1e5;
const int maxm=2*maxn;

int cat[maxn];
int to[maxm],nxt[maxm],cur[maxn],cnt;
void insert(int x,int y){
to[cnt]=y,nxt[cnt]=cur[x],cur[x]=cnt++;
to[cnt]=x,nxt[cnt]=cur[y],cur[y]=cnt++;
}

int d,ans=0;
bool being[maxn];
void DFS(int u,int now){
if(now>d) return;
being[u]=true;
bool leaf=true;
for(int i=cur[u];i>=0;i=nxt[i]){
int v=to[i];
if(!being[v]){
leaf=false;
DFS(v,cat[v]?now+1:0);
}
}
if(leaf) ans++;
}

int main(){
memset(cur,-1,sizeof(cur));
int n; scanf("%d%d",&n,&d);
for(int i=0;i<n;i++) scanf("%d",&cat[i]);
for(int i=1;i<n;i++){
int x,y; scanf("%d%d",&x,&y);
insert(--x,--y);
}
DFS(0,cat[0]);
printf("%d",ans);
return 0;
}

D. Kefa and Dishes

[Description]

给定n个物品,要求选出m个排序,第i个物品获得a[i]的贡献。给出k条关系,表示若i排在j之前,则获得b[i][j]的贡献。求一种选物品和排序的方案,使得总贡献最大。

[Hint]

$1≤m≤n≤18$

[Solution]

状压DP(看着数据范围就知道).
设i为状态,j为序列的最后一个数,转移方程为$$f[i][j]=f[i\ xor\ (1<<j)][k]+a[j]+a[k][j],j∈i且k∈i\ xor\ (1<<j)$$

[Code]

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
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const int maxn=18;
int a[maxn],b[maxn][maxn];
ll f[1<<maxn][maxn];
int bin[maxn+1];

inline int lowbit(int x){ return x&-x; }
inline int no(int x){
int res=0;
while(x)
if(x&1) return res;
else x>>=1,res++;
}
inline int cnt(int x){
int res=0;
while(x){
if(x&1) res++; x>>=1;
}
return res;
}

int main(){
int n,m,k; scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<k;i++){
int x,y,z; scanf("%d%d%d",&x,&y,&z);
b[--x][--y]=z;
}
bin[0]=1;
for(int i=1;i<=maxn;i++) bin[i]=bin[i-1]<<1;
ll ans=0;
for(int i=1,t=1;i<bin[n];t=++i){
while(t){
int p1=lowbit(t),cnt1=no(p1); t-=p1;
int v1=i^p1;
if(!v1) f[i][cnt1]=a[cnt1];
while(v1){
int p2=lowbit(v1),cnt2=no(p2); v1-=p2;
int v2=i^p1;
f[i][cnt1]=max(f[i][cnt1],f[v2][cnt2]+a[cnt1]+b[cnt2][cnt1]);
}
}
if(cnt(i)==m)
for(int j=0;j<n;j++)
ans=max(ans,f[i][j]);
}
printf("%lld",ans);
return 0;
}

E. Kefa and Watch

[Description]

给定一个不超过$10^5$个元素的数字字符序列a,给定不超过$10^5$个操作,分为两种:
1)l r c : 将区间[l,r]内所有元素改为c
2)l r d:询问区间[l,r-d]里所有i是够满足a[i]=a[i+d]

[Solution]

线段树+Hash.
满足条件的区间满足[l,r/d*d]和[l+r-r/d*d,r]的哈希值相同。