省流： 计算贡献。考虑如何减去三点一线，当且仅当三点一线 a,b,ca,b,ca,b,c, 且 ab=bcab=bcab=bc 时会产生贡献，我们枚举 aaa 和 ccc, 通过中点公式得到中点 mmm, 只需要判断点 mmm 是否在 nnn 里面出现过就行。这一部分答案记为 cntcntcnt。 对于所有合法等腰+非法的答案 ansansans, 我们通过枚举两点, 确定所有边, 并存入 EdgeEdgeEdge, 对于所有边我们记录他的一个端点和长度。对 EdgeEdgeEdge 双关键字排序后, 扫一遍, 我们就可以知道任意具有公共交点长度相同的边的重复次数 p, 那么一种 ppp 对答...

牛客 上海理工L：捡贝壳 状压线段树+节点合并 题目省流：长度 nnn 的序列，每个值表示成 aiaiai，aiaiai 有且仅有四种 (ai∈[1,4]ai∈[1,4]ai∈[1,4])。mmm 次操作或询问，操作 111 将 [l,r][l,r][l,r] 赋值成同一个值 xxx，操作 222 询问 [l,r][l,r][l,r] 内是否存在最短的一段连续区间，其中包含四种 aiaiai，有则输出长度，否则输出 −1-1−1。 10 1 2 3 4 1 2 3 4 1 2 6 1 3 5 2 1 4 6 3 2 2 10 2 7 10 2 6 9 2 6 10  4 4 -1 4  思路：...

https://ac.nowcoder.com/acm/problem/20203  大佬原帖： https://www.cnblogs.com/acceptedzhs/p/solution-p5261.html  %%%% tql 写了点注释 #include <iostream> #include <bitset> #include <algorithm> #include <vector> #define int long long using namespace std; const int N = 110, S = 1010; int ...

很有意思的题 题目  样例 6 1 1 4 5 1 4 1 2 1 3 2 4 2 5 3 6  158    思路： dfsdfsdfs 求节点深度 题目给出了一个由 nnn 个有权重的节点、n−1n-1n−1 条无向边构成的一棵树， 且需要用到节点的深度，所以要用 dfsdfsdfs 一遍预处理所有节点的深度的没跑了。 根节点深度为 000， 题目规定根节点为 111 。 int d[N]; void dfs(int x, int f) { for (auto i: h[x]) { if (i == f) continue; d[i] = d[x] + 1; dfs(i, x); } } ...

/* 如果 [l, r] 满足m个条件，那么[l, r+1]也满足条件 考虑尺取(双指针) 区间共长n，对于每一个i，我们可以求出最小的j，令其满足 满足m个条件、且从i开始，在j结束的最短子区间，设其长度为len 那么len个人从i开始坐，坐到j刚好满足， 如果有len+1个人，从i开始坐到j+1, 也满足 所以len个人、len+1个人坐法的方案可以分别+1 当且仅当 len <= (n-i+1) 是合法的(你总不超出n了吧，且左端点确定了) 我们可以注意到，我们要将len, len+1, len+2.....max(len) 都加上1， 即区间加、求单点 考虑差分 我们用suf维护...

对于铸币(指我)非常不友好的题目，心态容易写炸。 观察数据范围，显然需要读入字符串类型 题目   样例及hack： 样例 1 4 Happy birthday to YXGG  hack1 0 500 Happy birthday to YXGG //0.5直接把小数抹掉，变成0.0，赚了  hack2 101101 50 Happy birthday to MFGG // 抹掉小数，整数进1，亏了  hack3 200202211 00000 PLMM // 把小数抹掉，相当于没抹掉  hack4 101 0500 Happy birthday to YXGG  hack5 808 5000...

牛客小白月赛 61 E 排队 题目  样例 3 1 2 3  9  思路 from 机房学长 翻译题目 nnn 个体总共有 n!n!n! 种排队方式，记 Pi(a)P_i(a)Pi​(a) 表示序列 aaa 的第 iii 种排队方式，cnt(Pi(a))cnt(Pi(a))cnt(Pi(a)) 表示PiP_iPi​ 的逆序对个数。PLMM 想知道 ∑i=1n!cnt(Pi(a)) {\textstyle \sum_{i=1}^{n!}} cnt(Pi(a))∑i=1n!​cnt(Pi(a)) 给定一个 nnn 个数，在所有排列顺序中，每种排列的分别的逆序对总数的总数是多少 所以我们根据题意就能...

牛客小白月赛61 C 小喵觅食 题目   格式  样例 5 3 2 1 ... .M. ... ... .P.  3  PLMM 进行移动 (5,2)→(4,2)→(3,2)(5,2)→(4,2)→(3,2)(5,2)\rightarrow(4,2)\rightarrow(3,2)(5,2)→(4,2)→(3,2)(5,2)→(4,2)→(3,2)(5,2)→(4,2)→(3,2)，此时小喵闻到了坐标 (3,2)(3,2)(3,2)(3,2)(3,2)(3,2) 位置上小鱼干的气味并进行移动 (2,2)→(3,2)(2,2)→(3,2)(2,2)\rightarrow(3,2)(2,2)→(3...

学佳澳杯 G 密码专家 区间dp 题目  样例及输出 1 32 40 17 40 35 13 19 7 3 5 11 41 42 6 17 47 21 42 35 23 20 45 36 16 42 5 addbd  88  思路 区间dp 我们规定字符串s[], 下标从1开始 1、一段区间 [i, j], 我们想要从s中删去这一段, 我们必须一个点、一个点的删去(因为题目说的) 2、我们假设s从开始到完全删去[i,j]这段字符串的过程最后一个字母是s[k] 3、那么我们可以 由 从s中删去[i,k] 和 从删去[k,j] 两个步骤推出 从s中删去[i,j] 。 准确来说, 删[i,k] 和 ...

学佳澳杯 F 区间计数 双指针、尺取 题目  样例及输出 4 2 1 3 2 4 3 2 2 4  5   思路 from 神秘的学长 双指针, 尺取 枚举每一个i可以到达的最远的j, 使得<i, j>内, 每一个人的敌人数量为0, 我们用 emy[] 记录 1、一段区间是合法的, 当且仅当区间内所有的人的所有敌人, 在此区间内出现次数为0 即 我们只要保证每次右端点加入的点, 自身的敌人不在区间内, 我们用emy记录i敌人的个数 while (j <= n && !emy[a[j]]) j ++ ; 2、每加入一个点a[j], 我们都要更新一下它的敌人A, ...