Codeforces Round 891 (Div. 3)补题
Array Coloring(Problem - A - Codeforces)
题目大意:给定一个数组a[],我们将其划分为两堆,要求两堆和的奇偶性相同,问是否可以划分。
思路:很显然只有奇数+偶数=奇数,很显然偶数可以随便分,那么我们只需要统计奇数的个数,如果奇数的个数可以平均分进两堆,那么奇偶性就相同,否则就不同。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int x,j=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
if(x&1) j++;
}
if(j&1) printf("NO\n");
else printf("YES\n");
}
}
Maximum Rounding(Problem - B - Codeforces)
题目大意:给定一个有若干位的正整数,你需要选择其中的某些位进行四舍五入操作,问最后能得到的数最大是多少。
思路:很显然,我们在选的时候如果当前位是大于5的数,后面有能让它变成6的数,它变了对前一位的贡献也还是1,所以没什么区别,如果是9的话,进位变成0,前一位加1,和直接从这一位进位区别不大,所以我们只需要找到第一个可以进位的地方操作一下即可,对了,记得往前累计,另外边界值的处理什么的也要注意一下,不然没注意越界的话会有特殊字符输出,但是本地编译器可能看不到。
#include<bits/stdc++.h>
using namespace std;
char s[200010];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",s+1);
s[0]='0';
int len=strlen(s+1);
int i=1;
for(i=1;i<=len;i++)
if(s[i]>='5') break;
int d=i;
while(d<=len&&s[d]>='5')
{
s[d-1]++;
d -= 1;
}
if(d>len) d=len;
if(s[0]=='0')
{
for(i=1;i<=d;i++) printf("%c",s[i]);
for(i=d+1;i<=len;i++) printf("0");
printf("\n");
}
else
{
printf("1");
for(i=1;i<=len;i++) printf("0");
printf("\n");
}
}
}
Assembly via Minimums(Problem - C - Codeforces)
题目大意:有一个a[],我们任取两位求最小值(每次取得两位视为一组,组与组之间不同),最后得到一个数组b[],先给出数组b[],要求一个可能的数组a[].
思路:我们可以统计出b[]中每个数的个数,显然对于数值较大的我们应该先填,因为后面小的还可以用它们,在填的时候,首先要把这个数填进去,用cnt记录现在让它成为最小值的有几对,同时用另一个数组记录一下,当前已经填了多少对了。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int l=n*(n-1)/2;
map<int,int>mp;
for(int i=1;i<=l;i++)
{
int x;
scanf("%d",&x);
mp[x]++;
}
vector<pair<int,int>>p;
for(auto it:mp)
{
p.push_back({it.first,it.second});
}
sort(p.begin(),p.end());
reverse(p.begin(),p.end());
vector<int>q;
int c=0;
for(auto it:p)
{
int v=it.first;
int d=it.second;
q.push_back(v);
int cnt=c;
c++;
while(cnt<d)
{
q.push_back(v);
cnt +=c;
c++;
}
}
for(auto it:q) cout<<it<<" ";
cout<<endl;
}
}
Strong Vertices(Problem - D - Codeforces)
题目大意:现有两个数组a[]和b[],我们由此构建一张有向图,如果au-av>=bu-bv,那么u到v有一条有向边,如果一个点到其他点都有边,那么称这个点为强项点,问有多少个这样的点,并且按照下标输出这些点。
思路:现在虽然原不等式的左右两边都是在同一个数组中的,但是这样看显然还是不方便的,我们交换一下变成au-bu>=av-bv,那么就很好找了,如果一个u,它的au-bu的值大于等于其他任何点,那么它到其他任何点之间都有边,那么我们直接统计一下ai-bi的值就好。
#include<bits/stdc++.h>
using namespace std;
int a[200010],b[200010],c[200010];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
int mx=-2e9-10;
for(int i=1;i<=n;i++) c[i]=a[i]-b[i],mx=max(mx,c[i]);
vector<int>p;
for(int i=1;i<=n;i++)
{
if(mx==c[i]) p.push_back(i);
}
cout<<p.size()<<endl;
for(auto it:p) cout<<it<<" ";
cout<<endl;
}
}
Power of Points(Problem - E - Codeforces)
题目大意:现有一个n长数组a[],我们选定一个数s,s是a[]中的数,构造出n个区间[s,a[i]]或者[a[i],s],然后对于每个点,我们定义f[p]为p点处覆盖的线段的条数,计算对于每个s,f[1]+f[2]+...+f[1e9].
思路:很显然,一条线段对线段内部所有的点的贡献都是1,对总结果的贡献为(r-l+1),那么我们只要对于每一条线段计算出来这个值,然后累加即可。然后还有一个问题就是s的不同位置该怎么处理。这里显然要计算每个点到其他点的距离和,但是n的范围到2e5,显然直接暴力不合适。那么我们来找一下规律,显然这里如果排个序的话,区间更明显,我们排序后来看:
那么结果就很明显了,我们处理一个前缀和和一个后缀和即可,当然,也可以只处理一个前缀和。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200010],b[200010],sump[200010],sumb[200010];
signed main()
{
int t;
scanf("%lld",&t);
while(t--)
{
int n;
scanf("%lld",&n);
map<int,int>mp;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=a[i],mp[a[i]]++,sump[i]=sumb[i]=0;
sump[0]=0,sumb[n+1]=0;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) sump[i]=sump[i-1]+a[i];
for(int i=n;i>=1;i--) sumb[i]=sumb[i+1]+a[i];
map<int,int>d;
for(int i=1;i<=n;i++)
{
d[a[i]]=(2*i-n)*a[i]+n+sumb[i+1]-sump[i];
}
for(int i=1;i<=n;i++)
{
printf("%lld ",d[b[i]]);
}
printf("\n");
}
}
Sum and Product(Problem - F - Codeforces)
题目大意:给定一个数组a[]和若干组查询(x,y),我们要找出索引(i,j),使得a[i]+a[j]=x,a[i]*a[j]=y,问对于每个(x,y)有多少对符合要求的索引。
思路:这道题看上去没有办法可以解,但是注意到给定的这两个式子,和表示一元二次方程中两个未知数关系的式子长的很像,那么我们转变思路,相当于求解x^2-b*x+c=0的一元二次方程,直接用求根公式就好。不过要注意的地方是,这里的数据较大,sqrt开平方不方便,我们用二分来开平方,类似于对浮点数进行二分。但是也不太一样,这里我们并未将数值转化成浮点数,只是将r的数据设得比较大。
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int>c;
int sq(int a)
{
int l=0,r=5000000001;
while(r-l>1)
{
int mid=(l+r)/2;
if(mid*mid<a) l=mid;
else if(mid*mid>a) r=mid;
else return mid;
}
return l;
}
int find(int a,int b)
{
//x^2−bx+c=0
int d=a*a-4ll*b;
if(d<0) return 0;
int tmp=sq(d);
int x1=(a+tmp)/2ll;
int x2=(a-tmp)/2ll;
if(x1+x2!=a||x1*x2!=b) return 0;
if(x1==x2) return c[x1]*(c[x1]-1)/2;
else return c[x1]*c[x2];
}
signed main()
{
int t;
scanf("%lld",&t);
while(t--)
{
int n;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%lld",&x);
c[x]++;
}
int q;
scanf("%lld",&q);
while(q--)
{
int a,b;
scanf("%lld%lld",&a,&b);
cout<<find(a,b)<<endl;
}
c.clear();
}
}