Codeforces Round 905 (Div
Codeforces Round 905 (Div. 3)
A. Morning
此题将其看为光标一直移动，其中移动次数就是坐标之差的绝对值，0看做10，由于其显示也需一次操作，所以加上四。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int arr[4],count=0;
char k;
for(int i=0;i<4;i++)
{
cin>>k;
arr[i]=k-'0';
if(arr[i]==0)
{
arr[i]=10;
}
}
count=abs(arr[0]-1)+abs(arr[1]-arr[0])+abs(arr[2]-arr[1])+abs(arr[3]-arr[2])+4;
cout<<count<<endl;
}
return 0;
}
B. Chemistry
这道题读题出问题了，在删除后会重新排列这点没有读到，并且在测样例6打印了YES，当时一直想为什么不是NO，原来是会重新排列。所以这道题排列后就比较简单了，然后就统计字母出现次数为奇数的情况，分最后是奇数还是偶数就行。
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
string s;
cin>>s;
int arr[26]={0};
for(int i=0;i<n;i++)
{
arr[s[i]-'a']++;
}
int count=0;
for(int i=0;i<26;i++)
{
if(arr[i]%2==1)
{
count++;
}
}
if((n-k)%2==0)
{
if((k-count)%2==0&&k>=count)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
else
{
if(k-count==1||n-k==1)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
}
C. Raspberries
注意到k的范围在2—5之间，那么只用分情况讨论即可，其中只有4需要讨论数组元素偶数个数（当k==4时num取最大也就2），其余情况要是有元素被k整除则直接为0，要是没有则需穷举每个元素被整除时增加了多少，取最小即可。
#include<iostream>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
int arr[n];
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
int num=9;
if(n!=1)
{
if(k!=4)
{
for(int i=0;i<n;i++)
{
if(arr[i]%k==0)
{
num=0;
break;
}
else
{
num=min(num,(k-arr[i]%k));
}
}
}
else
{
int cnt=0,count=9,p;
for(int i=0;i<n;i++)
{
if(arr[i]%4==0)
{
num=0;
cnt=2;
count=0;
break;
}
if(arr[i]%2==0)
{
cnt++;
}
if(arr[i]%4==3)
{
count=1;
}
}
num=max(0,2-cnt);
num=min(num,count);
}
}
else
{
if(arr[0]%k==0)
{
num=0;
}
else
{
num=k-arr[0]%k;
}
}
printf("%d\n",num);
}
return 0;
}
D. In Love
这道题就是考察multiset的用法（刚学了set相关用法就写。。。题目直接写了multiset，大抵是暗示我吧，样例中也有多次添加同一段的），定义一个左端点，右端点的集合就行，最后只需判断右端点最小值是否小于左端点最大值，左端点multiset中的元素是按照从小到大的顺序排列的，其中的最大值就是最右侧的线段的右端点。同样，右端点multiset中的最小值就是最左侧的线段的左端点，当右端点multiset R中的最小值小于左端点multiset L中的最大值时，意味着存在一个右端点小于左端点的情况。找那个multiset的最大值最开始用的end一直不对，后面才查了end指向最后一个的下一个位置，用rbegin就行另外rend指向第一个元素的前一个（逆向迭代器）。
#include<bits/stdc++.h>
using namespace std;
multiset<int> L, R;
int main()
{
int t;
scanf("%d",&t);
char k;
int l, r;
while(t--)
{
cin>>k>>l>>r;
if(k == '+') L.insert(l), R.insert(r);
else L.erase(L.find(l)), R.erase(R.find(r));
if(L.size()!=0&& *R.begin() < *L.rbegin())
printf("YES\n");
else printf("NO\n");
}
return 0;
}
E. Look Back
这个题就是因为不能让他爆数据所以不能一直遍历使其一直增加，用一个cnt来记录上一个数被乘的次数然后后面再进行比较的时候只需让后一个数乘以2大于前一个数记录进行的次数加上cnt就是总共进行的次数，然后要是这个数比前一个数大那么久也可能要乘也可能不乘，就让它除以2和这个cnt！=0来判断最后加上就行。（再也不用cin和cout了，每次都会超时）
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
vector<long long> a(n);
for(int i = 0; i < n; i ++ )
scanf("%lld",&a[i]);
long long cnt = 0, sum = 0;
for(int i = 1; i < n; i ++ )
{
int x = a[i];
if(x < a[i - 1]) {
while(x < a[i - 1]) x *= 2, cnt ++;
}
else {
while(x >= a[i - 1] * 2 && cnt!=0) x /= 2, cnt --;
}
sum += cnt;
}
printf("%lld\n",sum);
}
F. You Are So Beautiful
题意就是对于每个子序列(l,r),无法从a中按另一种顺序挑出r-l+1个数(可以不连续)构成这个子序列。一开始以为必须连续样例4怎么算都是8(，那么对于一段序列(l,r)合法,必须满足l左边没有al,ar右边没有ar所以对于一个序列al .... ar，只需要满足它的左端点al没在之前出现过，ar没在之后出现过即可。