简单题

• A . 位数判断(公式位数相加mod 10，递归)

#include<stdio.h>

int ghh(int n)
{
    return n==0 ? n:n%10+ghh(n/10);
}

int hh(int x)
{
    x=ghh(x);
    return x/10==0 ? x:hh(x) ;
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", hh(n));
    return 0;
} 

• B. 简单输出(签到题)

cout<<"1 1 2 3 5 8 13 21 34 55"<<endl;

• C. lear year (模拟)

int main(){
  int n;cin>>n;
  if((n%4==0&&n%100!=0)||(n%400==0))cout<<"yes"<<endl;
  else cout<<"no"<<endl;
  return 0;
}

• D.Out of the maze(bfs/搜索简单题)

int bfs()
{
    while(!que.empty())
    {
        P p=que.front();
        que.pop();

        if(maze[p.first][p.second]=='E') 
        {
           return 1;
        }
        for(int i = 0;i<4;i++)
        {
            int nx=p.first+dx[i],ny=p.second+dy[i];
            if(0<=nx&&nx<N&&0<=ny&&ny<M&&maze[nx][ny]!='#'&&d[nx][ny]==0)
            {
                que.push(P(nx,ny));
                d[nx][ny] = 1;
            }
        }
    }
    return 0;
}

• E. 0 1 String(循环/bitset函数的运用)

#include<iostream>
#include<bitset>
using namespace std;
int main()
{
    for(int i=0;i<=127;i++)
    cout<<bitset<7>(i)<<endl;
}

• F.Fibonacci Sequence B (高精度模板题/python直接计算)

a=1
b=1
c=int(input())
if c>2:
    for i in range(c-2):
        ans=a+b
        a=b
        b=ans
else:
    ans=1;
print(ans

提高题

• G．憨憨回家了(DP-01 背包问题）

 f[j]=max(f[j],f[j-v[i]]+w[i]);

• H.憨憨求阶乘(规律题 当n>5后面全是0)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int f(ll n){
    if(n==4)return 4;
    else if(n==3)return 6;
    else if(n==2)return 2;
    else if(n==1)return 1;
    else if(n==0)return 1;
    else return 0;
}
int main() {
    ll n;cin>>n;
    cout<<f(n)<<endl;
    return 0;
}

• I.憨憨的工作(标记问题)
  先读入，在搜索他出现的位置，（题意：就是简单看一个序列某一个数字是第几次出现）

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int *array;
    array=new int[n];
    for(int i=0;i<n;i++)
        cin>>array[i];
    for(int i=0;i<n;i++)
    {
        int number=1;
        for(int j=0;j<i;j++)
        {
            if(array[i]==array[j])
                number++;
        }
        cout<<number<<" ";
    }
    return 0;
}

• J 憨憨同学的数学小问题（矩阵乘法）
  对于矩阵乘法我们直接模拟就好了，数据范围不大所以我们直接暴力模拟！

#include<iostream>
using namespace std;
typedef long long int ll;
int main()
{
    ll a[500][500],b[500][500],c[500][500];
    int a1,b1,a2,b2;
    cin>>a1>>b1;
    for(int i=0;i<a1;i++)
    {
        for(int j=0;j<b1;j++)
        {
            cin>>a[i][j];
        }
    }
    cin>>a2>>b2;
    for(int i=0;i<a2;i++)
    {
        for(int j=0;j<b2;j++)
        {
            cin>>b[i][j];
        }
    }
    ll sum;
    for(int i=0;i<a1;i++)
    {
        for(int j=0;j<b2;j++)
        {
            sum=0;
            for(int z=0;z<a2;z++)
            {
                sum+=a[i][z]*b[z][j];
            }
            c[i][j]=sum;
        }
    }
    for(int i=0;i<a1;i++)
    {
        for(int j=0;j<b2;j++)
        {
            cout<<c[i][j]<<" ";
        }
        cout<<endl;
    }

    return 0;
}

• L 憨憨同学的团队比赛(排序+规律)
  直接排序，用最大的三个值减最小的三个值即可。当然也可以线性做，但是太过麻烦(需要扫描 6 次或者用 6 个变量来记录最大最小的三个值)，作为签到题，不推荐这种做法。
  时间复杂度$O(nlogn)$。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, a[maxn];
int main(){
   cin >> n;
  for(int i = 1; i <= n; i++)
   cin >> a[i];
   sort(a+1, a+1+n);
   cout << 1ll * a[n] + a[n-1] + a[n-2] - a[1] - a[2] - a[3] << endl;
}

进阶题

• K 憨憨同学的小游戏(DP)
  若有n个人在(a,b)状态相遇，则有n/2个人变为(a+1,b)和 (a,b+1)(不出局的情况)。那么我们
  可以用 bfs 或直接递推来求解出每个位置的人数，注意将除二变成乘以二的逆元，特判出局的情况。预处理好之后，即可处理所有询问。
  时间复杂度$O(nm+q)$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
ll cnt[4005][4005];
ll quickpow(ll a,ll b,ll c = mod, ll ans = 1){
   while(b){if(b & 1) ans = (a * ans)% c; 
   a = (a * a) % c, b >>= 1;} return ans;
}
const ll inv2 = quickpow(2, mod - 2);

int main() {
 int n, m, q, a, b;
 cin >> n >> m >> q;
  cnt[0][0] = quickpow(2, n + m);
  for (int i = 0; i < n + m; ++i)
    for (int j = max(i - n + 1, 0); j <= min(m - 1, i); ++j) {
      cnt[i + 1][j] = (cnt[i + 1][j] + cnt[i][j] * inv2 % mod) % mod;
        cnt[i + 1][j + 1] = cnt[i][j] * inv2 % mod;
}
while (q--) {
  cin >> a >> b;
  cout << cnt[a + b][b] << endl;
  }
}

• M 憨憨同学的排序问题(DP)
  本来是有 10 道水题，但是害怕无法满足实力过强的选手，于是增加了几道提高题题 QAQ。
  首先题目要求严格递增，我们发现这样不好处理，于是可以想到将第i个数字减去i ，作为新的 a[i]。
  这样问题就变成了将序列变成单调不递减的，求最小花费。经过分析可知，最终的序列的每一个元素的
  值一定在初始序列中可以找到，那么我们可以将初始序列离散化。令dp[i][j]代表前 i个位置均有序(不递减)，且第i个数字被修改成a[j]的最小花费。不难写出$O(n^3)$的动态规划，即枚举i,j,k ，其中k代表第i-1个数字被修改成a[k] ，且a[k]<=a[j] 。此时前i-1 个数字均小于等于a[j] ， 所以直接将第a[i]修改为a[j] 即可。花费为 abs(abs(a[j] - a[i]))，状态转移方程为：dp[i][j]=min(dp[i][j],dp[i-1][k]+ans(a[j)-a[i]))
  观察转移方程得，如果已经确定了i,j ，ans(a[j)-a[i])是确定的，即我们要求的是dp[i-1][1]到dp[i-1][j]
  的最小值，所以无需每次都枚举k，只要在每次转移之后求一个前缀最小值即可。用
  ans[i]代表此时前i个dp值的最小值，状态转移方程被优化为：dp[i][j]=min(dp[i][j],ans[[j]+ans(a[j)-a[i]))
  时间复杂度$O(n^2)$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
#define ll long long
ll ans[maxn], dp[maxn][maxn], co[maxn], pos[maxn];
int main(){
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++)
  cin >> co[i], co[i] -= i, pos[i] = co[i];
  sort(pos + 1, pos + 1 + n);
  memset(ans, 0x3f, sizeof ans);
  for(int i = 1; i <= n; i++)
  for(int j = 1; j <= n; j++){
  if(i == 1) dp[i][j] = abs(pos[j] - co[i]);
  else dp[i][j] = ans[j] + abs(pos[j] - co[i]);
  ans[j] = min(dp[i][j], ans[j-1]);
}
 cout << ans[n];
}