ACM-ICPC 2018 沈阳赛区网络预赛

Diposting di | Edited on

传送门

B.Call of Accepted

题意

类似于计算器,不过就是特殊了一个计算d,变成一个骰子的类似,2d3表示投了两次三面骰子,给你一串字符串，问你结果的最大最小值

思路

直接转化成后缀表达式,但是比赛的时候太单纯没有想到一些特殊情况所以GG

正确解法应该是把所有的情况都考虑,每一次计算都算出一个最大最小值,然后在新的计算的时候再通过最大最小值计算

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
#include<bits/stdc++.h>
using namespace std;
map<char,int>L;
map<char,int>R;
typedef long long ll;
#define pp pair<int,int>
string ac(string str){
    string ret;
    stack<char>s;
    s.push('#');
    int len=str.length();
    for(int i=0;i<len;i++){
        char t=str[i];
        if(t=='(')s.push(t);
        else if(t==')'){
            while(s.top()!='('){
                ret+=s.top();
                s.pop();
                ret+=' ';
            }
            s.pop();
        }
        else if(t=='+'||t=='-'||t=='*'||t=='d'){
            while(L[s.top()]>=R[t]){
                ret+=s.top();
                ret+=' ';
                s.pop();
            }
            s.push(t);
        }
        else{
            while(isdigit(str[i]))
                ret+=str[i++];
            i--,ret+=' ';
        }
    }
    while(s.top()!='#'){
        ret+=s.top();
        ret+=' ';
        s.pop();
    }
    return ret;
}
pp operator+(pp a,pp b){
    int vec[]={a.first+b.first,a.first+b.second,a.second+b.first,a.second+b.second};
    sort(vec,vec+4);
    return{vec[0],vec[3]};
}
pp operator-(pp a,pp b){
    int vec[]={a.first-b.first,a.first-b.second,a.second-b.first,a.second-b.second};
    sort(vec,vec+4);
    return{vec[0],vec[3]};
}
pp operator*(pp a,pp b){
    int vec[]={a.first*b.first,a.first*b.second,a.second*b.first,a.second*b.second};
    sort(vec,vec+4);
    return{vec[0],vec[3]};
}
pp operator^(pp a,pp b){
    int vec[]={a.first,a.second,a.first*b.first,a.first*b.second,a.second*b.first,a.second*b.second};
    sort(vec,vec+6);
    return{vec[0],vec[5]};
}
pp solve(string str){
    stack<pp>s;
    int i=0;
    pp tmp;
    while(i<str.length()){
        if(str[i]==' '){
            i++;continue;
        }
        if(str[i]=='+')tmp=s.top(),s.pop(),tmp=tmp+s.top(),s.pop(),i++;
        else if(str[i]=='-')tmp=s.top(),s.pop(),tmp=s.top()-tmp,s.pop(),i++;
        else if(str[i]=='*')tmp=s.top(),s.pop(),tmp=s.top()*tmp,s.pop(),i++;
        else if(str[i]=='d'){
            tmp=s.top(),s.pop(),
            tmp=s.top()^tmp,s.pop(),
            i++;
        }
        else{
            int x=0;
            while(isdigit(str[i]))
                x=x*10+str[i++]-'0';
            tmp={x,x};
        }
        s.push(tmp);
    }
    return s.top();
}
int main(){
    L['+']=1,L['-']=1,L['*']=2,L['d']=3;
    R['+']=1,R['-']=1,R['*']=2,R['d']=3;
    string s;
    while(cin>>s){
        string tmp=ac(s);
        pp res=solve(tmp);
        cout<<res.first<<" "<<res.second<<endl;
    }
}

D. Made In Heaven

题意

N个点，M条边，起始点为s，结束为n，求s到n的第k短的路的长度，判断长度是否大于T，如果大于，输出“Whitesnake!”，否则输出“yareyaredawa”

思路

队友A的,我并不会这种K最短路….

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
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#define MAXN 1005
#define MAXM 500005
#define INF 1000000000
using namespace std;
struct node
{
    int v, w, next;
}edge[MAXM], revedge[MAXM];
struct A
{
    int f, g, v;
    bool operator <(const A a)const {
        if(a.f == f) return a.g < g;
        return a.f < f;
    }
};
int e, vis[MAXN], d[MAXN], q[MAXM * 5];
int head[MAXN], revhead[MAXN];
int n, m, s, t, k;
void init()
{
    e = 0;
    memset(head, -1, sizeof(head));
    memset(revhead, -1, sizeof(revhead));
}
void Insert(int x, int y, int w)
{
    edge[e].v = y;
    edge[e].w = w;
    edge[e].next = head[x];
    head[x] = e;
    revedge[e].v = x;
    revedge[e].w = w;
    revedge[e].next =revhead[y];
    revhead[y] = e++;
}
void spfa(int src)
{
    for(int i = 1; i <= n; i++) d[i] = INF;
    memset(vis, 0, sizeof(vis));
    vis[src] = 0;
    int h = 0, t = 1;
    q[0] = src;
    d[src] = 0;
    while(h < t)
    {
        int u = q[h++];
        vis[u] = 0;
        for(int i = revhead[u] ; i != -1; i = revedge[i].next)
        {
            int v = revedge[i].v;
            int w = revedge[i].w;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                if(!vis[v])
                {
                    q[t++] = v;
                    vis[v] = 1;
                }
            }
        }
    }
}
int Astar(int src, int des)
{
    int cnt = 0;
    priority_queue<A>Q;
    if(src == des) k++;
    if(d[src] == INF) return -1;
    A t, tt;
    t.v = src, t.g = 0, t.f = t.g + d[src];
    Q.push(t);
    while(!Q.empty())
    {
        tt = Q.top();
        Q.pop();
        if(tt.v == des)
        {
            cnt++;
            if(cnt == k) return tt.g;
        }
        for(int i = head[tt.v]; i != -1; i = edge[i].next)
        {
            t.v = edge[i].v;
            t.g = tt.g + edge[i].w;
            t.f = t.g + d[t.v];
            Q.push(t);
        }
    }
    return -1;
}
int main()
{
    int x, y, w, len;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        init();
        scanf("%d%d%d%d", &s, &t, &k,&len);
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &x, &y, &w);
            Insert(x, y, w);
        }

        spfa(t);
        int ans=Astar(s, t);
        if(ans<=len&&ans!=-1){
            puts("yareyaredawa");
        }
        else{
            puts("Whitesnake!");
        }
    }
    return 0;
}

F. Fantastic Graph

题意

一个二分图，M条边，选用M条边的一些，令最后所有点的度数都在[l,r]内 ，可以Yes 否则 No

思路

网络流 solve by fsh

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
159
160
161
162
163
164
165
166
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<string>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
const int N=20005;
const int M=200005;
const int INF=0x3f3f3f3f;
using namespace std;

int top;
int h[N],pre[N],g[N],cost[N];

struct Vertex{
    int first;
}V[N];

struct Edge{
    int v,next;
    int cap,flow;
}E[M];

void init(){
    for(int i=0;i<N;i++){
        V[i].first=-1;
    }
    top=0;
}

void add_edge(int u,int v,int c){
    E[top].v=v;
    E[top].cap=c;
    E[top].flow=0;
    E[top].next=V[u].first;
    V[u].first=top++;
}

void add(int u,int v,int c){
    add_edge(u,v,c);
    add_edge(v,u,0);
}

void set_h(int t){
    queue<int>Q;
    mem(h,-1);
    mem(g,0);
    h[t]=0;
    Q.push(t);
    while(!Q.empty()){
        int v=Q.front();
        Q.pop();
        ++g[h[v]];
        for(int i=V[v].first;~i;i=E[i].next){
            int u=E[i].v;
            if(h[u]==-1){
                h[u]=h[v]+1;
                Q.push(u);
            }
        }
    }
}

int Isap(int s,int t,int n){
    set_h(t);
    int ans=0,u=s;
    int d;
    while(h[s]<n){
        int i=V[u].first;
        if(u==s){
            d=INF;
        }
        for(;~i;i=E[i].next){
            int v=E[i].v;
            if(E[i].cap>E[i].flow&&h[u]==h[v]+1){
                u=v;
                pre[v]=i;
                d=min(d,E[i].cap-E[i].flow);
                //cost[i]=d;
                if(u==t){
                    while(u!=s){
                        int j=pre[u];
                        E[j].flow+=d;
                        E[j^1].flow-=d;
                        u=E[j^1].v;
                    }
                    ans+=d;
                    d=INF;
                }
                break;
            }
        }
        if(i==-1){
            if(--g[h[u]]==0) break;
            int hmin=n-1;
            for(int j=V[u].first;~j;j=E[j].next){
                if(E[j].cap>E[j].flow){
                    hmin=min(hmin,h[E[j].v]);
                }
            }
            h[u]=hmin+1;
            ++g[h[u]];
            if(u!=s){
                u=E[pre[u]^1].v;
            }
        }
    }
    return ans;
}

int main(){
    int n,m,s,t,k;
    int v,u,w;
    int L,R;
    int co=1;
    while(~scanf("%d %d %d",&n,&m,&k)){
        init();
        s=0,t=(n+m)*2+1;
        scanf("%d %d",&L,&R);
        for(int i=1;i<=m+n;i++){
            add(i*2-1,i*2,R);
        }
        for(int i=1;i<=n;i++){
            add(s,i*2-1,INF);
        }
        for(int i=n+1;i<=m+n;i++){
            add(i*2,t,INF);
        }
        for(int i=0;i<k;i++){
            scanf("%d %d",&u,&v);
           // add(u,v,1);
           add(u*2,(v+n)*2-1,1);
        }
        int now;
        int flag=0;
        int ans=Isap(s,t,n+m+2);
        for(int i=1;i<=(n+m)*2;i+=2){
            for(int j=V[i].first;~j;j=E[j].next){
                if(E[j].v==i+1){
                    if(E[j].flow<L){
                        flag=1;
                    }
                }
            }
        }
        if(flag){
            printf("Case %d: No\n",co++);
        }
        else{
            printf("Case %d: Yes\n",co++);
        }
        /*
        int refer=L*(n+m)/2;
        cout<<refer<<" "<<ans<<endl;
        if(ans<=refer){
            printf("Case %d: No\n",co++);
        }
        else{
            printf("Case %d: Yes\n",co++);
        }*/
    }
    return 0;
}

I. Lattice’s basics in digital electronics

题意

给一系列二进制到ASCII的映射，给出一个十六进制数，需要你转化为二进制01串，然后9位9位得取，前八位的1的个数如果是偶数，第九位为1，说明校验结果正确，或者1的个数为奇数，第九位为0，校验结果正确，校验结果正确则保留前八位，反之舍弃这九位，不足九位的直接舍弃。最后通过上面的映射，输出得到的ASCII码对应字符的前m个字符。（题意很迷，直接看hint比较好理解）

思路

直接模拟,注意大小写和个数限制

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
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int maxn=1e8+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int n,m;
struct node{
    string s;
    int num;
    int k;
}my[350];
int cmp(node a,node b){
    return a.s<b.s;
}
string str;
string now;
void init(){
    now="";
    int len=str.length();
    for(int i=0;i<len;i++){
        switch(str.at(i)){
        case '0':
            now+="0000";break;
        case '1':
            now+="0001";break;
        case '2':
            now+="0010";break;
        case '3':
            now+="0011";break;
        case '4':
            now+="0100";break;
        case '5':
            now+="0101";break;
        case '6':
            now+="0110";break;
        case '7':
            now+="0111";break;
        case '8':
            now+="1000";break;
        case '9':
            now+="1001";break;
        case 'A':
            now+="1010";break;
        case 'B':
            now+="1011";break;
        case 'C':
            now+="1100";break;
        case 'D':
            now+="1101";break;
        case 'E':
            now+="1110";break;
        case 'F':
            now+="1111";break;
        case 'a':
            now+="1010";break;
        case 'b':
            now+="1011";break;
        case 'c':
            now+="1100";break;
        case 'd':
            now+="1101";break;
        case 'e':
            now+="1110";break;
        case 'f':
            now+="1111";break;
        }
    }
}
int main()
{
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(0);
    //std::cout.tie(0);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&m,&n);
        for(int i=0;i<n;i++){
            cin>>my[i].num;
            cin>>my[i].s;
            my[i].k=my[i].s.length();
        }
        sort(my,my+n,cmp);
        cin>>str;
        init();
       // cout<<now<<endl;
        int nowlen=now.length();
        string anw="";
        string haha="";
        for(int i=0;i<nowlen;i+=9){
            int endnum=0;
            if(i+8>=nowlen)break;
            for(int j=i;j<i+8;j++){
                if(now[j]=='1')endnum++;
            }
            if((endnum%2!=0)&&now[i+8]=='0'){
                anw+=now.substr(i,8);
               // cout<<endnum<<endl;
            //    cout<<"i=="<<i<<" "<<anw<<endl;
            }
            else if((endnum%2==0)&&now[i+8]=='1'){
                anw+=now.substr(i,8);
               // cout<<endnum<<endl;
            //    cout<<"i=="<<i<<" "<<anw<<endl;
            }
        }
      // cout<<"i m here"<<endl;
       // cout<<anw<<endl;
       int num=0;
        for(int i=0;i<anw.length();i++){
            haha+=anw[i];
            for(int j=0;j<n;j++){
                if(haha==my[j].s){
                    cout<<char(my[j].num);
                   // cout<<my[j].num<<"  "<<haha<<endl;
                    haha="";
                    num++;
                    break;
                }
            }
            if(num>=m)break;
        }
        cout<<endl;
    }
    return 0;
}

K. Supreme Number

题意

定义supreme number：一个数是素数，这个数的每一项都是1或素数，并且由这个数的每一位数组成的序列中，取出组成的任意子序列组成一个数，都是素数

求小于等于N的最大的supreme number

思路

直接打表发现最大到317

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
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
char s[1200];
int prime[21]={1,2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317,10000};
void init(){
    int one=1;
    for(int i=1;i<=10000;i++){
        int flag=0;
        for(int j=2;j<=sqrt(i);j++){
            if(i%j==0){ flag=1;
                break;

            }
        }
    if(flag==0)cout<<one++<<"   "<<i<<endl;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    scanf("%d",&t);
    int tt=1;
    while(t--){
        scanf("%s",s);
        int len=strlen(s);
        printf("Case #%d: ",tt++);
        if(len>=4)printf("317\n");
        else{
            int num=0;
            for(int i=0;i<len;i++){
                num=num*10+s[i]-'0';
            }
            for(int i=0;i<21;i++){
                if(prime[i]>num){
                    printf("%d\n",prime[i-1]);
                    break;
                }
            }
        }
    }
    return 0;
}