2017青岛网络赛

自用笔记算法

2017青岛网络赛

HDU 6208

题目要求

给出n个字符串 问所有的字符串是否都是最长那个的子串
若是 输出最长字符串 否则输出no

参考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
#include<bits/stdc++.h>
#define maxn 100050
using namespace std;
string s[maxn];
int main(){
//    freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int mxlen=0,mxpo=0;
        for(int i=1;i<=n;i++){
            cin>>s[i];
            int len=s[i].length();
            if(len>mxlen) mxlen=len,mxpo=i;
        }
        int flag=0;
        for(int i=1;i<=n;i++){
            if(i==mxpo) continue;
            if(s[mxpo].find(s[i])==string::npos){
                flag=1;
                break;
            }
        }
        if(!flag) cout<<s[mxpo]<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

思路

找到最长字符串位置
string暴力

HDU 6213

题目要求

问2个生肖的人年龄相差最小多少

参考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
#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
void init(){
    mp["rat"]=1;
    mp["ox"]=2;
    mp["tiger"]=3;
    mp["rabbit"]=4;
    mp["dragon"]=5;
    mp["snake"]=6;
    mp["horse"]=7;
    mp["sheep"]=8;
    mp["monkey"]=9;
    mp["rooster"]=10;
    mp["dog"]=11;
    mp["pig"]=12;
}
char s1[20],s2[20];
int main(){
//    freopen("input.txt","r",stdin);
    init();
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s %s",s1,s2);
        int ans;
        int ans1=mp[s1],ans2=mp[s2];
        if(ans1==ans2) ans=12;
        if(ans1<ans2) ans=ans2-ans1;
        if(ans1>ans2) ans=ans2-ans1+12;
        printf("%d\n",ans);
    }
    return 0;
}

思路

模拟

HDU 6214

题目要求

求割边最小的最小割

参考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
#include<bits/stdc++.h>
#define maxn 500
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const int mod=1001;
const LL inf = (LL)1e18;
int n,m,S,T;
struct Edge{
  int from, to,cap,flow;
};
struct Dinic{
  int n, m, s, t;
  vector<Edge> edges;   
  vector<int> G[maxn];   
  bool vis[maxn];         
  int d[maxn];           
  int cur[maxn];       
void ClearAll(int n){
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
}
void AddEdge(int from, int to, int cap){
    edges.push_back((Edge){from, to, cap, 0});
    edges.push_back((Edge){to, from, 0, 0});
    m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}
bool BFS(){
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    d[s] = 0;
    while(!Q.empty()) {
      int x = Q.front(); Q.pop();
      for(int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if(!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          d[e.to] = d[x] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
}
LL DFS(int x, LL a){
    if(x == t || a == 0) return a;
    LL flow = 0, f;
    for(int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, (LL)e.cap-e.flow))) > 0) {
        e.flow += f;
        edges[G[x][i]^1].flow -= f;
        flow += f;
        a -= f;
        if(a == 0) break;
      }
    }
    return flow;
}
LL Maxflow(int s, int t){
    this->s = s; this->t = t;
    LL flow = 0;
    while(BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, inf);
    }
    return flow;
}
}g;
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        g.ClearAll(maxn);
        scanf("%d%d",&n,&m);
        scanf("%d%d",&S,&T);
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            g.AddEdge(u,v,w*mod+1);
        }
        int ans=g.Maxflow(S,T)%mod;
        printf("%d\n",ans);
    }
    return 0;
}

思路

每条边的容量括弧到w*(E+1)+1 E是边数 最小边数最小割就是跑出来的答案mod(E+1)
注意扩容后dinic的板子换成LL

HDU 6215

题目要求

给你长度为n的数组，定义已经排列过的串为：相邻两项a[i],a[i+1]，满足a[i]<=a[i+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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[maxn],que[maxn],nxt[maxn],last[maxn];
int t,n,top;
int main(){
//    freopen("input.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        top=0,a[0]=0;
        nxt[0]=1,last[n+1]=n;
        int ans=n;
        for(int i=1;i<=n;i++){
            nxt[i]=i+1;
            last[i]=i-1;
            scanf("%d",&a[i]);
            que[top++]=i;
        }
        int flag=1;
        while(flag){
            int s=0,now=0;
            flag=0;
            while(now<top){
                int x=que[now],ff=0;
                while(nxt[x]<=n){
                    if(a[x]>a[nxt[x]]) ff++,x=nxt[x],flag=1;
                    else break;
                }
                if(ff) ans-=(ff+1);
                if(ff){
                    nxt[last[que[now]]]=nxt[x];
                    last[nxt[x]]=last[que[now]];
                    que[s++]=last[que[now]];
                }
                while(que[now]<=x && now<top) now++;
            }
            top=s;
        }
        printf("%d\n",ans);
        int now=0;
        while(now<=n){
            if(now!=0) printf("%d ",a[now]);
            now=nxt[now];
        }
        printf("\n");
    }
    return 0;
}

思路

数组模拟队列 nxt和last模拟双向链表的指针
每次删除不满足a[i]<=a[i+1]的项 合并剩下的项 再删除 以此类推直到结束
注意now要从0开始 该位不输出 用nxt[now]来找到第一个元素的位置 因为第一个元素可能被删除

HDU 6216

题目要求

问一个小于10^12的素数是否能转换成2个立方数的差

参考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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
bool check(LL x){
    int l=1,r=1000000;
    while(l<=r){
        int mid=(l+r)>>1;
        LL ans=(LL)mid*(LL)mid*3LL+mid*3LL+1LL;
        if(ans==x) return true;
        if(ans>x) r=mid-1;
        else l=mid+1;
    }
    return false;
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        LL x;
        scanf("%lld",&x);
        if(check(x)) puts("YES");
        else puts("NO");
    } 
    return 0;
}

思路

a³-b³=(a-b)(a²+ab+b²)
由于p是素数 所以a-b=1 把a=b+1带入求得3b³+3b+1
二分这样的b是否存在即可

本文标题:2017青岛网络赛

文章作者:Hippopmonkey

发布时间:2017-09-18, 10:19:00

最后更新:2017-09-18, 10:41:55

原始链接:http://xuboming8.github.io/2017/09/18/2017青岛网络赛/

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

文章目录
  1. 1. 2017青岛网络赛
    1. 1.1. HDU 6208
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6213
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6214
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 6215
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. HDU 6216
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
|