The 17th Zhejiang University Programming Contest Sponsored by TuSimple(浙江省赛)

发表于 | 更新于 | 阅读次数：
本文字数： 15k | 阅读时长 ≈ 14 分钟

A - Marjar Cola

ZOJ - 3948

签到题，x,y,a,b,都很小直接暴力。判断INF，只要判断次数有没有过多就行。

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
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;


int main() {
    int x,y,a,b;
    int t;
    scanf("%d",&t);
    while(t--) {
        int ans=0;
        scanf("%d%d%d%d",&x,&y,&a,&b);
        if(x==1||y==1)puts("INF");
        else {
            while(a>=x||y<=b) {
                if(a>=x) {
                    a-=x;
                    a++;
                    b++;
                    ans++;
                } else {
                    b-=y;
                    b++;
                    a++;
                    ans++;
                }
//                debug(a);
//                debug(b);
                if(ans>3e5){
                    break;
                }
            }
            if(ans>3e5){
                puts("INF");
            }
            else printf("%d\n",ans);
        }
    }
    return 0;
}

C - How Many Nines

ZOJ - 3950

打个表，比较考虑细节，真的难处理。

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
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=1e4+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int Year[maxn], Mon[35], pre1[maxn], pre2[35];
int hh[13], mon[13];
bool leap(int y){
    if(y%400==0)return 1;
    if(y%100==0)return 0;
    if(y%4==0)return 1;
    return 0;
}
int nine(int y){
    int cnt = 0;
    while(y){
        if(y%10==9)cnt++;
        y/=10;
    }
    return cnt;
}
void init(){
    Mon[1]=Mon[3]=Mon[5]=Mon[7]=Mon[8]=Mon[10]=Mon[12]=3;///31
    Mon[2]=2;
    Mon[4]=Mon[6]=Mon[9]=Mon[11] = 3;///30
    Mon[9] += 30;
    hh[1]=hh[3]=hh[5]=hh[7]=hh[8]=hh[10]=hh[12]=31;
    hh[2] = 28;
    hh[4]=hh[6]=hh[9]=hh[11]=30;
    mon[0] = 0;
    for(int i = 1; i <= 12; ++i){
        mon[i] = hh[i]+mon[i-1];
    }
    int sum = 0;pre1[1999]=pre2[0] = 0;
    for(int i = 1; i <= 12; ++i){
        sum += Mon[i];
        pre2[i] = pre2[i-1]+Mon[i];
    }
    for(int i = 2000; i <= 9999; ++i){
        int tmp = nine(i);
        if(tmp){
            Year[i] = sum + tmp*365;
            if(leap(i))Year[i] += tmp + 1;
        }else{
            Year[i] = sum;
            if(leap(i))++Year[i];
        }
        pre1[i] = pre1[i-1]+Year[i];
    }
}
int get(int d){
    if(d<=9)return 3;
    if(d<=19)return 2;
    if(d<=29)return 1;
    return 0;
}
int main(){
#ifndef ONLINE_JUDGE
    //freopen("E://ADpan//in.in", "r", stdin);
    //freopen("E://ADpan//out.out", "w", stdout);  
#endif
    init();
    int tim;scanf("%d",&tim);
    while(tim--){
        int y1,m1,d1,y2,m2,d2;
        scanf("%d%d%d%d%d%d",&y1,&m1,&d1,&y2,&m2,&d2);
        if(y1==y2){
            if(m1==m2){
                int ans = get(d1)-get(d2+1);
                if(m1==9)ans += d2-d1+1;
                int tmp = nine(y1);
                ans += tmp*(d2-d1+1);
                printf("%d\n", ans);
                continue;
            }
            int ans = pre2[m2-1]-pre2[m1];
            if(leap(y1)&&2>m1&&2<m2)ans++;
            ans += get(d1) + 3 - get(d2+1);
            if(m1==2&&leap(y1)==false)ans--;
            if(m1==9){
                ans+=30-d1+1;
            }
            if(m2==9){
                ans += d2;
            }
            int tmp = nine(y1);
            if(tmp){
                int day = mon[m2-1]-mon[m1] + (hh[m1] - d1 + 1) + d2;
                if(leap(y1)&&2>m1&&2<m2)day++;
                if(leap(y1)&&m1==2)day++;
                ans += day*tmp;
            }
            printf("%d\n", ans);
        }else{
            int ans = pre1[y2-1]-pre1[y1];
            int a = 0, b = 0, tmp = nine(y1),day;
            a = pre2[12]-pre2[m1];
            a += get(d1);
            if(leap(y1)==0&&m1==2)a--;
            if(leap(y1)&&m1==1)a++;
            if(m1==9)a += 30-d1+1;
            b = pre2[m2-1];
            b += 3-get(d2+1);
            if(leap(y2)&&m2>2)b++;
            if(m2==9)b+=d2;
            if(tmp){
                day = mon[12]-mon[m1] + (hh[m1] - d1 + 1);
                if(leap(y1)&&m1<=2)day++;
                a += tmp * day;
            }
            tmp = nine(y2);
            if(tmp){
                day = mon[m2-1] + d2;
                if(leap(y2)&&m2>2)day++;
                b += tmp * day;
            }
            ans += a+b;
            printf("%d\n", ans);
        }
    }
    return 0;
}

F - Knuth-Morris-Pratt Algorithm

ZOJ - 3957

签到题，KMP，判断一下次数就行。暴力判断也没事

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
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n;
char ch1[]="dog",ch2[]="cat";
int nex[2000];
void get_next(char *t,int lent){
    nex[0] = -1;
    for(int i = 0,k = -1;i < lent;){
        if(k==-1||t[i] == t[k]){
            ++k;++i;
            nex[i]=k;
        }else k = nex[k];
    }
}
int kmp(char *s,int lens,char *t,int lent){
    if(lens<lent)return 0;
    get_next(t,lent);
    int i = 0, j = 0;
    int cnt = 0;
    while(i < lens&&j<lent) {
        if(j==-1||s[i] == t[j]){
            i++;j++;
            if(j==lent){
                cnt++;
                j = nex[j];
            }
        }else j=nex[j];
    }
    return cnt;
}

int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        char s[2000];
        scanf("%s",s);
        int l=strlen(s);
        int ans=0;
        ans+=kmp(s,l,ch1,3);
        ans+=kmp(s,l,ch2,3);
        printf("%d\n",ans);
    }
    return 0;
}

G - Intervals

ZOJ - 3953

贪心，真的贪的内心崩溃。贪心策略，按L排序，每次判断3个区间，如果出现3个重合，丢去 R最大的，因为影响最大。

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<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
struct seg {
    int st,en,id;
    bool operator < (const  seg a )const {
        return en<a.en;
    }
} sg[maxn];
bool cmp(seg a,seg b) {
    if(a.st==b.st) {
        return a.en<b.en;
    }
    return a.st<b.st;
}
int res[maxn];


int main() {
    int n,t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        for(int i=0; i<n; i++) {
            scanf("%d%d",&sg[i].st,&sg[i].en);
            sg[i].id=i+1;
        }
        sort(sg,sg+n,cmp);
        priority_queue<seg>q;
        int ans=0;
        for(int i=0; i<n; i++) {
            if(q.size()<2) {
                q.push(sg[i]);
            } else {
                q.push(sg[i]);
                seg s[3];
                for(int i=0; i<3; i++) {
                    s[i]=q.top();
                    q.pop();
                }
                if(s[0].st<=s[2].en&&s[1].st<=s[2].en) {
                    res[ans++]=s[0].id;
                    q.push(s[1]);
                    q.push(s[2]);
                } else {
                    q.push(s[0]);
                    q.push(s[1]);
                }
            }
        }
        sort(res,res+ans);
        printf("%d\n",ans);
        for(int i=0; i<ans; i++) {
            printf("%d",res[i]);
            if(i+1==ans)printf("\n");
            else printf(" ");
        }
        if(ans==0)puts("");
    }
    return 0;
}

H - Seven-Segment Display

ZOJ - 3954

题意 ：1-9九个数，分别可以用后面7个0 1表示，下面给你n个数，每个数后面跟有7个01串，你可以交换n个数任意两列。如果可以通过交换表示出来输出YES 否则NO。

例子 :

1
7 0101011 1 1101011

把第2列和第5列交换，变成

1
1 1001111 7 0001111

与1 7 的表示匹配，所以输出YES

题解：这题只有9个数，暴力啊匹配，n^2都不会超时。。。；我是把每一列的状态用一个10进制数保存，每次能够从原来的数里面找与之匹配的状态，如果找不到，就输出NO；

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
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int mp[10];
int n;
int k[10],v[10];
int p[10];
map<int,int> m;
int main() {
    mp[1]=1001111;
    mp[2]=10010;
    mp[3]=110;
    mp[4]=1001100;
    mp[5]=100100;
    mp[6]=100000;
    mp[7]=1111;
    mp[8]=0;
    mp[9]=100;
    int t;
    p[0]=1;
    for(int i=1; i<10; i++) {
        p[i]=p[i-1]*10;
    }
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        for(int i=0; i<n; i++) {
            scanf("%d%d",&k[i],&v[i]);
        }
        m.clear();
        for(int i=0; i<7; i++) {
            int sum=0;
            for(int j=0; j<n; j++) {
                sum+=mp[k[j]]/p[i]%10*p[j];
            }
            m[sum]++;
        }
        int flag=1;
        for(int i=0; i<7; i++) {
            int sum=0;
            for(int j=0; j<n; j++) {
                sum+=v[j]/p[i]%10*p[j];
            }
            m[sum]--;
            if(m[sum]<0) {
                flag=0;
                break;
            }
        }
        puts(flag?"YES":"NO");
    }
    return 0;
}

J - Course Selection System

ZOJ - 3956

傻逼题,一开始还在想怎么推公式，结果发现，CI的和只有5e4，枚举所用能够到的状态H 的和最大不久行了，直接转换成了 0 1 背包。。。。。

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<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));

const long long mod=1e9+7;
const int maxn=5e4+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n;
int a[maxn];
int x[maxn],y[maxn];
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        for(int i=0; i<n; i++) {
            scanf("%d%d",&x[i],&y[i]);
        }
        mem(a,-1);
        a[0]=0;
        for(int i=0; i<n; i++) {
            for(int j=5e4-y[i]; j>=0; j--) {
                if(a[j]!=-1) {
                    a[j+y[i]]=max(a[j+y[i]],a[j]+x[i]);
                }
            }
        }
        ll ans=0;
        for(ll i=1;i<=5e4;i++){
            if(a[i]!=-1)
            ans=max(ans,1LL*a[i]*a[i]-i*a[i]-i*i);
        }
        printf("%lld\n",ans);
    }
    return 0;
}