A-除法

如果B是负数，则需要用括号把分母括起来输出；如果B为0，则输出的商应为Error。注意这两点即可。

#include<bits/stdc++.h>

using namespace std;

int main()

{

int A,B;

scanf("%d %d",&A,&B);

if(B>0)

printf("%d/%d=%.2f",A,B,1.0*A/B);

else if(B==0)

printf("%d/%d=Error",A,B);

else

printf("%d/(%d)=%.2f",A,B,1.0*A/B);

return 0;

}

B-藏宝图

题意：相当于从一个大的01矩阵上切下一个小矩阵，但大矩阵上可能有多个位置都能完美匹配上这个小矩阵，要求出有多少个位置满足条件。

需要特别注意，矩阵A中坐标的范围为0~L，矩阵B中坐标的范围为0~S。所以L和S并不是矩阵的边长，还需要+1.

由于L≤2000，S≤50，数据范围很小，所以可以将矩阵A和B都用二维数组表示出来，然后再枚举每个宝藏可能在的位置，暴力匹配即可。注意，由于矩阵B(0,0)这个位置一定为1，这里没有必要做复杂度为L^2S^2的暴力匹配，只需要枚举n个1所在的位置，以此为左下角开始匹配即可。代码如下：

#include<bits/stdc++.h>

using namespace std;

int n,L,S,ans;

int a[2010][2010],b[52][52];

int x[1010],y[1010];

int main()

{

cin>>n>>L>>S;

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

{

cin>>x[i]>>y[i];

a[x[i]][y[i]]=1;

}

//注意左下角坐标为(0,0)，右上角坐标为(S,S)，所以i要倒着枚举

for(int i=S;i>=0;i--)

{

for(int j=0;j<=S;j++)

{

cin>>b[i][j];

}

}

for(int k=1;k<=n;k++) //枚举每一个宝藏可能在的位置，尝试是否能匹配

{

bool flag=1;//flag==1表示能匹配

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

{

for(int j=0;j<=S;j++)

{

int ai=x[k]+i,aj=y[k]+j;

// 如果越界，或者匹配不上，就break

if(ai>L || aj>L || a[ai][aj]!=b[i][j])

{

flag = 0;

break;

}

}

if(flag==0) break;

}

if(flag==1) ans++;

}

cout<<ans;

return 0;

}

思考部分：若L≤10^9，就不能真正将a数组建立出来。但我们可以使用map，标记这些点的位置为1，然后用同样的做法即可。

#include<bits/stdc++.h>

using namespace std;

int n,L,S;

int x[1010],y[1010];

int b[60][60];

map<pair<int,int>,int> ma;

int ans;

int main()

{

cin>>n>>L>>S;

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

{

cin>>x[i]>>y[i];

ma[make_pair(x[i],y[i])]=1;

}

for(int i=S;i>=0;i--) for(int j=0;j<=S;j++) cin>>b[i][j];

for(int k=1;k<=n;k++)

{

int flag=1;

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

{

for(int j=0;j<=S;j++)

{

if(x[k]+i>L || y[k]+j>L || ma[make_pair(x[k]+i,y[k]+j)]!=b[i][j])

{

flag=0;

break;

}

}

if(flag==0) break;

}

if(flag==1) ans++;

}

cout<<ans;

return 0;

}

C-进制转换

由于二进制中有且只有一位数字错了，而且只可能是0错成1或者1错成0，所以可以枚举二进制数中是哪一位错了，改正确之后再与三进制数比较，如果有且只有一位不同，那么就是这个数。

需要注意，由于N比较大，所以二进制和三进制数字会很长，需要使用字符串输入 。

#include<bits/stdc++.h>

using namespace std;

string a,b;//二进制和三进制数字

int num;//二进制数对应的十进制数

int main()

{

cin>>a>>b;

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

for(int i=0;i<la;i++) //算出该二进制数对应的十进制

num=num*2+a[i]-'0';

for(int i=0;i<la;i++) //枚举是二进制中的哪一位错了

{

int t=la-i-1; //这一位表示2的t次方

if(a[i]=='0') //如果是0，求出这一位变为1之后的十进制数

num+=(1<<t); //1<<t即2^t

else //如果是1，求出这一位变为0之后的十进制数

num-=(1<<t);

//num已经改正确了，转三进制，与三进制数比较

int tmp=num, j=lb-1, cnt=0;

while(tmp)

{

if(tmp%3 != b[j]-'0') //如果这一位不同，cnt++

cnt++;

tmp/=3;

j--;

}

if(cnt==1) //与三进制有且只有一位不同，输出

{

cout<<num;

return 0;

}

//这一位枚举结束，将其复原

if(a[i]=='0')

num-=(1<<t);

else

num+=(1<<t);

}

return 0;

}

D-排队形

典型的区间dp问题，每个人进入队伍里，只有 2 种可能：

1. 从右边进入。

2. 从左边加入;

所以dp数组可以定义为：

dp[i][j][0]表示从i~j这些人已经排好队了，且i这个人是从左边进来的方案数；

dp[i][j][1]表示从i~j这些人已经排好队了，且j这个人是从右边进来的方案数；

考虑状态转移：

i从左边进来，肯定前一个人比他高，前一个人有 2 种情况，要么在 i+1 号位置，要么在 j 号位置。

同理，j从右边进来，肯定前一个人比他矮，前一个人有2种情况，要么在 j−1 号位置，要么在 i 号位置。

所以可以得到状态转移方程：

// i从左边进有两种情况

if(a[i]<a[i+1]) dp[i][j][0]+=dp[i+1][j][0];

if(a[i]<a[j]) dp[i][j][0]+=dp[i+1][j][1];

// j从右边进有两种情况

if(a[j]>a[i]) dp[i][j][1]+=dp[i][j-1][0];

if(a[j]>a[j-1]) dp[i][j][1]+=dp[i][j-1][1];

初始化：

当 i==j 的时候显然只有一种方案，所以边界条件是：

for(int i=1; i<=n; i++) dp[i][i][0]=1;

注意这里不能将dp[i][i][1]也赋值为1，因为只有一个人的时候方案只有 1 种，所以默认 1 个人的时候是从左边进来。

完整代码如下：

#include <bits/stdc++.h>

using namespace std;

int dp[2010][2010][2],a[2010];

int main()

{

int n;

cin>>n;

for(int i=1; i<=n; i++)cin>>a[i];

for(int i=1; i<=n; i++) dp[i][i][0]=1;

for(int len=2; len<=n; len++)

for(int i=1; i+len-1<=n; i++)

{

int j=i+len-1;

if(a[i]<a[i+1]) dp[i][j][0]+=dp[i+1][j][0];

if(a[i]<a[j]) dp[i][j][0]+=dp[i+1][j][1];

if(a[j]>a[i]) dp[i][j][1]+=dp[i][j-1][0];

if(a[j]>a[j-1]) dp[i][j][1]+=dp[i][j-1][1];

dp[i][j][0]%=12345;

dp[i][j][1]%=12345;

}

cout<<(dp[1][n][0]+dp[1][n][1])%12345;

return 0;

}