AtCoder Beginner Contest 125 解题报告

 

那天晚上刚好有事就咕了。

最近的那一场E题还不会写。F题全场又只过了三个?留坑吧...

 

A - Biscuit Generator

#include <cstdio>
using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main() {
    int a = read(), b = read(), t = read();   
    printf("%d\n", t / a * b);
    return 0;    
}

 

B - Resale

#include <cstdio>
#include <algorithm>
using namespace std;


inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int N  = 100;
int a[N];

int main() {
    int sum = 0;
    int n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1, x; i <= n; i++) {x = read(), a[i] -= x; if (a[i] > 0) sum += a[i]; }
    printf("%d\n", sum);
    return 0;  
}

 

C - GCD on Blackboard

题意：给一个序列，能把其中一个数变成任意数，要求之后所有数字的GCD最大

思路：刚开始把所有质因子都求出来，然后 >= n - 1 的质因子相乘，可惜第三组样例就不过了。因为有的质因子不止一个。这种情况就比较麻烦了。

由于$C^{n-1}_{n} = n$ 题目相当于让你求任意$n - 1$个数中的GCD最大的那一组，所以所有答案的情况只有$n$种

开两个数组，$g1[i]$表示从1到$i$的GCD $g2[i]$表示$i$到$n$的GCD $ans=\max \left( \gcd \left( g_{1}\left[ i-1\right] ,g2\left[ i+1\right] \right) \right)$

#include <bits/stdc++.h>
#define ll long long
using namespace std;


inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int N = 1e5 + 10;
int g1[N], g2[N], a[N];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
    int n = read();
    for (int i = 1; i <= n; i++) a[i] = read();  
    g1[1] = a[1]; g2[n] = a[n];
    for (int i = 2, j = n - 1; i <= n; i++, j--) g1[i] = gcd(a[i], g1[i-1]), g2[j] = gcd(a[j], g2[j+1]);
   // for (int i = 1; i <= n; i++) printf("%d %d\n" , g1[i], g2[i]);
    int ans = max(g1[n], max(g1[n-1], g2[2]));
    for (int i = 2; i <= n; i++) {
        ans = max(gcd(g1[i-1], g2[i+1]), ans);
    }
    printf("%d\n", ans);
    return 0;
}

 

D - Flipping Signs

题意：一个序列，能进行$n$次操作，每次对$a_{i}$和$a_{i+1}$都乘上-1，求最后序列和最大

思路：首先从1开始往后，如果这一位小于0，那么对它和它后面的数乘上-1，这样到$n-1$位置，最后序列至多有一个为负，即$a_{n}$，如果$a_{n}$为负，就肯定可以把这个负号传递给绝对值最小的那个数字，如果为正就直接是答案了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline ll real() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int N = 1e5 + 10;
ll a[N];

int main() {
    ll ans = 0;
    ll n = real();
    for (int i = 1; i <= n; i++) a[i] = real();
    for (int i = 1; i <= n - 1; i++) {
        if (a[i] < 0) a[i+1] *= -1, a[i] *= -1;
        ans += a[i];
    }     
    ans += a[n];
    ll temp = *min_element(a + 1, a + n);
    if (a[n] < 0) ans = max(ans, ans - 2 * a[n] - 2 * temp);
    printf("%lld\n", ans);
    return 0;
}