头像

Peter_5




离线:15小时前


最近来访(1148)
用户头像
后视镜里的世界
用户头像
simonhan
用户头像
cheems
用户头像
ZZ_20
用户头像
Botton
用户头像
levelna
用户头像
cdm
用户头像
java初学者
用户头像
Hygen
用户头像
10serrrrrr
用户头像
Pipipapi
用户头像
凌乱之风
用户头像
Rick0_o
用户头像
Code_Xu
用户头像
L_H_R
用户头像
_Airヾ梦及丨
用户头像
种花家的小兔子
用户头像
教练...我想打电竞
用户头像
otohana
用户头像
樱满集集集集集集

活动打卡代码 AcWing 4084. 号码牌

Peter_5
16小时前
/*
    在同一个并查集中的人的牌子一定是可以互相交换的;
    因此,只需要考虑每一个人和想换的牌子是不是在同一个并查集中就行了;
*/
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int a[N], d[N], p[N];

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= n;i ++) cin >> d[i];
    for(int i = 1;i <= n;i ++) p[i] = i;

    for(int i = 1;i <= n;i ++)
    {
        int j = i - d[i], k = i + d[i];
        if(j >= 1 && j <= n) p[find(j)] = p[find(i)];
        if(k >= 1 && k <= n) p[find(k)] = p[find(i)];
    }

    for(int i = 1;i <= n;i ++)
        if(find(i) != find(a[i])) 
        {
            puts("NO");
            return 0;
        }

    puts("YES");
    return 0;
}


活动打卡代码 AcWing 4083. 最大公约数

Peter_5
16小时前
/*
    把每一个数字a[i]想象成一个树的节点, 该节点会向所有的因子连一条边;
    最后找除了1的所有因子中, 那个因子连了最多的边;
*/
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, a[N];
int cnt[N];

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];

    // 6 9 12
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= a[i] / j;j ++) 
            if(a[i] % j == 0)
            {
                int k = a[i] / j;
                if(j != k) cnt[j] ++, cnt[k] ++;
                else cnt[j] ++;
            }
    }

    int res = 0;
    for(int i = 2;i < N;i ++) res = max(res, cnt[i]);
    cout << max(res, 1) << endl;

    return 0;
}


活动打卡代码 AcWing 4082. 子序列

Peter_5
17小时前
/*
    对于每一个‘A’, 他所能够构成的“QAQ”的个数是‘A’两边的‘Q’的数量相乘;
    用前缀和处理‘Q’的数量, 在用变量累加;
*/
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

string s;
int a[N];

int main()
{
    cin >> s;
    s = ' ' + s;

    for(int i = 1;i < s.size();i ++) 
        if(s[i] == 'Q') 
            a[i] ++;

    for(int i = 1;i < s.size();i ++) a[i] += a[i - 1];

    int res = 0;
    for(int i = 1;i < s.size();i ++) 
        if(s[i] == 'A') 
            res += a[i - 1] * (a[s.size() - 1] - a[i]);

    cout << res << endl;

    return 0;
}
// 数据很小, 直接暴力 QAQ
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

string s;

int main()
{
    cin >> s;

    int res = 0;
    for(int i = 0;i < s.size();i ++)
        for(int j = i + 1;j < s.size();j ++)
            for(int k = j + 1;k < s.size();k ++)
                res += (s[i] == 'Q' && s[j] == 'A' && s[k] == 'Q');

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 135. 最大子序和

Peter_5
1天前
/*
    f[i] : 序列a中, 以i为结尾的, 长度不超过m的连续子序列最大和;

    先对序列做前缀和;
    对于一个f[i]表示的连续序列, 序列的左端点l可以为[i - m + 1, i], 因此对于前缀和作差来说, 寻找的区间就在[i - m, i - 1];
    这样连续和就可以表示为: a[i] - a[l];
    要使f[i]尽量大, 就要让a[l]尽量小;
    这样就将问题转化为在区间[i - m + 1, i]中找a[l]最小值;
*/
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3e5 + 10;

int n, m, a[N];
int q[N], tt, hh;

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> a[i], a[i] += a[i - 1];

    int res = -0x3f3f3f3f;
    for(int i = 1;i <= n;i ++)
    {
        while(tt >= hh && i - m > q[hh]) hh ++;
        res = max(res, a[i] - a[q[hh]]);
        while(tt >= hh && a[i] <= a[q[tt]]) tt --;
        q[++ tt] = i;
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 132. 小组队列

Peter_5
13天前
/*
    用queue来模拟;
    每一个人所在队列的情况用一个哈希表记录;
    设置一个队列数组, 代表每一个队列的情况;
    再设置一个队列号队列, 存储每一个队列号的排列;
    然后就可以开始模拟了:
        如果一个人入队前该队伍是空的, 则需要将队伍号放到队伍号队列末尾;
        如果一个人入队前该队伍非空,则直接入队即可;

        出队每次从队伍号队列中的队头队伍出;
        出队后队伍中如果为空, 则移除队伍号;
*/
#include <iostream>
#include <queue>

using namespace std;

const int N = 1000010, M = 1010;

int n, cases = 1;
int id[N];

int main() 
{
    while(cin >> n, n)
    {
        queue<int> qid;
        queue<int> q[M];

        for(int i = 1;i <= n;i ++) 
        {
            int cnt;
            scanf("%d", &cnt);
            for(int j = 0;j < cnt;j ++) 
            {
                int x;
                scanf("%d", &x);
                id[x] = i;
            }
        }

        printf("Scenario #%d\n", cases ++);

        string op;
        while(cin >> op, op != "STOP")
        {
            if(op == "ENQUEUE")
            {
                int x;
                scanf("%d", &x);

                int t = id[x];
                if(!q[t].size()) qid.push(t);
                q[t].push(x);
            }
            else 
            {
                int t = qid.front();
                printf("%d\n", q[t].front());
                q[t].pop();

                if(q[t].empty()) qid.pop();
            }
        }

        puts("");
    }
}



Peter_5
13天前
/*
    先考虑暴力做法, 对于每一个位置的h[i],他能表示矩形的最大面积是:h[i] * (r[i] - l[i] + 1);
    r[i]、l[i]分别表示i这个位置向两边扩展能够到的最远的位置;

    r[i]和l[i]的做法对称, 因此先只考虑l[i]的求法;
    假如在[1, i - 1]区间内有一个h[j]小于h[i];
    则在区间[1, j]内,即使存在比h[i]大的位置h[k], h[i]也无法向左扩展到;
    因此可以发现这道题对于每一个l[i], 只需要找到离i最远的j, 满足h[j] >= h[i];
    因此可以用单调栈来优化;

    对于某一个位置i, 如果栈顶元素j的h[j] >= h[i], 则i能扩展到j能扩展的位置(l[i] = l[j]), 然后将i入栈;
    如果h[j] < h[i], 则直接入栈, l[i]只能扩展到自己所在的位置(l[i] = i);
*/
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long 

using namespace std;

const int N = 100010;

int n;
int h[N];
int stk[N], tt;
int l[N], r[N];

signed main()
{
    while(cin >> n, n) 
    {
        for(int i = 0;i < n;i ++) scanf("%lld", &h[i]);

        tt = 0;
        for(int i = 0;i < n;i ++) 
        {
            l[i] = i;
            while(tt && h[stk[tt]] >= h[i]) l[i] = l[stk[tt]], tt --;
            stk[++ tt] = i;
        }

        tt = 0;
        for(int i = n - 1;i >= 0;i --) 
        {
            r[i] = i;
            while(tt && h[stk[tt]] >= h[i]) r[i] = r[stk[tt]], tt --;
            stk[++ tt] = i;
        }

        int res = 0;
        for(int i = 0;i < n;i ++) res = max(res, h[i] * (r[i] - l[i] + 1));
        cout << res << endl;
    }

    return 0;
}




Peter_5
14天前
/*
    卡特兰数:C(n, 2n) - C(n - 1, 2n) = C(n, 2n) / (n + 1);

    1, 1, 2, 5, 14, 42, ......
*/
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int n;

int qmi(int a, int k) 
{
    int res = 1;
    while(k) 
    {
        if(k & 1) res = (LL) res * a % mod;
        a = (LL) a * a % mod;
        k >>= 1;
    }
    return res;
}

int C(int a, int b)
{
    LL res = 1;
    for(int i = 1, j = a;i <= b;i ++, j --)
    {
        res = (LL)res * j % mod;
        res = (LL)res * qmi(i, mod - 2) % mod;
    }
    return res;
}

int main()
{
    cin >> n;

    cout << (LL) C(2 * n, n) * qmi(n + 1, mod - 2) % mod << endl;

    return 0;
}


活动打卡代码 AcWing 656. 钞票和硬币

Peter_5
15天前
import java.util.Scanner;

public class Main{
    public static void main(String [] args){
        int[] n = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1};

        Scanner sc = new Scanner(System.in);

        int x = (int)(sc.nextDouble() * 100);

        System.out.println("NOTAS:");
        for(int i = 0;i < 6;i ++)
        {
            System.out.printf("%d nota(s) de R$ %.2f\n", (int)(x / n[i]), (double)n[i] / 100);
            x %= n[i];
        }

        System.out.println("MOEDAS:");
        for(int i = 6;i < n.length;i ++)
        {
            System.out.printf("%d moeda(s) de R$ %.2f\n", (int)(x / n[i]), (double)n[i] / 100);
            x %= n[i];
        }
    }
}


活动打卡代码 AcWing 655. 天数转换

Peter_5
15天前
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        System.out.printf("%d ano(s)\n%d mes(es)\n%d dia(s)\n", n / 365, n % 365 / 30, n % 365 % 30);
    }
}


活动打卡代码 AcWing 654. 时间转换

Peter_5
15天前
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        System.out.printf("%d:%d:%d", n / 3600, n / 60 % 60, n % 60);
    }
}