absi2011's Blog & Daily Life.

全新的开始　　　　　　　我要省选翻盘　　　　　　　I wanna AK in 高考\化学　　　　　　　自此,生无可恋
[破碎的状态] JSOI Round 3 Day 2 碎碎念
[破碎的状态] [-47] 北大夏令营 Day 2

[破碎的状态] [-48] 北大夏令营 Day 1

absi2011 posted @ 9 年前 in OI系列 with tags NOI POJ 小高考 JSOI NOIP 字符串 DP 模拟 dijkstra BFS 线段树 搜索 DFS AC自动机 瞎搞 pku , 739 阅读

早上他们说了一堆东西..

然后..那些东西暂时无视

反正..我现在是来签约的

早上:http://bailian.openjudge.cn/oitraining2016a/

========

开场

看到B题是a*b 问题仔细看了下是FFT版,弃疗..

看D题是个分形的好题

dfs了下..

WA!

发现被回车问题坑了一发

再交

WA!

数组开小了TAT

再交

AC!一血!

*题意:给你个n,求打印一个n阶的这样的三角形

n<=10

....并没啥用....罚了4次时

?
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
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<time.h>
#include<string>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[2005][3005];
void dfs(int n,int sx,int sy)
{
    if (n==1)
    {
        a[sx][sy+1]='/';
        a[sx][sy+2]='\\';
        a[sx+1][sy]='/';
        a[sx+1][sy+1]='_';
        a[sx+1][sy+2]='_';
        a[sx+1][sy+3]='\\';
        return;
    }
    dfs(n-1,sx,sy+(1<<(n-1)));
    dfs(n-1,sx+(1<<(n-1)),sy);
    dfs(n-1,sx+(1<<(n-1)),sy+(1<<n));
}
int main()
{
    #ifdef absi2011
    freopen("output.txt","w",stdout);
    #endif
    int flag=0;
    for (;;)
    {
        memset(a,' ',sizeof(a));
        int n;
        scanf("%d",&n);
        if (n==0) return 0;
        if (flag==1)
        {
            putchar('\n');
        }
        flag=1;
        dfs(n,0,0);
        int i;
        for (i=0;i<(1<<n);i++)
        {
            int j;
            for (j=0;j<i+(1<<n)+1;j++)
            {
                putchar(a[i][j]);
            }
            putchar('\n');
        }
    }
}

然后再接着看

E题似乎是个挺长的题面

AC两题有人交没人过

想了想,看C

不会做..

看A

不会做..

抱着"反正这次是来玩玩的"的心态

所以就写了个暴搜

TLE!

优化一发

AC..又是个一血!

*题意:

给你一个#字形的东西,你要在尽量少的步数内(如果步数一样字典序最小)操作,每次操作如图所示

具体的输入格式可以见题面..

要求中间的8个数字相同,求方案

所以..

?
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
167
168
169
170
171
172
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<time.h>
#include<string>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int af[15]={0,2,6,11,15,20,22,24};   //a : <--
int be[15]={1,3,8,12,17,21,23,24};   //b : <--
int ch[15]={4,5,6,7,8,9,10,24};      //c : -->
int dg[15]={13,14,15,16,17,18,19,24};//d : -->
int center[15]={6,7,8,11,12,15,16,17};
char ans[25];
int a[25];
void oper(int x)
{
    if (x==0)
    {
        a[24]=a[af[0]];
        int i;
        for (i=0;i<7;i++)
        {
            a[af[i]]=a[af[i+1]];
        }
    }
    if (x==1)
    {
        a[24]=a[be[0]];
        int i;
        for (i=0;i<7;i++)
        {
            a[be[i]]=a[be[i+1]];
        }
    }
    if (x==2)
    {
        int i;
        int t=a[ch[6]];
        for (i=6;i>0;i--)
        {
            a[ch[i]]=a[ch[i-1]];
        }
        a[ch[0]]=t;
    }
    if (x==3)
    {
        int i;
        int t=a[dg[6]];
        for (i=6;i>0;i--)
        {
            a[dg[i]]=a[dg[i-1]];
        }
        a[dg[0]]=t;
    }
    if (x==4)
    {
        int i;
        int t=a[be[6]];
        for (i=6;i>0;i--)
        {
            a[be[i]]=a[be[i-1]];
        }
        a[be[0]]=t;
    }
    if (x==5)
    {
        int i;
        int t=a[af[6]];
        for (i=6;i>0;i--)
        {
            a[af[i]]=a[af[i-1]];
        }
        a[af[0]]=t;
    }
    if (x==6)
    {
        a[24]=a[dg[0]];
        int i;
        for (i=0;i<7;i++)
        {
            a[dg[i]]=a[dg[i+1]];
        }
    }
    if (x==7)
    {
        a[24]=a[ch[0]];
        int i;
        for (i=0;i<7;i++)
        {
            a[ch[i]]=a[ch[i+1]];
        }
    }
}
int find_ans=0;
int anti[15]={5,4,7,6,1,0,3,2};
void dfs(int x,int y,int last_oper=-1)
{
    if (x==y)
    {
        int val=a[center[0]];
        int i;
        for (i=1;i<8;i++)
        {
            if (a[center[i]]!=val) return;
        }
        find_ans=1;
        return;
    }
    if (x==y+1)
    {
        if ((a[7]!=a[11])||(a[11]!=a[16])||(a[16]!=a[12])) return;
    }
    int i;
    for (i=0;i<8;i++)
    {
        ans[y]='A'+i;
        if (last_oper==anti[i]) continue;
        oper(i);
        dfs(x,y+1,i);
        if (find_ans==1) return;
        oper(anti[i]);
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    for (;;)
    {
        scanf("%d",&a[0]);
        if (a[0]==0) return 0;
        int i;
        for (i=1;i<24;i++)
        {
            scanf("%d",&a[i]);
        }
        find_ans=0;
        for (i=0;;i++)
        {
            dfs(i,0);
            if (find_ans)
            {
                if (i==0)
                {
                    printf("No moves needed\n");
                }
                else
                {
                    ans[i]=0;
                    printf("%s\n",ans);
                }
                printf("%d\n",a[6]);
                break;
            }
        }
    }
}

我就接着来看别的题

B题很显然放弃

C题不会,读E题去

看起来是个dp

*题意:

两个人彼此憎恨,所以他们希望离得越远越好

他们俩住在一个n*n的方格里,一个要从H到S,一个要从h到s

这天,他们俩从家到学校,你要构造他们俩走路的一个方案,使得他们距离最小的时刻距离最大

PS:图上有障碍物

PS:H和S对于h出发的人不可到达,同理h和s对于H出发的人不可到达

n<=30

感觉..是个dp的好题啊

随便dp了一发

WA!

回车问题..重新弄一下

WA!

唉?哪里有错?

那..再修改下回车问题

WA!

等下!H对于h不可到达?

居然没看到这条件

WA!

等下S也不可到达?

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<time.h>
#include<string>
#include<vector>
#include<memory>
#include<bitset>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int dp[1500625];
int pre[1500625];
bool visit[1500625];
char a[35][35];
int code(int x,int y,int z,int w)
{
    return (((x*35+y)*35+z)*35+w);
}
int dist(int x,int y,int z,int w)
{
    return ((z-x)*(z-x))+((y-w)*(y-w));
}
int dire[5][2]={
{0,1},
{0,-1},
{-1,0},
{1,0},
{0,0}};
void dfs1(int x1,int y1,int x2,int y2)
{
    int t=pre[code(x1,y1,x2,y2)];
    if (t==-1) return;
    int nowx1,nowx2,nowy1,nowy2;
    nowy2=t%35;
    t/=35;
    nowx2=t%35;
    t/=35;
    nowy1=t%35;
    t/=35;
    nowx1=t;
    dfs1(nowx1,nowy1,nowx2,nowy2);
    if ((nowx1==x1-1)) printf("S");
    if ((nowx1==x1+1)) printf("N");
    if ((nowy1==y1-1)) printf("E");
    if ((nowy1==y1+1)) printf("W");
}
void dfs2(int x1,int y1,int x2,int y2)
{
    int t=pre[code(x1,y1,x2,y2)];
    if (t==-1) return;
    int nowx1,nowx2,nowy1,nowy2;
    nowy2=t%35;
    t/=35;
    nowx2=t%35;
    t/=35;
    nowy1=t%35;
    t/=35;
    nowx1=t;
    dfs2(nowx1,nowy1,nowx2,nowy2);
    if ((nowx2==x2-1)) printf("S");
    if ((nowx2==x2+1)) printf("N");
    if ((nowy2==y2-1)) printf("E");
    if ((nowy2==y2+1)) printf("W");
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    int flag=0;
    for (;;)
    {
        scanf("%d",&n);
        if (n==0) return 0;
        if (flag) printf("\n");
        flag=1;
        int i;
        int sx1,sy1,sx2,sy2,ex1,ey1,ex2,ey2;
        memset(visit,false,sizeof(visit));
        memset(dp,-1,sizeof(dp));
        for (i=0;i<n;i++)
        {
            scanf("%s",a[i]);
            int j;
            for (j=0;j<n;j++)
            {
                if (a[i][j]=='H')
                {
                    sx1=i;
                    sy1=j;
                }
                if (a[i][j]=='h')
                {
                    sx2=i;
                    sy2=j;
                }
                if (a[i][j]=='S')
                {
                    ex1=i;
                    ey1=j;
                }
                if (a[i][j]=='s')
                {
                    ex2=i;
                    ey2=j;
                }
            }
        }
        priority_queue<pair<int,int> > q;
        q.push(make_pair(dist(sx1,sy1,sx2,sy2),code(sx1,sy1,sx2,sy2)));
        dp[code(sx1,sy1,sx2,sy2)]=dist(sx1,sy1,sx2,sy2);
        pre[code(sx1,sy1,sx2,sy2)]=-1;
        for (;!q.empty();)
        {
            int t=q.top().second;
            q.pop();
            if (visit[t]) continue;
            visit[t]=true;
            int nowx1,nowx2,nowy1,nowy2;
            nowy2=t%35;
            t/=35;
            nowx2=t%35;
            t/=35;
            nowy1=t%35;
            t/=35;
            nowx1=t;
            t=code(nowx1,nowy1,nowx2,nowy2);
            int i,j;
            for (i=0;i<5;i++)
            {
                int tx1=nowx1+dire[i][0];
                int ty1=nowy1+dire[i][1];
                if ((tx1<0)||(tx1>=n)||(ty1<0)||(ty1>=n)) continue;
                if ((i!=4)&&((nowx1==ex1)&&(nowy1==ey1))) continue;
                if ((i==4)&&((nowx1!=ex1)||(nowy1!=ey1))) continue;
                if (a[tx1][ty1]=='*') continue;
                if (a[tx1][ty1]=='h') continue;
                if (a[tx1][ty1]=='s') continue;
                for (j=0;j<5;j++)
                {
                    int tx2=nowx2+dire[j][0];
                    int ty2=nowy2+dire[j][1];
                    if ((tx2<0)||(tx2>=n)||(ty2<0)||(ty2>=n)) continue;
                    if ((j!=4)&&((nowx2==ex2)&&(nowy2==ey2))) continue;
                    if ((j==4)&&((nowx2!=ex2)||(nowy2!=ey2))) continue;
                    if (a[tx2][ty2]=='*') continue;
                    if (a[tx2][ty2]=='H') continue;
                    if (a[tx2][ty2]=='S') continue;
                    int t2=code(tx1,ty1,tx2,ty2);
                    if (visit[t2]) continue;
                    if (dp[t]>dp[t2])
                    {
                        dp[t2]=min(dp[t],dist(tx1,ty1,tx2,ty2));
                        q.push(make_pair(dp[t2],t2));
                        pre[t2]=t;
                    }
                }
            }
        }
        printf("%.2lf\n",sqrt(dp[code(ex1,ey1,ex2,ey2)]));
        dfs1(ex1,ey1,ex2,ey2);
        printf("\n");
        dfs2(ex1,ey1,ex2,ey2);
        printf("\n");
    }
    return 0;
}

========上午三题=======

========下面是下午=======

题面:http://bailian.openjudge.cn/oitraining2016b/

开场

看到E题唯一一个题

等下冷血竞技场?这不是noijudge上的题么

好像一个map就能水过去

冷静了下,写了一发直接过sample,交

果断9分钟过了

1A!一血!

?
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<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<math.h>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
map<int,int> s;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    s[1000000000]=1;
    for (i=0;i<n;i++)
    {
        int id,ab;
        scanf("%d%d",&id,&ab);
        printf("%d ",id);
        map<int,int>::iterator ii=s.lower_bound(ab);
        if (ii==s.begin())
        {
            printf("%d\n",(*ii).second);
        }
        else
        {
            int t1=(*ii).first-ab;
            int val1=(*ii).second;
            ii--;
            int t2=ab-(*ii).first;
            int val2=(*ii).second;
            if ((t1<t2)||((t1==t2)&&(val1<val2)))
            {
                printf("%d\n",val1);
            }
            else
            {
                printf("%d\n",val2);
            }
        }
        if (s[ab]==0) s[ab]=id;
        s[ab]=min(s[ab],id);
    }
    return 0;
}

然后..我擦?那么多人都过了A?几个意思

感觉难道A题是sb题?为啥都是0Kb/0ms过的

然后..

喜闻乐见的告诉我们A题数据有问题别交

然后他们全部被rejudge成WA/TLE了

我怎么就这么轻易的rank 1了..感觉好慌啊

过了一会儿有人过AE了,我就掉下去了

想吐槽一发

上午我记住密码了一发,之后有人拿我的号交了个E...

然后..

出现了一些奇怪的情况

所以..让我重新交一发

所以就多了一次罚时

然后..掉下去了

感觉F题是个AC自动机的东西

*题意:给你n个字符串,要问你每个字符串是否在大字符串中出现过

*字符串可能被折叠成"[x个T]"的形式

*如果一个字符串出现过,它的子串视为没有出现过

然后..

就写了一发..

一直在RE,终于调到不RE了!

WA了!

思考了一发,重新修改修改

过了..

又是一血..

一血进度5/5..

这题主要是第三个*有点难弄而已..

大概需要在适当的地方(见代码)去稍微去更新下,大概就可以了..

?
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
167
168
169
170
171
172
173
174
175
176
177
178
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<math.h>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
char a[5100005];
struct node
{
    int flag;
    bool vis;
    node * fail;
    node * ch[26];
};
int top=0;
node * new_node()
{
    static node a[3000005];
    memset(a[top].ch,0,sizeof(a[top].ch));
    a[top].flag=0;
    a[top].vis=false;
    return &a[top++];
}
void read_str()
{
    int now=0;
    char x;
    for (;;)
    {
        x=getchar();
        if (x=='[')
        {
            int y;
            scanf("%d",&y);
            int i=0;
            static char z[5100005];
            for (;;)
            {
                z[i]=getchar();
                if (z[i]==']') break;
                i++;
            }
            for (;y>0;y--)
            {
                int j;
                for (j=0;j<i;j++)
                {
                    a[now++]=z[j];
                }
            }
            continue;
        }
        a[now++]=x;
        if (x=='\n') return;
        if (x==-1)
        {
            a[now-1]='\n';
            return;
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        int n;
        scanf("%d",&n);
        read_str();
        int i;
        top=0;
        node * root=new_node();
        for (i=0;i<n;i++)
        {
            read_str();
            int j;
            node * now=root;
            for (j=0;a[j]!='\n';j++)
            {
                if (now->ch[a[j]-'A']==0)
                {
                    now->ch[a[j]-'A']=new_node();
                }
                now=now->ch[a[j]-'A'];
            }
            now->flag=true;
        }
        static node * que[3000005];
        int front=0,rail=1;
        que[0]=root;
        root->fail=root;
        for (;front<rail;front++)
        {
            node * t=que[front];
            int i;
            for (i=0;i<26;i++)
            {
                if (t->ch[i]==0)
                {
                    t->ch[i]=t->fail->ch[i];
                    if (t->ch[i]==0) t->ch[i]=root;
                }
                else
                {
                    t->ch[i]->fail=t->fail->ch[i];
                    if (t==root) t->ch[i]->fail=root;
                    que[rail++]=t->ch[i];
                }
            }
        }
        read_str();
        node * now=root;
        for (i=0;a[i]!='\n';i++)
        {
            now=now->ch[a[i]-'A'];
            now->vis=true;
        }
        for (i=rail-1;i>=0;i--)
        {
            if (que[i]->vis) que[i]->fail->vis=true;
        }
        for (i=rail-1;i>=0;i--)
        {
            int j;
            for (j=0;j<26;j++)
            {
                if (que[i]->ch[j]!=que[i]->fail->ch[j])
                {
                    if (((que[i]->ch[j]->flag)&&(que[i]->ch[j]->vis))||(que[i]->ch[j]->flag==2))
                    {
                        que[i]->flag=2;
                    }
                }
            }
            if (que[i]->flag)
            {
                if (que[i]->vis)
                {
                    que[i]->fail->flag=2;
                }
                else if (que[i]->flag==2)
                {
                    que[i]->fail->flag=2;
                }
            }
        }
        int sum=0;
        for (i=0;i<rail;i++)
        {
            if ((que[i]->vis)&&(que[i]->flag==1))
            {
                sum++;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

然后..

接下来就是回头看A题

*题意:给你n个点(n<=50000)求两两的最长欧几里德距离的平方

思考了一发,根据坐标范围在[-10000,10000]内的性质

果断大暴力走起

前面因为某些原因电脑卡了直接交,WA了两次(后来发现sample没过)

又TLE了一次,一怒之下我把n^2的值给预处理了

过了..2960ms/3000ms

这个不是一血..

?
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
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<math.h>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int dist(int x,int y,int xx,int yy)
{
    return (xx-x)*(xx-x)+(yy-y)*(yy-y);
}
int bi[20005],bx[20005];
int square[20005];
int main()
{
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<=20000;i++)
    {
        bi[i]=200000;
        bx[i]=-100000;
        square[i]=i*i;
    }
    for (i=0;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        bi[x+10000]=min(bi[x+10000],y);
        bx[x+10000]=max(bx[x+10000],y);
    }
    int max_ans=0;
    for (i=0;i<=20000;i++)
    {
        if (bx[i]==-100000) continue;
        int j;
        for (j=i;j<=20000;j++)
        {
            if (bx[j]==-100000) continue;
            int ans=square[j-i];
            if (bx[j]-bi[i]>bx[i]-bi[j]) ans+=square[bx[j]-bi[i]]; else ans+=square[bx[i]-bi[j]];
            if (ans>max_ans) max_ans=ans;
        }
    }
    printf("%d\n",max_ans);
}

然后就来看D

D似乎也不是什么难题..

*题意:

从2000年1月1号0时开始算第一个小时

你要在m个小时内做月饼,第i个小时做的代价是给定的,做一个就要那么大的代价

每个月饼做出来以后,保质期是T天

每个月饼放冰箱里冷场的代价是S,做出来不卖掉就得冷藏

现在有一堆人过来订月饼吃,你要求最小的代价,使得满足所有人的订单

PS:每个小时的整点时刻可以做任意多个月饼

一个线段树题..

我们考虑一发

我们可以发现,每个订单是独立的..

然后..线段树搞下就行了..

?
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
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<time.h>
#include<math.h>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int querys[2505];
int a[100005];
int val[1<<18];
void build_tree(int num,int l,int r)
{
    if (l==r-1)
    {
        val[num]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build_tree(num*2+1,l,mid);
    build_tree(num*2+2,mid,r);
    val[num]=min(val[num*2+1],val[num*2+2]);
}
int query(int num,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        return val[num];
    }
    int mid=(l+r)/2;
    int ans=1999999999;
    if (l0<mid) ans=min(ans,query(num*2+1,l,mid,l0,r0));
    if (mid<r0) ans=min(ans,query(num*2+2,mid,r,l0,r0));
    return ans;
}
int days[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
map<string,int> ma;
int need[2505];
int read_time(int x)
{
    static char a[5];
    scanf("%s",a);
    string b=a;
    int month=ma[b];
    int day;
    int year;
    scanf("%d%d",&day,&year);
    year-=2000;
    day--;
    int hour;
    scanf("%d",&hour);
    scanf("%d",&need[x]);
    for (;;)
    {
        if (month==0)
        {
            if (year==0) break;
            year--;
            month=12;
        }
        if ((month==2)&&(year%4==0)) day++;
        day+=days[month];
        month--;
    }
    return day*24+hour+1;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    //"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov" or "Dec"
    ma["Jan"]=0;
    ma["Feb"]=1;
    ma["Mar"]=2;
    ma["Apr"]=3;
    ma["May"]=4;
    ma["Jun"]=5;
    ma["Jul"]=6;
    ma["Aug"]=7;
    ma["Sep"]=8;
    ma["Oct"]=9;
    ma["Nov"]=10;
    ma["Dec"]=11;
    for (;;)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        if ((n==0)&&(m==0)) return 0;
        int i;
        for (i=0;i<n;i++)
        {
            querys[i]=read_time(i);
        }
        int s,t;
        scanf("%d%d",&t,&s);
        for (i=0;i<m;i++)
        {
            int x;
            scanf("%d",&x);
            x+=s*(m-i-1);
            a[i]=x;
        }
        build_tree(0,0,m);
        long long ans=0;
        for (i=0;i<n;i++)
        {
            ans+=(query(0,0,m,max(querys[i]-t-1,0),querys[i])-s*(m-querys[i]))*(long long)need[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

B题是个计算几何,不会写

C题..不知道怎么弄..

好像是个二分图的最小覆盖?

没时间弄了不太会..不管了

Small_feed 评论 (2)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter