第十七届中国计量大学程序设计竞赛（同步赛）-部分题解（B,C,F,H,I,K）

缺乏、安全感 2022-12-10 14:40 157阅读 0赞

# 第十七届中国计量大学程序设计竞赛（同步赛）-部分题解（B,C,F,H,I,K） #

[**比赛地址**][Link 1]

## B：Broken Pad ##

#### 题意 ####

多组输入，每次输入t组数据；每组数据给定两个字符串，分别为操作串和目标串。共有两种操作方法：

1.  对于任意位置选择当前位置的纸牌进行翻转，由于按钮坏了，于是包括当前位置以及它后面的所有纸牌都会翻转。
2.  可以选择空白区域（注意：题目有点难懂，并不是字符串中的0，而是理解为空白区域）进行操作，使得操作串所有的字符都变成0.

现需要求：最少操作次数，使得操作串等于目标串。

#### 题意 ####

分析两种操作，可以考虑两种情况：

1.  直接不考虑将所有的字符都转成0，而是只进行操作一，计算出需要的操作次数，并将操作情况存到一动态数组中。
2.  首先将操作串初始化为0（即：进行操作二），然后进行操作一，计算出需要的操作次数，并将操作情况存到另一个动态数组中。  
    从这两种情况取最优情况即可。

#### AC代码（cpp） ####

## C：Cook Steak ##

#### 题意 ####

多组输入，每组输入数据给定一整数n，表示n个步骤。接着给定每个步骤需要的温度区间。求最少需要多少分钟使得牛排烤成功。

#### 题解 ####

**有个坑点：步骤不能排序，而是按照它给定的顺序进行操作。**  
首先对于第一个操作，当然是将温度调到最小的温度为最优，记录当前温度  
然后遍历第2~第n个操作，分别计算上一温度与当前操作最小温度以及最大温度的差值，从中选择差值小的，将温度调到对应差值小的温度，然后更新当前温度，方便下一操作判断。

具体见代码。

#### AC代码（cpp） ####

#include<cstdio>
    #include<string>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=1e5+5;
    const int mod=1000000;
    struct node {
        
        ll x,y;
    };
    node a[maxn];
    int t,n;
    int main() {
        
        while(~scanf("%d",&t)) {
        
            while(t--) {
        
                scanf("%d",&n);
                memset(a,0,sizeof(a));
                for(int i=1; i<=n; i++) scanf("%lld%lld",&a[i].x,&a[i].y);
                ll ans=a[1].x+1;
                ll num=a[1].x;
                for(int i=2; i<=n; i++) {
        
                    if(num>=a[i].x&&num<=a[i].y){
        
                        ans++;continue;
                    }
                    if(abs(a[i].x-num)<=abs(a[i].y-num)) {
        
                        ans+=(abs(a[i].x-num)+1);
                        num=a[i].x;
                    } else {
        
                        ans+=(abs(a[i].y-num)+1);
                        num=a[i].y;
                    }
                }
                printf("%lld\n",ans);
            }
        }
        return 0;
    }

## F：Flag Scramble Competition ##

#### 题意 ####

直接计算题目描述中出现最多的字母，输出相应字母（不区分大小写）

#### 题解 ####

签到题，最终计算是e，于是直接输出e即可。

## H：Happy Time is Always Short ##

#### 题意 ####

多组输入，每组输入数据给定n个人的value值，然后有m个操作，每次操作给定l,r表示区间\[l,r\]，即区间\[l,r\]的人将离开，然后计算剩余人中value值最大的，并输出最大value值。

#### 题解 ####

很明显一道数据结构题：**区间修改&区间查询**。  
于是直接用线段树维护即可。

#### AC代码（cpp） ####

#include<cstdio>
    #include<vector>
    #include<map>
    #include<iostream>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    #define lowbit x x&(-x)
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    const int maxnode = (1e5+5)*4;
    int _max, op, qL, qR, v;
    
    struct IntervalTree {
        
        int maxv[maxnode], setv[maxnode];
    
        // 维护信息
        void maintain(int o, int L, int R) {
        
            int lc = o*2, rc = o*2+1;
            if(R > L) {
        
                maxv[o] = max(maxv[lc], maxv[rc]);
            }
            if(setv[o] >= 0) {
        
                maxv[o] = setv[o];
            }
        }
    
        // 标记传递
        void pushdown(int o) {
        
            int lc = o*2, rc = o*2+1;
            if(setv[o] >= 0) {
         //本结点有标记才传递。注意本题中set值非负，所以-1代表没有标记
                setv[lc] = setv[rc] = setv[o];
                setv[o] = -1; // 清除本结点标记
            }
        }
    
        void update(int o, int L, int R) {
        
            int lc = o*2, rc = o*2+1;
            if(qL <= L && qR >= R) {
         // 标记修改
                setv[o] = v;
            } else {
        
                pushdown(o);
                int M = L + (R-L)/2;
                if(qL <= M) update(lc, L, M);
                else maintain(lc, L, M);
                if(qR > M) update(rc, M+1, R);
                else maintain(rc, M+1, R);
            }
            maintain(o, L, R);
        }
    
        void query(int o, int L, int R) {
        
            if(setv[o] >= 0) {
         // 递归边界1：有set标记
                _max = max(_max, setv[o]);
            } else if(qL <= L && qR >= R) {
         // 递归边界2：边界区间
                _max = max(_max, maxv[o]);
            } else {
         // 递归统计
                int M = L + (R-L)/2;
                if(qL <= M) query(o*2, L, M);
                if(qR > M) query(o*2+1, M+1, R);
            }
        }
    };
    
    IntervalTree tree;
    
    int main() {
        
        int n, m,t;
        while(~scanf("%d",&t)) {
        
            while(t--) {
        
                scanf("%d%d",&n,&m);
                memset(&tree, 0, sizeof(tree));
                memset(tree.setv, -1, sizeof(tree.setv));
                scanf("%d",&v);
                tree.setv[1] = v;
                for(int i=2;i<=n;i++){
        
                    scanf("%d",&v);
                    qL=i;qR=i;
                    tree.update(1,1,n);
                }
                while(m--) {
        
                    scanf("%d%d",&qL, &qR);
                    v=0;
                    tree.update(1,1,n);
                    _max = -inf;
                    int l=qL,r=qR;
                    qL=1;qR=l-1;
                    tree.query(1, 1, n);
                    qL=r+1;qR=n;
                    tree.query(1,1,n);
                    printf("%d\n",_max);
                }
            }
        }
        return 0;
    }

## I：Isolated Pointset ##

#### 题意 ####

n个点，判断是否存在任意两点的中垂线必过其他的的一点。

#### 题解 ####

其实这题是：**祖冲之点集问题**，但是稍微猜一下也是能过的。

何为祖冲之点集：[**点我**][Link 2]

具体怎么构造呢，可以考虑正三角形某一顶点在圆心，然后其他正三角形都有一顶点在圆心（即：共顶点三角形），见下图：

![在这里插入图片描述][20200926181832722.png_pic_center]  
只要n>=3时，无论如何都能构造出符合条件的情况。

#### AC代码（cpp） ####

## K：Known-Well Palindrome Date-Easy Version ##

#### 题意 ####

多组数据，每组数据给定一字符串，求：字符串是否存在回文日期子串。

#### 题解 ####

1.  首先考虑子串问题：直接可以用一滑动窗口维护即可
2.  回文子串问题：直接遍历判断即可
3.  回文日期子串：复杂点在此。
    
     *  首先考虑日期在0001.01.01~9999.12.31之间；
     *  然后考虑闰年情况，以及含31号和不含31号的月份情况
     *  看似可以了，但是并没有考虑月份或日期为0的情况（这里我就wa了一发）

解决上述问题后，题目就简单了

#### AC代码（cpp） ####

#include<cstdio>
    #include<vector>
    #include<map>
    #include<iostream>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    #define lowbit x x&(-x)
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    char s[maxn];
    char window[maxn];
    int checkRui(int year){
        
        if(year%4==0||(year%400!=0&&year%100==0)) return 1;
        return 0;
    }
    int checkday(int year,int month,int day){
        
        if(day==0||year==0||month==0) return 0;
        if(checkRui(year)&&month==2&&day>29) return 0;
        if(!checkRui(year)&&month==2&&day>28) return 0;
        if((month==1||month==3||month==5||month==7||month==8||month==10||month==12)&&day>31) return 0;
        if((month==4||month==6||month==9||month==11)&&day>30) return 0;
        return 1;
    }
    int check(int l,int r){
        
        for(int i=l;i<=r;i++){
        
            if(window[i]==' ') return 0;
        }
        for(int i=l;i<=l+3;i++){
        
            if(window[i]==window[r-i+l]) continue;
            else return 0;
        }
        int num=0;
        for(int i=l;i<=r;i++){
        
            num=num*10+(window[i]-'0');
        }
        if(!(num>=10101&&num<=99991231)) return 0;
        int year=(window[l]-'0')*1000+(window[l+1]-'0')*100+(window[l+2]-'0')*10+(window[l+3]-'0');
        int month=(window[l+4]-'0')*10+(window[l+5]-'0');
        if(month>12) return 0;
        int day=(window[l+6]-'0')*10+(window[l+7]-'0');
        if(!checkday(year,month,day)) return 0;
        return 1;
    }
    int main(){
        
        while(gets(s+1)){
        
            if(strcmp(s+1,"#")==0) break;
            int len=strlen(s+1);
            int ans=0;
            for(int i=1;i<=8;i++) window[i]=s[i];
            int l=1,r=8;
            //for(int i=l;i<=r;i++) cout<<window[i];
            //cout<<endl;
            if(check(l,r)){
        
                ans++;
            }
            for(int i=9;i<=len;i++){
        
                l++;r++;
                window[r]=s[i];
                //for(int i=l;i<=r;i++) cout<<window[i];
                //cout<<endl;
                //if(strcmp(window+l,"20200202")==0) cout<<window+l<<endl;
                //for(int i=l;i<=r;i++) cout<<window[i];
                //cout<<endl;
                if(check(l,r)) ans++;
            }
            printf("%d\n",ans);
        }
        return 0;
    }

其他题没看…

[Link 1]: https://ac.nowcoder.com/acm/contest/7591#question
[Link 2]: https://zhidao.baidu.com/question/439624288142014004.html
[20200926181832722.png_pic_center]: /images/20221123/7caaad26eba149b0aae89fa3914f2e88.png