Codeforces Round #538 (Div. 2)原題記

B題看暈了，C題神仙數論題。

無意點開luogu，發現C題原來是原題。

1h30min左右抄了題解交了上去，沒想到還能漲一點rating。。。

A

直接模拟就是了。我懶得再看一次題面。

#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
#define ll long long
int x, y, z, a, b, c;
int main() {
    cin >> x >> y >> z >> a >> b >> c;
    if(x > a) {
        cout << "NO" << endl;
        return 0;
    }
    a -= x;
    int sum = a + b;
    if(y > sum) {
        cout << "NO" << endl;
        return 0;
    }
    sum = sum - y + c;
    if(z > sum) {
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
    return 0;
}                

B

這道題有點東西，我亂搞還是WA了。

題解說有結論：其實前\(m \times k\)大的數字全都能取到。

接下來就是考慮如何寫出方案：

我們利用離散化的方法，記錄值和下标。先按值從大到小排序，然後取前\(m\times k\)個。

取到的再按下标從小到大排序，每隔\(m\)個就斷開，也就是輸出這個下标。

就這麼做完了。。。

并不知道這個結論啊啊啊

/*************************************************************************
 @Author: Garen
 @Created Time : Mon 11 Feb 2019 07:49:40 PM CST
 @File Name: CF1114B.cpp
 @Description:
 ************************************************************************/
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
#define ll long long
const ll maxn = 200005;
std::pair<int,int> a[maxn];
ll idx[maxn];
ll n, m, k;
ll ans;
std::vector<int> answers;
int main() {
    cin >> n >> m >> k;
    for(ll i = 1; i <= n; i++) {
        cin >> a[i].first; a[i].second = i;
    }
    std::sort(a + 1, a + n + 1, std::greater<std::pair<int,int>>());

    for(ll i = 1; i <= m * k; i++) {
        ans += a[i].first;
        idx[i] = a[i].second;
    }
    std::sort(idx + 1, idx + m * k + 1);
    for(ll i = 1; i < k; i++) {
        answers.push_back(idx[i * m]);
    }
    cout << ans << endl;
    for(auto it: answers) cout << it << ' ';
    cout << endl;
    return 0;
}                

C

原題：P3927 SAC E#1 - 一道中檔題 Factorial

題意：求\(n!\)在\(b\)進制下末尾有連續多少個\(0\)。

手摸幾下，就會發現：\(n!\)能夠除\(b\)多少次，\(b\)進制末尾就有連續多少個\(0\)！

是以問題轉換為：求\(n!\)能連續除\(b\)的次數。

我們把\(k\)分解質因數，然後看\(n!\)包含多少個質因數，求完這個個數後再除以在\(k\)裡面質因數的指數，最後的答案就是這些數的最小值。

然後問題又轉換為：求\(n!\)包含某個質因數\(i\)的個數。

把\(n!\)展開後，顯然每\(i\)個數裡面一定有個\(i\)，這\(i\)個\(i\)裡面也一定有個\(i\)。以此類推就可以求了。（有點繞）

看看代碼8，說不下去了：

/*************************************************************************
 @Author: Garen
 @Created Time : Tue 19 Feb 2019 02:25:33 PM CST
 @File Name: P3927.cpp
 @Description:
 ************************************************************************/
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
#define ll long long
const ll maxn = 100005;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll a[maxn], b[maxn], tot;
ll n, k;

int main() {
    cin >> n >> k;
    // 正宗的分解質因數過程，要記牢啊
    for(ll i = 2; i * i <= k; i++) {
        if(k % i == 0) {
            a[++tot] = i;
        }
        while(k % i == 0) {
            b[tot]++; k /= i;
        }
    }
    if(k > 1) {
        a[++tot] = k; b[tot] = 1;
    }
    // 分解質因數到此為止
    ll ans = INF;
    for(ll i = 1; i <= tot; i++) {
        ll temp = n, cnt = 0;
        while(temp) {
            temp /= a[i];
            cnt += temp;
        }
        cnt /= b[i];
        ans = std::min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}                

後面的題目

沒有

轉載于:https://www.cnblogs.com/Garen-Wang/p/10403580.html