A-图书管理员

思路：

若一个需求码长度为x，则需要检查每个图书的后x位是否等于该需求码。

要求一个数字的后x位，用到取余的方法：比如取个位可以%10，那么取后两位可以%100，以此类推，取后x位可以%(10^x)。

用pow函数计算10^x（如果会快速幂的话建议自己写），取模看是否和需求码相等，在满足需求码的图书中找最小的。

#include<bits/stdc++.h>

using namespace std;

int n,q,book[1010],len[1010],num[1010];

int main()

{

cin>>n>>q;

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

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

{

cin>>len[i]>>num[i];

int tmp = pow(10,len[i]), minn = 10000001;

for(int j=1; j<=n; j++) if(book[j] % tmp == num[i] && book[j] < minn) minn = book[j];

if(minn != 10000001) cout<<minn<<endl;

else cout<<-1<<endl;

}

return 0;

}

B-直播获奖

50分思路：

可以每出一个人的成绩就用sort对前i个人排序，求出获奖人数x后，找到当前分数第x高的人，他的分数即为分数线。

由于sort从小到大排序，所以要用i-x+1来求分数第x高的人的下标。

#include<bits/stdc++.h>

using namespace std;

int a[100010];

int main()

{

int n,w;

cin>>n>>w;

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

{

cin>>a[i];

sort(a+1,a+i+1);

int x=max(1,i*w/100);

cout<<a[i-x+1]<<' ';

}

return 0;

}

85分思路：

注意到我们每次插入一个新数字时，前面的数字是有序的，在一个已经有序的序列中插入一个新的数字，可以直接扫一遍进行排序，类似于冒泡的思路，直接给新插入的数找到一个合适的位置即可。

这样，每次新来一个数，我们排序的时间复杂度从O(nlogn)降到了O(n)，可以得到85分。

#include<bits/stdc++.h>

using namespace std;

int a[100010];

int main()

{

int n,w;

cin>>n>>w;

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

{

cin>>a[i];//从1~i-1的数都已经排好序了

for(int j=i;j>=1;j--)

{

if(a[j]<a[j-1]) swap(a[j],a[j-1]);

else break;

}

int x=max(1,i*w/100);

cout<<a[i-x+1]<<' ';

}

return 0;

}

100分思路：

考虑桶排序的做法。

桶排序适用于需要排序的数字比较小的情况。比如现在有100000000个1~10之间的数想要排序我们只需要建立一个数组a，a[i]表示大小为i的数的数量，那么就可以用以下代码输出排序后的结果：

for(int i=1;i<=10;i++) for(int j=1;j<=a[i];j++) cout<<i<<' ';

由于这道题分数不超过600，数据比较小，可以用桶排序来做。

这道题也类似上面的做法，每新来一个成绩x，当前成绩为x的人数就要加1。用t[i]表示分数为i的人的个数，那么我们每次输入新来的分数w后，t[w]++;

之后我们需要找到排在第x名的人，那么我们从600从高到低枚举，用一个变量累积当前分数超过某个值的人数。如果这个人数>=获奖人数，就停止循环，当前的分数即为分数线。

注意，以下代码在超能力编程网站上提交得不到满分，需要改为scanf和printf。

#include<bits/stdc++.h>

using namespace std;

int t[605];//t[i]表示当前分数为i的人有多少个

int n,w;

int main()

{

int x;

cin>>n>>w;

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

{

cin>>x;

t[x]++;

int sum=0;

for(int j=600;j>=0;j--)//枚举分数

{

sum+=t[j];//当前能获奖的总人数

if(sum>=max(1,i*w/100))

//如果当前获奖的人数已经等于或大于规定人数 输出分数线

//可以大于是因为同分取齐

{

cout<<j<<' ';

break;

}

}

}

return 0;

}

C-花生采摘

思路：

这道题题干比较长，但其实思路很简单，只需要对每块地里花生的数量进行排序，从大到小采摘，每次加上要走的距离即可。

两点之间要走的距离是他们x坐标的差加上y坐标的差。注意采摘还要花一个单位时间。

要注意的地方是每走一步要判断一下走了之后是否可以在指定时间内出去，如果出不去，就不走这一步。第一次走要特别判断，因为是从路边走最短的路线到达第一个点，即直接加上x坐标的值。

排序时可以用结构体存储。

#include<bits/stdc++.h>

using namespace std;

int n,m,k,ans,cnt,t;

struct node

{

int x,y,sum;

}a[410];//数组大小开到n*m的最大值即可

bool cmp(node x,node y)

{

return x.sum>y.sum;

}

int main()

{

scanf("%d%d%d",&n,&m,&k);

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

{

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

{

int w;

scanf("%d",&w);

if(w) //花生的数量不为0时才放入结构体

{

cnt++;

a[cnt].x=i;

a[cnt].y=j;

a[cnt].sum=w;

}

}

}

sort(1+a,1+cnt+a,cmp);

t=a[1].x+1; //采摘还需要花一个单位的时间

ans+=a[1].sum;

if(t+a[1].x>k) //特判第一棵花生能否采摘

{

printf("0");

return 0;

}

for(int i=2;i<=cnt;i++)

{

t+=abs(a[i].x-a[i-1].x)+abs(a[i].y-a[i-1].y)+1; //采摘还需要花一个单位的时间

if(t+a[i].x>k) break; //如果摘了i这棵花生再回去路边所需时间>k，就不加入ans中，直接break

ans+=a[i].sum;

}

printf("%d",ans);

return 0;

}

D-摆花

方法1：记忆化搜索

就算没有思路，也要想到搜索。

从 1 到 n 考虑每种花的盆数，记录当前前 i 种花盆数的总和 k，枚举所有可能的盆数值，递归求解。

下面给出简单的dfs代码：

int dfs(int x,int k) //考虑到第x种花，当前一共选了k盆 { if(k > m) return 0; if(k == m) return 1; //如果当前正好选到m盆，则是一种可行方案 if(x == n+1) return 0; int ans = 0; for(int i=0; i<=a[x]; i++) ans = (ans + dfs(x+1, k+i))%mod; return ans; }

这个方法显然会超时，所以要用记忆化优化。

所谓记忆化，其实就是用一个数组将搜索过的值存起来，避免重复搜索，从而提高效率。代码的改动也很简单，就是用数组f[x][k]来记录调用dfs(x,k)时会返回的值。如果当前f[x][k]==0，证明还没有调用过，就正常搜索；如果!=0，证明以前已经调用过，并且f[x][k]中已经记录了搜索出的值，可以直接返回f[x][k]。

#include<bits/stdc++.h>

using namespace std;

const int maxn=105, mod = 1000007;

int n, m, a[maxn], f[maxn][maxn];

int dfs(int x,int k)

{

if(k > m) return 0;

if(k == m) return 1;

if(x == n+1) return 0;

if(f[x][k]) return f[x][k]; //搜过了就返回

int ans = 0;

for(int i=0; i<=a[x]; i++) ans = (ans + dfs(x+1, k+i))%mod;

f[x][k] = ans; //记录当前状态的结果

return ans;

}

int main()

{

cin>>n>>m;

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

cout<<dfs(1,0)<<endl;

return 0;

}

方法2：动态规划

实际上，记忆化搜索都可以转化为动态规划，但是动态规划不一定能用记忆化搜索。

定义状态：f(i, j) 表示前 i 种花共选了j盆的方案数。

容易得到状态转移方程：f(i, j) = \sum\limits_{k=0}^{a_{i}}f(i-1,j-k)

其中, k是枚举当前第 i 种花选多少盆。

所以可以用三重循环，分别枚举i,j,k，最后输出f[n][m]即可。

#include<bits/stdc++.h>

using namespace std;

const int maxn=105, mod = 1000007;

int n, m, a[maxn], f[maxn][maxn];

int main()

{

cin>>n>>m;

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

f[0][0] = 1;

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

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

for(int k=0; k<=min(j, a[i]); k++)

f[i][j] = (f[i][j] + f[i-1][j-k])%mod;

cout<<f[n][m]<<endl;

return 0;

}