首页 > 代码库 > Codeforces Round #424 (Div. 2) C. Jury Marks(乱搞)

Codeforces Round #424 (Div. 2) C. Jury Marks(乱搞)

2024-10-26 07:00:02   209人阅读

题目链接：Codeforces Round #424 (Div. 2) C. Jury Marks

题意：

给你一个有n个数序列，现在让你确定一个x，使得x通过挨着加这个序列的每一个数能出现所有给出的k个数。

问合法的x有多少个。题目保证这k个数完全不同。

题解：

显然，要将这n个数求一下前缀和，并且排一下序，这样，能出现的数就可以表示为x+a,x+b,x+c了。

这里 x+a,x+b,x+c是递增的。这里我把这个序列叫做A序列

然后对于给出的k个数，我们也排一下序，这里我把它叫做B序列，如果我们确定了A序列的第一个数，那么就可以确定一个x，然后用二分来判断这个x能不能使得B序列中每个数出现，如果能，就把这个x放进容器。

然后就可以枚举每个A序列的数作为开头。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const int N=2007;
 6 int n,k,a[N],b[N];
 7 set<int>st;
 8 
 9 int main(){
10     scanf("%d%d",&n,&k);
11     F(i,1,n)scanf("%d",a+i),a[i]+=a[i-1];
12     sort(a+1,a+1+n);
13     F(i,1,k)scanf("%d",b+i);
14     sort(b+1,b+1+k);
15     F(i,1,n)
16     {
17         int flag=1,x=b[1]-a[i];
18         F(j,1,k)
19         {
20             int tmp=b[j]-x;
21             int idx=lower_bound(a+i,a+n+1,tmp)-a;
22             if(idx>n||a[idx]!=tmp ){flag=0;break;}
23         }
24         if(flag)st.insert(a[i]);
25     }
26     printf("%d\n",(int)st.size());
27     return 0;
28 }
View Code

 

Codeforces Round #424 (Div. 2) C. Jury Marks(乱搞)


联系
我们