寒假训练营第一场补题+题解

A.九小时九个人九扇门

思路：

前置知识：一个数的数字根等于这个数对9取模的结果（特别地，取模得 0则数字根为9）；

对每个数字预处理mod9，则将问题转化为了在1-n人里面，能选取一些人的数字和mod9等于0~8的方案数。典型的DP背包问题： $d p [i] [j]$ 表示可选前i个人，数字和 $m o d 9 = j$ 的方案数，显然状态方程有 $dp[i][j]=dp[i-1][j]+dp[i-1][(j-a[i]+9)\%9]$
注意：当一个人不选时虽然无意义，但为了保证状态转移的正确性，也应算一个方案即dp[0][0]=1。最后输出时减去这个无意义方案即可。复杂度:O(N)

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
const int N = 1e5 + 10;
const int mod = 998244353;
int a[N];
ll dp[N][20];
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] %= 9;
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 9; j++)
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][(j - a[i] + 9) % 9]) % mod;
    dp[n][0]--;
    for (int i = 1; i <= 9; i++)
        cout << dp[n][i % 9] % mod << " ";
    return 0;
}

B.炸鸡块君与FIFA22

思路：

code：

C.Baby's first attempt on CPU

思路：

用 $i d x [i]$ 存储第i个语句后接的空语句数量，按题意判断当前语句和前三个语句是否冲突。若是，则贪心处理在前一个语句后补齐最小需要的空语句即可。复杂度:O(N)

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
const int N = 1e3 + 10;
ll idx[N];
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (a)
        {
            int sum = idx[i - 1];
            if (sum < 3)
            {
                int need = 3 - sum;
                idx[i - 1] += need;
                ans += need;
            }
        }
        if (b)
        {
            int sum = idx[i - 2] + idx[i - 1] + 1;
            if (sum < 3)
            {
                int need = 3 - sum;
                idx[i - 1] += need;
                ans += need;
            }
        }
        if (c)
        {
            int sum = idx[i - 1] + idx[i - 2] + idx[i - 3] + 2;
            if (sum < 3)
            {
                int need = 3 - sum;
                idx[i - 1] += need;
                ans += need;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

D.牛牛做数论

思路：

code：

E.炸鸡块君的高中回忆

思路：

1.当m为1，且n不为1时，显然不可能都进入校园。其他时候，正常计算即可。复杂度:O(1)

code：

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        ll ans=0;
        if(m==1&&n!=1){
            cout<<-1<<endl;
            continue;
        }
        else{
            n-=m;
            ans++;
            int t=0;
            if(n>0){
                t=n/(m-1);
                if(n%(m-1))t++;
            }
            ans+=2*t;
            cout<<ans<<endl;
        }
    }
    return 0;
}

F.中位数切分

思路：

每个分段里面大于等于m的数字比小于m的数字多一个是最优分法,计算整个区间大于等于m的数字比小于m的数字多多少（cnt），若cnt<1则说明不可划分，若cnt>=1则可划分为cnt段。

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--)
    {
        int n, m, cnt1 = 0, cnt2 = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            int w;
            cin >> w;
            w >= m ? cnt1++ : cnt2++;
        }
        int ans = cnt1 - cnt2;
        if (ans >= 1)
            cout << ans << endl;
        else
            cout << -1 << endl;
    }
    return 0;
}

G.ACM is all you need

思路：

code：

H.牛牛看云

思路：

O(1e6)做法：a[i],记录数值为i出现的次数，推公式求贡献即可。
O(nlogn)做法，将a[i]-500，分别维护一个正数和负数的单调序列，分类计算贡献。

code：

O(1e6)

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
const int N = 1e3 + 10;
ll a[N];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        a[t]++;
    }
    ll ans = 0;
    for (int i = 0; i <= 1000; i++)
    {
        ans += ((a[i] + 1) * a[i] / 2) * abs(i + i - (ll)1000);
        for (int j = i + 1; j <= 1000; j++)
            ans += a[i] * a[j] * abs(i + j - (ll)1000);
    }
    cout << ans << endl;
    return 0;
}

O(nlogn)

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
const int N = 1e6 + 10;
ll a[N], b[N], c[N], numa[N], numb[N], sba[N], sbb[N];
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        c[i] = t - 500;
    }
    sort(c + 1, c + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        int t = c[i];
        if (t > 0)
            numa[i] = 1, a[i] = t, sba[i] = t;
        else
            numb[i] = 1, b[i] = t, sbb[i] = t;
        numa[i] += numa[i - 1];
        numb[i] += numb[i - 1];
        a[i] += a[i - 1];
        b[i] += b[i - 1];
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ll t = 0, x = 0, y = 0, z = 0;
        x += abs(c[i] + c[i]);
        int pos1 = lower_bound(sba + i + 1, sba + n, abs(c[i])) - sba;
        int l1 = i, r1 = pos1 - 1, l2 = pos1, r2 = n;
        if (l1 <= r1)
            y += abs(c[i]) * (numa[r1] - numa[l1]) - (a[r1] - a[l1]);
        if (l2 <= r2)
            y += c[i] * (numa[r2] - numa[l2 - 1]) + a[r2] - a[l2 - 1];
        z += abs(c[i] * (numb[n] - numb[i]) + b[n] - b[i]);
        t += x + y + z;
        ans += t;
    }
    cout << ans << endl;
    return 0;
}

I.B站与各唱各的

思路：

code：

J.小朋友做游戏

思路：

若安静的小朋友小于ceil(n/2),则显然不可能有满足条件的取法。
若有满足条件的取法，则对两组小朋友幸福值降序排序，依次比较选择幸福值较大的孩子，同时保证吵闹的孩子不大于安静的孩子即可。复杂度:O(nlogn)

code：

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
const int N = 1e4 + 10;
int a[N], b[N];
bool cmp(int a, int b)
{
    return a > b;
}
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ak
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--)
    {
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        int x, y, n;
        cin >> x >> y >> n;
        for (int i = 1; i <= x; i++)
            cin >> a[i];
        for (int i = 1; i <= y; i++)
            cin >> b[i];
        if (x < ceil((double)n / 2))
        {
            cout << -1 << endl;
            continue;
        }
        sort(a + 1, a + 1 + x, cmp);
        sort(b + 1, b + 1 + y, cmp);
        ll ans = 0, good = 0, bad = 0, idxa = 1, idxb = 1;
        for (int i = 1; i <= n; i++)
        {
            if (a[idxa] >= b[idxb])
            {
                ans += a[idxa++];
                good++;
            }
            else
            {
                if (bad < good)
                    ans += b[idxb++], bad++;
                else
                    ans += a[idxa++], good++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

K.冒险公社

思路：

code：

L.牛牛学走路

思路：

按题意简单模拟即可。复杂度:O(N)

code：

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const double eps=1e-9;
double calu(int dx,int dy){
    double a=dx,b=dy;
    return sqrt((a*a)+(b*b));
}
int main()
{
std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef ak
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t;
    cin>>t;
    while(t--){
        int l;
        string s;
        cin>>l>>s;
        int dx=0,dy=0;
        double ans=0;
        for(int i=0;i<l;i++){
            if(s[i]=='U')dy++;
            if(s[i]=='D')dy--;
            if(s[i]=='L')dx--;
            if(s[i]=='R')dx++;
            ans=max(calu(dx,dy),ans);
        }
        cout<<fixed<<setprecision(10)<<ans<<endl;
    }
    return 0;
}

算法入门题单刷题记录文章被收录于专栏