传送门CF1882D题意给出一颗树，节点编号为 $1 ... n$，每个点有一个权值 $a_i$。你可以执行任意次操作：选择一个 $x$ 满足 $1 \le i \le n$，和一个正整数 $c$。并将 $x$ 子树中所有点的权值异或上 $c$，这次操作的代价为 $u \cdot c$，其中 $u$ 为子树 $x$ 的节点个数。现在需要你求出，对于每个 $r,1 \le r \le n$，以 $r$ 为根时，让所有 $a_i$ 相等的最小代价。$1 \le n \le 2 \cdot 10 ^ 5,1 \le a_i \le 2 ^ {20}$题解我们首先考虑，只需要求出以 $1$ 为根时的答案。看到异或操作，而且 $a \le 2 ^ {20}$，可以想到对每一位分别处理。接下来我们考虑树形DP，设 $f_{x,j,k}$ 表示将子树 $x$ 所有点权值的第 $j$ 位均变成 $k$ 的方案数，那么答案就是 $\sum_{j=0}^{20} {\min \{f_{1,j,0},f_{1,j,1}\}}$。对于一个叶子节点，可以很容易地求出它的 $f$ 值。对于任意非叶子节点 $x$。
备注：此做法来自nzq巨佬题意：FJ 有一个边长为 $n (n \leq 500)$， 共有 $n^2$ 个格子的正方形草地，每一个格子有一个 $1...200$ 的绿度值。对于 FJ 的这个草地，有很多个子矩阵。现在需要你求出子矩阵中所有格子的最小值是 $100$ 的子矩阵的个数。样例:输入3 57 120 87 200 100 150 2 141 135输出8_思路我们可以发现答案显然等于最小值小于 $100$ 的矩阵的个数减去最小值小于等于 $100$ 的个数。如何计算这两个值呢？我们设函数 query(m) 为最小值小于 $m$ 的子矩阵个数，那么答案就等于 query(100)-query(101) 。这个函数怎么写呢，我们将所有小于 $m$ 的格子设为 $1$, 将所有大于等于 $m$ 的格子设为 $0$， 我们对于每一行记一个 $sum_{i,j}$。代码如下:for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(a[i][j]<maxx)b[i][j]=1,sum[i][j]=0;
题意有 $n$ 场电影，第 $i$ 场电影能够带来 $a_i$ 的快乐值，但是当距离上一次观看电影 $cnt$ 天后观看一场电影，这场电影带来的欢乐值会减少 $d \cdot cnt$（可能减少至负数）。现在我们可以去选择观看 $n$ 场电影中的不大于 $m$ 场，使得最终所获得的欢乐值最大。题解假设我们观看了第 $i_1, i_2 ... i_s$ 这 $s$ 场电影，那么我们获得的欢乐值表示为$a_{i_1} - i_1 \cdot d + a_{i_2} - (i_2 - i_1) \cdot d + ... + a_{i_s} - (i_s - i_{s - 1}) \cdot d$将 $d$ 提取出来得到：$a_{i_1} + a_{i_2} + ... + a_{i_s} - i_s \cdot d$由此可见，$d$ 的系数仅与看的最后一场 $i_s$ 有关，因此我们可以枚举看的最后一场电影，得到 $- i_s \cdot d$ 的取值，随后贪心选择第 $i_1 ... i_{s-1}$ 场电影。Code#include <iostream> #include
题目意思题目意思是给你 $n$ 个元素的序列，要你判断执行若干次操作后，整个序列是否能够全部相等。对于每次操作的定义：每次操作选择 $n-1$ 个元素，把它们全部变成这 $n-1$ 个元素的平均值。思路先来考虑是否可以经过一次操作就能使序列全部相等。很简单，看看那 $n-1$ 个元素的平均值是否等于剩下一个元素。那么如果一次操作完成不了呢？其实一次操作完成不了的话，用多少次操作都完成不了。因为一次操作只改变了每个数，但数组和没有改变。最后贴上代码#include<iostream> #include<cstdio> #include<cstring> using namespace std; int t,n,a[55]; int main(){ scanf("%d",&t); while(t--){ bool flag=0; scanf("%d",&n);int sum=0; for(int i=1;i<=n;i++)scan
准备一个电话号码（国内的、已注册过的号码也可以）一台ios系统的设备。一个没注册过Apple ID的邮箱。开始首先打开美国地址生成器，生成一个地址（最好选择阿拉斯加州）。然后不要关掉网站。接着开始注册Appid，可以在ios系统的设置里注册，也可以打开注册Appleid注册。地区选美国，邮箱、密码按要求填写，出生日期最好选成年的。选择 +86中国大陆，然后填写电话号码，最后填下面的验证码就行，按要求填写邮箱、电话的验证码（可能会提示密码不够好等等）。最后打开你的ios系统设备，在设置里输入邮箱、密码登录Appid。然后打开App-Store开始选择、下载。但是，下载的时候它会问我们一些资料，如下图。直接按要求填写之前生成的地址即可。PS:不要选择付款方式。例子：End本文章转载参考https://zhuanlan.zhihu.com/p/623576755。
题意给出 $n$ 和 $l$，要你构造 $3n$ 个长度为 $l$ 字符串，使得字符串都是由 0,1,2 组成且字符串两两不同，每个字符在每个字符串的同一位的出现次数都是 $n$ 次。要你最小化你构造出来的字典序最大的字符串的字典序，输出 $3n$ 个字符串。题解我们可以将 $3n$ 个字符串分为0开头的，1开头的，2开头的。对于前两种字符串，它们的字典序显然不是最大的，因此既然要求最大字典序最小，我们就要考虑构造2开头的字符串，使得其最大字典序最小。我们可以这样按照3进制下的 $[0,n)$ 贪心构造出 $n$ 个字符串，即可满足最小：200...00000 200...00001 200...00002 200...00010 200...00011 200...00012 200...00020 ...而对于1开头和0开头的字符串，我们直接从2开头的置换而来即可。#include<iostream> using namespace std; const int maxn=50010,maxl=20; int n,l,a[maxn][maxl],b[maxn][maxl
题意有 $N$ 个人，他们的编号分别为 $1 ... N$。现在有三种操作：柜台呼叫尚未被呼叫的编号最小的人。表示编号为 $x$ 的人来到了柜台（保证 $x$ 已经被呼叫过一次及以上）询问已经被呼叫但是没有来到柜台的人中的最小编号。题解我们发现一个人有三种状态：没有被呼叫，呼叫了但没来，被呼叫且来了。因此我们用两个小根堆维护前两个状态的人（最后一个状态的人相当于不会在被操作或询问了，所以不用维护）。因此对于操作1，我们询问状态1的人中编号最小的人，将其变成状态2，对于操作2，我们直接将指定的 $x$ 从状态2堆中删除。#include <iostream> #include <queue> using namespace std; int n, m; priority_queue <int, vector<int>, greater<int>> q1, q2, d; int main () { ios::sync_with_stdio (false), cin.tie (0); cin >> n >&
传送门题意有一个长度为 $N$ 的排列 $A_1 \dots A_N$，然后给出 $M$ 对大小关系：输入 $i,j$ 表示 $A_i<A_j$。问 $A$ 是否只有一种可能，若是，输出Yes然后输出 $A$，如果不是输出No。题解如果要 $A$ 只要一种可能，则必须要求每两个数的大小关系都确定，因此我们对每一对输入的 $(i,j)$ 建边 $i->j$，然后跑拓扑排序，如果有环（大小关系矛盾）或者队列里同时有两个数（这两个数可以调换位置）则输出No，否则按照拓扑排序的序列得出答案。#include <map> #include <iostream> #include <vector> #include <queue> using namespace std; const int maxn = 200010; int n, m, tot, tp[maxn], rd[maxn], a[maxn]; map <pair<int, int>, bool> p; queue <int> q; vec
ybaggio
