2017沈阳网络赛

自用笔记算法

2017沈阳网络赛

HDU 6194

题目要求

给你一个串，给你一个数字k ，然后让你计算出在串中出现恰好k次的字串的数目

参考AC代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <cmath>
#include <cstring>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define ll long long
#define PQ priority_queue
#define fr(x) freopen(x, "r", stdin)
#define fw(x) freopen(x, "w", stdout)
#define cls(ar, val) memset(ar, val, sizeof(ar))
#define debug(a) cerr << #a << "==" << a << endl
#define lp(loop, start, end) for (int loop = start; loop < end; ++loop)
#define lpd(loop, start, end) for (int loop = start; loop > end; --loop)
#define lpi(loop, start, end) for (int loop = start; loop <= end; ++loop)
#define lpdi(loop, start, end) for (int loop = start; loop >= end; --loop)
const int inf = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int maxn = 1e5 + 200;
char str[maxn];
int t;
int A[maxn], B[maxn];
template <typename T> inline void read(T &x) {
  x = 0;
  T f = 1;
  char ch;
  do {
    ch = getchar();
    if (ch == '-')
      f = -1;
  } while (ch < '0' || ch > '9');
  do
    x = x * 10 + ch - '0', ch = getchar();
  while (ch <= '9' && ch >= '0');
  x *= f;
}
template <typename A, typename B> inline void read(A &x, B &y) {
  read(x);
  read(y);
}
template <typename A, typename B, typename C>
inline void read(A &x, B &y, C &z) {
  read(x);
  read(y);
  read(z);
}
template <typename A, typename B, typename C, typename D>
inline void read(A &x, B &y, C &z, D &w) {
  read(x);
  read(y);
  read(z);
  read(w);
}
int suffaa_[maxn], suffb_[maxn], suffa_[maxn];
int ch[maxn], suff_auto[maxn], Rank[maxn], height[maxn];
int a[maxn];
struct Suffix_Auto {
  void Gersuff_a(int *ch, int *suff_auto, int *rank, int n) {
    for (int i = 0; i < maxn; i++)
      suffaa_[i] = 0;
    for (int i = 1; i <= n; i++)
      suffaa_[ch[i]]++;
    for (int i = 1; i <= maxn; i++)
      suffaa_[i] += suffaa_[i - 1];
    for (int i = n; i; i--)
      suff_auto[suffaa_[ch[i]]--] = i;
    rank[suff_auto[1]] = 1;
    for (int i = 2; i <= n; i++) {
      rank[suff_auto[i]] = rank[suff_auto[i - 1]];
      if (ch[suff_auto[i]] != ch[suff_auto[i - 1]])
        rank[suff_auto[i]]++;
    }
    for (int l = 1; rank[suff_auto[n]] < n; l <<= 1) {
      lpi(i, 0, maxn - 1) suffaa_[i] = 0;
      lpi(i, 0, maxn - 1) suffb_[i] = 0;
      lpi(i, 1, n) {
        suffaa_[A[i] = rank[i]]++;
        suffb_[B[i] = (i + l <= n) ? rank[i + l] : 0]++;
      }
      lpi(i, 1, maxn - 1) suffb_[i] += suffb_[i - 1];
      for (int i = n; i; i--)
        suffa_[suffb_[B[i]]--] = i;
      for (int i = 1; i < maxn; i++)
        suffaa_[i] += suffaa_[i - 1];
      for (int i = n; i; i--)
        suff_auto[suffaa_[A[suffa_[i]]]--] = suffa_[i];
      rank[suff_auto[1]] = 1;
      for (int i = 2; i <= n; i++) {
        rank[suff_auto[i]] = rank[suff_auto[i - 1]];
        if (A[suff_auto[i]] != A[suff_auto[i - 1]] || B[suff_auto[i]] != B[suff_auto[i - 1]])
          rank[suff_auto[i]]++;
      }
    }
  }
  void GetHeight(int *ch, int *suff_auto, int *rank, int *height, int n) {
    cls(height, 0);
    cls(rank, 0);
    cls(suff_auto, 0);
    Gersuff_a(ch, suff_auto, rank, n);
    for (int i = 1, j = 0; i <= n; i++) {
      if (j)
        j--;
      while (ch[i + j] == ch[suff_auto[rank[i] - 1] + j])
        j++;
      height[rank[i]] = j;
    }
  }
  ll GetIndex(int k, int n) {
    int f = 0, l = 1;
    ll ans = 0;
    a[0] = height[1];
    k--;
    if (k == 0) {
      for (int i = 1; i <= n; ++i)
        ans = ans + (n - suff_auto[i] + 1 - height[i]);
      return ans;
    }
    int last = 0;
    for (int i = 2; i <= n; i++) {
      if (i > k && height[i - k] == a[f])
        f++;
      while (l > f && a[l - 1] > height[i])
        l--;
      a[l] = height[i];
      l++;
      if (i >= k) {
        if (a[f] >= last)
          ans = ans + a[f] - last;
        last = height[i - k + 1];
      }
    }
    return ans;
  }
} suff;
int main() {
  //  freopen("in.txt","r",stdin);
  read(t);
  lpi(i, 1, t) {
    cls(ch, 0);
    int n, k;
    scanf("%d", &k);
    scanf("%s", str);
    n = (int)strlen(str);
    for (int i = 1; i <= n; i++)
      ch[i] = str[i - 1];
    suff.GetHeight(ch, suff_auto, Rank, height, n);
    printf("%lld", suff.GetIndex(k, n) - suff.GetIndex(k + 1, n));
    printf("\n");
  }
  return 0;
}

思路

据说是sam模版题

HDU 6200

转跳链接

HDU 6201

题目要求

有n个城市，每个城市有一本书，买书需要花钱，卖书可以得到钱，并且两个城市之间的距离也有花费。选择两个城市，一个城市买书一个城市卖书，问得到的最大收益
保证给定的n-1条边组成一棵树

参考AC代码(树形dfs)

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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
    int to,w;
    node(int to,int w):to(to),w(w){}
};
int val[maxn];
vector<node>e[maxn];
int Min[maxn],Max[maxn];
int ans;
void dfs(int x,int fa){
    Max[x]=val[x];
    Min[x]=val[x];
    for(auto p:e[x]){
        if(p.to==fa) continue;
        dfs(p.to,x);
        Max[p.to]-=p.w;
        Min[p.to]+=p.w;
        Max[x]=max(Max[p.to],Max[x]);
        Min[x]=min(Min[p.to],Min[x]);
        ans=max(ans,Max[x]-Min[x]);
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        mm(Min,inf),mm(Max,-1);
        for(int i=0;i<=n;i++) e[i].clear();
         for(int i=1;i<=n;i++) scanf("%d",&val[i]);
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            e[u].push_back(node(v,w));
            e[v].push_back(node(u,w));
        }
        ans=0;
        dfs(1,0);
        printf("%d\n",ans);
    }
    return 0;
}

参考AC代码(建图跑spfa最长路)

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>
#define maxn 100050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int val[maxn];
struct Edge {
  int from, to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];     // 是否在队列中
  int d[maxn];     // s到各个点的距离
  int p[maxn];        // 最短路中的上一条弧
  int cnt[maxn];
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  void spfa(int s){
    queue<int> Q;
    memset(inq, false, sizeof inq);
    memset(cnt, 0, sizeof cnt);
    memset(d, -inf, sizeof d);
    Q.push(s);
    d[s]=0,cnt[s]=1,inq[s]=true;
    while(!Q.empty()) {
      int u = Q.front(); 
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] < d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) {
              cnt[e.to]++;
              if(cnt[e.to]>n) return ;
            Q.push(e.to); inq[e.to] = true; 
          }
        }
      }
      Q.pop();
      inq[u] = false;
    }
  }
}sp;
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        sp.init(maxn);        
        for(int i=1;i<=n;i++) scanf("%d",&val[i]);
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            sp.AddEdge(u,v,-w);
            sp.AddEdge(v,u,-w);
        }
        int S=0,T=n+1;
        for(int i=1;i<=n;i++){
            sp.AddEdge(S,i,-val[i]);
            sp.AddEdge(i,T,val[i]);
        }
        sp.spfa(S);
        printf("%d\n",sp.d[T]);
    }
    return 0;
}

思路

树上dfs：维护子树(包括根节点)的最大值和最小值 再维护最大值-最小值差值的最大值
对于边权的处理：由于边权是需要话费的 所以最大值(卖书赚钱)-路费 最小值(买书花钱)+路费
建图跑spfa最长路：看数据范围就知道网络流会t 建图跟网络流是类似的
构造一个S和T S连向每个点 边权为负点权 每个点再连向T 边权为正点权 点和点之间的权值取负
跑一遍S到T的spfa最长路即可

HDU 6203

题目要求

n+1个点 n条边的树(点标号0 ~ n),有若干个点无法通行,导致p组U->V无法连通。问无法通行的点最少有多少个。

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 10050
#define maxq 50050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct query{
    int x,y;
    int val;
}a[maxq];
vector<int>e[maxn];
int deep[maxn],f[maxn],anc[maxn][25],vis[maxn];
int n,q;
void init(){
    mm(f,0),mm(anc,0),mm(deep,0);
    mm(vis,0),deep[1]=1;
    for(int i=0;i<=n+1;i++) e[i].clear();
}
bool cmp(query x,query y){
    return deep[x.val]>deep[y.val];
}
void dfs(int x,int fa){
    anc[x][0]=f[x];
    for(int i=1;i<=20;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
    for(int i=0;i<e[x].size();i++){
        int next=e[x][i];
        if(next!=fa){
            f[next]=x;
            deep[next]=deep[x]+1;
            dfs(next,x);
        }
    }
}
int lca(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return f[x];
}
void dfs2(int x,int fa){
    vis[x]=1;
    for(auto p:e[x]){
        if(p==fa) continue;
        if(!vis[p]) dfs2(p,x);
    }        
}
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        init();
        for(int i=1;i<=n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            u++,v++;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs(1,0);
        scanf("%d",&q);
        for(int i=1;i<=q;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            u++,v++;
            a[i].x=u,a[i].y=v;
            a[i].val=lca(a[i].x,a[i].y);
        }
        sort(a+1,a+1+q,cmp);
        int ans=0;
        for(int i=1;i<=q;i++){
            if(vis[a[i].x] || vis[a[i].y]) continue;
            ans++;
            dfs2(a[i].val,anc[a[i].val][0]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

思路

lca+离线贪心
记录下所有的query按照深度从大到小排序 每次找到一对询问和他的lca ans++并把lca下的子树全部访问一遍
如果有另一组询问已经访问过 跳过 否则重复上述过程访问lca子树
注意lca模版下标从1开始

HDU 6205

题目要求

n堆扑克牌，从第1堆开始，当到某一堆使朝上的牌少于朝下的牌时，游戏结束，否则，取走所有的牌，在游戏开始之前可以移动若干堆，
把最前面的牌移到最后面，问能取走的牌数最多时，开始前需要移动几堆到最后

参考AC代码(前缀和)

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
#include<bits/stdc++.h>
#define maxn 1000050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[maxn],sum[maxn];
int main(){
//    freopen("input.txt","r",stdin);
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        mm(sum,0);
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            sum[i]=sum[i-1]+a[i]-x;
        }
        int ans=0,po=0;
        for(int i=1;i<=n;i++){
            if(ans>sum[i]){
                ans=sum[i];
                po=i;
            }
        }
        printf("%d\n",po);
    }
    return 0;
}

参考AC代码(尺取法)

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
#include<bits/stdc++.h>
#define maxn 1000050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[2*maxn],b[2*maxn];
int main(){
//    freopen("input.txt","r",stdin);
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i+n]=a[i];
        for(int i=1;i<=n;i++) scanf("%d",&b[i]),b[i+n]=b[i];
        int st=1,po=1;
        int now=a[1]-b[1];
        int sum=a[1];
        int ans=a[1];
        for(int i=2;i<=n+n;i++){
            if(now>=0){
                now+=a[i]-b[i];
                sum+=a[i];
            }
            else{
                now=a[i]-b[i];
                sum=a[i];
                st=i;
            } 
            if(sum>ans){
                ans=sum;
                po=st;
            }
            if(i-st==n) break;
        }
        printf("%d\n",(po-1+n)%n);
    }
    return 0;
}

思路

前缀和策略：对a[i]-b[i]的值求前缀和 sum数组其实就是一条折线 找到这条折线的最低点并记录下index 即为答案
由于是最低点确保后面没有点比它更低 所以从该点后一位取到的数量可以确保最大 所以贪心策略正确
尺取法策略：转换为求连续区间最大正值的起点位置 用尺取法双指针维护起点终点的思想 维护起点st并记录和最大的起点po

本文标题:2017沈阳网络赛

文章作者:Hippopmonkey

发布时间:2017-09-11, 21:32:42

最后更新:2017-09-18, 21:05:26

原始链接:http://xuboming8.github.io/2017/09/11/2017沈阳网络赛/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 2017沈阳网络赛
    1. 1.1. HDU 6194
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6200
    3. 1.3. HDU 6201
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码(树形dfs)
      3. 1.3.3. 参考AC代码(建图跑spfa最长路)
      4. 1.3.4. 思路
    4. 1.4. HDU 6203
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. HDU 6205
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码(前缀和)
      3. 1.5.3. 参考AC代码(尺取法)
      4. 1.5.4. 思路
|