第十二届蓝桥杯省赛CC++题解

#include 
#include 
#include 
using namespace std;
const int N = 2200,M=N*50;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];
bool st[N];
int n;
void spfa()  // 求1号点到n号点的最短路距离
{
    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q[tt ++ ] = 1;
    st[1] = true;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}
int gcd(int a, int b)  // 欧几里得算法
{
    return b ? gcd(b, a % b) : a;
}
void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int main()
{
    n  = 2021;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
        for(int j = max(1,i-21);j<=min(1,i+21);j++)
        {
            int d = gcd(i,j);
            add(i,j,i*j/d);
        }
    spfa();
    cout<

#include
using namespace std;
const int N = 110;
const int M = 200010;
const int B = M/2;
int n,m;
int w[N];
bool f[N][M];
int main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ )
    {
        cin>>w[i];
        m+=w[i];
    }
    f[0][B]=true;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = -m; j <=m; j ++ )
        {
            f[i][j+B]=f[i-1][j+B];
            if(j-w[i]>=-m)
            {
                f[i][j+B]|=f[i-1][j-w[i]+B];
            }
            if(j+w[i]<=m)
            {
                f[i][j+B]|=f[i-1][j+w[i]+B];
            }
        }
    }
    int res = 0;
    for (int j = 1; j <=m; j ++ )
    {
        if(f[n][j+B])
        {
            res++;
        }
    }
    cout<