目录
写在前面
比赛地址：https://codeforces.com/gym/105173
以下按个人难度向排序。
就俩人刚开学处于唐氏状态于是开把省赛，呃呃然而还是唐多亏 dztlb 大神爆切两道计数还不算烂。
J
签到。
唉感觉读研究生好可怕感觉还不如直接去打工不想打了就跑路。
Code by dztlb:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int lim=1e18;
const int N=2e5+5;
inline int read(){
int x=0,f=1; char s;
while((s=getchar())<'0'||s>'9') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x*10)+(s^'0'),s=getchar();
return x*f;
}
int T;
signed main(){
puts("39.20");
return 0;
}
D
签到，博弈，
实际诈骗题，手玩下发现后手获胜的情况根本不存在，于是直接 lose。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n;
std::cin >> n;
std::cout << "lose\n";
}
return 0;
}
A
签到，枚举。
乘方后再开方是无贡献的，则操作顺序一定是先一直开方再一直乘方。
于是直接枚举开方次数，再大力乘方直到第一个已经出现过的数或者大于上限 \(10^9\)，则可以保证之后的乘方的值一定不会重复出现。
偷懒写个 map，总时间复杂度 \(O(\log x\log v)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const LL kInf = 1e9;
//=============================================================
LL ans;
std::map<LL, bool> yes;
//=============================================================
void check(int remain_, LL t_) {
++ ans;
yes[t_] = 1;
int flag = 0;
while (remain_ && t_ <= kInf) {
t_ = t_ * t_;
if (yes.count(t_)) {
flag = 1;
break;
}
yes[t_] = 1;
-- remain_;
++ ans;
}
if (!flag) ans += remain_;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
LL x, k; std::cin >> x >> k;
if (x == 1) {
std::cout << 1 << "\n";
return 0;
}
ans = 1 + k;
yes[x] = 1;
for (int i = 1; i <= k; ++ i) {
LL t = sqrt(x);
if (t == 1) {
++ ans;
break;
}
check(k - i, t);
x = t;
}
std::cout << ans << "\n";
return 0;
}
/*
9 10
5 2
*/
E
签到，数学，枚举。
设给定字符串中 1 的数量为 \(m\)，记 \(\operatorname{cnt}\) 表示某个正整数中 1 的个数，则有下式成立：
\[(m + \operatorname{cnt}(B)) \bmod 2^k = B \]把 \(\bmod 2^k\) 拆掉然后移项，则有：
\[m - c\times 2^k = B - \operatorname{cnt}(B) \]此时等式左右两部分是独立的，于是考虑预处理右边，并枚举左边。因为 \(B - \operatorname{cnt}(B)\ge 0\)，则 \(m \ge c\times 2^k\)，可行的 \(c\) 的数量级为 \(O(m)\) 级别，于是可以考虑直接大力枚举 \(c\) 计算 \(m-c\times 2^k\)，并检查对应的 \(B - \operatorname{cnt}(B)\) 的最小值即可。
总时间复杂度 \(O\left(2^k + \sum n\right)\) 级别。
妈的赛时没特判 0 挂了四发太唐乐。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e6 + 10;
//=============================================================
int n, k, m, all, ans;
std::string s;
int val[kN];
//=============================================================
int count(int x_) {
int ret = 0;
while (x_) {
if (x_ & 1) ++ ret;
x_ >>= 1;
}
return ret;
}
std::string get(int x_) {
std::string t;
for (int i = 1; i <= k; ++ i) {
if (x_ & 1) t.push_back('1');
else t.push_back('0');
x_ >>= 1;
}
std::reverse(t.begin(), t.end());
return t;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
for (int i = 0; i <= 2e6; ++ i) val[i] = -1;
for (int i = 0; i <= 2e6; ++ i) {
int c = count(i);
if (val[i - c] == -1) val[i - c] = i;
}
int T; std::cin >> T;
while (T --) {
std::cin >> n >> k;
std::cin >> s; s = "$" + s;
m = 0, all = (1 << k), ans = kN;
for (int i = 1; i <= n; ++ i) m += (s[i] == '1');
for (int i = 0; i * all <= m; ++ i) {
if (0 <= val[m - i * all] && val[m - i * all] < all) {
ans = std::min(ans, val[m - i * all]);
}
}
if (ans == kN) std::cout << "None\n";
else std::cout << get(ans) << "\n";
}
return 0;
}
/*
1
2 1
0
*/
M
枚举，计算几何
实际大力枚举题。
发现房子的上下两部分实际上是独立的，仅需保证这两部分分别合法，且在天花板不同的两侧即可。判断直角使用点乘，判断点在直线的哪一侧使用叉乘即可。
于是考虑 \(O(n^3)\) 地枚举天花板和房顶并预处理对于每个天花板，两侧合法的屋顶数量有多少。然后再 \(O(n^3)\) 地枚举天花板和房子下部分矩形的另一个点，并计算第四个点检查是否存在，再直接检查天花板另一侧的屋顶数量即可。
发现仅比较距离和算点乘叉乘的符号因此可以全程用 LL。偷懒写个 map，总时间复杂度 \(O(n^3\log n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 310;
//=============================================================
int n, x[kN], y[kN];
struct Point {
LL x, y;
} a[kN];
std::map <pr <LL, LL>, bool> node;
int roof[kN][kN][2];
//=============================================================
LL distance2(LL x1_, LL y1_, LL x2_, LL y2_) {
return 1ll * (x1_ - x2_) * (x1_ - x2_) + (y1_ - y2_) * (y1_ - y2_);
}
LL dotProduct(LL x1_, LL y1_, LL x2_, LL y2_) {
return 1ll * x1_ * x2_ + y1_ * y2_;
}
LL crossProduct(LL x1_, LL y1_, LL x2_, LL y2_) {
return 1ll * x1_ * y2_ - x2_ * y1_;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n;
for (int i = 1; i <= n; ++ i) {
std::cin >> x[i] >> y[i];
node[mp(x[i], y[i])] = 1;
}
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
for (int k = 1; k <= n; ++ k) {
if (i == k || j == k) continue;
if (distance2(x[i], y[i], x[k], y[k]) ==
distance2(x[j], y[j], x[k], y[k])) {
LL cp = crossProduct(x[j] - x[i], y[j] - y[i], x[k] - x[i], y[k] - y[i]);
if (cp == 0) continue;
++ roof[i][j][cp > 0];
}
}
// std::cout << i << " " << j << " " << roof[i][j][0] << "-" << roof[i][j][1] << "\n";
}
}
LL ans = 0;
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
for (int k = 1; k <= n; ++ k) {
if (i == k || j == k) continue;
if (dotProduct(x[j] - x[i], y[j] - y[i], x[k] - x[i], y[k] - y[i]) != 0) continue;
LL xl = x[k] + x[j] - x[i];
LL yl = y[k] + y[j] - y[i];
if (!node.count(mp(xl, yl))) continue;
LL cp = crossProduct(x[j] - x[i], y[j] - y[i], x[k] - x[i], y[k] - y[i]);
if (cp == 0) continue;
ans += roof[i][j][(cp > 0) ^ 1];
}
}
}
std::cout << ans << "\n";
return 0;
}
F
数论，搜索
实际大力题呃呃，妈的怎么这么多大力题
题目要求实际即下式：
\[p\times k^{\infin} \bmod q = 0 \]即仅需保证：
- \(q\) 中仅有 \(p, k\) 中的质因数。
- \(q\) 中各质因数的次数不大于 \(p\times k^{\infin}\) 中对应质因数的次数。
因为 \(p\times k\) 的质因数至多只有不到 100 个，且有 \(q\le x\le 10^{14}\)，由数学直觉可知实际上答案的数量级并不会很大，又发现给了 5s 的时限，于是考虑直接 DFS 大力枚举因数即可。可以保证一定仅会搜到有贡献的答案则复杂度并不会很高。
注意搜因数过程中可能爆 LL。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define i128 __int128
const int kN = 1e6;
//=============================================================
LL p, x, k, ans, prisz;
std::vector<LL> pri;
std::map<LL, int> cnt;
//=============================================================
void init() {
LL temp = p;
for (LL i = 2; i * i <= temp; ++ i) {
if (temp % i != 0) continue;
if (!cnt.count(i)) pri.push_back(i), cnt[i] = 0;
while (temp % i == 0) temp /= i, cnt[i] = cnt[i] + 1;
}
if (temp != 1) {
if (!cnt.count(temp)) pri.push_back(temp), cnt[temp] = 0;
cnt[temp] = cnt[temp] + 1;
}
temp = k;
for (LL i = 2; i * i <= temp; ++ i) {
if (temp % i != 0) continue;
if (!cnt.count(i)) pri.push_back(i);
cnt[i] = kN;
while (temp % i == 0) temp /= i;
}
if (temp != 1) {
if (!cnt.count(temp)) pri.push_back(temp);
cnt[temp] = kN;
}
}
void dfs(int now_, i128 prod_) {
if (prod_ > x) return ;
if (now_ >= prisz) {
++ ans;
// std::cout << prod_ << "\n";
return ;
}
for (int i = 0, sz = cnt[pri[now_]]; i <= sz && prod_ <= x; ++ i) {
dfs(now_ + 1, prod_);
prod_ *= pri[now_];
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> p >> x >> k;
init();
prisz = pri.size();
// for (auto [a, b]: cnt) std::cout << a << " " << b << "\n";
dfs(0, 1);
std::cout << ans << "\n";
return 0;
}
L
计数，栈，括号序列。
发现对于一个括号嵌套的形式，一定是从内到外操作的。则实际上规定了操作的一个拓扑序，操作间构成了一个有根树的结构，不同子树间的操作是独立的，它们在操作序列中的顺序任意；有祖先关系的节点间必须保证操作顺序。
于是考虑按照括号的包含关系建树。因为加括号是每次往括号序列的末端加的，考虑倒序枚举括号序列进行操作序列的构造，并考虑枚举到的括号可以被插入到操作序列的什么位置，即按照树的先序遍历的倒序进行构造。对于倒序枚举到的某个节点 \(i\)：
- 若为叶节点，则仅能插入到操作序列的开头，对答案贡献为 1；
- 若不为叶节点，则可插入操作序列的任意位置，对答案贡献为 \(n-i+1\)。
贡献的乘积即为答案。
当然也可以直接考虑倒序枚举括号序列，根据组合意义进行推导，可以得到和上面的式子本质一样的做法。赛时 dztlb 大神就是这样直接倒着做就切了太牛逼了。
Code by dztlb：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int lim=1e18;
const int N=1e6+5;
const int mod=998244353;
inline int read(){
int x=0,f=1; char s;
while((s=getchar())<'0'||s>'9') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x*10)+(s^'0'),s=getchar();
return x*f;
}
int n;
char s[N];
int st[N],top;
int a[N],tot;
int id[N];
signed main(){
scanf("%s",s+1);
n=strlen(s+1);
top=1;
st[1]=1;
int cnt=0;
for(int i=2;i<=n;++i){
if(s[i]==')'){
if(st[top]==i-1){
++cnt;
id[i]=cnt;
--top;
}else{
id[i]=id[i-1];
a[++tot]=id[i]-1;
--top;
}
}else{
st[++top]=i;
}
}
int ans=1;
cnt--;
for(int i=tot;i>=1;--i){
ans=ans*(cnt-a[i]+1+tot-i)%mod;
}
cout<<ans;
return 0;
}
/*
((()())()())(())
(())()
(())()()()()()()()()()()()
*/
I
计数，DP。
妈的 dztlb 大神最后爆切，可惜吃了 9 发呃呃唐。
显然考虑计数 DP。设当前填到了前缀 \(1\sim i\) 且令其合法的方案数为 \(f_i\)。由性质可保证所有前缀的最后 \(k\) 个数一定构成大小为 \(k\) 的排列，于是考虑枚举填到 \(i\) 时最后一步添加了多少数 \(j\) 使得 \([i-k+1, i]\) 也为排列。初始化 \(f_{k} = k!\)。
由于排列是不重复的，并不需要考虑之前的数的具体种类，仅需考虑其个数即可。于是记 \(g_{j}\) 表示在一个大小为 \(k\) 的排列后面添加 \(j\) 个数使得下列两条件成立的方案数：
- 新数列区间 \([j + 1, j + k]\) 构成大小为 \(k\) 的排列；
- 对于任意 \(1\le i\le j\)，\([i, i + k - 1]\) 不是排列，即保证添加 \(j\) 个数后最后一个长度为 \(k\) 的区间一定是好的，从而保证上述对 \(f\) 的定义的性质。
则有：
\[f_{i} = \sum_{j=1}^{k} f_{i - j}\times g_{j} \]然后考虑如何预处理 \(g\)，显然此时添加 \(j\) 个数的权值是唯一的，于是考虑将添加的数看做 \(1\sim j\)，仅需考虑满足上述定义即可。发现上述限制等价于对于添加的 \(j\) 个数中构成的排列 \(1\sim j\)，任意小于 \(j\) 的前缀 \(i\) 不能是一个 \(1\sim i\) 的排列。于是考虑容斥，枚举每一个不合法排列最后一个违反限制的前缀。显然第一个不合法前缀为 \(i\) 时，方案数即为子问题 \(g_{i}\)，再乘上后面填数的方案数。则显然有：
\[g_{j} = j! - \sum_{i=1}^{j-1} (j-i)!\times g_{i} \]于是做完了，式子很简洁。总时间复杂度 \(O(k^2 + nk)\)。
虽然场上写了快速取模但实际上常数并不大并无必要，不写也能跑过去。
Code by dztlb：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int lim=1e18;
const int N=1e6+5;
const int mod=998244353;
inline int read(){
int x=0,f=1; char s;
while((s=getchar())<'0'||s>'9') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x*10)+(s^'0'),s=getchar();
return x*f;
}
int n,k;
int a[N],fac[N];
typedef __int128_t i128;
i128 _base=1;
inline int mol(int x){return x-mod*(_base*x>>64);}
int pre[N],onl[N];
signed main(){
_base=(_base<<64)/mod;
cin>>n>>k;
fac[0]=0;fac[1]=1;
pre[1]=1;
for(int i=2;i<=n;++i){
fac[i]=fac[i-1]*i%mod;
pre[i]=mol(pre[i-1]+fac[i]);
}
if(n<k){
puts("0");
return 0;
}
if(n==k){
cout << fac[n] << endl;
return 0;
}
a[k]=1;
onl[1]=1;
for(int i=2;i<=k;++i){
onl[i]=fac[i];
for(int j=1;j<i;++j){
onl[i]=mol(onl[i]-mol(onl[j]*fac[i-j]));
}
}
a[k]=fac[k];
for(int x=k+1;x<=n;++x){
int tmp=0;
for(int i=1;i<=k;++i){
if(x-i<k) break;
a[x] += mol(a[x-i]*onl[i]), a[x] = mol(a[x]);
}
}
cout<<a[n]<<endl;
return 0;
}
H
二分答案，图论
场上一直跟榜没开这题呃呃，我们是擅长这种经典题的没开到亏亏亏
为了方便讨论钦定 1 为根固定树的形态，考虑二分答案 \(\operatorname{mid}\)，枚举 \(m\) 条给定的路径 \((x, y)\) 并检查：
- 若路径长度 \(\operatorname{dis} \le \operatorname{mid}\)，则根可任意取。
- 否则汇合点一定在路径 \((x, y)\) 上，考虑路径端点 \(x\) 到 \(\operatorname{lca}\) 的长度 \(d\)：
- 若 \(d< \operatorname{mid}\)，则合法的汇合点一定在 \(x\) 到其 \(\operatorname{mid}\) 级祖先这条路径上，则 \(x\) 的 \(\operatorname{mid}\) 级祖先的子树内所有点都是合法的；
- 若 \(d\ge \operatorname{mid}\)，则合法的汇合点一定在 \(x\) 到 \(y\) 的 \(\operatorname{dis} - \operatorname{mid}\) 级祖先这条路径上，则除了\(y\) 的 \(\operatorname{dis} - \operatorname{mid}-1\) 级祖先的子树内所有点都是合法的。
- 另一端点 \(y\) 同理。
若上述所有合法点集有交集，说明有解。发现上述过程中合法的点转化到 dfs 序上至多只有 2 段连续的区间，于是直接差分实现即可。
需要求 \(\operatorname{lca}\) 和节点的 \(k\) 级祖先，使用倍增实现，总时间复杂度 \(O(n\log n + m\log^2 n)\) 级别。
妈的又没特判 0 挂了一发太唐乐。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, m, x[kN], y[kN], lca[kN], dis[kN];
int edgenum, head[kN], v[kN << 1], ne[kN << 1];
int dfnnum, fa[kN][21], dep[kN], dfn[kN], L[kN], R[kN];
int d[kN];
//=============================================================
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Dfs(int u_, int fa_) {
L[u_] = dfn[u_] = ++ dfnnum;
dep[u_] = dep[fa_] + 1;
fa[u_][0] = fa_;
for (int i = 1; i <= 18; ++ i) {
fa[u_][i] = fa[fa[u_][i - 1]][i - 1];
}
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
Dfs(v_, u_);
}
R[u_] = dfnnum;
}
int Lca(int u_, int v_) {
if (dep[u_] < dep[v_]) std::swap(u_, v_);
for (int i = 18; i >= 0; -- i) {
if (dep[fa[u_][i]] >= dep[v_]) {
u_ = fa[u_][i];
}
}
if (u_ == v_) return u_;
for (int i = 18; i >= 0; -- i) {
if (fa[u_][i] != fa[v_][i]) {
u_ = fa[u_][i];
v_ = fa[v_][i];
}
}
return fa[u_][0];
}
int get(int u_, int k_) {
for (int i = 18; i >= 0; -- i) {
if (k_ >= (1 << i)) {
u_ = fa[u_][i];
k_ -= (1 << i);
}
}
return (k_ == 0) * u_;
}
int Dis(int u_, int v_) {
return dep[u_] + dep[v_] - 2 * dep[Lca(u_, v_)];
}
bool check(int mid_) {
for (int i = 0; i <= n; ++ i) d[i] = 0;
for (int i = 1; i <= m; ++ i) {
if (dis[i] <= mid_) {
d[0] += 2;
continue;
}
if (dep[x[i]] - dep[lca[i]] > mid_) {
int p = get(x[i], mid_);
++ d[L[p]], -- d[R[p] + 1];
} else {
int p = get(y[i], dis[i] - mid_ - 1);
if (!p) return false;
++ d[0], -- d[L[p]], ++ d[R[p] + 1];
}
if (dep[y[i]] - dep[lca[i]] > mid_) {
int p = get(y[i], mid_);
++ d[L[p]], -- d[R[p] + 1];
} else {
int p = get(x[i], dis[i] - mid_ - 1);
if (!p) return false;
++ d[0], -- d[L[p]], ++ d[R[p] + 1];
}
}
for (int i = 1; i <= n; ++ i) d[i] += d[i - 1];
for (int i = 0; i <= n; ++ i) if (d[i] == 2 * m) return true;
return false;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n >> m;
for (int i = 1; i < n; ++ i) {
int u_, v_; std::cin >> u_ >> v_;
Add(u_, v_), Add(v_, u_);
}
Dfs(1, 0);
for (int i = 1; i <= m; ++ i) {
std::cin >> x[i] >> y[i];
lca[i] = Lca(x[i], y[i]);
dis[i] = Dis(x[i], y[i]);
}
int ans = n;
for (int l = 0, r = n; l <= r; ) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
std::cout << ans << "\n";
return 0;
}
写在最后
学到了什么：
- H：对点集的标记转化到 dfs 序上进行。
- E、H：考虑答案能否取到边界情况！0！0！0！
我是？？？
标签：std,Invitational,Northeast,Contest,int,LL,mid,long,operatorname From： https://www.cnblogs.com/luckyblock/p/18398471