Namomo Fish(Easy) Round 1

C - Number

题目链接
做的时候就感觉是预处理$a_i$变成每个数的步数，然后枚举最终变成的数。不过感觉dist[][]数组开不了那么大，赛后正解真的是这样于是就用map试了一下AC了

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#include<cmath>
#include<queue>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=100010;
int a[N],n,maxa;
unordered_map<int,int> dist[N];
void bfs(int u)
{
    dist[u][u]=0;
    queue<int> q;
    q.push(u);
    while(q.size())
    {
        int t=q.front();q.pop();
        if(t<=maxa/t&&!dist[u].count(t*t)) 
        {
            dist[u][t*t]=dist[u][t]+1; 
            q.push(t*t);
        }
        int y=sqrt(t);
        if(!dist[u].count(y))
        {
            dist[u][y]=dist[u][t]+1;
            q.push(y);
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        maxa=max(maxa,a[i]);
    }
    for(int i=1;i<=n;i++) bfs(a[i]);
    int res=0x3f3f3f3f;
    for(int j=1;j<=maxa;j++)
    {
        int cnt=0;
        bool ok=1;
        for(int i=1;i<=n;i++)
        {
            if(!dist[a[i]].count(j))
            {
                ok=0;
                break;
            }
            cnt+=dist[a[i]][j];
        }
        if(ok) res=min(res,cnt);
    }
    cout<<res<<endl;
}

D - Deadline

题目链接
对原数组排序，$f[i][j]$表示考虑前$i$个deadline完成$j$个所花费的最小天数。对于目前deadline可以考虑做与不做，如果不做$f[i][j]=f[i-1][j]$，如果做那么$f[i][j]=x$，$x$从$f[i-1][j-1]$天开始最少到第$x$天才能完成第$i$个任务

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#include<cmath>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int N=1010;
const int INF=1e7;
ll a[N];
int n,m;
ll f[N][N];// f[i][j] 表示前i个任务 完成j个任务 花费最小天数
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=n;j++)
        {
            f[i][j]=min(f[i][j],f[i-1][j]);
            if(!j||f[i-1][j-1]>INF) continue;
            ll d=f[i-1][j-1]+1;
            if((a[i]-d+1+1)*(a[i]-d+1)/2>=m)
            {
                ll b=-2*a[i]-1,c=(d-1)*(2*a[i]+2-d)+2*m;
                ll delta=sqrt(b*b-4*c);
                ll x=(-b-delta+1)/2;
                f[i][j]=min(f[i][j],x);
            }
        }
    for(int i=n;i>=0;i--)
        if(f[n][i]<INF) 
        {
            cout<<i<<endl;
            return 0;
      	}
}