JcWing

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

3534

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);
}
};


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天前

# 峰会

### 输出格式

• 如果安排满足其中的任意两人之间都是直接朋友关系并且不存在额外的人与被安排的所有人都是直接朋友关系（即无法安排更多的人在这一区域休息），则输出 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$ 之间连一条无向边，这可以用一个邻接矩阵来存（这道题中使用邻接矩阵效率较高）

### 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} {【暑假每日一题】题解}}$$

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;
}


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天前

# 数列

### 矩阵快速幂

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

// 矩阵快速幂解法
#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天前