【CF Div. 1 + Div. 2】A. Divide and Multiply、B. William the Vigilant

A. Divide and Multiply

传送门

题意：
给一个数组，对于一个偶数可以任意的另一个数可以进行操作：偶数/2，另一个数x2。

题解：
有个我认为最清晰的想法：暂且只做/2的操作，并统计次数。然后找到剩下的数组中的最大值，进行x2操作就好！

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000;
#define ll long long
#define sc scanf
#define pr printf
ll a[maxn];
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        int now=0;
        for(int i=0;i<n;i++){
            sc("%lld",&a[i]);
            while(a[i]%2==0){a[i]/=2;now++;}
        }
        sort(a,a+n);
        while(now--)a[n-1]*=2;
        ll sum=0;
        for(int i=0;i<n;i++){
            sum+=a[i];
        }
        cout<<sum<<endl;
    }
    return 0;
}

B. William the Vigilant

题意：
一个字符串，只有a，b，c三个字母。求最小修改数，使得这个字符串没有“abc”的子字符串。
q操作，每次修改一个字符，求每一次新的最小修改数。

题解：
个人认为这题比A好想。因为有一条很明显的思路：求原字符串的最小修改数很简单，凡是有连续的abc，修改任意一个即可。遍历一遍即可求出。但要是每一次操作后都这样处理必然会爆掉。那我们就可以想，修改一个字符，顶多是多生成一个abc字符串，或者破坏掉一个字符串，或无影响。
多生成一个字符串，修改数+1。
破坏掉一个字符串，修改数-1。
并且它们也有可能同时发生，只需要if语句就够了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define sc scanf
#define pr printf
int main()
{
    int n,q;cin>>n>>q;
    string s;cin>>s;
    int x;char c;
    int sum=0;
    for(int i=0;i<n-2;i++){
        if(s[i]=='a'&&s[i+1]=='b'&&s[i+2]=='c'){
            sum++;
        }
    }
    while(q--){ 
        sc("%d %c",&x,&c);
        x--;
        if(s[x]==c){ s[x]=c;pr("%d\n",sum);continue;}
        if(c=='a'){
            if(x+1<n&&x+2<n&&s[x+1]=='b'&&s[x+2]=='c')sum++;
            if(x-1>=0&&x-2>=0&&s[x-2]=='a'&&s[x-1]=='b'&&s[x]=='c')sum--;
            if(x-1>=0&&x+1<n&&s[x-1]=='a'&&s[x]=='b'&&s[x+1]=='c')sum--;
        }
        else if(c=='b'){
            if(x-1>=0&&x+1<n&&s[x-1]=='a'&&s[x+1]=='c')sum++;
            if(x-1>=0&&x-2>=0&&s[x-2]=='a'&&s[x-1]=='b'&&s[x]=='c')sum--;
            if(x+1<n&&x+2<n&&s[x]=='a'&&s[x+1]=='b'&&s[x+2]=='c')sum--;
        }
        else {
            if(x-1>=0&&x-2>=0&&s[x-2]=='a'&&s[x-1]=='b')sum++;
             if(x+1<n&&x+2<n&&s[x]=='a'&&s[x+1]=='b'&&s[x+2]=='c')sum--;
            if(x-1>=0&&x+1<n&&s[x-1]=='a'&&s[x]=='b'&&s[x+1]=='c')sum--;
        }
        s[x]=c;
       pr("%d\n",sum);
    }
    return 0;
}