LKOJ一本通题解报告

 1 /*
 2 problem:yibentong10000
 3 date:2019/4/21
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cstring>
10 #include<algorithm>
11 using namespace std;
12 const int maxn = 1e3+5;
13 struct node{
14     int s,f,dif;
15 };
16 node a[maxn];
17 int n,ans;
18 inline void init(){
19     cin>>n;
20     for(int i =1;i <= n;i++)scanf("%d%d",&a[i].s,&a[i].f);
21 }
22 inline bool cmp(node x,node y){
23     return x.f < y.f;
24 }
25 int main(){
26     init();
27     sort(a+1,a+1+n,cmp);
28     ans = 1;
29     int tmp = a[1].f;
30     for(int i = 2;i <= n;i++)
31         if(a[i].s >= tmp){
32             ans++;
33             tmp = a[i].f;
34         }
35     cout<<ans<<endl;
36     return 0;
37 }

T2种树

 1 /*
 2 problem:yibentong10001
 3 date:2019.4.21
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cstring>
10 #include<algorithm>
11 using namespace std;
12 const int maxn = 3e4+5;
13 struct node{
14     int b,e,t;
15 }a[maxn];
16 int visit[maxn];
17 int n,ans,h;
18 inline void init(){
19     cin>>n;
20     cin>>h;
21     for(int i = 1;i <= h;i++)
22         scanf("%d%d%d",&a[i].b,&a[i].e,&a[i].t);
23 }
24 inline bool cmp(node x,node y){
25     return x.e < y.e;
26 }
27 int main(){
28     init();
29     sort(a+1,a+1+h,cmp);
30     for(int i = 1;i <= h;i++){
31         int cnt = 0;
32         for(int j = a[i].b;j <= a[i].e;j++)
33             cnt += visit[j];
34         if(cnt >= a[i].t)continue;
35         for(int j = a[i].e;j >= a[i].b;j--)
36             if(!visit[j]){
37                 visit[j] = 1;
38                 cnt++;
39                 ans++;
40                 if(cnt == a[i].t)break;
41             }
42     }
43     cout<<ans<<endl;
44     return 0;
45 }

T3喷水装置

 1 /*
 2 problem:yibentong10002
 3 date:2019/4/21
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cstring>
10 #include<algorithm>
11 #include<cmath>
12 using namespace std;
13 const int maxn = 25e3+5;
14 struct node{
15     double head,tail;
16 }a[maxn];
17 int n,l,w,T,cnt,ans;
18 inline bool cmp(node x,node y){
19     return x.head < y.head;
20 }
21 inline void init(){
22     cin>>n>>l>>w;
23     cnt = 0;
24     for(int i = 1,r,position;i <= n;i++){
25         scanf("%d%d",&position,&r);
26         if(r <= w/2)continue;
27         cnt++;
28         double tmp = r*r-w*w/4.0;
29         a[cnt].head = position-sqrt(tmp);
30         a[cnt].tail = position+sqrt(tmp);
31     }
32 }
33 int main(){
34     cin>>T;
35     while(T--){
36         init();
37         sort(a+1,a+1+cnt,cmp);
38         ans = 0;
39         double position = 0;
40         bool flag = false;
41         while(position < l){
42             ans++;
43             double tmp = position;
44             for(int i = 1;a[i].head <= tmp && i <= cnt;i++)
45                 if(position < a[i].tail)
46                     position = a[i].tail;
47             if(position == tmp && position < l){
48                 puts("-1");
49                 flag = true;
50                 break;
51             }
52         }
53         if(flag == false)cout<<ans<<endl;
54     }
55     return 0;
56 }

T4加工生产调度

 1 /*
 2 problem:yibentong10003
 3 date:2019/4/30
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cstring>
10 #include<algorithm>
11 #include<cmath>
12 using namespace std;
13 const int maxn = 1e3+5;
14 struct node{
15     int position,Min;
16 }p[maxn];
17 int a[maxn],b[maxn],ans[maxn];
18 int n;
19 inline void init(){
20     cin>>n;
21     for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
22     for(int i = 1;i <= n;i++)scanf("%d",&b[i]);
23     for(int i = 1;i <= n;i++){
24         p[i].Min = min(a[i],b[i]);
25         p[i].position = i;
26     }
27 }
28 inline bool cmp(node x,node y){
29     return x.Min < y.Min;
30 }
31 int main(){
32     init();
33     sort(p+1,p+1+n,cmp);
34     int tmph = 0,tmpt = n+1;
35     for(int i = 1;i <= n;i++)
36         if(p[i].Min == a[p[i].position]){tmph++;ans[tmph] = p[i].position;}
37         else{tmpt--;ans[tmpt] = p[i].position;}
38     int timea = 0,timeb = 0;
39     for(int i = 1;i <= n;i++){
40         timea += a[ans[i]];
41         if(timeb < timea)timeb = timea;
42         timeb += b[ans[i]];
43     }
44     cout<<timeb<<endl;
45     for(int i = 1;i <= n;i++)printf("%d%c",ans[i],i == n ? '
':' ');
46     return 0;
47 }

T5智力大冲浪

 1 /*
 2 problem:yibentong10004
 3 date:2019/4/30
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cstring>
10 #include<algorithm>
11 using namespace std;
12 const int maxn = 5e2+5;
13 struct node{
14     int x,y;
15 }a[maxn];
16 int vis[5000010];
17 int flag,s;
18 int cmp(node a,node b){
19     return a.y > b.y;
20 }
21 int main(){
22     int m,n;
23     cin>>m>>n;
24     for(int i = 1;i <= n;i++)scanf("%d",&a[i].x);
25     for(int i = 1;i <= n;i++)scanf("%d",&a[i].y);
26     sort(a+1,a+n+1,cmp);
27     for(int i = 1;i <= n;i++){
28         flag = 1;
29         for(int j = a[i].x;j >= 1;j--)
30             if(vis[j] == 0){
31                 flag = 0;
32                 vis[j] = 1;
33                 break;
34             }
35         if(flag == 1){
36             for(int k = n;k >= 1;k--)
37                 if(vis[k] == 0){
38                     vis[k] = 1;
39                     break;
40                 }
41             s += a[i].y;
42         }
43     }
44     printf("%d
",m-s);
45     return 0;
46 }

练习T1数列极差

 1 /*
 2 problem:yibentonglian10000
 3 date:2019/5/5
 4 author:Lonely.Devil
 5 */
 6 
 7 
 8 #include<iostream>
 9 #include<algorithm>
10 #include<cstdio>
11 using namespace std;
12 const int maxn = 1e3+5;
13 int a[maxn];
14 int n,Max,Min;
15 int main(){
16     cin>>n;
17     for(int i = 1;i <= n; i++)
18         scanf("%d",&a[i]);
19     int tmp;
20     cin>>tmp;
21     sort(a+1,a+1+n);
22     Min = a[n];
23     for(int i = 1;i < n;i++)
24         Min = Min*a[n-i]+1;
25     for(int i = 1;i <= n;i++){
26         a[i+1] = a[i]*a[i+1]+1;
27         for(int j = i+1;j < n;j++)
28             if(a[j] > a[j+1])
29                 swap(a[j],a[j+1]);
30     }
31     Max = a[n];
32     cout<<Max-Min<<endl;
33     return 0;
34 }

练习T2数列分段

 1 /*
 2 problem:yibentonglian10001
 3 date:2019/5/5
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 using namespace std;
10 int n,m,ans,now;
11 int main(){
12     cin>>n>>m;
13     for(int i = 1,tmp;i <= n;i++){
14         scanf("%d",&tmp);
15         now += tmp;
16         if(now < m && i == n){
17             ans++;
18             break;
19         }
20         if(now > m){
21             ans++;
22             now = tmp;
23         }
24         if(now == m){
25             ans++;
26             now = 0;
27         }
28     }
29     cout<<ans<<endl;
30     return 0;
31 }

练习T3线段

 1 /*
 2 problem:yibentonglian10002
 3 date:2019/5/5
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<algorithm>
10 using namespace std;
11 const int maxn = 1e6+5;
12 struct node{
13     int x,y;
14 }a[maxn];
15 int n,now,ans;
16 inline bool cmp(node a,node b){
17     return a.y < b.y;
18 }
19 int main(){
20     cin>>n;
21     for(int i = 1;i <= n;i++)scanf("%d%d",&a[i].x,&a[i].y);
22     sort(a+1,a+1+n,cmp);
23     now = a[1].y;
24     ans = 1;
25     for(int i = 2;i <= n;i++){
26         if(a[i].x >= now){
27             ans++;
28             now = a[i].y;
29         }
30     }
31     cout<<ans<<endl;
32     return 0;
33 }

练习T4家庭作业

 1 /*
 2 problem:yibentonglian10003
 3 date:2019/5/5
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cstring>
10 #include<algorithm>
11 using namespace std;
12 const int maxn = 1e6+5;
13 struct node{
14     int date,val;
15 }a[maxn];
16 bool visit[maxn];
17 bool flag;
18 int n,ans,s;
19 inline bool cmp(node a,node b){
20     return a.val > b.val;
21 }
22 int main(){
23     cin>>n;
24     for(int i = 1;i <= n;i++)scanf("%d%d",&a[i].date,&a[i].val);
25     memset(visit,false,sizeof(visit));
26     sort(a+1,a+1+n,cmp);
27     for(int i = 1;i <= n;i++){
28         if(a[i].date <= s)continue;
29         flag = false;
30         for(int j = a[i].date;j >= 1;j--)
31             if(visit[j] == false){
32                 visit[j] = true;
33                 ans += a[i].val;
34                 flag = true;
35                 break;
36             }
37         if(flag == false)s = a[i].date;
38     }
39     cout<<ans<<endl;
40     return 0;
41 }

练习T5钓鱼

 1 /*
 2 problem:yibentonglian10004
 3 date:2019/5/5
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cmath>
10 using namespace std;
11 const int maxn = 1e2+5;
12 int a[maxn],d[maxn],t[maxn],fish[maxn];
13 int n,ans,h,sum,Max,position;
14 int main(){
15     cin>>n>>h;
16     h *= 12;
17     for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
18     for(int i = 1;i <= n;i++)scanf("%d",&d[i]);
19     for(int i = 1,tmp;i < n;i++)scanf("%d",&tmp),t[i] = t[i-1]+tmp;
20     for(int i = 1;i <= n;i++){
21         for(int j = 1;j <= i;j++)fish[j] = a[j];
22         int time = h - t[i-1];
23         sum = 0;
24         for(int j = 1;j <= time;j++){
25             Max = 0;
26             for(int k = 1;k <= i;k++)
27                 if(fish[k] > Max)Max = fish[k],position = k;
28             if(Max == 0)break;
29             fish[position] -= d[position];
30             sum += Max;
31         }
32         ans = max(ans,sum);
33     }
34     cout<<ans<<endl;
35     return 0;
36 }

练习T6糖果传递

 1 /*
 2 problem:yibentonglian10005
 3 date:2019/5/7
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<algorithm>
10 #include<cmath>
11 using namespace std;
12 const int maxn = 1e6+5;
13 long long a[maxn],c[maxn];
14 long long total,ave,ans;
15 int n;
16 int main(){
17     cin>>n;
18     for(int i = 1;i <= n;i++)scanf("%d",&a[i]),total += a[i];
19     ave = total/n;
20     for(int i = 1;i <= n;i++)c[i] = c[i-1]+a[i]-ave;
21     sort(c+1,c+1+n);
22     int mid = (n+1)>>1;
23     for(int i = 1;i <= n;i++)
24         ans += abs(c[mid]-c[i]);
25     printf("%lld
",ans);
26     return 0;
27 }

T1数列分段II

 1 /*
 2 problem:yibentong10000
 3 date:2019/5/7
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 using namespace std;
10 const int maxn = 1e5+5;
11 int a[maxn];
12 int n,m,l,r;
13 inline bool check(int x){
14     int ans = 1,sum = 0;
15     for(int i = 1;i <= n;i++){
16         sum += a[i];
17         if(sum > x)ans++,sum = a[i];
18     }
19     if(ans <= m)return true;
20     return false;
21 }
22 int main(){
23     cin>>n>>m;
24     int Max = 0,sum = 0;
25     for(int i = 1;i <= n;i++)scanf("%d",&a[i]),Max = max(Max,a[i]),sum += a[i];
26     l = Max,r = sum;
27     while(l <= r){
28         int mid = (l+r)>>1;
29         if(check(mid))r = mid-1;
30         else l = mid+1;
31     }
32     cout<<l<<endl;
33     return 0;
34 }

T2愤怒的牛

 1 /*
 2 problem:yibentong10001
 3 date:2019/5/7
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<algorithm>
10 using namespace std;
11 const int maxn = 1e5+5;
12 int a[maxn];
13 int n,m;
14 inline bool check(int x){
15     int ans = 1;
16     int cnt = a[1]+x;
17     for(int i = 2;i <= n;i++){
18         if(a[i] < cnt)continue;
19         ans++;
20         cnt = a[i]+x;
21     }
22     return ans >= m;
23 }
24 int main(){
25     cin>>n>>m;
26     for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
27     sort(a+1,a+1+n);
28     int l = 0,r = a[n];
29     while(l <= r){
30         int mid = (l+r)>>1;
31         if(check(mid))l = mid+1;
32         else r = mid-1;
33     }
34     cout<<r<<endl;
35     return 0;
36 }

T3扩散

法一：Kruscal

 1 /*
 2 problem:yibentong10002
 3 date:2019/5/11
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<algorithm>
10 using namespace std;
11 #define ll long long
12 const ll maxn = 5e1+5;
13 ll father[maxn],x[maxn],y[maxn];
14 ll n,cnt,sum;
15 struct edge{
16     ll x,y,w;
17 }e[maxn*maxn/2];
18 ll dist(ll i,ll j){
19     return (abs(x[i]-x[j])+abs(y[i]-y[j])+1)/2;
20 }
21 ll cmp(edge a,edge b){
22     return a.w < b.w;
23 }
24 ll find(ll x){
25     if(father[x] == x)return x;
26     else return father[x] = find(father[x]);
27 }
28 void Kruscal(){
29     sort(e+1,e+1+cnt,cmp);
30     for(ll i = 1;i <= cnt;i++)
31         if(find(e[i].x) != find(e[i].y)){
32             father[find(e[i].x)] = find(e[i].y);
33             sum++;
34             if(sum == n-1){
35                 printf("%lld
",e[i].w);
36                 break;
37             }
38         }
39 }
40 int main(){
41     cin>>n;
42     for(ll i = 1;i <= n;i++)scanf("%d%d",&x[i],&y[i]);
43     for(ll i = 1;i <= n;i++)father[i] = i;
44     for(ll i = 1;i <= n;i++)
45         for(ll j = i+1;j <= n;j++){
46             cnt++;
47             e[cnt].x = i;
48             e[cnt].y = j;
49             e[cnt].w = dist(i,j);
50         }
51     Kruscal();
52     return 0;
53 }

法二：Floyd

 1 /*
 2 problem:yibentong1000
 3 date:2019/5/11
 4 author:Lonely.Devil
 5 */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<algorithm>
10 using namespace std;
11 #define ll long long
12 const ll maxn = 5e1+5;
13 struct point{
14     ll x,y;
15 }p[maxn];
16 ll map[maxn][maxn];
17 ll n,ans;
18 inline ll Abs(ll x){
19     if(x < 0)x = -x;
20     return x;
21 }
22 inline ll Min(ll x,ll y){
23     return x < y ? x : y;
24 }
25 inline ll Max(ll x,ll y){
26     return x > y ? x : y;
27 }
28 inline ll dist(int i,int j){
29     return (Abs(p[i].x-p[j].x)+Abs(p[i].y-p[j].y)+1)/2;
30 }
31 inline void Floyd(){
32     for(ll k = 1;k <= n;k++)
33         for(ll i = 1;i <= n;i++)
34             for(ll j = 1;j <= n;j++)
35                 map[i][j] = min(map[i][j],max(map[k][j],map[i][k]));
36 }
37 int main(){
38     cin>>n;
39     for(ll i = 1;i <= n;i++)scanf("%lld%lld",&p[i].x,&p[i].y);
40     for(ll i = 1;i <= n;i++)
41         for(ll j = 1;j <= n;j++)
42             if(i == j)map[i][j] = 0;
43     for(ll i = 1;i <= n;i++)
44         for(ll j = i+1;j <= n;j++)
45             map[i][j] = map[j][i] = dist(i,j);
46     Floyd();
47     for(ll i = 1;i <= n;i++)
48         for(ll j = i+1;j <= n;j++)
49             if(ans < map[i][j])
50                 ans = map[i][j];
51     cout<<ans<<endl;
52     return 0;
53 }

LKOJ一本通题解报告

目录