第六届河海大学程序设计大赛(低年级组)题解

**题目地址：** [题目地址](http://acm.hhu.edu.cn/problemset.php?search=%E7%AC%AC%E5%85%AD%E5%B1%8A%E6%B2%B3%E6%B5%B7%E5%A4%A7%E5%AD%A6%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E5%A4%A7%E8%B5%9B%EF%BC%88%E4%BD%8E%E5%B9%B4%E7%BA%A7%E7%BB%84%EF%BC%89)
总的来说这些题目如果给一个之前没有比赛过的人确实还是有点难的.
> 两年之后来补题解了.
---
## [A. 买零食](http://acm.hhu.edu.cn/problem.php?id=1058)
比赛的时候我其实是不会动态规划的,但是还好比赛可以带书,带了紫书上面就有一些可以用的代码,但是打印上出了点问题,所以改了7,8次才过的.对于不会背包问题的小白,你可以参考这一篇写的很好背包九讲(~~虽然很好,但是注意一下在01背包里面的常数优化那里的公式写错了,聪明的你肯定能看出来的~~):
**[背包九讲](https://hodam.top/myfile/acm/背包九讲_2.0.pdf)**
这题是一个01背包的模板题.所以直接上代码:
```cpp
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
int w[1010],v[1010],dp[10010];
using namespace std;
int main()
{
  int n,m;
  cin >> n >> m;
  for(int i = 0;i < n;i++){
  scanf("%d%d",&w[i],&v[i]);
  }
  for(int i = 0;i < n;i++){
  for(int j = m;j >= w[i];j--){
   dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
   }
  }
  cout << dp[m];
  return 0;
}
```
---
## [B. iPhone X](http://acm.hhu.edu.cn/problem.php?id=1059)
这个题目其实也只是模拟了一下C++ STL中的双端队列(deque).
代码:
```cpp
#include <iostream>
#include <queue>
#include <string>
using namespace std;
deque <string> p;
int main()
{
    string s;
    int n;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> s;
        if(s=="Join"){
            cin >> s;
            p.push_back(s);
        }
        else if(s=="Quit"){
            s=p.back();
            cout << s << endl;
            p.pop_back();
        }
        else if(s=="Pop"){
            s=p.front();
            cout << s << endl;
            p.pop_front();
        }
    }
    return 0;
}
```
---
## [C. 滑冰](http://acm.hhu.edu.cn/problem.php?id=1060)
题目就是一个普通的dfs加标记,但是这个算是我们那个时候的防AK的题了.但是我们只要dfs加方向标记就可以过了.
> 注意不要用getchar()读入,不然你们就会像我一样,在这个鬼地方debug三个小时
以下是代码:
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <list>
using namespace std;
//ios::sync_with_stdio(false);
const int MINF = 0x7fffffff;
const int INF = 0x3f3f3f3f;
const int Maxn = 1e5+5;
typedef long long ll;
char mp[11][11];
bool mb[11][11][4];
int n,m,sx,sy;
int dx[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
bool dfs(int x,int y,int dir)
{
    //printf("now x=%d,y=%d\n",x,y);
    if(mp[x][y]=='U') return false;
    if(mb[x][y][dir]||mp[x][y]=='X') return true;
    mb[x][y][dir]=true;
    x+=dx[dir][0];y+=dx[dir][1];
    if(x>0&&x<=n&&y>0&&y<=m){
        if(mp[x][y]=='O'||mp[x][y]=='K') {return dfs(x,y,dir);}
        else if(mp[x][y]=='U') return false;
        else{
            x-=dx[dir][0];y-=dx[dir][1];
            return dfs(x+dx[(dir+3)%4][0],y+dx[(dir+3)%4][1],(dir+3)%4)&&dfs(x+dx[(dir+1)%4][0],y+dx[(dir+1)%4][1],(dir+1)%4);
        }
    }
    else return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        scanf("%s",mp[i]+1);
        for(int j = 1;j <= m;j++){
            if(mp[i][j]=='K') sx=i,sy=j;
        }
    }
    bool flag=true;
    flag=dfs(sx,sy,0)&&dfs(sx,sy,1)&&dfs(sx,sy,2)&&dfs(sx,sy,3);
    if(flag) puts("Safe");
    else puts("Dangerous");
    return 0;
}
```
---
## [D. 连接](http://acm.hhu.edu.cn/problem.php?id=1061)
这个题目实际上是1998年NOIp提高组的题目,[链接](https://www.luogu.org/problemnew/show/P1012).
而这个题目实际上算是一个排序题,对于两组数字a,b,`a+b`如果大于`b+a`的话,那么a就排序在b的前面.
代码:
```cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
string num[101];
bool cmp(string a,string b)
{
    return a+b>b+a;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin  >> num[i];
    }
    sort(num,num+n,cmp);
    for(int i = 0;i < n;i++) cout << num[i];
    return 0;
}
```
---
## [E. 死亡笔记](http://acm.hhu.edu.cn/problem.php?id=1062)
这题也很简单,可以读入所有的string(人名),排序,前后相同合并一下.或者使用STL的map直接搞.
代码:
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <list>
using namespace std;
//ios::sync_with_stdio(false);
const int MINF = 0x7fffffff;
const int INF = 0x3f3f3f3f;
const int Maxn = 1e5+5;
typedef long long ll;
map<string,int>s;
int main()
{
    string name;
    while(cin >> name) s[name]++;
    for(auto it=s.begin();it!=s.end();it++){
        cout << (*it).first << ' ' << (*it).second << endl;
    }
    return 0;
}
```
---
## [F. 找规律](http://acm.hhu.edu.cn/problem.php?id=1063)
这个题目实际上是当年(2017)NOIp提高组的题目,~~那个题目我还看过,就是没有去写,血亏100~~.题如其名,找到规律就好.
**[严格证明](https://www.luogu.org/problemnew/solution/P3951)**
代码:
```cpp
#include <iostream>
using namespace std;
int main()
{ 
  int a,b;
  cin >> a >> b;
  cout << a*b-a-b;
  return 0;
}
```
---
## [G. 颜文字](http://acm.hhu.edu.cn/problem.php?id=1064)
题目意思很简单,但是有个小坑,那就是`\\`符号输出的时候会当作转移字符,要输出`\\`就得用`\\\\`来表示~~因为本篇博客开了一个mathjax的支持,现在原来的文章里面其实也是写了两倍的`\\`符号的~~
代码:
```cpp
#include <cstdio>
int main(){puts("\\\\('0w0')/");}
```

Last modification：March 19, 2019