A-数字反转

这道题比较简单，不多赘述。注意判断负号、前导0以及单独一个0的情况。

#include <bits/stdc++.h>

using namespace std;

char a[1110000];

int l;

int main()

{

scanf("%s",a);

l=strlen(a);

while(a[l-1]=='0'&&l>1) l--;//去除前导0 同时注意只有一个0的情况

if(a[0]!='-') for(int i=l-1;i>=0;i--) printf("%c",a[i]); //如果不是负数 直接倒着输出即可

else //如果是负数 先输出负号再倒着输出

{

printf("-");

for(int i=l-1;i>=1;i--) printf("%c",a[i]);

}

return 0;

}
 

B-统计单词数

首先输入两个字符串a,b，然后把单词a放入字符串b中依次匹配。匹配之前，要将所有字符统一转成大写或小写。

变量t记录当前字符串a匹配到的位置，如果a[t]与当前枚举到的字符串b中的字符不同，就说明匹配失败，t重新归为0；

如果相同，则需要判断此时t是否为0，如果是0的话，证明此时是单词的开始，所以需要保证b[i-1]为空格，防止出现从半路开始匹配的情况，如单词to匹配到了onto；如果t不为0或t为0且b[i-1]为空格，则成功匹配，t++。

如果t++之后发现t已经等于字符串a的长度，就证明已经匹配上了，但此时还不能更新答案，还需要判断b[i+1]是否为空格，如果是空格才能累积答案，防止出现love和lover匹配的情况。

#include <bits/stdc++.h>

using namespace std;

string a,b;

int t=0,first=-1,ans=0;

int main()

{

getline(cin,a);

getline(cin,b);

//getline函数碰到空格不会停止

int la=a.length(),lb=b.length();

for(int i=0; i<la; i++) a[i]=tolower(a[i]);

for(int i=0; i<lb; i++) b[i]=tolower(b[i]);

//使用tolower函数实现大小写转换

for(int i=0; i<lb; i++)

{

if(a[t]!=b[i])//如果当前这个字母没有匹配上，回到起点

{

t=0;

continue;

}

if(t==0&&i!=0&&b[i-1]!=' ') continue;//如果正在匹配第一个字母，就要确定此时是不是一个单词的开始，如果不是就要跳过

//这一行代码时为了防止出现用to匹配onto类似的情况

t++; //当前字母匹配成功，t++匹配下一个字母

if(t==la)

{

//a字符串已经匹配完成，还要判断当前是不是一个单词的末尾

if(b[i+1]==' ')

{

ans++;

t=0;

if(ans==1) first=i-la+1;

//记录这个单词的首字母第一次出现的位置，即用当前所在位置减去单词的长度再加一

}

else t=0;

}

}

if(first==-1) printf("-1");//first==-1表明没有找到过这个单词

else printf("%d %d",ans,first);

return 0;

}

C-考前抱佛脚

思路：搜索

每道题有放在左脑和放在右脑两种选择，暴力枚举每道题是放在左脑还是右脑，使用递归的方法把所有可能性都枚举出来取最小值。

核心代码如下：

void dfs(int q,int x)

{

if(l>=minn||r>=minn) return;

if(x>a[q])

{

minn=min(minn,max(l,r));

return;

}

l+=s[q][x]; dfs(q,x+1); l-=s[q][x];

r+=s[q][x]; dfs(q,x+1); r-=s[q][x];

}

现在是第q科的第x道题，做这道题需要花费的时间为s[q][x]，q这一科一共有a[q]道题。那么我们从第一道题开始选择把这道题放在左脑还是右脑，根据选择去修改l和r的值。当x==a[q]+1时 就表明这a[q]道题已经全部选完了，需要更新答案即minn。

函数的第一行为一个剪枝，如果左脑或者右脑当前的答案已经大于已知最优解，就没比较继续搜下去了，因为继续搜到最后也不可能得到更好的答案。

#include<bits/stdc++.h>

using namespace std;

int l,r,ans,minn;

int a[5];

int s[5][21];

void dfs(int q,int x)

{

if(l>=minn||r>=minn) return;

if(x>a[q])

{

minn=min(minn,max(l,r));

return;

}

l+=s[q][x]; dfs(q,x+1); l-=s[q][x];

r+=s[q][x]; dfs(q,x+1); r-=s[q][x];

}

int main()

{

scanf("%d%d%d%d",&a[1],&a[2],&a[3],&a[4]);

for(int i=1;i<=a[1];i++) scanf("%d",&s[1][i]); l=r=0; minn=1234567890; dfs(1,1); ans+=minn;

for(int i=1;i<=a[2];i++) scanf("%d",&s[2][i]); l=r=0; minn=1234567890; dfs(2,1); ans+=minn;

for(int i=1;i<=a[3];i++) scanf("%d",&s[3][i]); l=r=0; minn=1234567890; dfs(3,1); ans+=minn;

for(int i=1;i<=a[4];i++) scanf("%d",&s[4][i]); l=r=0; minn=1234567890; dfs(4,1); ans+=minn;

printf("%d",ans);

return 0;

}

D-两只牛

暴力模拟题，题目本身难度不大，但需要一定的代码熟练度。

我们需要的信息是约翰的坐标、约翰的方向、奶牛的坐标、奶牛的方向。每分钟我们做出的操作是：判断向前走一步是否是障碍，如果是，改变方向；如果不是，向前走一步。这一分钟的最末端我们判断约翰和奶牛是否相遇，如果相遇，程序结束；如果没有相遇，继续这个过程。

方向问题很好解决，用0,1,2,3分别表示四个方向即可，然后用一个方向数组来表示朝这个方向走一步的坐标变化。每次改变方向时只需要把方向变量+1，再对4取模即可。

最大的问题是怎么判断永远不会相遇。其实也很简单，思路和我们以前搜索时建立book数组类似，但这里的book数组要复杂一些。我们可以建立一个六维数组（不要被数组的维数吓到），表示约翰在这个坐标和这个方向上，奶牛在这个坐标和这个方向上，这样的状态我们已经走过。如果下一次再走到这个状态就表示陷入死循环了，永远无法相遇。

#include<bits/stdc++.h>

using namespace std;

const int dx[4]={-1,0,1,0};//上、右、下、左四个方向

const int dy[4]={0,1,0,-1};

int cx,cy,ct;//记录奶牛的坐标和方向

int fx,fy,ft;//记录约翰的坐标和方向

bool f[21][21],v[21][21][4][21][21][4];//f表示地图是否能走，v表示这种情况是否有出现过

void search()

{

int k=0;//当前分钟数

while(1)

{

if(cx==fx && cy==fy)//如果抓到了牛

{

printf("%d\n",k);//输出

exit(0);

}

if(v[fx][fy][ft][cx][cy][ct])//如果这种情况出现过 证明进入死循环

{

printf("0\n");

exit(0);

}

v[fx][fy][ft][cx][cy][ct]=1;//把这种情况设置为出现过

//找奶牛的方向

if(f[cx+dx[ct]][cy+dy[ct]]==false)//如果这个方向不能走

{

ct++;

ct%=4;

}

else cx=cx+dx[ct],cy=cy+dy[ct];//如果可以走就走

//找john的方向

if(f[fx+dx[ft]][fy+dy[ft]]==false)

{

ft++;

ft%=4;

}

else fx=fx+dx[ft],fy=fy+dy[ft];

k++;

}

}

int main()

{

char st[21];

//一开始f数组均为false 现在把能走的地方确定

for(int i=1;i<=10;i++)

{

scanf("%s",st+1);//输入

for(int j=1;j<=10;j++)

{

if(st[j]=='.') f[i][j]=true;//如果能走

if(st[j]=='F') fx=i,fy=j,f[i][j]=true;//如果是john

if(st[j]=='C') cx=i,cy=j,f[i][j]=true;//如果是牛

}

}

ct=ft=0;//一开始是向上

search();//开始搜索

return 0;

}