2020牛客暑期多校训练营(第七场)题解DBH

发布于 2020-08-02  0 次阅读


D. Fake News

思路:

提前打了一下表,发现好像就1和24可以,试了一下A了
附上大佬的证明:如何证明 1²+2²+…+n² 为平方数的解只有 n=1 或 n=24?

AC Code:

#include<stdio.h>
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);
        if(n==1 || n==24)   printf("Fake news!\n");
        else    printf("Nobody knows it better than me!\n");
    }
    return 0;
}

B. Mask Allocation

题目大意:

对于n*m个口罩,将其分成可以组合成n个m个m个n,只能序列内叠加,不能拆分,答案按照字典序排序输出

思路:

每次选择当前可以组合的最大数即可

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int N=1e5 +9;
// #define TDS_ACM_LOCAL
int n, m, a[N], ans; 
void solve(){
    cin>>n>>m;
    ans=0;
    while(n&&m){                            //当口罩为0时结束
        if(n<m) swap(n,m);                  //找到当前可选择的最大数
        for(int i=1; i<=m; i++) a[++ans]=m; 
        n-=m;
    }
    cout<<ans<<endl;
    for(int i=1; i<=ans; i++)   cout<<a[i]<<" ";
    cout<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

H. Dividing(除法分块)

思路:

在这里插入图片描述

看一下上图,稍微推一下其实很容易就能发现规律了, 每列的公式为n ∗ k或者 n ∗ k − ( n − 1 ) ,n为N的行,直接跑O(n)的话很明显T了,所以我们讲将公式换一种方式写一下:

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
const int mod=1e9+7;
// #define TDS_ACM_LOCAL
inline ll division(ll n,ll k, ll t) //除法分块
{
    ll ans=0,j;
	for (register ll i=t;i<=k;i=j+1){
        j=n/(n/i);
        ans+=(min(j,k)-i+1)*(n/i);
    }
    return ans;
}
void solve(){
    ll n, k;
    cin>>n>>k;
    cout<<(division(n, min(n,k), 1)%mod + division(n-1, min(n-1,k), 2)%mod +k-1)%mod<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}


平平无奇的大学在读本科生