「Codeforces 1034C」Region Separation
没有思维能力了
题意
给你一棵 \(n\) 个点的树,有点权\(a_1,..,a_n\),整棵树是一个1级区域
除非 \(i\) 是最后一个等级,否则每一个
i级区域
都要被分成至少两个i+1级区域
每个点必须恰好属于一个每种等级的区域
一个区域必须是连通的
每个相同等级的区域必须拥有相同的点权和
求有多少种不同的划分方案,模 \(10^9+7\)
\(n\le 10^6,a_i\le 10^9\)
没有思维能力了
给你一棵 \(n\) 个点的树,有点权\(a_1,..,a_n\),整棵树是一个1级区域
除非 \(i\)
是最后一个等级,否则每一个i级区域
都要被分成至少两个i+1级区域
每个点必须恰好属于一个每种等级的区域
一个区域必须是连通的
每个相同等级的区域必须拥有相同的点权和
求有多少种不同的划分方案,模 \(10^9+7\)
\(n\le 10^6,a_i\le 10^9\)
给你一张 \(n\) 个点 \(m\) 条边的无向图,满足每一个简单环上的点两两有边
\(q\) 次询问两个点之间的最短路
\(n\le 10^5,m\le5*10^5,q\le2*10^5\)
给你一张 \(n\) 个点 \(m\) 条边的无向图,每个点有点权,\(q\) 次操作
C a w
,将第 \(a\)
个点的权值改为 \(w\)
A a b
,询问 \(a\)
到 \(b\)
所有可能的简单路径上的点权最小值
简单路径即不经过一个点超过一次的路径
\(n,m,q\le 10^5\)
给定 \(n\) 次多项式 \(F(x)\),求 \(G(x)\) 满足
\[ G(x)\equiv \left(\left(1+\ln\left(2+F(x)-F(0)-\exp\left(\int\frac{1}{\sqrt{F(x)}}\right)\right)\right)^k\right)' \pmod{x^n} \]
保证常数项是模 \(998244353\) 的二次剩余。
注意 \(\pm\sqrt{F(x)}\) 均为合法解,你只需要输出 \(\sqrt{F(x)}\),舍去 \(-\sqrt{F(x)}\),我们认为两个解中常数项较小的解为 \(\sqrt{F(x)}\)。
所有运算在模 \(998244353\) 意义下进行。
有 \(n\) 座城市,第 \(i\) 座城市的人口是 \(w_i\),有一些无向边。
现在城市被划分为了若干个州,每个州至少包含一个城市,每个城市恰好在一个州内。
设 \(V_i\) 是第 \(i\) 个州的城市集合。
定义一条道路是一个州的内部道路,当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同,不经过任何不属于这个州的城市,且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径(路径长度可以为 \(0\)),则称这个州是不合法的。
定义第 \(i\) 个州的满意度为:第 \(i\) 个州的人口在前 \(i\) 个州的人口中所占比例的 \(p\) 次幂,即:
\[\left(\frac{\sum_{x\in V_i}w_x}{\sum_{j=1}^i\sum_{x\in V_j}w_x}\right)^p\]
定义一个划分的满意度为所有州的满意度的乘积。
求所有合法的划分方案的满意度之和。
答案对 \(998244353\) 取模。
\(n\le 21,0\le p\le 2\)
时限 \(10s\)
给你两个数组 \(A[0\dotsc 2^m-1]\) 和 \(B[0 \dotsc 2^m-1]\)
你需要计算
\[C[k]=\sum_{i~{\rm and}~j=k}A[i~{\rm xor}~j]\times B[i~{\rm or}~j]\]
输出 \(\sum_{i=0}^{2^m-1}C[i]\times 1526^i \bmod 998244353\)
\(m\le 19\)
NOIP2018 唯一没做出来的题
要是写完两题后直接去打暴力大概也不止50分吧
反正确实跪在这题了
你有一个 \(n\) 行 \(m\) 列的矩阵,左上角为 \((0,0)\)
每一个位置有一个数字 \(0/1\)
你需要从 \((0,0)\) 走到 \((n-1,m-1)\),只能向右或向下走 \((R/D)\),一共 \(n+m-2\) 步,这会形成一条路径
把方向记下来可以得到同样长度的只包含 \(R/D\) 的字符串 \(w(P)\)
并且经过的 \(n+m-1\) 个位置的数字连起来可以得到一个 \(01\) 串 \(s(P)\)
你需要求出有多少种填数的方案,使得对于任意两条路径 \(P_1,P_2\),若 \(w(P_1)>w(P_2)\),那么 \(s(P_1)\le s(P_2)\)
模 \(10^9+7\)
\(n\le 8,m\le 10^6\)
平面上有\(n\)个圆,编号\(1..n\)
重复如下操作直到不存在圆
选择一个半径最大的圆,如果有多个,选择编号最小的
把所有与第1步选出的圆有交的圆删除
其中两个圆有交当且仅当存在一个点,这个点同时被两个圆包含,包含定义为点在圆内或者圆上
\(n\le 3*10^5\)
你有一张 \(n\) 个点 \(m\) 条边的无向图,你需要选择三个互不相同的点 \(s,c,f\)
询问有多少种选择的方案使得存在至少一条从 \(s\) 出发经过 \(c\) 到达 \(f\) 的简单路径(不经过重复点)
\(n\le 10^5,m\le 2*10^5\)
您正在打galgame,然后突然发现您今天太颓了,于是想写个数据结构题练练手:
给出一个长为\(n\)的序列\(a\)。
有\(m\)个询问,每次询问三个区间,把三个区间中同时出现的数一个一个删掉,问最后三个区间剩下的数的个数和,询问独立。
注意这里删掉指的是一个一个删,不是把等于这个值的数直接删完,比如三个区间是\([1,2,2,3,3,3,3]\),\([1,2,2,3,3,3,3]\)与\([1,1,2,3,3]\),就一起扔掉了\(1\)个\(1\),\(1\)个 \(2\),\(2\)个\(3\)。
\(n,m\le 10^5,a_i\le 10^9\)