感想：

估计自己填空题就对了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。