A-字符串问题

#include<bits/stdc++.h>
using namespace std;
int main()
{
string s1,s2;
getline(cin,s1);
getline(cin,s2);
bool book[300]={0}; //ascii码范围是0~255，用book[i]==1表示ascii码为i的字符出现过
int len1=s1.length(),len2=s2.length();
//标记每一个在s2中出现的字符
for(int i=0;i<len2;i++) book[s2[i]]=1;
//只输出没有被标记的字符
for(int i=0;i<len1;i++) if(!book[s1[i]]) cout<<s1[i];
return 0;
}

B-身份证

#include <bits/stdc++.h>
using namespace std;
int a[17] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
int b[11] = {1, 0, 10, 9, 8, 7, 6, 5, 4, 3, 2};
string s;
bool isTrue() //检查s这个身份证号是否合法
{
int Z = 0;
for (int i = 0; i < 17; i++)
{
if (s[i] < '0' || s[i] > '9') return false; //如果前17位不是数字，非法
Z += (s[i] - '0') * a[i]; //计算Z值
}
int temp;
if(s[17] == 'X') temp = 10;
else temp = s[17] - '0';
Z %= 11;
return b[Z] == temp; //比较Z值与校验码M的值
}
int main()
{
int n, flag = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s;
if (!isTrue()) //检查是否合法
{
cout << s << endl;
flag = 1;
}
}
if (flag == 0) cout << "All passed";
return 0;
}

C-阅读统计

#include <bits/stdc++.h>
using namespace std;

const int maxn= 1e3+5;
int book[maxn]; //记录书借出的时间


int cnt(string s) //将一个字符串类型的时间换算为秒数
{
int h = (s[0] - '0') * 10 + s[1] - '0';
int m = (s[3] - '0') * 10 + s[4] - '0';
int time = h * 60 + m;
return time;
}
int main()
{
int day, id; //记录的天数和书的编号
char ch;
string s;
cin >> day;
int t = 0, n = 0; //t-借书次数,n-总阅读时间
for(int i = 0;i < maxn;i++) book[i] = -1;
while(day != 0)
{
cin >> id >> ch >> s;
if(id == 0) //一天结束，要重置
{
for(int i = 0;i < maxn;i++) book[i] = -1;
int ans; //平均阅读时间
if(t)
ans = n / t;
else
ans = 0;
cout << t << " " << ans << endl;
day--; //这一天过完了
t = 0;
n = 0;
}
else if(ch == 'S')
{
book[id] = cnt(s); //记录借出的时间
}
else if(ch == 'E' && book[id] != -1)
{
t++; //在这里记录借书次数，就自然的忽略了无效的借书记录
n += cnt(s) - book[id];
book[id] = -1; //还完了书后，重置
}
}
return 0;
}

D-藏宝图

#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，应该如何处理？

在L≤2000时，我们可以建立a数组来完整存储藏宝图。但如果图太大，就不可以了。但由于这个藏宝图中为1的点是稀疏的，n的范围并不大，所有我们可以用其它数据结构来存储为1的点。

这里提供一种思路：使用map<pair<int,int>,bool>，将每个为1的点存到map中。其余代码与上述代码类似。

#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()
{
freopen("treasure.in","r",stdin);
freopen("treasure.out","w",stdout);
cin>>n>>L>>S;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
ma[make_pair(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++) //枚举每一个宝藏可能在的位置，尝试是否能匹配
{
int flag=1; //flag==1表示能匹配
for(int i=0;i<=S;i++)
{
for(int j=0;j<=S;j++)
{
// 如果越界，或者匹配不上，就break
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;
}

E-最大得分

思路：简单dp，从第n行开始，首先预处理一开始的三个可能走到的格子，然后从最后一行推到第一行，类似于2380数字金字塔的做法。

#include <bits/stdc++.h>
using namespace std;
int n,m,a[210][210],f[210][210],maxx;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%d",&a[i][j]);
for(int i=1; i<=n; i++)
for(int j=0; j<=m+1; j++)
f[i][j]=-0x3f3f3f3f; //存储到达这个格子时得分的最大值
int t=m/2;
//预处理第n行可能走到的三个格子
f[n][t]=a[n][t];
f[n][t+1]=a[n][t+1];
f[n][t+2]=a[n][t+2];
for(int i=n-1; i>=1; i--) //倒着枚举每一行
{
for(int j=1; j<=m; j++)
{
//从三个可能的之前的位置上转移过来
f[i][j]=max(f[i+1][j],max(f[i+1][j+1],f[i+1][j-1]));
//如果能走到这个点，加上这个点本身的值
if(f[i][j]!=-0x3f3f3f3f) f[i][j]+=a[i][j];
}
}
for(int i=1; i<=m; i++)
maxx=max(maxx,f[1][i]);//取第一行的最大值作为答案
printf("%d",maxx);
return 0;
}