2020牛客多校第七場 解題報告BDH

題目連結：https://ac.nowcoder.com/acm/contest/5672

A-Social Distancing

B-Mask Allocation 

題意

• 将n*m個口罩分成k份，使得可以從中挑出n組，每組口罩一樣多；或者從中挑出m組，每組口罩一樣多，最後輸出字典序最大。

思路

• 思維。不難發現，若 n>m，每次向答案中加入的就是 m 個 m，然後再對 (n-m,m) 進行分組，類似于輾轉相除法求gcd。

 AC代碼

#include <bits/stdc++.h>
#define LL long long
#define sc(a) scanf("%d", &a)
#define sc2(a, b) scanf("%d%d", &a, &b)
#define sc3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define scl(a) scanf("%lld", &a)
#define scl2(a, b) scanf("%lld%lld", &a, &b)
#define ss(a) scanf("%s", a)
#define mem(a, b) memset(a, b, sizeof(a))
#define PII pair<int, int>
using namespace std;
const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
int main()
{
    int t;
    sc(t);
    while (t--)
    {
        int n, m;
        sc2(n, m);
        vector<int> v;
        while (n && m)
        {
            if (n < m)
                swap(n, m);
            // cout << "n: " << n << endl;
            // cout << "m: " << m << endl;
            n = n - m;
            for (int i = 1; i <= m; i++)
                v.push_back(m);
        }
        int f = 0;
        cout << v.size() << endl;
        for (auto i : v)
        {
            if (f)
                cout << " ";
            f = 1;
            cout << i;
        }
        cout << endl;
    }
    system("pause");
    return 0;
}
           

D- Fake News 

題意

• 給t組整數n，問

  

  是不是一個完全平方數。
• 如果是的話，輸出"Fake news!",
• 否則輸出“Nobody knows it better than me!”

思路

• 打個表就會發現隻有1 和24滿足條件，其他的都不滿足 

AC代碼

#include <bits/stdc++.h>
#define LL long long
#define sc(a) scanf("%d", &a)
#define sc2(a, b) scanf("%d%d", &a, &b)
#define sc3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define scl(a) scanf("%lld", &a)
#define scl2(a, b) scanf("%lld%lld", &a, &b)
#define ss(a) scanf("%s", a)
#define mem(a, b) memset(a, b, sizeof(a))
#define PII pair<int, int>
using namespace std;
const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        LL n;
        scanf("%lld", &n);
        if (n == 1 || n == 24)
            printf("Fake news!\n");
        else
            printf("Nobody knows it better than me!\n");
    }
    system("pause");
    return 0;
}
           

H-Dividing 

題意

•  規定傳奇元組（n,k）
• (1,k)總是傳奇元組
• 如果說（n,k）是傳奇元組的話，(n+k,k)和(n*k,k)都是傳奇元組
• 統計有多少個傳奇元組(i,j)滿足（1<=i<=N，1<=j<=K） 

思路

以（6 ，6）為例，傳奇元組是

（1，1）（2，1）（3，1）（4，1）（5，1）（6，1）

（1，2）（2，2）（3，2）（4，2）（5，2）（6，2）

（1，3）（3，3）（4，3）（6，3）

（1，4）（4，4）（5，4）

（1，5）（5，5）（6，5）

（1，6）（6，6）

1. n=1，都是傳奇數組
2. k=1的可以從（1，1）然後按照（n+k，k）的原則，使得k=1的都是傳奇數組 
3. 然後是其他情況，可以從（1，k）擴充成（1*k，k）、（k+1，k）、（k*2，k）、（k*2+1，k）...... 是以每行除去1，2兩種情況的就是

   

   ，其中

   

   是向下取整的結果。

接下來就是求 

這個公式了，代碼裡有解釋

AC代碼 

#include <bits/stdc++.h>
#define LL long long
#define sc(a) scanf("%d", &a)
#define sc2(a, b) scanf("%d%d", &a, &b)
#define sc3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define scl(a) scanf("%lld", &a)
#define scl2(a, b) scanf("%lld%lld", &a, &b)
#define ss(a) scanf("%s", a)
#define mem(a, b) memset(a, b, sizeof(a))
#define PII pair<int, int>
using namespace std;
const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
LL k;
LL work(LL n)
{
    LL ans = 0, l = 0, r = 0;
    for (l = 2; l <= min(n, k); l = r + 1) //l從2開始了，因為第一行之前已經求過了
    {
        r = n / (n / l);                                 //l是産生值為n/l左端位置，r是産生n/l右端位置，l到r之間都是n/l
        ans = (ans + n / l * (min(r, k) - l + 1)) % mod; //對l到r區間的值求和，題目裡的上界是k
    }
    return ans;
}
int main()
{
    LL n;
    scanf("%lld%lld", &n, &k);
    LL ans = (n + k - 1) % mod;  //1 2兩種情況的個數
    ans = (ans + work(n)) % mod; //以下是3情況個數
    ans = (ans + work(n - 1)) % mod;
    printf("%lld\n", ans);
    system("pause");
    return 0;
}
           

J-Pointer Analysis