Codeforces Round 905 (Div. 3)
A. Morning
题意：操作：显示，向前走都为一次操作；目标：显示这四个数
思路：0->10，然后依次作差就行
#include <bits/stdc++.h>
using namespace std;
void solve(){
char a[4];
int mi=100,sum=4,b[4];
for(int i=0;i<4;i++){
cin>>a[i];
b[i]=a[i]-'0';
if(b[i]==0) b[i]=10;
}
sum+=b[0]-1;
for(int i=1;i<4;i++){
sum+=abs(b[i]-b[i-1]);
}
cout<<sum<<"\n";
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
B. Chemistry
题意：操作：删除一个数；目标：让该字符串变成一个回文字符串
！！！操作之后可以随意更改顺序看题不要只看一半不然会被卡
思路：一共26个字母统计出现次数，只要是偶数就可以当成回文串
#include <bits/stdc++.h>
using namespace std;
int num[27];
void solve(){
memset(num,0,sizeof(num));
int n,k;
cin>>n>>k;
int res=0;
for(int i=0;i<n;i++){
char a;
cin>>a;
int x=a-'a';
num[x]++;
}
for(int i=0;i<26;i++){
if(num[i]%2!=0) res++;
}
if(res-k>1) cout<<"NO"<<"\n";
else{
cout<<"YES"<<"\n";
}
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
C. Raspberries
题意：操作：给其中一个数+1；目标：使所有数的乘积可以被k整除
思路：k=2,3,4,5，其中3个质数为一类，4为一类
1.只要数列中有一个数的因子为k那么就能整除，不能的话就算他的mod最大的
2.如果有其中一个数+1刚好为4的倍数(特殊情况)/其中有一个数为2的倍数不为4的倍数得1，或者有两个数为2的倍数则可以直接得0，最多只需加两次，即将两个奇数分别+1然后变为偶数可直接除4.
#include <iostream>
using namespace std;
const int MAX=1e5+10;
#define int long long
int arr[MAX];
void solve() {
int n, k;
cin >> n >> k;
if (k == 4) {
int res = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
bool x=false;
for(int i=0;i<n;i++){
if((arr[i]+1)%4==0){
x=true;
}while(arr[i]%2==0){
res++;
arr[i]/=2;
if(res==2){
cout<<"0\n";
return ;
}
}
}
if(x||res==1) cout<<"1\n";
else cout<<"2\n";
} else {
int ma = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}for(int i=0;i<n;i++){
if (arr[i] % k == 0) {
cout<<"0\n";
return ;
}
ma = max(ma, arr[i] % k);
}
cout << k - ma << endl;
}
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D. In Love
题意：操作：增加或者减少一条边；结果：是否存在不重合的边
思路：只需要判断有边的右端点小于他的左端点
#include <bits/stdc++.h>
using namespace std;
map<int,int> l;
map<int,int> r;
void solve(){
char a;
int b,c;
cin>>a>>b>>c;
if(a=='+'){
l[b]++;
r[c]++;
}else{
auto x=l.find(b);
x->second--;
if(x->second==0) l.erase(x);
auto h=r.find(c);
h->second--;
if(h->second==0) r.erase(h);
}if(l.empty()||l.rbegin()->first<=r.begin()->first)
{
cout<<"No\n";
}else cout<<"Yes\n";
}
int main()
{
int t;
cin>>t;
while(t--){ solve(); }
return 0;
}
E. Look Back
题意：操作ai=ai*2；结果：整个数组为递增数组
思路：首先排除暴力，必爆long long，所以可以拿一个变量来记录前一个乘了几个2
#include <iostream>
using namespace std;
#define int long long
void solve(){
int n,res=0,a=0,b=0,num=0;
cin>>n>>a;
for(int i=1;i<n;i++) {
cin >> b;
if (b > a) {
int a2 = a;
while (a2 <= b && a2 != 0) {
a2 <<= 1;
num--;
}
num++;
num = num > 0 ? num : 0;
res += num;
a = b;
continue;
} else if (a == b) {
res += num;
continue;
} else {
int b2 = b;
while (b2 < a) {
num++;
b2*=2;
}
res += num;
a = b;
}
}
cout<<res<<endl;
}
signed main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
F. You Are So Beautiful
题意：有多少个子数组让数组中只有一个子序列和他相等
坑货，没注意是子序列，直接给我卡爆了
注意：子序列是不连续的，子数组是连续的
思路：只需要保证子数组的左端点是第一次出现在数组中，右端点是最后一次出现在数组中
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+10;
int a[MAX];
void solve(){
int n;
cin>>n;
map<int,int> mp;
for(int i=0;i<n;i++){
cin>>a[i];
mp[a[i]]=i;
}
long long int res=0,pre=0;
set<int> num;
for(int i=0;i<n;i++){
if(num.count(a[i])==0){
pre++;
num.insert(a[i]);
}if(mp[a[i]]==i){
res+=pre;
}
}
cout<<res<<endl;
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
G1. Dances (Easy version)
题意：操作：删除a[i]，b[i]；要求：a[i]<b[i]
思路：排序，然后删除，双指针
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+10;
int a[MAX],b[MAX];
void solve(){
int n,m;
cin>>n>>m;
a[0]=1;
for(int i=1;i<n;i++){
cin>>a[i];
}for(int i=0;i<n;i++){
cin>>b[i];
}
sort(a,a+n);
sort(b,b+n);
int ia=0,res=0;
for(int ib=0;ib<n;ib++){
if(a[ia]>=b[ib]){
res++;
}else{
ia++;
}
}
cout<<res<<"\n";
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}