首页 > 其他分享 >Acwing周赛102

Acwing周赛102

时间:2023-05-08 13:44:51浏览次数:50  
标签:周赛 typedef const int LL long ans 102 Acwing

倍增

这是一道简单数论题


using namespace std;
typedef long long LL;
const int N = 1e5 + 10;

int a[N], n;

int div(int x)
{
    if(x % 2 == 0)
        while(x % 2 == 0)    x /= 2;
    if(x % 3 == 0)
        while(x % 3 == 0)    x /= 3;
    return x;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)    scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++ i)    a[i] = div(a[i]);
    for(int i = 1; i <= n; ++ i)
    {
        if(a[1] != a[i])
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0; 
}

三元组

这道题目我们可以直接用stlmap套vector+stl的二分暴力来做也可以选择用前后缀分解,前后缀分解是我第一次见这种思想,会用一篇博客单独整理运用这种思想的题目

stl直接做

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N];
LL ans;
int main()
{
    int n, k;
    cin >> n >> k;

    map<LL, vector<int>>mp;
    for(int i = 1; i <= n; ++ i)
    {
        scanf("%d", &a[i]);
        mp[a[i]].push_back(i);
    }

    for(int i = 2; i < n; ++ i)
    {
        int ay = a[i];
        if(a[i] % k == 0)
        {
            LL ax = ay / k, az = 1LL * ay * k;
            if(mp.find(ax) != mp.end() && mp.find(az) != mp.end())
            {
                auto& v1 = mp[ax];
                auto& v2 = mp[az];
                int m = v2.size();
                int k1 = lower_bound(v1.begin(), v1.end(), i) - v1.begin();
                if(k1 >= 0)
                {
                    -- k1;
                    int k2 = upper_bound(v2.begin(), v2.end(), i) - v2.begin();
                    ans += 1LL * (k1 + 1) * (m - k2);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

前后缀分解去做

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N];
map<LL, LL>l, r;
LL ans;
int main()
{
    LL n, k;
    scanf("%lld%lld", &n, &k);
    for(int i = 1; i <= n; ++ i)
    {
        scanf("%lld", &a[i]);
        r[a[i]] ++;
    }
    for(int i = 1; i <= n; ++ i)
    {
        r[a[i]] --;
        if(a[i] % k == 0)
        {
            if(l.find(a[i] / k) != l.end() && r.find(a[i] * k) != r.end()) 
                ans += 1LL * l[a[i] / k] * r[a[i] * k];
        }
        l[a[i]] ++;
    }
    cout << ans << endl;
}

标签:周赛,typedef,const,int,LL,long,ans,102,Acwing
From: https://www.cnblogs.com/cxy8/p/17381480.html

相关文章

  • AcWing 770. 单词替换
    AcWing770.单词替换1.地址https://www.acwing.com/problem/content/772/2.题解#include<iostream>#include<cstdio>#include<sstream>usingnamespacestd;intmain(){strings;stringa,b;stringresult="";......
  • LeetCode 周赛 344(2023/05/07)手写递归函数的固定套路
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。今天下午有力扣杯战队赛,不知道官方是不是故意调低早上周赛难度给选手们练练手。往期周赛回顾:LeetCode单周赛第343场·结合「下一个排列」的贪心构造问题周赛概览T1.找出不......
  • 【算法基础】DFS深度优先算法 —— AcWing 843. n-皇后问题 AcWing 842. 排列数字
    n-皇后问题是一个经典的dfs深度优先遍历的题目,在题解这一题之前,将由浅入深,先讲解一个n-皇后问题的母题。-------AcWing842.排列数字 [AcWing842].排列数字题目概述给定一个整数 n,将数字 1∼n排成一排,将会有很多种排列方法。现在,请你按照字典序将所有的排列方法输出。输入格......
  • POJ2739 Sum of Consecutive Prime Numbers&&Acwing4938 连续质数之和
    方法:单调队列为什么是单调队列?因为这里让我们求连续的质数和,我们可以利用欧拉筛来维护质数,再利用单调队列来维护连续的质数。代码(POJ不支持C++11差评):#include<cstdlib>#include<cstring>#include<cstdio>#include<cctype>namespaceFastIo{ #definegcgetchar() #d......
  • acwing 4645. 选数异或
     输出yesnoyes no题意分析,给一串数组,再在每次提问时给出一个区间,l,r;求l,r区间内是否存在两个数,两数异或后值为给出的x;已知a^b=x-->a^x=b;思路:1,把每个数异或x,存在另一个数组(b)里,暴力搜索,看区间内b数组内数字是否有等于a数组内数字,TLE2.记录下标,比较每个......
  • AcWing 3549. 最长非递减子序列
    \(AcWing\)\(3549\).最长非递减子序列一、题目描述给定一个长度为\(n\)的数字序列\(a_1,a_2,…,a_n\),序列中只包含数字\(1\)和\(2\)。现在,你要选取一个区间\([l,r](1≤l≤r≤n)\),将\(a_l,a_{l+1},…,a_r\)进行翻转,并且使得到的新数字序列\(a\)的最长非递减子序列......
  • LeetCode 周赛 343(2023/04/30)结合「下一个排列」的贪心构造问题
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。今天是五一假期的第二天,打周赛的人数比前一天的双周赛多了,难道大家都只玩一天吗?这场周赛是LeetCode第343场单周赛,如果不考虑第一题摆烂的翻译,整体题目质量还是很不错哒。往期回顾:L......
  • AcWing 1209. 带分数
    1-暴力解法思考1:暴力列举出1~9的全排列,之后再将这些数字按照一定规则相加,最后将结果与n比较。全排列好写,但相加的规则不好写,而且太暴力了,估计会超时。/*AcWing1209.带分数00.最暴力的写法1.枚举全排列2.枚举位数(枚举a和b,可算出c)3.直接算出n,判断等......
  • AcWing 754. 平方矩阵 II
    AcWing754.平方矩阵II1.地址https://www.acwing.com/problem/content/756/2.题解#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;//每个元素的值为:各个元素下标相减的绝对值+1intmain(){intmatrix[102][102];intn;......
  • LeetCode 双周赛 103(2023/04/29)区间求和的树状数组经典应用
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。这场周赛是LeetCode双周赛第103场,难得在五一假期第一天打周赛的人数也没有少太多。这场比赛前3题比较简单,我们把篇幅留给最后一题。往期周赛回顾:LeetCode单周赛第342场·容......