AtCoder Beginner Contest 255 部分题解

本篇题解只是记录我的做题过程代码，不提供最优解
（另外这里所有的时间复杂度都只分析单个样例，不算 t t t的时间复杂度）

点击此处查看对应的题目.
本题设计算法：模拟
直接输出指定的点即可。

时间复杂度 O ( 1 ) O(1) O(1)

#include 
#include  
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1010;
int g[N][N];

int main()
{
    int r,c;
    cin >> r >> c;
    for (int i = 1;i <= 2;i ++) {
        for (int j = 1;j <= 2;j ++ ) { 
            cin >> g[i][j];
        }
    }
    cout << g[r][c] << 'n';
    return 0;
}

点击此处查看对应的题目.
本题设计算法：模拟 + 贪心

枚举所有点到发光点的距离，得到最小的那个（因为每个等只要被照到就行，所以只要最小值），最后将要保证所有的点都要被照亮，所以只留最大的。

贪心策略：因为每个等只要被照到就行，所以只要最小值

注意double的精度加入

时间复杂度 O ( n ∗ k ) O(n * k) O(n∗k)

#include 
#include  
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1010;
typedef pair PDD;
PDD a[N];
int s[N];

int main()
{
    int n,k;
    cin >> n >> k;
    for (int i = 1;i <= k;i ++ ) cin >> s[i];
    for (int i = 1;i <= n;i ++ ) cin >> a[i].first >> a[i].second;

    double res = 0.0;
    for (int i = 1;i <= n;i ++ ) {
        double t = 1e9;
        for (int j = 1;j <= k;j ++ ) {
            double x = a[i].first,y = a[i].second;
            double tx = a[s[j]].first,ty = a[s[j]].second;
            t = min(t,sqrt(1.*((x - tx) * (x - tx)) + 1.*((y - ty) * (y - ty))));
        }
        res = max(res,t);
    }
    cout << res << 'n';
    return 0;
}

点击此处查看对应的题目.
本题设计算法：数学取模运算 + 数学等差数列性质

因为这道题数据太大，不能直接加，所以可以通过取模运算找到最近的数，不过，要对 x 和 d 分情况讨论，且注意取绝对值。详细见代码。

时间复杂度 O ( 1 ) O(1) O(1)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

int main()
{
    ll x,a,d,n;
    cin >> x >> a >> d >> n;
    ll an = a + (n - 1ll) * d;//等差数列求值
    if (!d) {cout << abs(x - a) << 'n';return 0;}//特判d等于0

    if (d >= 0) {
        if (x >= an || x <= a) cout << min(abs(x - an),abs(x - a)) << 'n';
        else {
            ll mod = (x - a) % d;
            cout << min(mod,d - mod) << 'n';
        } 
    }else {
        if (x <= an || x >= a) cout << min(abs(x - an),abs(x - a)) << 'n';
        else {
            ll mod = (x - an) % d;
            cout << min(mod,abs(d) - mod) << 'n';
        } 
    }
    
    return 0;
}

点击此处查看对应的题目.
本题设计算法：二分查找 + 贪心 + 前缀和

本题目要求 q 次操作，每次操作，将所有的数通过加 1 或减 1 任意次数到达指定的数

做法：
每次给出的指定的数在数列中必然有大于它的，也有小于它的，所以我们可以通过排序原数列，将整个数列分成两段，一段小于指定的数，一段大于指定的数，然后就可以利用前缀和快速算出两段的和，最后将总差值算出来。

同时注意，这里的分成前后两段的操作，应该用二分查找算出，因为此时整体已经具备有单调性，可以二分加快查找速度。

时间复杂度 O ( q l o g n ) O(qlogn) O(qlogn)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll s[N],a[N];

int main()
{
    ll n,q;
    cin >> n >> q;
    for (int i = 1;i <= n;i ++ ) cin >> a[i];
    sort(a + 1,a + n + 1);
    for (int i = 1;i <= n;i ++ ) s[i] = s[i - 1] + a[i];
    while (q -- ) {
        ll val;
        cin >> val;
        ll dir = lower_bound(a + 1,a + n + 1,val) - a;
        //cout << "------------" << dir << ' ' << a[dir] << 'n';
        ll res = ((dir - 1) * val) - ((n - dir + 1) * val) - 2 * s[dir - 1] + s[n]; 
        cout << res << 'n';
    }   
    return 0;
}

点击此处查看对应的题目.
本题设计算法：数学归纳法 + map统计

这里思路太长了，键盘坏了，我就不码字了~~

字写的一般~~，hh

时间复杂度 O ( n ∗ m ) O(n * m) O(n∗m)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll s[N],x[N],b[N];
int n,m;

int main()
{
    cin >> n >> m;
    for (int i = 1;i < n;i ++ ) scanf("%lld",&s[i]);
    for (int i = 1;i <= m;i ++ ) scanf("%lld",&x[i]);
    for (int i = 2;i <= n;i ++ ) b[i] = s[i - 1] - b[i - 1];
    unordered_map mp;//表示first值为首项的幸运数子会出现多少次
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            ll c = x[j] - b[i];
            if(i % 2 == 0) c *= -1;
            mp[c] ++;
        }
    }

    ll res = 0;
    for (auto it : mp) res = max(res,it.second);
    cout << res << 'n';
    return 0;
}