Before the Beginning
转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/nowcoderweekly15/
前言
A:乱搞
B:贪心
C:神仙题，贪心+图论？
D:数据结构
E:数论
A 数列下标
看到范围，随便打个 (O(n^2)) 水过去，理论上卡满可能会TLE，但就是过了……
#include <cstdio>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
return getchar();
#endif
static char buf[bufSize],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
static char c;
r=0;
for(c = nc();!isdigit(c);) c = nc();
for(;isdigit(c);c=nc()) r = r * 10 + c - 48;
return r;
}
const int maxn = 1e4 + 100;
int n;
int a[maxn];
int b[maxn];
int main()
{
read(n);
for(int i = 1;i<=n;++i) read(a[i]);
for(int i = 1;i<=n;++i)
{
for(int j = i + 1;j<=n;++j)
if (a[j] > a[i])
{
b[i] = j;
break;
}
}
for(int i = 1;i<=n;++i) printf("%d ",b[i]);
return 0;
}
B 可持久化动态图上树状数组维护01背包
说实话我都不知道可持久化动态图是个啥东西……
题目其实是贪心：显然每次删除第一个元素，可以让整体代价最小。
但 (a_i < 0) 时，代价是负数，要求最大，那么对于 (a_i) 而言最大的下标就是原始下标。
#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define int long long
#define DEBUG
inline char nc()
{
#ifdef DEBUG
return getchar();
#endif
static char buf[bufSize],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
static char c;
static int flag;
r=0;
flag = 1;
for(c = nc();!isdigit(c);c = nc()) if(c == '-') flag = -1;
for(;isdigit(c);c=nc()) r = r * 10 + c - 48;
return r * flag;
}
const int maxn = 1e6 + 100;
int n;
int a[maxn];
signed main()
{
scanf("%lld",&n);
for(int i = 1;i<=n;++i) scanf("%lld",a + i);
long long sum = 0;
for(int i = 1;i<=n;++i) if(a[i] < 0) sum += i * a[i]; else sum += a[i];
printf("%lld
",sum);
return 0;
}
D 树上求和
其实这是我打的第二道题……一眼可以用树剖做，于是就是树链剖分的板子题。
但其实似乎只求子树用dfs序就可以……？是我蠢了。
线段树维护平方和也是老套路了：
(sum (a_i + k)^2 = sum a_i^2 + sum a_i imes k imes 2 + len imes k^2)
#include <cstdio>
#include <ctype.h>
#define DEBUG
#define int long long
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
return getchar();
#endif
static char buf[bufSize],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
static char c;
r=0;
for(c = nc();!isdigit(c);) c = nc();
for(;isdigit(c);c=nc()) r = r * 10 + c - 48;
return r;
}
const int maxn = 1e5 + 100,maxm = 2e5 + 100;
int n,m;
struct node
{
int to,next;
}E[maxm];
int head[maxn];
inline void add(const int &x,const int &y)
{
static int tot = 0;
E[++tot].next = head[x],E[tot].to = y,head[x] = tot;
}
int w[maxn];
int size[maxn],fa[maxn],son[maxn],dfn[maxn],id[maxn],cnt;
long long sum[maxn<<2],tsum[maxn<<2],tag[maxn<<2];
const int mod = 23333;
#define ls p<<1
#define rs p<<1|1
inline void pushup(const int &p){sum[p] = sum[ls] + sum[rs];tsum[p] = tsum[ls] + tsum[rs];sum[p] %= mod,tsum[p] %= mod;}
inline void pushdown(const int &l,const int &r,const int &p)
{
if(!tag[p]) return;
int mid = l + r >> 1;
tsum[ls] += (mid - l + 1) * tag[p] * tag[p] + 2 * sum[ls] * tag[p];
tsum[rs] += (r - mid) * tag[p] * tag[p] + 2 * sum[rs] * tag[p];
sum[ls] += (mid - l + 1) * tag[p];
sum[rs] += (r - mid) * tag[p];
tag[ls] += tag[p],tag[rs] += tag[p];
tsum[ls] %= mod,tsum[rs] %= mod,sum[ls] %= mod,sum[rs] %= mod,tag[ls] %= mod,tag[rs] %= mod;
tag[p] = 0;
}
void build(int l,int r,int p)
{
if(l == r) return (void)(sum[p] = w[id[l]] % mod,tsum[p] = (w[id[l]] * w[id[l]]) % mod);
int mid = l + r >> 1;
build(l, mid, ls), build(mid + 1, r, rs);
pushup(p);
}
void modify(int l,int r,int p,int ll,int rr,long long k)
{
if(l >= ll && r <= rr)
{
tsum[p] += (r - l + 1) * k * k + 2 * sum[p] * k;
sum[p] += (r - l + 1) * k;
tag[p] += k;
tsum[p] %= mod,sum[p] %= mod,tag[p] %= mod;
return;
}
int mid = l + r >> 1;
pushdown(l,r,p);
if(ll <= mid) modify(l,mid,ls,ll,rr,k);
if(rr > mid) modify(mid + 1,r,rs,ll,rr,k);
pushup(p);
}
long long ask(int l,int r,int p,int ll,int rr)
{
if(l >= ll && r <= rr) return tsum[p];
int mid = l + r >> 1,ans = 0;
pushdown(l,r,p);
if(ll <= mid) ans = ask(l,mid,ls,ll,rr) % mod;
if(rr > mid) ans = (ans + ask(mid + 1,r,rs,ll,rr)) % mod;
return ans;
}
void dfs1(int u)
{
size[u] = 1;
for(int p = head[u];p;p=E[p].next)
{
int v = E[p].to;
if(v == fa[u]) continue;
fa[v] = u,dfs1(v),size[u] += size[v];
if(size[son[u]] < size[v]) son[u] = v;
}
}
void dfs2(int u)
{
dfn[u] = ++cnt;
id[cnt] = u;
if(!son[u]) return;
dfs2(son[u]);
for(int p = head[u];p;p=E[p].next)
{
int v = E[p].to;
if(v == son[u] || v == fa[u]) continue;
dfs2(v);
}
}
signed main()
{
read(n),read(m);
for(int i = 1;i<=n;++i) read(w[i]);
for(int i = 1;i<n;++i)
{
int a,b;
read(a),read(b);
add(a,b),add(b,a);
}
dfs1(1),dfs2(1);
build(1,n,1);
while(m--)
{
int opt,x,y;
read(opt),read(x);
if(opt == 1) read(y),modify(1,n,1,dfn[x],dfn[x] + size[x] - 1,y);
else printf("%lld
",ask(1,n,1,dfn[x],dfn[x] + size[x] - 1) % mod);
}
return 0;
}
E 算式子
数论题。
显然左半边右半边可以分开计算。
不知道为啥用整除分块会TLE自闭到怀疑人生
定义：
(operatorname{cnt}(i)) 为值 (leq i) 的元素的数量。
(operatorname{ans}(i)) 为 (x = i) 时，(sum lfloor dfrac{a_i}{x} floor) 的值。
我们可以枚举 (x)：
对于一个 (x)，可以枚举右半边的商 (k)，即：
(lfloor dfrac{x}{a_i} floor = k)
那么符合条件的 (a_i) 显然在一个连续的值域范围内，即：
(l = k imes x, r = (k + 1) imes x - 1)
对于这个范围内的 (a_i)，对答案的贡献都为 (k)，这一段内的贡献就是 (k imes num)。
可以使用 (cnt) 数组计算 (num)
此时计算完右半边式子的答案了，考虑如何计算左半边式子。
左半边式子乍一看不好处理，但可以发现对于每个 (a_i)，有一段连续的 (x) 的答案是相同的，启示我们用类似的方法。
枚举 (a_i) 的值域 (i) 与商 (k)，同理可以得到：
(l = k imes i, r = (k + 1) imes i - 1)
那么对于 ([l,r]) 中的 (x)，这个 (i) 值对左半边的贡献为 (num imes k)，即 (i) 值出现的次数乘上商。
对于这个区间修改，可以用差分处理，在 (l) 点加上贡献，在 (r + 1) 点减去贡献，最后做前缀和即可。
那么就可以预处理出 (ans) 数组了。
#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
#define int long long
inline char nc()
{
#ifdef DEBUG
return getchar();
#endif
static char buf[bufSize],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
static char c;
r=0;
for(c = nc();!isdigit(c);) c = nc();
for(;isdigit(c);c=nc()) r = r * 10 + c - 48;
return r;
}
const int maxn = 2e6 + 100;
int n,m;
int a[maxn];
int cnt[maxn<<1],ans[maxn<<1];
signed main()
{
read(n),read(m);
for(int i = 1;i<=n;++i) read(a[i]),cnt[a[i]]++;
for(int i = 1;i <= m; i++) if(cnt[i])
for (int k = 1; i * k <= m; ++k)
{
int l = k * i, r = (k + 1) * i - 1;
ans[l] += cnt[i] * k, ans[r + 1] -= cnt[i] * k;
}
for (int i = 1; i <= 2 * m; ++i) cnt[i] += cnt[i - 1];
for (int i = 1; i <= 2 * m; ++i) ans[i] += ans[i - 1];
long long last = 0;
for(int i = 1;i<=m;++i)
{
long long sum = 0;
/*
for (int l = 1, r, k; l <= i; l = r + 1)
{
k = i / l, r = i / k;
sum += k * (cnt[r] - cnt[l - 1]);
}
*/
sum += ans[i];
for (int k = 1; i * k <= m; ++k)
{
int l = k * i, r = (k + 1) * i - 1;
sum += k * (cnt[r] - cnt[l - 1]);
}
last ^= sum;
}
printf("%lld
",last);
return 0;
}
C 璀璨光滑
首先推几个结论：
- 原编号为 (1) 的点新编号为 (0) ，可使字典序最小。
- 距离新编号为 (0) 的点，最短距离为 (x) 的点，新编号中有 (x) 个 (1)。考虑从 (0) 号点开始走，每次增加一个 (1)，最少 (x) 步后才能走出 (x) 个 (1)，且该距离为最小距离，若不如此走，分两种情况：将新编号中 (1) 位走成 (0) 或将新编号中 (0) 位走成 (1)，则都需要走回头路，因此距离更长。
- 新编号含有 (x) 个 (1) 的点，仅与若干个含有 (x + 1) 个 (1) 的点与含有 (x - 1) 个 (1) 的点联通，且若干个含有 (x - 1) 个 (1) 的点新编号的或和即为该点新编号。考虑含有 (x - 1) 个 (1) 的点，根据第二条结论发现它们离 (0) 的距离为 (x - 1)，则其直接与含有 (x) 个 (1) 的点联通的路径即为其最短路。因此可以推出，这些点与含有 (x) 个 (1) 的点仅相差一个包含在 (x) 个 (1) 中的 (1)，且每个点相差的 (1) 位置都不同。这些点或起来，即可得到含有 (x) 个 (1) 的点的新编号。
- 交换二进制位列，对图性质无影响。例如有点：101 001 010，将第一列交换至第三列，第二列交换至第一列，第三列交换至第二列，新编号为：011 010 100，而原先的图关系不变。
- 将所有点的二进制编号看做矩阵，行为点原编号，列为二进制位，值为对应的 (0) 或 (1)，那么交换任意两列，图的性质不变。由于字典序，应当让原编号小的对应的 (1) 的列排在低位。
可以看到，推出的前三个结论与距离密切相关。
整个图可以看做一圈一圈的、距离依次加一的几层，而用该层编号即可推出下层编号，因此可以对原图做一遍宽度优先搜索。
将与原 (1) 号点相连的点随意分配初始编号，进行一次宽度优先搜索，即可找出一组可行解。
再根据后两个结论，将列进行排序，即可找出最优解。
#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
return getchar();
#endif
static char buf[bufSize], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T &r)
{
static char c;
r = 0;
for (c = nc(); !isdigit(c);)
c = nc();
for (; isdigit(c); c = nc())
r = r * 10 + c - 48;
return r;
}
const int maxn = 2e6 + 100, maxm = 5e6 + 100;
int T, n, m;
struct node
{
int to, next;
} E[maxm];
int head[maxn], tot;
inline void add(const int &x, const int &y)
{
E[++tot].next = head[x], E[tot].to = y, head[x] = tot;
}
int q[maxn], qt, qh;
int f[maxn], vis[maxn], inq[maxn];
struct A
{
bool s[maxn];
int id;
} P[22];
bool cmp(const A &a, const A &b)
{
for (int i = 1; i <= (1 << n); ++i)
if (a.s[i] != b.s[i]) return a.s[i] > b.s[i];
return 1;
}
int main()
{
read(T);
while (T--)
{
read(n), read(m);
qh = 1, qt = 0;
tot = 0;
for (int i = 1; i <= (1 << n); ++i)
vis[i] = f[i] = inq[i] = head[i] = 0;
for (int i = 1; i <= m; ++i)
{
int a, b;
read(a), read(b);
add(a, b), add(b, a);
}
vis[1] = 1;
for (int p = head[1], t = 0; p; p = E[p].next)
{
int v = E[p].to;
f[v] = 1 << (t++);
q[++qt] = v;
}
while (qt >= qh)
{
int u = q[qh++];
vis[u] = 1,inq[u] = 0;
for (int p = head[u]; p; p = E[p].next)
{
int v = E[p].to;
if (vis[v]) continue;
f[v] |= f[u];
if (!inq[v]) q[++qt] = v, inq[v] = 1;
}
}
for (int i = 0; i < n; ++i) P[i].id = i;
for (int i = 1; i <= (1 << n); ++i)
for (int j = 0; j < n; ++j)
P[j].s[i] = (f[i] >> j) & 1;
std::sort(P, P + n, cmp);
for (int i = 1; i <= (1 << n); ++i)
{
int res = 0;
for (int j = 0; j < n; ++j) if (P[j].s[i]) res |= (1 << j);
printf("%d ", res);
}
putchar('
');
}
return 0;
}