集训Day 4

王浩泽 / 2023-07-28 / 原文

比赛开始，先看了一眼A题，great！这个数据写一个DFS就可以过100%于是就开始写DFS但是一直爆，数组也没越界，也没开太大，我就十分奇怪，于是就这样调了大约十来分钟发现是因为遍历器的问题（我已经因为遍历器炸了2次了，再也不用遍历器了Q w Q）将遍历器换成正常的for循环就过了（get100pt）。然后看了第二题，em……没有思路，为了保分只能硬着头皮写了两个打表的程序，但是，第二个打表的程序没写好，导致直接浪费了30分钟。（哭）最后一会我就写了一个DFS充数。（get40pt）。总分140

B题题解：

这道题是一道01背包（灵异背包），板子部分不再赘述，按照题意将题目转化为背包容量为S现要求塞入若干个数，每个数的所占空间为其本身大小，装完后要求背包中所有数的最大公约数最大，问最大多少？简单了？

A题程序：

#include<bits/stdc++.h>
using namespace std;
//const int N=1e3;
int n,m,vis[11451],ans=0;
vector<int> mp[19198];
void dfs(int k,int step)
{
    if(step==n) ans++;
    else
    {
        for(int i=0;i<mp[k].size();i++)
        {
            if(vis[mp[k][i]]==0)
            {
                vis[mp[k][i]]=1;
                dfs(mp[k][i],step+1);
                vis[mp[k][i]]=0;
            }
        }
    }
}
int main()
{
    freopen( "hami.in", "r", stdin );
     freopen( "hami.out", "w", stdout );
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        ans=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++) mp[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v;
            cin>>u>>v;
            mp[u].push_back(v);
            mp[v].push_back(u);
        }
        for(int i=1;i<=n;i++) vis[i]=0;
        vis[1]=1;
        dfs(1,1);
        printf("%d\n",ans);
    }
    return 0;
}

B题程序：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int S,sum[N],f[N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>S;
    for(int i=1;i<=S;i++) for(int j=2;i*j<=S;j++) sum[i*j]+=i;
    for(int i=1;i<=S;i++) for(int j=S;j>=1;j--) f[j]=max(f[j],f[j-i]+sum[i]);
    int maxn=-100;
    for(int i=1;i<=S;i++) maxn=max(maxn,f[i]);
    cout<<maxn;
    return 0;
}