A-字符串问题

解法一：对于s1中的每个字符，枚举s2中的每个字符，判断其有没有在s2中出现过。

#include<bits/stdc++.h>

using namespace std;

int main()

{

string s1,s2;

getline(cin,s1);

getline(cin,s2);

int i,j;

int len1=s1.length(),len2=s2.length();

// 对于s1中的每个字符 判断其有没有在s2中出现过

for(i=0;i<len1;i++)

{

for(j=0;j<len2;j++)

{

if(s1[i]==s2[j])

break;

}

if(j==len2)

printf("%c",s1[i]);

}

return 0;

}

解法二：用一个数组标记s2中所有出现过的字符，然后枚举s1中的字符，如果这个字符没有被标记，则可以输出。

#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

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-超能搭档

许多同学错误的原因是输出顺序错误，要注意小组的输出顺序按照名次较高学生的名次从高到低排列。

依次枚举前n/2名学生，根据该学生的性别来找到对应的此时还没有组队的最后一名男生或女生即可。

用两个指针，分别指向最后一名女生的位置和最后一名男生的位置，如果这个男生或女生已经配队成功了便让指针向前移动，继续找下一个需要配队的男生或者女生。这样避免了每次都要从头开始枚举，加快了程序运行效率（当然，这道题数据范围较小，每次从后往前循环找到没有被标记的异性同学同样可行）。具体实现见代码：

#include<bits/stdc++.h>

using namespace std;

struct students

{

int gender; //性别

string name; //姓名

} s[51];

int main()

{

int n;

cin>>n;

for(int i=1; i<=n; i++) cin>>s[i].gender>>s[i].name;

int x=n,y=n;//x指向最后一名女生的位置，y指向最后一名男生的位置

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

{

if(s[i].gender==1)

{

while(s[x].gender!=0) x--; //找到最后一名还没有被分配的女生

cout<<s[i].name<<' '<<s[x].name<<endl;

x--; //该名女生已经被分配，继续往前找

}

else if(s[i].gender==0)

{

while(s[y].gender!=1) y--; //找到最后一名还没有被分配的男生

cout<<s[i].name<<' '<<s[y].name<<endl;

y--; //该名男生已经被分配，继续往前找

}

}

return 0;

}

C-幸运数

该题没有特别的算法，重点在读题，读清楚题意之后直接模拟即可。

首先可以求出每个数迭代后的下一个数，存储在nex[i]中，这是一个简单的数位分解问题。在这个过程中，我们可以顺便求出每个数有没有被l~r之间的数经过，可以用book来标记。

然后通过nex数组，我们可以递归求出每个数字变到1的过程中经过了多少个数，进而可以判断这个数幸不幸运以及得到每个数的幸运度。

但是递归的时候要特别注意死循环的情况，因为有些数并不幸运，永远无法变为1。所以可以在第一次递归找一个数的幸运度时标记它的幸运度为-1，如果在递归的过程中发现遇到的数幸运度为-1，则证明发生了死循环。如果最终递归到1，或者递归到我们已经找到了幸运度的数，则直接返回幸运度即可。

最后，枚举l~r之间的数，如果这个数没有被经过（book[i]==0）且它是一个幸运数(lucky[i]!=-1)，则是特殊的幸运数，需要输出。输出时要判断它是否是质数，如果是质数还要输出lucky*2。

用一个标记来表示是否有特殊的幸运数，如果没有，最后需要输出SAD。

由于这道题数据范围不大，所以枚举时可以直接从1枚举到10000。由于迭代后最大为9999迭代到81+81+81+81=324，所以不用担心数组越界。

#include<bits/stdc++.h>

using namespace std;

int nex[10010];//nex[i]表示数字i迭代后的下一个数

bool book[10010];//判断一个数是否被区间内的其他数字所经过

int lucky[10010];//判断一个数是否为幸运数，如果是的话经过了多少个数字

int dfs(int x) //递归求一个数变为1的过程中经过的数字个数

{

if(x==1||lucky[x]!=0) return lucky[x];

lucky[x]=-1; //初始化为-1，防止形成死循环

int tmp=dfs(nex[x]);

if(tmp!=-1) lucky[x]=tmp+1;

//如果tmp为-1，表示形成了死循环；否则，返回的是经过的数字个数

return lucky[x];

}

int main()

{

int l,r;

cin>>l>>r;

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

{

int x=i;

int y=0;

while(x)

{

int tmp=x%10;

y+=tmp*tmp;

x/=10;

}

nex[i]=y;

if(i>=l&&i<=r) book[y]=1; //被经过

}

for(int i=2;i<=10000;i++) dfs(i); //求每个数的幸运度

bool flag=0;

for(int i=l;i<=r;i++)

{

if(book[i]==0&&lucky[i]!=-1) //是特殊的幸运数

{

flag=1;

int x=lucky[i]; //初始化幸运度为经过的数字个数

bool zs=1;

for(int j=2;j*j<=i;j++) //判断质数

{

if(i%j==0)

{

zs=0;

break;

}

}

if(zs) x*=2;

cout<<i<<' '<<x<<endl;

}

}

if(flag==0) cout<<"SAD";

return 0;

}

D-逃亡计划

思路：dp

用dp[i][j]表示使用前i波能量，搭出的梯子高度为j时，能保存的最大生命。

枚举前i-1波能量搭出的梯子高度j（从0枚举到d-1，因为如果搭出了高度为d的梯子就能出去了）：

首先，如果dp[i-1][j]<a[i].t，就证明用前i-1波能量搭j这么高的梯子会导致超能侠不能撑到第i波能量到来，直接continue；

其次，如果j+a[i].h>=d，就证明这波能量可以让超能侠逃出去，输出答案即可； 

如果不满足这两种情况，常规的转移方程如下：

1. 如果选择用第i波能量搭梯子：

dp[i][j+a[i].h]=max(dp[i][j+a[i].h],dp[i-1][j]);

2. 如果选择用第i波能量恢复生命 ：

dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i].hp);

同时我们需要更新ans（能存活的最长时间），即每次取dp数组中的最大值即可。

#include<bits/stdc++.h>

using namespace std;

struct node

{

int t,hp,h;

}a[110];

int d,g,ans=10; //至少能活10小时

int dp[110][110];//前i波能量，高度为j的最大生命

const int inf = 0x3f3f3f3f;

bool cmp(node a,node b)

{

return a.t<b.t;

}

int main()

{

scanf("%d%d",&d,&g);

for(int i=1;i<=g;i++) scanf("%d%d%d",&a[i].t,&a[i].hp,&a[i].h);

sort(1+a,1+g+a,cmp); //按时间顺序排序

for(int i=0;i<=g;i++) for(int j=0;j<=d;j++) dp[i][j]=-inf;

dp[0][0]=10; //初始化

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

{

for(int j=0;j<d;j++) //枚举前i-1波能量的高度

{

if(dp[i-1][j]<a[i].t) continue;//如果不能撑到第i波能量来就无法更新答案

if(j+a[i].h>=d) //如果这个高度加上用第i波能量建立能量梯的高度就能逃出去

{

printf("%d",a[i].t);//可以出去了

return 0;

}

//选择用这波能量搭梯子

dp[i][j+a[i].h]=max(dp[i][j+a[i].h],dp[i-1][j]);

ans=max(ans,dp[i][j+a[i].h]);

//选择用这波能量恢复生命

dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i].hp);

ans=max(ans,dp[i][j]);

}

}

//没有逃出去，输出能存活的最长时间

printf("-1 %d",ans);

return 0;

}