Codeforces Round #373 (Div. 2)

题目链接

 

A题题解

• 题解：判断最后一天,若是0则UP,是15则DOWN. 若n是1且a[1]不是0或15则-1. 否则比较a[n]与a[n-1]即可.

AC代码

#include
      
       using namespace std;typedef long long ll;# define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)//struct note{//    int x ,y;//}st[300000 + 10];//set
       
         s1,s2; //ll a[300000 + 10][2];int a[100];int main(){    IOS;int n;cin >> n; for(int i = 1; i<= n ; i++){    cin >> a[i];    }if(n==1 && a[1] == 15){puts("DOWN"); return 0;}if(n==1 && a[1] == 0){puts("UP"); return 0;}if(n == 1) {    puts("-1");    return 0;}if(a[n] == 15 && a[n] > a[n-1]) {puts("DOWN");return 0;}if(a[n] == 0 && a[n-1] == 1) {    puts("UP");    return 0 ; }if(a[n] > a[n-1])puts("UP");elseputs("DOWN");    return 0; }
       
      

 

B题题解

• 题意：一个只含有r和b的字符串，两种操作，1 交换字符串中任意两个元素的位置，2 把r替换为b，或者把b替换为r，输出把字符串转换为交替的序列需要的最小操作数
• 思路：目标字符串只有两种情况，rbrbrbrb或者brbrbrbr，分别求出给定字符串向这两种字符串转换所需的操作次数，取最小即可，那么如何求转换所需的最小次数呢，遍历一遍即可，分别求出与目标字符串不同的r 和 b的个数，例如，给定字符串与目标字符串字符不相同的位置上r有6个，b有4个，那么可以交换操作4次，修改操作2次，共6次

AC代码

#include
      
       using namespace std;typedef long long ll;# define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)//struct note{//    int x ,y;//}st[300000 + 10];//set
       
         s1,s2; //ll a[300000 + 10][2];string a;int main(){    IOS;int n;cin >> n;cin >> a;int x = 0 , y = 0;for(int i = 0 ; i < a.size();i++){    if(i % 2 == 0){        if(a[i]!='r')        x ++;            }    else    {        if(a[i] != 'b')            y++;    }}int ans = 0;ans = abs(x - y) + min(x,y);x = y = 0;for(int i = 0 ; i < a.size();i++){    if(i % 2 != 0){        if(a[i]!='r')        x ++;            }    else    {        if(a[i] != 'b')            y++;    }}ans = min(ans , abs(x - y) + min(x,y));cout << ans << endl;    return 0; }
       
      

 

C题题解

• 题意：你有n次操作，可以让给定的这个数的小数位四舍五入，求这个数经过t次操作后最大是多少
• 题解：小数位如果第一个小数位是>=5的情况下，整数位的个位就要+1，如果整数位是999这种情况就要变成1000
• 为了使得经过变换后的数最大，我们先从小数位的最前面开始进位

AC代码

#include
      
       using namespace std;typedef long long ll;# define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)//struct note{//    ll x ,y;//}st[300000 + 10];//set
       
         s1,s2; //ll a[300000 + 10][2];string s;int main(){    int n,t;    scanf("%d%d",&n,&t);    cin>>s;    int i=0;    while(s[i]!='.')i++;    while(i
        
         <'5')i++;    if(i==n)    {        cout<
         <
          
           0)    {        if(s[i]!='.')s[i]++;        else{            i--;len=i;            while(i>=0&&s[i]=='9')s[i--]='0';            if(i==-1)cout<<'1';            else s[i]++;            break;        }        if(s[i]<'5')        {            len=i;            break;        }        else        {            len=i;            i--;        }        t--;    }    for(int k=0;k<=len;k++)        cout<
          
        
       
      

 

E题题解

• 题意：给出n个数字，有m个询问，每个询问：

 

• 1： 区间(l,r)内，每个数，增加c
• 2：区间(l,r)内，查询对应的f(x)之和（f（）指的是斐波那契数列）
• 分析：我们可以用过，矩阵快速幂来快速求出对应的斐波那契数，那么我们可以用线段树维护一个区间乘法矩阵。

AC代码

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include