头像

繁花似锦

南京理工大学




离线:1天前


活动打卡代码 AcWing 1064. 小国王

思路点:

1.第i行的状态只与第i-1行状态有关,启示我们可以用DP来做

2.第i行的状态已经确定了,f[i][j][s],s是状态压缩后的值,考虑前i-1行转移过来, 假设i-1行状态是b,i行状态是a,满足条件:(a&b)==0&&check(a|b), check():不能有两个相邻的1

3.大多数状态都是无效的,预处理出来 有效状态 满足时间复杂度

国王.jpg

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;//应该是溢出了对吧,所以我们要把所有的f改成long long 

const int N=12;//待会儿我会给大家解释一下为什么要开到12

const int M=1<<10,K=110;//K是我们的国王数量

int n,m;//这里用m来表示国王数量,因为我习惯用n来表示一个数然后m来表示另外一个值

vector<int> state; //state 用来表示所有的合法的状态

int id[M];//id的话是存这个每一个状态和这个它的下标之间的映射关系 id有用到吗?好像没有用到
//应该是我之前写的时候思路不太一样,想的时候可能,就是前面设计的思路和实际用到的思路可能会有一点区别
//所以这里其实是不要加id i 的

vector<int> head[M];//这个是每一状态所有可以转移到的其他状态

int cnt[M];/*然后cnt的话存的是每个状态里面 1 的个数,因为我们刚才我们的状态转移方程里面,
其实有一个需要求这个每一个状态里面1的个数的一个过程对吧*/

LL f[N][K][M];//这就是我们刚才说的那个状态表示

bool check(int state)
{
    for(int i=0;i<n;i++)
     if((state >> i & 1)&&(state >> i + 1 & 1))
       return false;//如果存在连续两个1的话就不合法

    return true;//否则的话就是合法的
}

int count(int state)//这里y总没具体解释,我补充一下,这里就是计算某个数二进制里面1的个数
{
    int res=0;

    for(int i=0;i<n;i++)res+=state>>i&1;

    return res;
}

int main()
{
    cin>>n>>m;

    //首先我们需要把所有合法状态处理出来对吧,把它预处理一下
    for(int i=0;i<1<<n;i++)
       if(check(i))
    /*check函数是检查一下我们当前状态是不是合法,也就是检查一下我们这个状态里面是不是存在连续的两个1,
    如果不存在的话就表示它是合法的*/
       {
           state.push_back(i);
           id[i]=state.size()-1;//id存的是我们这个合法状态对应的下标是多少
           cnt[i]=count(i);//cnt的话存的是这个i里面 1 的个数是多少
       }

    //然后我们来看一下这个不同状态之间的一个这个边的关系
    for(int i = 0;i< state.size();i ++ )
      for(int j=0;j<state.size();j++)
      {
          //用a来表示第一个状态,用b来表示第二个状态
          int a=state[i],b=state[j];
          //这里是建立一个不同状态之间的转移关系
          //先预处理一下哪些状态和哪些状态之间可以转移
          //首先转移的话是要满足两个条件对吧
          //一个是这个 a 和 b 的交集必须要是空集,它必须是空集才可以,否则的话同一列的两个国王会攻击到
          //并且的话它们的这个这个并集的话也是需要去满足我们不能包含两个相邻的1的
          if((a&b)==0&&check(a|b))
             // head[a].push_back(b);
             //然后只要这个 b 是合法的,那么我们就把 b 添加到 a 可以转移到的状态集合里面去
             //这里y总第一次写错了,debug了
             head[i].push_back(j);

             //这里是debug过程
             //这里写错了,这里应该是head[i].push_back(j);
             //因为咱么这里去做的时候用的是下标,不是一个状态的值
      }

      //好,那剩下的就是 DP 了对吧

      f[0][0][0]=1;
      //最开始的时候,我们f[0][0][0]=1
      /*什么意思呢,就是说,前0行对吧,我们前0行已经摆完了,其实也就是一行也没有摆的情况下,
      那么此时由于我们这个是在棋盘外面,
      所以肯定每个国王都不能摆对吧,所以我们就只有0这个状态时合法的,那么这个状态的方案数是1*/

      //好,然后从前往后枚举每一种状态

      for(int i=1;i<=n+1;i++)
         for(int j=0;j<=m;j++)//j的话是从0到m对吧,m表示的是国王数量
           for(int a=0;a<state.size();a++)//然后我们来枚举一下所有的状态,a表示第i行的状态
             for(int b : head[a])//然后来枚举所有a能到的状态
             {
                 //这里要判断一下
                 //首先要判断的是
                 //求一下我们a里面的一个1的个数对吧
                 int c=cnt[state[a]];
                 //好,然后如果说,呃,就我们的j必须要大于等于c对吧,j是必须要大于等于c的
                 //为什么呢,因为我们这个表示我们当前这行摆放的国王数量一定要小于等于我们整个的上限对吧
                 if(j>=c)//如果数说满足要求的话,那么我们就可以转移了
                 {
                     f[i][j][a]+=f[i-1][j-c][b];
                     //转移的话就是f[i][j][a]+=f[i-1][j-c][b],然后从b转移过来
                 }
             }

    //好,那我们最终的答案是什么呢?
    //我们的最终的答案应该是这个f[n][m][ ],然后最后一维可以直接去枚举对不对
    //去枚举一下最后一维是从,就是所有合法状态都是可以的,就最后一行它所有合法状态都是可以的对不对
    //那这里的话我们可以偷个懒,不是偷个懒,我们可以有个小技巧,就是我们在枚举i的时候,枚举到n+1就可以了
    //就是我们去算到第i+1行,假设我们的棋盘是一个n+1 * n的一个棋盘,多了一行
    /*那么我们最终算的时候 就需要输出一个 f[n+1],就是第n+1行,
    一共摆到了第n+1行,然后m,然后0,因为第n+1行一个都没摆,对吧*/

    cout<<f[n+1][m][0]<<endl;
    /*就是我们假设存在第n+1行,但是第n+1行完全没有摆,
    那这种情况里面的所有方案其实就是等于这个这个我们只有n行的一个所有方案,对吧*/
    /*那这样枚举n+1的一个好处是我们最后不需要再循环枚举最后一行的状态了,
    就是我们这个f[n+1][m][0]已经在这个循环里面被循环算出来了*/
    //所以可以少一层循环
    /*这里的话就是为什么我们一开始N要从12开始,对吧,首先我们要用到11这个下标对吧,
    那其实11这个下标是需要开长度是12才可以*/
    return 0;
}




二叉搜索树的性质:按照中序遍历是递增的

这道题既考察了树的深搜,也考察了宽搜,是道好题!

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int w[N], l[N], r[N];
int a[N], q[N];

void dfs(int u,int &k)
{
    if(u == -1) return;
    dfs(l[u],k);
    w[u] = a[k ++];
    dfs(r[u],k);
}

void bfs()
{
    int hh = 0, tt = 0;
    q[0] = 0;
    while(hh <= tt)
    {
        int t = q[hh ++];
        cout << w[t] << ' ';
        if(l[t] != -1) q[++ tt] = l[t];
        if(r[t] != -1) q[++ tt] = r[t];
    }
}


int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++ ) cin >> l[i] >> r[i];
    for(int i = 0;i < n;i ++ ) cin >> a[i];
    sort(a,a + n);

    int k = 0;
    dfs(0,k);
    bfs();

    return 0;
}



二叉搜索树的性质:按照中序遍历是递增的

这道题既考察了树的深搜,也考察了宽搜,是道好题!

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int w[N], l[N], r[N];
int a[N], q[N];

void dfs(int u,int &k)
{
    if(u == -1) return;
    dfs(l[u],k);
    w[u] = a[k ++];
    dfs(r[u],k);
}

void bfs()
{
    int hh = 0, tt = 0;
    q[0] = 0;
    while(hh <= tt)
    {
        int t = q[hh ++];
        cout << w[t] << ' ';
        if(l[t] != -1) q[++ tt] = l[t];
        if(r[t] != -1) q[++ tt] = r[t];
    }
}


int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++ ) cin >> l[i] >> r[i];
    for(int i = 0;i < n;i ++ ) cin >> a[i];
    sort(a,a + n);

    int k = 0;
    dfs(0,k);
    bfs();

    return 0;
}



利用上二叉搜索树的性质:左小右大

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if(!root) return 0;
        if(root->val > high) return rangeSumBST(root->left,low, high);
        if(root->val < low) return rangeSumBST(root->right,low, high);
        return root->val + rangeSumBST(root->left,low, high) + rangeSumBST(root->right,low,high);
    }
};

搜索

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        int ans = 0;
        dfs(root,low,high,ans);
        return ans;
    }

    void dfs(TreeNode* root,int low,int high,int &ans)
    {
        if(!root) return;
        int v = root->val;
        if(v >= low && v <= high) ans += v;
        dfs(root->left,low,high,ans);
        dfs(root->right,low,high,ans);
    }
};



感想:

估计自己填空题就对了D吧(10分),A,B不应该。
编程题F,G,I 过了样例,能骗点分吗?

赛前想冲国赛,赛后退我报名费就行…
10分能拿省一吗
自己还是要多做生题吧,不然题目稍稍一变就不会了.......
白给,我总是白给,可恶!

@[toc]

试题 A: 卡片(5分)(枚举)

在这里插入图片描述

俺要裂开了,好像在考场上写的是3182,拿样例测的,没发现11不能拼出,裂开。

答案:3181

#include <iostream>

using namespace std;

int cnt[10];

bool check(int x)
{
    while(x){
        int t = x % 10;
        cnt[t] --;
        if(cnt[t] < 0) return false;
        x /= 10;
    }
    return true;
}

int main()
{
    for(int i = 0;i <= 9;i ++) cnt[i] = 2021;

    int j = 1;
    while(1){
        if(check(j)) j ++ ;
        else break;
    }
    cout << j - 1 << endl; // 这里要 -1

    return 0;
}

试题 B: 直线(5分)(枚举)

在这里插入图片描述

考场上写的,==错误解法==,double炸精度了,裂开

#include <iostream>
#include <set>

using namespace std;

const int N = 30;

int lenx = 19,leny = 20;
int x[N],y[N];

int main()
{
    set<pair<double,double>> res;
    set<int> res2;

    for(int x1 = 0;x1 <= lenx;x1 ++ )
        for(int x2 = 0;x2 <= lenx;x2 ++ )
            for(int y1 = 0;y1 <= leny;y1 ++ )
                for(int y2 = 0;y2 <= leny;y2 ++ )
                {
                    if(x1 == x2 && y1 == y2) continue;
                    if(x1 - x2 == 0){
                        res2.insert(x1);
                    }else{
                        double k = (double)(y1 - y2) / (double)(x1 - x2);
                        double b = y1 - k * x1;
                        res.insert({k,b});
                    }
                }

    cout << res.size() + res2.size();
    return 0;
}

答案:40257

根据直线两点式推导转换成直线一般方程ax+by+c=0(见下图)这样就不用考虑斜率是否存在、避免除法的困扰了,通过除以公约数使a,b,c互质,放入set去重就行了
在这里插入图片描述

#include <iostream>
#include <set>

using namespace std;

const int N = 30;

int lenx = 19,leny = 20;
int x[N],y[N];

int gcd(int a,int b)
{
    return b ? gcd(b,a % b) : a;
}

int main()
{
    set<pair<int,pair<int,int>>> res;
    set<int> res2;

    for(int x1 = 0;x1 <= lenx;x1 ++ )
        for(int x2 = 0;x2 <= lenx;x2 ++ )
            for(int y1 = 0;y1 <= leny;y1 ++ )
                for(int y2 = 0;y2 <= leny;y2 ++ )
                {
                    if(x1 == x2 && y1 == y2) continue;
                    int a = y1 - y2,b = x2 - x1;
                    int c = -y1 * (x2 - x1) + x1 * (y2 - y1);
                    int d = gcd(a,gcd(b,c));
                    a = a/d, b = b/d, c = c/d;
                    res.insert({a,{b,c}});
                }

    cout << res.size() + res2.size();
    return 0;
}

试题 C: 货物摆放(10分)(质因数分解)

在这里插入图片描述

答案:2430

三重循环暴力是暴力不出来的了,考场上想到了质因数分解,然而没进一步往下想,不会。

在这里插入图片描述

别人的题解

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL yue[101000],cnt;

int main()
{
    LL n=2021041820210418;
    for(LL i=1;i<=n/i;i++){
        if(n%i==0){
            yue[++cnt]=i;
            if(i*i!=n)
                yue[++cnt]=n/i;
        }
    }
    //sort(yue+1,yue+cnt+1);
    //for(int i=1;i<=cnt;i++)cout<<yue[i]<<" ";
    //cout<<cnt;
    int ans=0;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            if(n%(yue[i]*yue[j])==0)
                ans++;
        }
    }
    cout<<ans;
    return 0;
}

试题 D: 路径(10分)(最短路)

在这里插入图片描述

答案:10266837

终于有一题会了,最短路模板题,朴素dijkstra

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2050;

int g[N][N];
bool st[N];
int dist[N];
int n = 2021;

int gcd(int a,int b)
{
    return b ? gcd(b,a % b) : a;
}

int lcm(int a,int b)
{
    return a * b / gcd(a,b);
}

void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

    for(int i = 0;i < n;i ++ ) 
    {
        int t = -1;
        for(int j = 1;j <= n;j ++)
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true;

        for(int j = 1;j <= n;j ++ )
            dist[j] = min(dist[j],dist[t] + g[t][j]);
    }
}


int main()
{
    memset(g,0x3f,sizeof g);
    for(int i = 1;i <= 2021;i ++ )
        for(int j =i + 1;j <= 2021;j ++ )
            if(j - i <= 21) g[i][j] = g[j][i] = lcm(i,j);

    dijkstra();

    cout << dist[n];

    return 0;
}

试题 E: 回路计数(15分)

在这里插入图片描述

知道基础课有个类似题,但是没复习状压DP,不会。

答案:881012367360

错误写法,自己写的,不知道错在哪..(答案还需要加上回到原点)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 22, M = 1 << N;

int n = 21;
bool st[N][N];
long long f[M][N]; // f[i][j] : 经过路径是i(i是状态压缩),最后停留在j  ans = f[(1 << n) - 1][n - 1]
                // 划分依据:倒数第2点是多少 

int gcd(int a,int b)
{
    return b ? gcd(b,a % b) : a;
}

int main()
{
    for(int i = 1;i <= n;i ++) // 映射到0 - 20 
        for(int j = 1;j <= n;j ++ )
            if(gcd(i ,j ) == 1) st[i - 1][j - 1] = st[j - 1][i - 1] =  true;

    f[1][0] = 1;
    for(int i = 0;i < (1 << n);i ++ )
        for(int j = 0;j < n;j ++ )
            if(i >> j & 1)
                for(int k = 0;k < n;k ++ )
                    if(i >> k & 1 && st[k][j])  f[i][j] += f[i - (1 << j)][k]; 

    cout << f[(1 << n) - 1][n - 1];
    // ans:12059283456 
    return 0;
}

正解:一样的题 – AcWing 731. 毕业旅行问题【集合类状态压缩DP】

#include <iostream>
#include <cstring>

using namespace std;

const int N = 22, M = 1 << N;

int n = 21;
bool st[N][N];
long long f[M][N]; // f[i][j] : 经过路径是i(i是状态压缩),最后停留在j  ans = f[(1 << n) - 1][n - 1]
                // 划分依据:倒数第2点是多少 

int gcd(int a,int b)
{
    return b ? gcd(b,a % b) : a;
}

int main()
{
    for(int i = 1;i <= n;i ++) // 映射到0 - 20 
        for(int j = 1;j <= n;j ++ )
            if(gcd(i ,j ) == 1) st[i - 1][j - 1] = st[j - 1][i - 1] =  true;

    f[1][0] = 1;
    for(int i = 0;i < (1 << n);i ++ )
        for(int j = 0;j < n;j ++ )
            if(i >> j & 1)
                for(int k = 0;k < n;k ++ )
                    if(i >> k & 1 && st[k][j])  f[i][j] += f[i - (1 << j)][k]; 

    long long ans = 0;
    for(int i = 1;i < n;i ++ )
        ans += f[(1 << n) - 1][i];

    cout << ans << endl;
    // ans:881012367360
    return 0;
}

试题 F: 砝码称重(15分)

在这里插入图片描述在这里插入图片描述在这里插入图片描述

一上来就DP?我是用背包DP做的,过了样例,不知道对不对。

试题 G: 异或数列(20分)

在这里插入图片描述在这里插入图片描述在这里插入图片描述

我在考场上的想法:异或不就是不进位加法吗?排序加和? 博弈类不会…

试题 H: 左孩子右兄弟(20分)

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

不会,没看懂题目意思,空白了。

试题 I: 括号序列(25分)

在这里插入图片描述在这里插入图片描述

简单写了个区间DP,估计也是错的,过了样例。

试题 J: 分果果(25分)

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

不会,暴力也不会,我是菜b。




类似题求方案数 - 2021第十二届蓝桥杯大赛软件赛省赛C++大学A组 – 试题 E: 回路计数

N 最多开到20,21就不行了

/*
    f[i][j] : 经过路径是i,且停留在j的花费
        属性:最小值 
        ans: f[(1 << n) - 1][j] + w[j][0] , f[1][0] = 0;
        对比 91. 最短Hamilton路径,答案 还需要回到原点

    f[i][j] = f[i - {j}][k] + w[k][j];
*/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20, M = 1 << N;

int n;
int w[N][N];
int f[M][N];

int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++ )
        for(int j = 0;j < n;j ++ )
            cin >> w[i][j];

    memset(f,0x3f,sizeof f);
    f[1][0] = 0;

    for(int i = 0;i < (1 << n) ;i ++ )
    {
        for(int j = 0;j < n;j ++ )
            if(i >> j & 1)
                for(int k = 0;k < n;k ++ )
                    if( (i - (1 << j)) >> k & 1) 
                        f[i][j] = min(f[i][j],f[i - (1 << j)][k] + w[k][j]);
    }

    // 枚举所有到达出发点前一个城市的状态并取最小值
    int ans = 0x3f3f3f3f;
    for(int i = 1;i < n;i ++ )
        ans = min(ans, f[(1 << n) - 1][i] + w[i][0]); 

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 524. 愤怒的小鸟

y总题解
更清楚的题解

本题考虑以下问题

愤怒的小鸟.jpg

时间复杂度

时间复杂度.jpg

易错点记录:
2. 多组测试数据,清空数组path[]
1. f[i | path[x][j]]

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 18, M = 1 << 18;
const double eps = 1e-8;

int n, m;
PDD q[N];
int path[N][N]; // 两点确定一条抛物线,path[i][j]:表示点i和点j所能覆盖的小猪
int f[M]; // f[state]:表示覆盖状态state的最少 抛物线数量

int cmp(double x, double y) // 浮点数比较
{
    if (fabs(x - y) < eps) return 0;
    if (x < y) return -1;
    return 1;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n >> m;
        for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;

        memset(path, 0, sizeof path);
        for (int i = 0; i < n; i ++ )
        {
            path[i][i] = 1 << i;
            for (int j = 0; j < n; j ++ )
            {
                double x1 = q[i].x, y1 = q[i].y;
                double x2 = q[j].x, y2 = q[j].y;
                if (!cmp(x1, x2)) continue; // 不存在斜率无限大的情况
                // 两点计算抛物线
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;

                if (cmp(a, 0) >= 0) continue; // 抛物线要开口向下
                int state = 0;
                for (int k = 0; k < n; k ++ )
                {
                    double x = q[k].x, y = q[k].y;
                    if (!cmp(a * x * x + b * x, y)) state += 1 << k;
                }
                path[i][j] = state;
            }
        }

        memset(f, 0x3f, sizeof f);
        f[0] = 0;
        for (int i = 0; i + 1 < 1 << n; i ++ )
        {
            // 找到还没有被覆盖的小猪
            int x = 0;
            for (int j = 0; j < n; j ++ )
                if (!(i >> j & 1))
                {
                    x = j;
                    break;
                }
            // 更新
            for (int j = 0; j < n; j ++ )
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
        }

        cout << f[(1 << n) - 1] << endl;
    }

    return 0;
}

状态压缩DP两类题
状压DP的两类题.jpg




如题



活动打卡代码 AcWing 2068. 整数拼接

哈希表

/*

    (A[i] * A[j].size() + A[j]) % k == 0
   = (A[i] * A[j].size()) = -A[j] % k;


*/

#include <iostream>

using namespace std;

const int N = 100010;

typedef long long LL;

int n,k;
int a[N];
int s[11][N];

int get(int n)
{
    int res = 0;
    while(n) res ++, n/=10;
    return res;
}

int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i ++ ) cin >> a[i];

    for(int i = 0;i < n;i ++ )
    {
        LL t = a[i] % k;
        for(int j = 0;j < 11;j ++ ) // 10 ^ 9,总共有10位,开0-10的哈希表11个
        {
            s[j][t] ++;
            t = t * 10 % k;
        }
    }

    LL res = 0;
    for(int i = 0;i < n;i ++)
    {
        LL t = a[i] % k;
        int len = get(a[i]);
        res += s[len][(k - t) % k]; // (k - t) % k, 数学意义上的取模

        // 判重
        LL r = t;
        while(len --) r = r * 10 % k;
        if(r == (k - t) % k) res --;
    }

    cout << res << endl;

    return 0;
}



@[toc]

6-10题Acwing均有提交地址

第一题:跑步训练(模拟)

在这里插入图片描述

答案:3880

#include <iostream>

using namespace std;

int main()
{
    int res = 0;
    int sum = 10000;

    while(sum >= 600){
        res += 120; // 跑步 + 休息
        sum -= 300;
    }

    res += sum / 10; // 不够一个周期了,每s损耗体力

    cout << res;

    return 0;
}

第二题:合并检测(数学,均值不等式)

在这里插入图片描述

答案:10

在这里插入图片描述

第三题:分配口罩(搜索,dfs)

在这里插入图片描述

答案:2400

#include <iostream>

using namespace std;

int nums[] = {9090400, 8499400, 5926800, 8547000, 4958200, 4422600, 5751200,
4175600, 6309600, 5865200, 6604400, 4635000, 10663400, 8087200, 4554000};

int ans = 1e9;

void dfs(int u,int s1,int s2)
{
    if(u == 15){
        ans = min(ans,abs(s1 - s2));
        return;
    }
    dfs(u + 1,s1 + nums[u],s2);
    dfs(u + 1,s1,s2 + nums[u]);
}

int main()
{
    dfs(0,0,0);
    cout << ans;

    return 0;
}

写法2:二进制搜索

#include <iostream>

using namespace std;

int nums[] = {9090400, 8499400, 5926800, 8547000, 4958200, 4422600, 5751200,
4175600, 6309600, 5865200, 6604400, 4635000, 10663400, 8087200, 4554000};

int ans = 1e9;

void dfs()
{
    for(int i = 0;i < (1 << 15);i ++ )
    {
        int s1 = 0,s2 = 0;
        for(int k = 0;k < 15;k ++ )
            if((i >> k) & 1) s1 += nums[k];
            else s2 += nums[k];
        ans = min(ans,abs(s1 - s2));
    }
}

int main()
{
    dfs();
    cout << ans;

    return 0;
}

第四题:矩阵(动态规划)

在这里插入图片描述

答案1340

在这里插入图片描述

#include <iostream>

using namespace std;

int mod = 2020;
int f[2030][1020];

int main()
{

    f[0][0] = 1;
    for(int i = 1;i <= 2020;i ++ )
        for(int j = 1;j <= i;j ++ )
        {
            f[i][j] = (f[i][j] + f[i - 1][j - 1]) % mod;
            if(i - j <= j) f[i][j] = (f[i][j] + f[i - 1][j]) % mod; // f[i][j]合理才转移
            /*
                说明:j 是第一行放的数量,i - j则是第二行放的数量
                第二行的数量不能大于第一行的数量,因为 是从前i个中顺序选的
                举例:假如第二行的数量 大于 第一行的数量
                1
                2 3 
                那么 4 只能接在 3后面,这样的情况放不满矩阵
            */
        }

    cout << f[2020][1010] << endl;

    return 0;
}

第五题:完美平方数

在这里插入图片描述

第六题:解码(模拟)

在这里插入图片描述

#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;

    string res;
    for(int i = 0;i < s.size();i ++ )
    {
        if(s[i] >= '0' && s[i] <= '9') continue;
        int cnt = 0;
        if(i + 1 < s.size() && s[i + 1] >= '0' && s[i + 1] <= '9') cnt = s[i + 1] - '0';
        if(cnt > 0){
            while(cnt -- ) res += s[i];
        }else res += s[i];
    }

    cout << res << endl;

    return 0;
}

第七题:走方格(动态规划)

在这里插入图片描述

#include <iostream>

using namespace std;

const int N = 32;

int n,m;
int f[N][N];

int main()
{
    cin >> n >> m;

    f[1][1] = 1;

    for(int i = 1;i <= n;i ++ )
        for(int j = 1;j <= m;j ++ )
        {
            if(i == 1 && j == 1) continue;
            if(i % 2 == 0 && j % 2 == 0) continue;
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }

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

    return 0;
}

第八题:整数拼接(哈希表)

在这里插入图片描述

题解

/*

    (A[i] * A[j].size() + A[j]) % k == 0
   = (A[i] * A[j].size()) = -A[j] % k;

*/

#include <iostream>

using namespace std;

const int N = 100010;

typedef long long LL;

int n,k;
int a[N];
int s[11][N];

int get(int n)
{
    int res = 0;
    while(n) res ++, n/=10;
    return res;
}

int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i ++ ) cin >> a[i];

    for(int i = 0;i < n;i ++ )
    {
        LL t = a[i] % k;
        for(int j = 0;j < 11;j ++ ) // 10 ^ 9,总共有10位,开0-10的哈希表11个
        {
            s[j][t] ++;
            t = t * 10 % k;
        }
    }

    LL res = 0;
    for(int i = 0;i < n;i ++)
    {
        LL t = a[i] % k;
        int len = get(a[i]);
        res += s[len][(k - t) % k]; // (k - t) % k, 数学意义上的取模

        // 判重
        LL r = t;
        while(len --) r = r * 10 % k;
        if(r == (k - t) % k) res --;
    }

    cout << res << endl;

    return 0;
}

第九题:超级胶水(贪心)

在这里插入图片描述

题解

#include<iostream>

using namespace std;

int n,x;

int main()
{
    cin>>n;

    long long  sum=0,res=0;
    for(int i=0;i<n;i++){
        cin>>x;
        res += sum * x;
        sum += x;
    }

    cout<<res<<endl;
    return 0;
}

第十题:网络分析(带权并查集)

在这里插入图片描述在这里插入图片描述在这里插入图片描述

详细题解

#include <iostream>

using namespace std;

const int N = 10010;

int n,m;
int p[N],v[N],d[N];

int find(int x)
{
    if(p[x] != x)
    {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}

int main()
{
    cin >> n >> m;

    for(int i = 1;i <= n;i ++ ) p[i] = i;

    for(int i = 0;i < m;i ++ )
    {
        int t,a,b;
        cin >> t >> a >> b;
        if(t == 1){
            int pa = find(a), pb = find(b);
            if(pa != pb)
            {
                d[pa] += v[pa] - v[pb];
                p[pa] = pb;    
            }
        }else{
            int pa = find(a);
            v[pa] += b;
        }
    }

    for(int i = 1;i<= n;i ++) 
        cout << v[find(i)] + d[i] << ' ';

    return 0;
}