头像

jyc20101031

小学 2017级




离线:15小时前


最近来访(14)
用户头像
一只可爱严
用户头像
大雪莱
用户头像
英特纳雄耐尔
用户头像
直行格子
用户头像
liyixiang1116
用户头像
灭神堂乄魂锁典狱长
用户头像
金伟
用户头像
gongcharlie

活动打卡代码 AcWing 3769. 移动石子

jyc20101031
16小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int n, d;
        cin >> n >> d;
        int res;
        cin >> res;
        int t;
        for (int i = 1; i < n; i ++ ){
            cin >> t;
            if (d > 0){
                int cnt = min(d / i, t);
                d -= cnt * i;
                res += cnt;
            }
        }
        cout << res << endl;
    }
}




新鲜事 原文

~机智如我~,换上了18周周赛第二题的头像


活动打卡代码 AcWing 3989. 看图做题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    cout << 6 * n * (n - 1) + 1 << endl;
    return 0;
}



照样例规律
找到后,会发现过了几个小时


算法

$O(1)$数学

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    cout << 6 * n * (n - 1) + 1 << endl;
    return 0;
}



题目描述

给定一个包含 n 个整数的数组 a1,a2,…,an。

请你从中找出 k 个元素,并要求找出的元素值两两不同。

数据范围

前三个测试点满足,1≤k≤n≤5。
所有测试点满足,1≤k≤n≤100,1≤a[i]≤100。

输入样例:

5 3
15 13 15 15 12

输出样例:

YES
1 2 5

算法

计数排序(思想)

不是桶排,我也是掉坑了

时间复杂度

$O(n)$

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

bool s[1010101];
int x;
int main()
{
    int n;
    int k;
    int b[k];//存结果的桶
    cin >> n >> k;
    int a;
    for (int i = 0; i < n; i ++ )
    {
        cin >> a;
        if (!s[a]) s[a] = 1, b[x ++ ] = i + 1;//只有没标记(第一个该数),就标记为已出现并记录其下标
    }
    if (x < k) cout << "NO";//因为x从0开始,最后又+1,所以判断为<k都不行,而输出却也是<k
    else
    {
        cout << "YES" << endl;
        for (int i = 0; i < k; i ++ ) cout << b[i] << ' ';
    }
}


活动打卡代码 AcWing 3988. 不同的数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

bool s[1010101];
int x;
int main()
{
    int n;
    int k;
    int b[k];
    cin >> n >> k;
    int a;
    for (int i = 0; i < n; i ++ )
    {
        cin >> a;
        if (!s[a]) s[a] = 1, b[x ++ ] = i + 1;
    }
    if (x < k) cout << "NO";
    else
    {
        cout << "YES" << endl;
        for (int i = 0; i < k; i ++ ) cout << b[i] << ' ';
    }
}


活动打卡代码 AcWing 3792. 质数问题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    get_primes(N - 1);
    int T;
    cin >> T;
    while (T -- )
    {
        int n, k;
        cin >> n >> k;
        int res = 0;
        for (int i = 2; i <= n; i ++ )
        {
            if (st[i]) continue;
            for (int j = 1; j < cnt; j ++ )
                if (primes[j - 1] + primes[j] + 1 == i)
                {
                    res ++ ;
                    break;
                }
        }
        if (res >= k) puts("YES");
        else puts("NO");
    }
}



活动打卡代码 AcWing 3818. 餐厅

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

struct node{
    int l, r;
}a[500005];
int s, t, n;
bool cmp(node x, node y) {
    return x.r < y.r;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;
    sort(a, a + n, cmp);
    for (int i = 0; i < n; i++) {
        if (t < a[i].l)
        {
            t = a[i].r;
            s++;
        }
    }
    cout << s << endl;
}



活动打卡代码 AcWing 3956. 截断数组

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int s[10000100];
int a[10000100];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    long long t = 0;
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    if (s[n] % 3) cout << 0;
    else
    {
        for (int i = 3, cnt = 0; i <= n; i ++ )
        {
            if (s[i - 2] == s[n] / 3) cnt ++ ;
            if (s[n] - s[i - 1] == s[n] / 3) t += cnt;
        }
        cout << t;
    }
}


活动打卡代码 AcWing 3767. 最小的值

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int n;
int a[N], b[N];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < n; i ++ ) cin >> b[i];
    int x = 0, y = 0;
    for (int i = 0; i < n; i ++ ){
        if (a[i] < b[i]) x ++ ;
        else if (a[i] > b[i]) y ++ ;
    }
    if (!y) puts("-1");
    else cout << (x + y) / y << endl;
}