Codeforces Round 891 (Div. 3)
A. Array Coloring
这个我vp的时候写复杂了,想不到答案的思路这么清晰,将两部分分别看,将偶数加进去其奇偶性不变,只有奇数加进去才会改变奇偶性,so只有改变偶数次奇偶性才能使其奇偶性相同,所以cnt%2==0.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int cnt=0;
int n;
cin>>n;
int k;
for(int i=0;i<n;i++)
{
cin>>k;
if(k%2==1)
{
cnt++;
}
}
if(cnt%2==0)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}
B. Maximum Rounding
这个主要使其最大那么就从末尾开始进行操作,但是操作后需更新其操作的位置,因为输出时这个位置后面都为0(我就这个地方没注意),下面代码复杂了点,能过就行!(s1=“0”+s这步操作是为了方便下标,上次刷题刷到的(^-^)V)。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int k;
cin>>k;
while(k--)
{
string s,s1;
cin>>s;
s1='0'+s;
int l=s1.size();
int t;
int flag=0;
for(int i=l-1;i>=0;i--)
{
if((s1[i]>='5'&&s1[i]<='9')||s1[i]==':')
{
s1[i-1]++;
s1[i]='0';
t=l-i;
flag=1;
}
}
if(s1[0]!='0'&&flag)
{
for(int i=0;i<l-t;i++)
{
cout<<s1[i];
}
for(int i=0;i<t;i++)
cout<<"0";
}
else if(s1[0]=='0'&&flag)
{
for(int i=1;i<l-t;i++)
{
cout<<s1[i];
}
for(int i=0;i<t;i++)
cout<<"0";
}
else
{
cout<<s;
}
printf("\n");
}
return 0;
}
C. Assembly via Minimums
这个题没做出来确实可惜了,最开始一直关注最大值和最小值的,方向错了。根据a序列i和j来看,取min那么其实amin出现了n-1次,第二小的出现了n-2次.....所以先循环读入数组,然后排序输出的时候引入一个变量控制下标即可使其输出指定位置的数,不过题解直接给了i+=--n更加方便。
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long t;
scanf("%lld",&t);
while(t--)
{
long long n;
scanf("%lld",&n);
long long m=n*(n-1)/2;
long long b[m];
for(long long i=0;i<m;i++)
{
scanf("%lld",&b[i]);
}
sort(b,b+m);
long long k=n;
for(long long i=0;k!=1;i+=k)
{
printf("%lld ",b[i]);
k--;
}
printf("1000000000\n");
}
return 0;
}
D. Strong Vertices
这个题比上个更简单,av-au>=bv-bu》》av-bv>=bv-bu来个新数组crr即可,然后根据题意要找到strong节点(题目一直没看懂英语差生+shi翻译真的ex)要找都能到达的点就是那个点比其他都大,就是crr里的最大值及其个数统计出来输出即可。(数据给个±1e9之内我就只给min赋值-1e9-1了,直接忽略了两个数据还要相减,算了我就csdn了INT_MIN)
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
int maxx = INT_MIN;
int arr[n], brr[n], crr[n];
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
for (int i = 0; i < n; i++)
{
scanf("%d", &brr[i]);
crr[i] = arr[i] - brr[i];
maxx = max(maxx, crr[i]);
}
int cnt = 0;
vector<int>w;
for (int i = 0; i < n; i++)
{
if (crr[i] == maxx)
{
w.push_back(i + 1);
cnt++;
}
}
printf("%d\n", cnt);
for (int i = 0; i < w.size(); i++)
{
printf("%d ", w[i]);
}
printf("\n");
}
return 0;
}
E. Power of Points
题意大概就是比如s=2,然后[2,6]然后算里面包含的点的个数就行,其中s为ai,另一个端点是aj。
其实这个思路很简单,假设a[n]排序后为b[n]找到a0与b[n]对应的元素进行前缀和就行,但是就是在b数组中找到ai时要进行二次循环,所以我就这样写的过不了,题解的做法实在是妙!但是这个pair是第一次见(应该就是一个结构体吧)还有最后那个1ll强制转化(不过我选择全部开long long)和三目运算符实在是长知识了,这个x[i].second实在是妙!!!就是因为这个下标问题,一直不知道用什么,maybe用Unorderde_map也行。(跟题解相似度99%,没办法了喵~)
#include<bits/stdc++.h>
using namespace std;
const long long N=200005;
pair<long long,long long>x[N];
long long a[N];
int main()
{
long long t;
cin>>t;
while(t--)
{
long long n;
cin>>n;
long long s1=0,s2=0;
for(long long i=1;i<=n;i++)
{
cin>>x[i].first;
x[i].second=i;
s2+=x[i].first;
}
sort(x+1,x+n+1);
for(long long i=1;i<=n;i++)
{
s2-=x[i].first;
s1+=x[i].first;
a[x[i].second]=n+x[i].first*(2*i-n)-s1+s2;
}
for(long long i=1;i<=n;i++)
cout<<a[i]<<" \n"[i==n];
}
}
F. Sum and Product
这个题读完题后我就构造了一元二次方程解出了x1x2于是这个题就变成了从a中搜索x1x2的个数,其相乘就是结果(排列组合),然后我最开始一直想这个x1,和x2的先后顺序对答案的影响,实际没有影响,因为就是两个式子都是对称的虽然i<j,用的时候倒换一下不就好了。。。。。实在不知道脑子在干啥。(似乎题解写了二分查找,不过我这样也过了)
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long t;
cin>>t;
while(t--)
{
long long n;
cin>>n;
map<long long,long long>a;
long long p;
for(long long i=0;i<n;i++)
{
scanf("%lld",&p);
a[p]++;
}
long long q;
cin>>q;
long long arr[q];
long long x,y;
for(long long i=0;i<q;i++)
{
scanf("%lld%lld",&x,&y);
if((x*x-4*y)<0) arr[i]=0;
else if((x*x-4*y)==0) arr[i]=a[x/2]*(a[x/2]-1)/2;
else
{
long long delta=sqrt(x*x-4*y);
long long a1=(x-delta)/2,a2=(x+delta)/2;
if(a1+a2==x&&a1*a2==y) arr[i]=a[a1]*a[a2];
else arr[i]=0;
}
}
for(long long i=0;i<q;i++)
{
cout<<arr[i]<<" \n"[i==q-1];
}
}
return 0;
}
标签:891,int,s1,Codeforces,long,cin,--,include,Div3
From: https://www.cnblogs.com/godcy/p/17909168.html