CCF201312 小结

出现次数最多的数

除了用数组下标储存值（a[x]=count）外，还可以使用map容器。map的函数包括容器都有的begin()，end()，clear()，size()等，本题使用迭代器遍历map，找出最大值：

    int maxn=0,ans;
    for(map<int,int>::iterator it=m.begin();it!=m.end();it++){
        if(it->second>maxn){
            maxn=it->second;  //it->first,it->second分别表示关联中左侧的值和右侧的值
            ans=it->first;
        }
    }

ISBN号码

使用string读取输入再根据题意处理，做这道题的时候新建了一个数组用于储存正确的数字，但这个数组是多余的，只需要计算并修改输入的字符串就可以了。

最大的矩形

暴力，没有想到更佳的解决方法。遍历方式可以是长方形的宽，但更优的方式是遍历长方形的高。

有趣的数

1.读题应该仔细，做题时因为理解错题意浪费很多时间。
2.用动态规划解决问题时可以想国王开金矿的问题，画出状态关系的树，这样就很好理解了。本题通过推导条件可以得出开头数字一定是2等额外条件，在这基础上想到长度为n的数字可以理解为一个长度为n-1的数加一个数，从而寻找到其他状态，接着将得到的状态继续分解，找到边界状态，也就是一个只包含数字2的数字。（国王不能解决问题，就把金矿分成n-1和1，再将n-1个金矿的问题交给大臣，以此类推。）
这样自顶向下分析问题，再写程序由下向上得到答案。
虽然现在理解了做法，但是当时还是没做出。下次如果卡住了就想想国王和金矿，看能不能用动态规划求解。
代码：

#include<iostream>
#include<cstring>
using namespace std;
const long long mod=10^9+7;
long long dp[1005][6];
int main(){
    int n;cin>>n;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        dp[i][0]=1;
        dp[i][1]=(dp[i-1][1]+dp[i-1][0])%mod;
        dp[i][2]=(dp[i-1][0]+dp[i-1][2]*2)%mod;
        dp[i][3]=(dp[i-1][2]+dp[i-1][3]*2)%mod;
        dp[i][4]=(dp[i-1][4]*2+dp[i-1][1]+dp[i-1][2])%mod;
        dp[i][5]=(dp[i-1][5]*2+dp[i-1][3]+dp[i-1][4])%mod;
    } 
    cout<<dp[n][5];
} 

I'm stuck!

思路容易想出，但实现较难，主要原因是：
1.需要重复处理边界和方向判断，代码量较多
2.需要进行两次dfs，感觉有简化的实现方式，但不知道如何下手
3.做到这里耐心和专注度已经很少了，没法认真下来写好代码
后来参考标准答案写完代码，里面有很多可学习的地方：

#include<iostream>
#include<cstring>
using namespace std;
const int N=55;
struct _direct{   //用结构体处理方向 
    int dr,dc;
}direct[4]={{-1,0},{1,0},{0,-1},{0,1}};

char grid[N][N];
int vis1[N][N],vis2[N][N];

int R,C;

inline bool islegal(int r,int c){  //inline用于节约栈内存 
    return 0<=r&&r<R&&0<=c&&c<C&&!vis1[r][c]&&grid[r][c]!='#';
}

void dfs(int r,int c){
    vis1[r][c]=1;
    
    int nextr,nextc;
    if(grid[r][c]=='S'||grid[r][c]=='T'||grid[r][c]=='+'){
        for(int i=0;i<4;i++){      //*方向的处理方式 
            nextr=r+direct[i].dr;
            nextc=c+direct[i].dc;
            if(islegal(nextr,nextc))
                dfs(nextr,nextc);
        }
    }
    else if(grid[r][c]=='-'){
        for(int i=2;i<4;i++){
            nextr=r+direct[i].dr;
            nextc=c+direct[i].dc;
            if(islegal(nextr,nextc))
                dfs(nextr,nextc);
        } 
    }
    else if(grid[r][c]=='|'){
        for(int i=0;i<2;i++){
            nextr=r+direct[i].dr;
            nextc=c+direct[i].dc;
            if(islegal(nextr,nextc))
                dfs(nextr,nextc);
        } 
    }
    else if(grid[r][c]=='.')
        if(islegal(r+1,c))
            dfs(r+1,c);
}

int main(){
    int sr,sc,tr,tc;
    
    cin>>R>>C;
    for(int i=0;i<R;i++)
        cin>>grid[i];    //直接输入数组 
        
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++)
            if(grid[i][j]=='S')
                sr=i,sc=j;
            else if(grid[i][j]=='T')
                tr=i,tc=j;
                
    memset(vis1,0,sizeof(vis1));    //dfs中对vis1进行操作，所以这里要建立vis2储存vis1的信息 
    dfs(sr,sc);
    memcpy(vis2,vis1,sizeof(vis1));
    
    if(!vis1[tr][tc]) cout<<"I'm stuck!";
    else{
        int ans=0;
        for(int i=0;i<R;i++)
            for(int j=0;j<C;j++){
                if(vis2[i][j]){
                    memset(vis1,0,sizeof(vis1));
                    dfs(i,j);
                    if(!vis1[tr][tc])
                        ans++;
                }
            }
        cout<<ans;
    } 
}

总结

第一次做ccf，难度超过自己的能力，如果现在就去考的话应该分数不高。这五道题有很多可学习的点：
1.容器map的使用（m->first,m->second,iterator）
2.识别动态规划的方法：国王的金矿
3.创建结构体_direct处理方向的问题，创建islegal处理边界的问题，灵活使用dfs中的vis表（memcpy）
4.*耐心的实现代码
还有很多地方可以提高~