“传智杯”初赛总结

题目及解答

题目一

原做法：用数组存放数字出现个数，再输出个数为奇数的值。
更好的做法：使用^=对输入数据逐个处理。使偶数个数的值两两异或消除，剩余一个奇数个数的值，将其输出。

该题的输入不定长，可使用fgets函数或者cin读取，存储类型可为char也可为int。
在判断输入的长度时，使用strlen(a)获取数组长度，使用a.length()获取字符串长度。

#include<stdio.h>
#include<string.h>
int main()
{
    char buff[128]="";
    fgets(buff,sizeof(buff),stdin);
    int ret=0;
    for(int i=0;i<strlen(buff)-1;i++)
        ret^=buff[i];
    printf("%c\n",ret);
} 

遇到奇偶时，应想到可以将相同的输入异或为零。初此之外，异或同样可以用于字母的大小写转换。

题目二

原作法：当输入数值大于4后，平方根一定小于自身的一半了，所以对输入除以2再穷举。错误。
更好的做法：二分法或牛顿迭代法。
二分法：

#include<iostream>
using namespace std;
int main()
{
    int x;
    cin>>x;
    int right=x;
    int left=0;
    int mid=(left+right)/2;
    while(1)
    {
        if(mid*mid<=x&&(mid+1)*(mid+1)>x)
            break;
        else if(mid*mid<x)
            left=mid;
        else
            right=mid; 
            
        mid=(left+right)/2;
    }
    cout<<mid<<endl;
}

牛顿迭代法:

#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
    double x;
    cin>>x;
    double cur=x;
    double last=0;
    while(cur-last>=1||cur-last<=-1)
    {
        last=cur;
        cur=(cur*cur+x)/(2*cur);
    }
    printf("%d\n",(int)cur);
}

使用cur=(cur * cur+x)/(2 * cur)进行收敛，cur-last的绝对值小于等于精度值1时停止循环，由于cur值随着收敛逐渐减少，所以不用考虑cur*cur大于输入数值的情况。

题目三

原思路：若输入字符串镜面对称，则yes，否则no。没有考虑完情况。错误。
更好的思路：使用栈对左括号进行存放，若遇到右括号则将对应左括号出栈，若无法对应则no。

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main()
{
    string x;
    stack<char> s;
    cin>>x;
    for(int i=0;i<x.length();i++)
    {
        if(x[i]=='('||x[i]=='{'||x[i]=='[')
            s.push(x[i]);
        else
        {
            if(s.empty()||
               s.top()=='('&&x[i]!=')'||
               s.top()=='{'&&x[i]!='}'||
               s.top()=='['&&x[i]!=']')
            {
                cout<<"no"<<endl;
                return 0;
            }
            else
                s.pop();
        }
    }
    if(!s.empty())    //检查栈是否清空
        cout<<"no"<<endl;
    else
        cout<<"yes"<<endl;
}

题目四、五思路同解答，略。

总结

做题应细致，先考虑清楚特例，构思好框架再写。不会很正常，慢慢做别急。