NOTE:没对答案,考场上的代码,不一定对,大佬们轻喷

题目下载链接:https://download.csdn.net/download/ljw_study_in_CSDN/16743273

4.20 更新B题代码,正确答案为40257
5.5 更新C题暴力解法,十分简单
@

A题 卡片(5分)

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10,M=1e7,inf=0x3f3f3f3f;
int vis[N+10],a[N+10];
bool judge(int x)
{
    string s=to_string(x);
    memset(a,0,sizeof(a));
    for(int i=0;s[i];i++)
        a[s[i]-'0']++;
    for(int i=0;i<N;i++)
        if(vis[i]<a[i])return 0;
    for(int i=0;i<N;i++)
        vis[i]-=a[i];
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    for(int i=0;i<N;i++)
        vis[i]=2021;
    for(int i=1;i<=M;i++)
    {
        if(!judge(i))
        {
            printf("%d\n",i-1);
            break;
        }
    }
    return 0;
}

答案:3181

B题 直线(5分)

在这里插入图片描述
如果斜率和截距用double存于map:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=22,inf=0x3f3f3f3f;
bool vis[N],flag[N][N][N][N];
unordered_map<double,unordered_map<double,int> >vis1;
bool judge(int x1,int y1,int x2,int y2)
{
    if(x2==x1) // 垂直于x轴
    {
        if(!vis[x1])
        {
            vis[x1]=1;
            return 1;
        }
        return 0;
    }
    double k=(double(y2-y1))/(double(x2-x1));
    double b=y1-k*x1;
    if(!vis1[k][b])
    {
        vis1[k][b]=1;
        return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m,ans=0;
    cin>>n>>m;
    for(int x1=0;x1<=n;x1++)
    {
        for(int y1=0;y1<=m;y1++)
        {
            for(int x2=0;x2<=n;x2++)
            {
                for(int y2=0;y2<=m;y2++)
                {
                    if(!flag[x1][y1][x2][y2]) // 去重 (x1,y1)(x2,y2) (x2,y2)(x1,y1)
                    {
                        flag[x1][y1][x2][y2]=flag[x2][y2][x1][y1]=1;
                        ans+=judge(x1,y1,x2,y2);
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}
/*
1 2
ans:11

19 20
ans:41509
*/

答案:41509

如果斜率和截距用分数形式存于map:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=22,inf=0x3f3f3f3f;
bool vis[N],flag[N][N][N][N];
unordered_map<int,unordered_map<int,unordered_map<int,unordered_map<int,bool> > > >vis1;
bool judge(int x1,int y1,int x2,int y2)
{
    if(x1==x2) // 垂直于x轴
    {
        if(!vis[x1])
        {
            vis[x1]=1;
            return 1;
        }
        return 0;
    }
    int k1=y2-y1;
    int k2=x2-x1;
    int tk=__gcd(k1,k2);
    k1/=tk;
    k2/=tk;
    int b1=k2*y1-k1*x1;
    int b2=x2-x1;
    int tb=__gcd(b1,b2);
    b1/=tb;
    b2/=tb;
    if(!vis1[k1][k2][b1][b2])
    {
        vis1[k1][k2][b1][b2]=1;
        return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m,ans=0;
    cin>>n>>m;
    for(int x1=0;x1<=n;x1++)
    {
        for(int y1=0;y1<=m;y1++)
        {
            for(int x2=0;x2<=n;x2++)
            {
                for(int y2=0;y2<=m;y2++)
                {
                    if(!flag[x1][y1][x2][y2]) // 去重 (x1,y1)(x2,y2) (x2,y2)(x1,y1)
                    {
                        flag[x1][y1][x2][y2]=flag[x2][y2][x1][y1]=1;
                        ans+=judge(x1,y1,x2,y2);
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}
/*
1 2
ans:11

19 20
ans:47561
*/

答案:47561

按分数形式存比double靠谱,还有就是枚举两个点的时候也要去重,比如(x1,y1)(x2,y2)与(x2,y2)(x1,y1)实际上是一种枚举方式。
但是答案还是错的。

更新正解:

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
struct point
{
    int x,y;
};
vector<point>p; // 存整点
struct node
{
    int a,b,c;
    bool operator < (const node &s) const
    {
        if(a!=s.a)return a<s.a;
        else if(b!=s.b)return b<s.b;
        return c<s.c;
    }
};
set<node>vis; // 存系数a,b,c    ax+by+c=0
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            p.push_back({i,j});
    for(int i=0;i<p.size();i++)
    {
        for(int j=0;j<p.size();j++)
        {
            int x1=p[i].x,y1=p[i].y;
            int x2=p[j].x,y2=p[j].y;
            if(x1==x2||y1==y2)continue; // 平行于坐标轴
            int a=y1-y2;
            int b=x2-x1;
            int c=x1*y2-x2*y1;
            //if(a<0)a=-a,b=-b,c=-c;
            int k=__gcd(__gcd(a,b),c);
            vis.insert({a/k,b/k,c/k});
        }
    }
    printf("%d\n",vis.size()+n+m+2);
    return 0;
}

答案:40257

C题 货物摆放(10分)

在这里插入图片描述
不会...没推出来公式,暴力搞不出

贴一个别人的代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll p[N],d[5],ans=0;
unordered_map<ll,unordered_map<ll,unordered_map<ll,bool>>>vis; // 三维标记
void find(ll a,ll b,ll c)
{
    d[0]=a,d[1]=b,d[2]=c;
    sort(d,d+3);
    if(!vis[d[0]][d[1]][d[2]])
    {
        vis[d[0]][d[1]][d[2]]=1;
        do
        {
            ans++;
        }while(next_permutation(d,d+3));
    }
}
int main()
{
    ll n=2021041820210418;
    int cnt=0;
    for(int i=1;i<=(ll)(sqrt(n));i++)
    {
        if(n%i==0)
        {
            p[++cnt]=i;
            p[++cnt]=n/i;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j<=cnt;j++)
        {
            if(p[i]*p[j]>n)continue;
            if(n%(p[i]*p[j])==0)
            {
                ll c=n/(p[i]*p[j]);
                find(p[i],p[j],c);
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

答案:2430

更新暴力解法:
其实不用分解素因子,直接$O(\sqrt{n})$暴力求出所有因子,发现只有128个,然后直接三层循环判断三个因子相乘是否为n即可:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n=2021041820210418,ans=0;
vector<ll>fac;
int main()
{
    for(ll i=1;i*i<=n;i++)
        if(n%i==0)fac.push_back(i),fac.push_back(n/i);
    int sz=fac.size(); // 128个因子
    for(int i=0;i<sz;i++)
        for(int j=0;j<sz;j++)
            for(int k=0;k<sz;k++)
                if(fac[i]*fac[j]*fac[k]==n)ans++;
    printf("%lld\n",ans);
    return 0;
}

D题 路径(10分)

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2021+100,M=N*N+10;
const ll inf=0x7f7f7f7f7f7f7f7f;
ll head[N],cnt,dis[N];
bool vis[N],flag[N][N];
struct edge
{
    ll to,w,next;
}e[M<<1];
void add(ll x,ll y,ll z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(ll x,ll y)
{
    ll z=x/__gcd(x,y)*y;
    add(x,y,z);
    add(y,x,z);
}
struct node
{
    ll u,w;
    bool operator < (const node &s) const
    {
        return w>s.w;
    }
};
ll dijkstra(ll s,ll t)
{
    memset(dis,inf,sizeof(dis));
    priority_queue<node>q;
    q.push({s,0});
    dis[s]=0;
    while(!q.empty())
    {
        node tmp=q.top();q.pop();
        ll u=tmp.u;
        if(vis[u])continue;
        vis[u]=1;
        for(ll i=head[u];i!=-1;i=e[i].next)
        {
            ll v=e[i].to;
            ll w=e[i].w;
            if(dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
    return dis[t];
}
int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    ll n=2021; 
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=n;j++)
        {
            if(i!=j&&!flag[i][j]&&abs(i-j)<=21)
            {
                flag[i][j]=flag[j][i]=1;
                add_edge(i,j);
            }
        }
    }
    ll ans=dijkstra(1,n);
    printf("%lld\n",ans);
    return 0;
}

答案:10266837

E题 回路计数(15分)

在这里插入图片描述
不会...暴力搞不出,不会剪枝...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110,inf=0x3f3f3f3f;
vector<int>g[N];
bool vis[N];
ll n,ans=0;
void dfs(int u,int cnt)
{
    for(auto v:g[u])
    {
        if(cnt==n&&v==1) // 已经走满,再走下一个点就是起点了
            ans++;
        if(!vis[v])
        {
            vis[v]=1;
            dfs(v,cnt+1);
            vis[v]=0;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n; // n=21
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(__gcd(i,j)==1)g[i].push_back(j),g[j].push_back(i);
    vis[1]=1;
    dfs(1,1);
    printf("%lld\n",ans);
    return 0;
}

F题 砝码称重(15分)

在这里插入图片描述
在这里插入图片描述
牛客上有个类似的题 小M和天平

但是我只会暴力,骗点分QAQ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110,inf=0x3f3f3f3f;
ll n,a[N],ans=0;
bool use[N];
unordered_map<ll,bool>vis;
void dfs(ll x)
{
    for(ll i=1;i<=n;i++)
    {
        if(!use[i])
        {
            use[i]=1;
            // 加
            ll y1=x+a[i];
            if(!vis[y1])
            {
                ans++;
                vis[y1]=1;
                dfs(y1);
                y1-=a[i]; // 还原
            }
            // 减
            ll y2=x-a[i];
            if(y2>0&&!vis[y2])
            {
                ans++;
                vis[y2]=1;
                dfs(y2);
                y2+=a[i]; // 还原
            }
            use[i]=0; // 还原
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1,greater<ll>());
    dfs(0);
    printf("%lld\n",ans);
    return 0;
}

G题 异或序列(20分)

在这里插入图片描述
在这里插入图片描述
不会...(看到有大佬说,特判一下平局,然后先手必赢?)

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

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
我的思路是每次往下找拥有直接相连的孩子数最多的点,若有k个孩子,则层数最多就能加k。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,inf=0x3f3f3f3f;
int n,mx=0,dp[N],child[N];
vector<int>g[N];
void dfs(int u)
{
    int sz=g[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        dp[v]=dp[u]+child[u];
        mx=max(mx,dp[v]);
        dfs(v);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    int fa;
    for(int i=2;i<=n;i++)
    {
        cin>>fa;
        child[fa]++; // 点fa的孩子数量
        g[fa].push_back(i); // fa -> i
    }
    dfs(1);
    printf("%d\n",mx);
    return 0;
}
/*
1
ans:0

2
1
ans:1

9
1 1 3 3 3 5 5 6
ans:7

14
1 1 1 2 4 5 5 5 6 6 6 11 11
ans:9
*/

I题 括号序列(25分)

在这里插入图片描述
不会...

J题 分果果(25分)

在这里插入图片描述
在这里插入图片描述
不会...