codeforces 1380 总结

116 阅读 0 评论 77 点赞

我是靠谱客的博主年轻小笼包，这篇文章主要介绍codeforces 1380 总结，现在分享给大家，希望可以做个参考。

A
给一串数，找是否有i<j<k,ai<aj,aj>ak

复制代码

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
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1005];
int main()
{
int t;
scanf("%d",&t);
int n;
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int p[4]={0};
int jud=0;
int flag=0;
for(int i=2;i<=n-1;i++)
{
p[2]=i;
jud=0;
flag=0;
for(int j=i-1;j>=1;j--)
{
if(a[j]<a[p[2]])
{
p[1]=j;
jud=true;
break;
}
}
if(jud)
{
for(int j=i+1;j<=n;j++)
{
if(a[p[2]]>a[j])
{
p[3]=j;
flag=1;
break;
}
}
}
if(flag) break;
}
if(flag)
{
printf("YESn");
printf("%d %d %d",p[1],p[2],p[3]);
printf("n");
}
else printf("NOn");
}
return 0;
}

B
剪子包袱锤，给出一串顺序，问另一串顺序怎样才能使赢得平均场数最多，（每个位置都轮换一遍）。
思路：
每个位置上的东西都要和上一串的每一个位置比，那么干脆就这样，找出能获胜最多的那个东西，然后这一串全是他。

复制代码

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 <iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<utility>
using namespace std;
char ch[200005];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
pair<int,char>d[4];
d[1].second='P';
d[2].second='S';
d[3].second='R';
scanf("%s",ch+1);
int len=strlen(ch+1);
d[1].first=0,d[2].first=0,d[3].first=0;
for(int i=1;i<=len;i++)
{
if(ch[i]=='P') d[2].first++;
else if(ch[i]=='S') d[3].first++;
else d[1].first++;
}
sort(d+1,d+4);
for(int i=1;i<=len;i++)
printf("%c",d[3].second);
printf("n");
}
return 0;
}

C
n个数分组，要求组内数的个数乘以组内最小的数要大于等于x，问最多分多少组？
思路：大的尽量单独或者少量几个数为一组，小的就扎堆为一组就好。

复制代码

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
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll a[100005];
bool cmp(ll p1,ll p2)
{
return p1>p2;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll n;
ll x;
scanf("%lld%lld",&n,&x);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
sort(a+1,a+1+n,cmp);
ll cnt=0;
ll num=0;
ll pos=0;
while(1)
{
pos++;
cnt=0;
while(1)
{
cnt++;
if(cnt*a[pos+cnt-1]>=x)
{
//printf("%lldn",a[pos+cnt-1]);
num++;
pos=pos+cnt-1;
//printf("%lldn",pos);
// printf("%lldn",cnt);
break;
}
if(pos+cnt-1>=n) break;
}
if(pos>=n) break;
if(pos+cnt-1>=n) break;
}
printf("%lldn",num);
}
return 0;
}

D
给一组数，有两种操作，一种是选连续的k个数，删掉他们，花费为x，一种是选连续的两个数，删掉小的一个，花费为y，问能否通过这两种操作得到指定的序列？
思路：连续这个条件很重要，如果不是连续的，那就糟了。由于对是连续的数操作，那么就定义两个指针，一个指向原有序列，一个指向给定序列，找出需要删掉的区间（两边夹着的就是），然后判断区间能否被删掉，若能，在找最小值。

但是，这题的官方题解有漏洞，官方题解在减掉余数后没有判断区间长度是否为零直接进行找小值的步骤，若为零的话，则有可能有错误出现。加上这个条件就好。

复制代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+5;
int n, m;
long long x, k, y;
int a[N];
int b[N];
ll res=0;
bool jud(int l, int r)
{
if (l > r) return true;
bool flag = false;
int mx = *max_element(a + l, a + r + 1);
int len = r - l + 1;
if (l - 1 >= 0 && a[l - 1] > mx) flag = true;
else if (r + 1 < n && a[r + 1] > mx) flag = true;
if (len < k && !flag) return false;
int need = len % k;
res += need * y;
len -= need;
if(len==0) return true;
if (y * k >= x)
{
res += len / k * x;
}
else if(flag)
{
res += len * y;
}
else
{
res += (len - k) * y + x;
}
return true;
}
int main()
{
scanf("%d %d", &n, &m);
scanf("%lld %lld %lld", &x, &k, &y);
for (int i = 0; i < n; ++i) scanf("%d", a + i);
for (int i = 0; i < m; ++i) scanf("%d", b + i);
int lst = -1, posa = 0, posb = 0;
while (posb < m)
{
while(posa < n && a[posa] != b[posb]) ++posa;
if (posa == n)
{
puts("-1");
return 0;
}
if (!jud(lst + 1, posa - 1))
{
puts("-1");
return 0;
}
lst = posa;
++posb;
}
if (!jud(lst + 1, n - 1))
{
puts("-1");
return 0;
}
printf("%lldn", res);
return 0;
}

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+5;
int n, m;
long long x, k, y;
int a[N];
int b[N];
ll res=0;
bool jud(int l, int r)
{
if (l > r) return true;
bool flag = false;
int mx = *max_element(a + l, a + r + 1);
int len = r - l + 1;
if (l - 1 >= 0 && a[l - 1] > mx) flag = true;
else if (r + 1 < n && a[r + 1] > mx) flag = true;
if (len < k && !flag) return false;
int need = len % k;
res += need * y;
len -= need;
if(len==0) return true;
if (y * k >= x)
{
res += len / k * x;
}
else if(flag)
{
res += len * y;
}
else
{
res += (len - k) * y + x;
}
return true;
}
int main()
{
scanf("%d %d", &n, &m);
scanf("%lld %lld %lld", &x, &k, &y);
for (int i = 0; i < n; ++i) scanf("%d", a + i);
for (int i = 0; i < m; ++i) scanf("%d", b + i);
int lst = -1, posa = 0, posb = 0;
while (posb < m)
{
while(posa < n && a[posa] != b[posb]) ++posa;
if (posa == n)
{
puts("-1");
return 0;
}
if (!jud(lst + 1, posa - 1))
{
puts("-1");
return 0;
}
lst = posa;
++posb;
}
if (!jud(lst + 1, n - 1))
{
puts("-1");
return 0;
}
printf("%lldn", res);
return 0;
}