CodeforcesRound791(Div2)

题目来源
https://codeforces.com/contest/1679

第一题

题意

有两种类型的车：两轴车，三轴车。一个轴能连接两个轮胎，题目给n个轮胎，计算最少可以组成多少辆车，最多可以组成多少辆车。如果给的n不能组成输出-1

思路

无论是两轴还是三轴车，由于每个轴只能连接2个轮胎，所以轮胎必然是偶数，奇数必然不满足要求。
首先将轮胎转换成轴数，即轴数=n/2。
对于最大值，我们尽量先组二轴车,剩下的轴数可能为0或者为1，如果为0则代表刚好可以全部组成2轴车，如果为1则可以拆一辆二轴车组成三轴车
对于最小值，我们尽量先组成三轴车，剩下的轴数可能为0,1,2，如果为0则刚好组成，为1则拆一辆三轴组成两辆二轴车，如果为2则自行组成一辆二轴车。
注：轮胎数小于等于4时要特殊考虑，当n等于4计算出来的结果恰好符合答案，所以不用单独考虑。当n小于4时也是无法组成任何一种车所以输出-1

代码

#include <iostream>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        if(n%2 !=0 || n< 4){
            cout<<-1<<endl;
        }else{
            long long minans = 0; 
            long long maxans = 0;
            n/=2;
            //轴数n;
            if(n%2 == 1){
                maxans = n/2-1+1;
            }else{
                maxans = n/2;
            }
            if(n%3 == 1){
                minans = n/3-1+2;
            }else if(n%3 == 2){
                minans = n/3+1;
            }else{
                minans = n/3;
            }
            cout<<minans<<" "<<maxans<<endl;
        }
    }
    return 0;
}

第二题

题意

给一个包含n个数的数组，对数组执行q次操作。
操作分为两种类型：

将数组中第i个元素改为x
将数组中所有元素改为x

每一次操作后输出数组的和。

思路

最暴力的方法是：

对于每一个操作都更新数组中的数(操作1是O(1)的操作2是O(N))
对数组求和(O(N))

一共有n次操作所以必然超时。
在此方法上对求和步骤进行优化：

保留上次操作的sum(和)。
对于操作1，新的sum只需要加上第_i位本次要修改的值减去_上次修改后的值。
对于操作2，新的sum是n*x。

优化更新操作：操作2更新整个数组的值必然会造成超时，所以我们优化一下只需要记录操作2执行了count次，保存整个数组要修改的值x，以及记录数组每个元素执行了多少次操作2。当操作1要查询上次修改后的值来更新sum时，先查询i元素执行了几次操作2和count进行比较，如果相等说明i元素已经进行了最新次的操作2那么该元素所存的值就是我们想要的值，因此直接按照操作1的求和来更新sum，如果不相等说明i元素未进行最新次的操作2，那么它上次操作后的值为最新次操作2所修改的值x，用x按照操作1的求和更新sum。整个操作1结束后更新 i位的值。
优化后为O(N)

代码

#include <iostream>
#include <map>
using namespace std;
const int N = 200005;
long long nums[N];
map<int ,int> m;
long long now_cnt;
long long now[N];

int main(){
    int n,q;
    cin>>n>>q;
    long long sum = 0;
    for(int i = 1; i<= n;i++){
        cin>>nums[i];
        sum+=nums[i];
    }
    
    for(int i = 0;i<q;i++){
        
        long long a,b,c;
        cin>>a;
        if(a == 1){
            cin>>b>>c;
            if(now_cnt == m[b]){
                sum+=c-nums[b];
            }else{
                sum+=c-now[now_cnt];
            }
            nums[b] = c;
            m[b] = now_cnt;
        }else{
            cin>>b;
            now_cnt++;
            now[now_cnt] = b;
            sum = n*b;
        }
        cout<<sum<<endl;
    }
    
    return 0;
}

第一题

题意

思路

代码

第二题

题意

思路

代码

第三题

题意

思路

代码

第四题

题意

思路

代码

第五题

题意

思路

代码

第六题

题意

思路

代码