头像

JcWing

$$\tiny{新初一蒟蒻}$$ $$\large\href{/blog/content/19548/}{\color{DarkTurquoise}{\text{【暑假每日一题】题解}}}$$




在线 


最近来访(582)
用户头像
种花家的兔兔
用户头像
Unnamed_juruo
用户头像
HeXing
用户头像
hanyucan
用户头像
csn
用户头像
chmffwn1
用户头像
sylikesplayingwithcpp
用户头像
yyjjhh
用户头像
宇宙有边
用户头像
lcjsjez
用户头像
江南牧牛人
用户头像
人间过客_追梦人
用户头像
琉璃肴
用户头像
LUFENG
用户头像
AcWing2AK
用户头像
Cold_heartless
用户头像
Finn2009
用户头像
wisdom2010
用户头像
大好河山
用户头像
窗外的麻雀


JcWing
18小时前
#define N 100005

class Solution
{
    public:
        int maxEqualFreq (vector <int> &nums)
        {
            int mx = 0, ans = 0, a[N], b[N];
            memset (a, 0, sizeof (a)), memset (b, 0, sizeof (b));
            for (int i = 0; i < nums.size (); i ++)
            {
                a[nums[i]] ++, mx = max (mx, a[nums[i]]), b[a[nums[i]]] ++;
                if (mx == 1 || b[mx] * mx == i || b[mx - 1] * (mx - 1) == i)
                {
                    ans = max (ans, i + 1);
                }
            }
            return ans;
        }
};



JcWing
18小时前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
    private:
        int res = 0, mxd = 0;

    public:
        int deepestLeavesSum (TreeNode* root)
        {
            dfs (root, 1);
            return res;
        }

        void dfs (TreeNode *now, int d)
        {
            if (now == nullptr)
            {
                return ;
            }
            if (d > mxd)
            {
                mxd = d, res = 0;
            }
            res += now -> val * (d == mxd);
            dfs (now -> left, d + 1), dfs (now -> right, d + 1);
        }
};


活动打卡代码 LeetCode 1656. 设计有序流

JcWing
19小时前
#define N 1005

class OrderedStream
{
    private:
        int n;
        string *p, val[N];
    public:
        OrderedStream (int n)
        {
            this -> n = n, p = &val[1];
        }
        vector <string> insert (int idKey, string value)
        {
            vector <string> v;
            val[idKey] = value;
            if (*p != "")
            {
                while (*p != "")
                {
                    v.push_back (*p ++);
                }
            }
            return v;
        }
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream* obj = new OrderedStream(n);
 * vector<string> param_1 = obj->insert(idKey,value);
 */



JcWing
1天前
#include <iostream> // 带边权并查集
#define N 50005
using namespace std;

int n, m, op, x, y, p, q, ans, fa[N], d[N];

int find (int x)
{
    if (!fa[x])
    {
        return x;
    }
    int t = find (fa[x]);
    d[x] = (d[x] + d[fa[x]]) % 3;
    return fa[x] = t;
}

int main ()
{
    cin >> n >> m;
    while (m --)
    {
        cin >> op >> x >> y, p = find (x), q = find (y);
        if (x > n || y > n)
        {
            ans ++;
            continue;
        }
        if (p == q)
        {
            if (op == 1 && d[x] != d[y] || op == 2 && d[x] % 3 != (d[y] + 1) % 3)
            {
                ans ++;
            }
        }
        else
        {
            fa[p] = q, d[p] = ((d[y] - d[x] + op - 1) % 3 + 3) % 3;
        }
    }
    cout << ans;
    return 0;
}



JcWing
3天前
class MyCircularDeque { // 数组模拟双端队列
    private:
        #define N 4005
        int l, r, k, a[N]; // 表示当前双端队列在 (l, r] 这个区间里
    public:
        MyCircularDeque(int k) {
            l = 2000, r = 2000, this -> k = k;
        }

        bool insertFront(int value) {
            if (r - l < k)
            {
                a[++ r] = value;
                return 1;
            }
            else
            {
                return 0;
            }
        }

        bool insertLast(int value) {
            if (r - l < k)
            {
                a[l --] = value;
                return 1;
            }
            else
            {
                return 0;
            }
        }

        bool deleteFront() {
            if (r > l)
            {
                r --;
                return 1;
            }
            else {
                return 0;
            }
        }

        bool deleteLast() {
            if (r > l)
            {
                l ++;
                return 1;
            }
            else {
                return 0;
            }
        }

        int getFront() {
            if (r > l)
            {
                return a[r];
            }
            else
            {
                return -1;
            }
        }

        int getRear() {
            if (r > l)
            {
                return a[l + 1];
            }
            else {
                return -1;
            }
        }

        bool isEmpty() {
            return l == r;
        }

        bool isFull() {
            return r - l == k;
        }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */



JcWing
4天前

峰会

题目描述

峰会是国家元首或政府首脑的会议。

为峰会安排休息区可不是一件简单的工作。

一共有 $N$ 个首脑参加峰会,编号 $1 \sim N$。

这些首脑之间存在 $M$ 对两两之间的直接朋友关系。

在划分区域时,我们希望被安排在同一休息区域的首脑们满足,任意两人之间都是直接朋友关系。

现在,给定 $K$ 个关于划分休息区域的安排,请你依次判断每个安排是否合理。

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行,每行包含两个整数 $a, b$,表示首脑 $a$ 和首脑 $b$ 之间存在直接朋友关系。

再一行包含整数 $K$。

接下来 $K$ 行,每行描述一个区域安排,首先包含一个整数 $L$,表示该安排打算将 $L$ 个首脑安排在同一区域休息,然后包含 $L$ 个整数,表示这些首脑的编号。

输出格式

共 $K$ 行,第 $i$ 行输出对第 $i$ 个安排的判断,具体格式为

  • 如果安排满足其中的任意两人之间都是直接朋友关系并且不存在额外的人与被安排的所有人都是直接朋友关系(即无法安排更多的人在这一区域休息),则输出 Area X is OK.
  • 如果安排满足其中的任意两人之间都是直接朋友关系并且存在额外的人与被安排的所有人都是直接朋友关系(即可以安排更多的人在这一区域休息),则输出 Area X may invite more people, such as H.,其中 $H$ 是额外可被安排的人的编号(如果不唯一,则输出最小的那个)。
  • 如果安排无法满足其中的任意两人之间都是直接朋友关系,则输出 Area X needs help.

$X$ 表示组别编号,从 $1$ 到 $K$ 。

数据范围

$1 \le N \le 200,$
$1 \le M \le N(N−1)2,$
$1 \le a, b \le N,$
$a \ne b,$
$1 \le K \le 100,$
$1 \le L \le N,$

同一对直接朋友关系不会在输入中重复出现。

输入样例:

8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
2 4 6
3 3 2 1

输出样例:

Area 1 is OK.
Area 2 is OK.
Area 3 is OK.
Area 4 is OK.
Area 5 may invite more people, such as 3.
Area 6 needs help.

正解:枚举

$a, b$ 为直接朋友关系,就可以在 $a, b$ 之间连一条无向边,这可以用一个邻接矩阵来存(这道题中使用邻接矩阵效率较高)

然后我们判断输入的分组中是否每个人都和其他人之间有连边。如果没有,就说明是第三种情况。

然后我们按编号从小到大的顺序枚举每一个人(其实不用特判这个人是否在分组里,如果他在分组里那么他和它自己之间就没有连边),如果这个人和这个分组里的每一个人之间都有连边,那么就是第二种情况,$H$ 就是这个人的编号。

否则就是第一种情况。

AC Code

#include <iostream>
#define N 205
using namespace std;

int n, m, q, x, y, a[N];
bool flag, flag_, g[N][N];

int main ()
{
    cin >> n >> m;
    while (m --)
    {
        cin >> x >> y, g[x][y] = g[y][x] = 1;
    }
    cin >> q;
    for (int kase = 1; kase <= q; kase ++)
    {
        cin >> x, flag = 0;
        for (int i = 1; i <= x && !flag; i ++)
        {
            cin >> a[i];
            for (int j = 1; j < i && !flag; j ++)
            {
                if (!g[a[i]][a[j]])
                {
                    flag = 1;
                }
            }
        }
        if (flag)
        {
            cout << "Area " << kase << " needs help.\n";
            continue;
        }
        for (int i = 1; i <= n; i ++)
        {
            flag_ = 1;
            for (int j = 1; j <= x; j ++)
            {
                if (!g[i][a[j]])
                {
                    flag_ = 0;
                    break;
                }
            }
            if (flag_)
            {
                cout << "Area " << kase << " may invite more people, such as " << i << ".\n", flag = 1;
                break;
            }
        }
        if (flag)
        {
            continue;
        }
        cout << "Area " << kase << " is OK.\n";
    }
    return 0;
}

感谢观看!

上一篇

下一篇

$$\href {/blog/content/19548/} {\color {MediumSlateBlue} {【暑假每日一题】题解}}$$



活动打卡代码 AcWing 4278. 峰会

JcWing
4天前
#include <iostream>
#define N 205
using namespace std;

int n, m, q, x, y, a[N];
bool flag, flag_, g[N][N];

int main ()
{
    cin >> n >> m;
    while (m --)
    {
        cin >> x >> y, g[x][y] = g[y][x] = 1;
    }
    cin >> q;
    for (int kase = 1; kase <= q; kase ++)
    {
        cin >> x, flag = 0;
        for (int i = 1; i <= x && !flag; i ++)
        {
            cin >> a[i];
            for (int j = 1; j < i && !flag; j ++)
            {
                if (!g[a[i]][a[j]])
                {
                    flag = 1;
                }
            }
        }
        if (flag)
        {
            cout << "Area " << kase << " needs help.\n";
            continue;
        }
        for (int i = 1; i <= n; i ++)
        {
            flag_ = 1;
            for (int j = 1; j <= x; j ++)
            {
                if (!g[i][a[j]])
                {
                    flag_ = 0;
                    break;
                }
            }
            if (flag_)
            {
                cout << "Area " << kase << " may invite more people, such as " << i << ".\n", flag = 1;
                break;
            }
        }
        if (flag)
        {
            continue;
        }
        cout << "Area " << kase << " is OK.\n";
    }
    return 0;
}


活动打卡代码 AcWing 4405. 统计子矩阵

JcWing
4天前
#pragma GCC optimize (3)
#include <iostream>
#define N 505
using namespace std;

int n, m, k, x;
long long ans, s[N][N];

long long get (int a, int b, int c, int d)
{
    return s[c][d] - s[a - 1][d] - s[c][b - 1] + s[a - 1][b - 1];
}

int main ()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            cin >> x, s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
        }
    }
    for (int i = 1; i <= n; i ++)
    {
        for (int j = i; j <= n; j ++)
        {
            for (int l = 1, r = 1; r <= m; r ++)
            {
                while (l <= r && get (i, l, j, r) > k)
                {
                    l ++;
                }
                ans += r - l + 1;
            }
        }
    }
    cout << ans;
    return 0;
}



JcWing
4天前

数列

我怎么感觉这道题我想得太复杂了……

矩阵快速幂

这题快速幂的次数很显然要用十进制表示,转二进制会超时。

我们可以把数列中相邻两项看成一个 $1 \times 2$ 的矩阵。

然后构建一个矩阵:

$
\begin {bmatrix}
0 & 1 \\
q & p
\end {bmatrix}
$

然后就是矩阵快速幂。

最后输出 $k$ 个数时就随便暴力求一下就好了。

// 矩阵快速幂解法
#pragma GCC optimize (3)
#include <iostream>
#include <cstring>
using namespace std;

long long p, q, m, k, t, f[2], a[2][2] = {0, 0, 1}, a_[2][2];
string str, n;

void mul (long long a[2], long long b[2][2]) // 1 x 2 乘 2 x 2
{
    long long c[2];
    memset (c, 0, sizeof (c));
    for (int j = 0; j < 2; j ++)
    {
        for (int k = 0; k < 2; k ++)
        {
            c[j] = (c[j] + a[k] * b[k][j]) % m;
        }
    }
    memcpy (a, c, sizeof (c));
    return ;
}

void mul_ (long long a[2][2], long long b[2][2]) // 2 x 2 乘 2 x 2
{
    long long c[2][2];
    memset (c, 0, sizeof (c));
    for (int i = 0; i < 2; i ++)
    {
        for (int j = 0; j < 2; j ++)
        {
            for (int k = 0; k < 2; k ++)
            {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % m;
            }
        }
    }
    memcpy (a, c, sizeof (c));
    return ;
}

void mulself (long long a[2][2]) // 2 x 2 自乘
{
    long long c[2][2];
    memset (c, 0, sizeof (c));
    for (int i = 0; i < 2; i ++)
    {
        for (int j = 0; j < 2; j ++)
        {
            for (int k = 0; k < 2; k ++)
            {
                c[i][j] = (c[i][j] + a[i][k] * a[k][j]) % m;
            }
        }
    }
    memcpy (a, c, sizeof (c));
    return ;
}

void power () // 矩阵快速幂(十进制会相对复杂)
{
    for (int i = str.length () - 1, ch; ~i; i --)
    {
        ch = str[i] - '0', memcpy (a_, a, sizeof (a_));
        for (; ch; ch >>= 1)
        {
            if (ch & 1)
            {
                mul (f, a);
            }
            mulself (a);
        }
        memcpy (a, a_, sizeof (a));
        mulself (a), mulself (a), mulself (a), mulself (a_), mul_ (a, a_);
    }
    return ;
}

int main ()
{
    ios::sync_with_stdio (0), cin.tie (0), cout.tie (0), cin >> f[0] >> f[1] >> p >> q >> m >> k >> str, a[0][1] = q, a[1][1] = p, power ();
    for (int i = 1; i <= k; i ++) // 暴力
    {
        t = f[1], f[1] = (f[0] * q + f[1] * p) % m, f[0] = t, cout << f[0] << endl;
    }
    return 0;
}


新鲜事 原文

JcWing
5天前
胜率 104.35% ??
图片