Codeforces Round #317 (div 2)
分类:
IT文章
•
2023-10-26 14:44:37
Problem A Arrays
思路:水一水。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+5;
4 int n1,n2,k,m,a[N],b[N];
5 int main()
6 {
7 scanf("%d%d",&n1,&n2);
8 scanf("%d%d",&k,&m);
9 for(int i=1;i<=n1;i++) scanf("%d",&a[i]);
10 for(int i=1;i<=n2;i++) scanf("%d",&b[i]);
11 if(a[k]<b[n2-m+1]) puts("YES");
12 else puts("NO");
13 return 0;
14 }
View Code
Problem B Order Book
思路:刚开始想优先队列搞一搞一直WA,换了个暴力做法就过了。。。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+5;
4 int B[N],S[N];
5 int n,s,tot1,tot2;
6 int main()
7 {
8 scanf("%d%d",&n,&s);
9 for(int i=1;i<=n;i++)
10 {
11 char ss[3];
12 int p,sum;
13 scanf("%s%d%d",ss,&p,&sum);
14 if(ss[0]=='B') B[p]+=sum;
15 else S[p]+=sum;
16 }
17 int cnt=0;
18 vector<int> ans;
19 for(int i=0;i<=1e5 && cnt<s;i++)
20 {
21 if(!S[i]) continue;
22 ans.push_back(i);
23 cnt++;
24 }
25 sort(ans.rbegin(),ans.rend());
26 for(int i:ans) printf("S %d %d
",i,S[i]);
27 cnt=0;
28 for(int i=1e5;i>=0 && cnt<s;i--)
29 {
30 if(!B[i]) continue;
31 printf("B %d %d
",i,B[i]);
32 cnt++;
33 }
34 return 0;
35 }
View Code
Problem C Lengthening Sticks
题目大意:给你a,b,c,l 三个数 将a,b,c分别加上x,y,z,且 x+y+z<=l 问你,有多少种方案使a,b,c能构成三角形。
思路: 模拟的时候没做出来,思路有,写起来巨麻烦,赛后一小时才A掉。。。
我们先将 a 当做最长的边,枚举a的长度,然后往b,c里加的合法长度在 down 到 up之间,问题就变成了,将一个整数
划分成两个整数,划分之后的整数的范围有限制。 然后我找了一下规律,o(1) 算了贡献。 然后我们找两个长边一样的情
况有多少种,三边一样的情况有多少种,总的加起来就是答案。
ps:看了网上的做法,是算不合法的数量,简单多了。。。。
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 int a,b,c,l;
5 ll ans;
6 void work(int a,int b,int c)
7 {
8 int base=b+c;
9 for(int i=a;i<=a+l;i++)
10 {
11 int u=l-i+a;
12 if(base+u<=i || i<=b || i<=c) continue;
13 ll down=max(0,i+1-base);
14 ll up=min(u,2*(i-1)-base);
15 if(down>up) continue;
16 ans+=(down+1+up+1)*(up-down+1)/2;
17 long long now=i-b-1;
18 if(up>now)
19 {
20 long long x=max(down,now+1)-now;
21 long long y=up-now;
22 ans-=(x+y)*(y-x+1)/2;
23 }
24 now=i-c-1;
25 if(up>now)
26 {
27 long long x=max(down,now+1)-now;
28 long long y=up-now;
29 ans-=(x+y)*(y-x+1)/2;
30 }
31 }
32 int sum=a+b;
33 int mx=max(a,b);
34 for(int i=mx;2*i<=l+sum;i++)
35 {
36 int res=l-(2*i-sum);
37 int up=min(i-1,c+res);
38 int down=max(1,c);
39 if(down>up) continue;
40 ans+=up-down+1;
41 }
42 }
43 int main()
44 {
45 cin>>a>>b>>c>>l;
46 int mn=min(a,min(b,c));
47 int mx=max(a,max(b,c));
48 work(a,b,c); work(b,c,a); work(c,a,b);
49 int sum=a+b+c;
50 for(int i=mx;i*3<=l+sum;i++) ans++;
51 printf("%lld
",ans);
52 return 0;
53 }
View Code