Codeforces Round #321 (Div.2)

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

A. Kefa and First Steps

  • [Description]
    给一个10510^5的数组，求最长连续不降序列的长度。

  • [Solution]
    O(n)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]
    不超过10510^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]
    给定一个结点不超过10510^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]
    给定一个不超过105个元素的数字字符序列a，给定不超过10510^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/dd]和[l+r-r/dd,r]的哈希值相同。

Comment