1004
题意
题目一通描述，弄得我完全懵逼。幸好讨论区，有题目意思。
题目意思为：定义f(l,r) 为区间 [l,r] 的不同元素个数/区间长度。求最小的 f(l,r) 定义域：
。题目意思，翻译转一下就是这么简单。
我很菜，想不出来
看了克拉丽丝的题解还是想不出来
看别人blog看懂了
思路就是，官方题解给出的，二分+线段树；我们二分答案，mid。需要判断mid是否满足，假设我们定义
为区间 [l,r] 的不同元素个数。那么就需要mid满足：
,按照题解进行变形式子可以得到：
，我们可以对r进行从左到右的枚举。在每一次枚举中r就是一个常数。我们可以用线段树维护区间最小值，维护
,每次r+1，需要更新r，r这个区间，区间加mid×r。还有需要给r区间到之前出现a[r]位置的右边这个区间的size都会加1。所以两次更新，每次我们需要查询区间 [1,r] 的区间最小值。先写一个区间维护最小值的插线问线的线段树。进行二分 。over；二分的时候，如果满足条件说明mid还不是最小的所以把上限
，否则下限
；
克拉丽丝快穿JK啊
克拉丽丝的代码好挤啊，没有阅读欲望
自己用毒瘤线段树写一开始wa了，以为是减法运算的锅，
然后，黑康说，你tmp是不是应该是double
好的，我是傻逼
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
double EPS = 1e-11;
int n, pos[N], arr[N], pre[N];
struct ZKWsegTree{
double tree[N];
int M, n;
void build(int n, double Mid){
this->n = n;
M = 1; while (M < n) M <<= 1; if (M!=1) M--;
for (int t = 1 ; t <= n; t++) tree[t+M] = 1.0*t*Mid;
for (int t = n+1; t <= M+1; t++) tree[t+M] = M * 2;
for (int t = M; t >= 1; t--) tree[t] = min(tree[t<<1], tree[t<<1^1]);
for (int t = 2*M+1; t >= 1; t--) tree[t] = tree[t] - tree[t>>1];
}
void update(int l, int r, double val){
double tmp;
for (l+=M-1, r+=M+1; l^r^1; l>>=1, r>>=1){
if (~l&1) tree[l^1] += val;
if ( r&1) tree[r^1] += val;
if (l > 1) tmp = min(tree[l], tree[l^1]), tree[l]-=tmp, tree[l^1]-=tmp, tree[l>>1]+=tmp;
if (r > 1) tmp = min(tree[r], tree[r^1]), tree[r]-=tmp, tree[r^1]-=tmp, tree[r>>1]+=tmp;
}
for (; l > 1; l >>= 1){
tmp = min(tree[l], tree[l^1]), tree[l]-=tmp, tree[l^1]-=tmp, tree[l>>1]+=tmp;
}
tree[1] += tree[0], tree[0] = 0;
}
double query(int l, int r){
double lAns = 0, rAns = 0;
l += M, r += M;
if (l != r){
for (; l^r^1; l>>=1, r>>=1){
lAns += tree[l], rAns += tree[r];
if (~l&1) lAns = min(lAns, tree[l^1]);
if ( r&1) rAns = min(rAns, tree[r^1]);
}
}
double ans = min(lAns + tree[l], rAns + tree[r]);
for (;l > 1;) ans += tree[l>>=1];
return ans;
}
} T;
bool check(double Mid){
T.build(n, Mid);
for (int r = 1; r <= n; r++){
T.update(pre[r] + 1, r, 1.0);
double ans = T.query(1, r);
if (ans <= Mid * (r + 1)) return true;
}
return false;
}
int main(){
//freopen("in.txt", "r", stdin);
int _;
scanf("%d", &_);
for (;_--;){
scanf("%d", &n);
memset(pos, 0, sizeof(pos));
for (int i = 1; i <= n; i++){
scanf("%d", &arr[i]);
pre[i] = pos[arr[i]];
pos[arr[i]] = i;
}
double L = 0, R = 1;
for (;R - L > EPS;){
double Mid = (L + R) / 2.0;
if (check(Mid)) R = Mid;
else L = Mid;
}
printf("%.10lf
", R);
}
return 0;
}
1005
码个题解，过两天补
1007
克拉丽丝题解
首先如果一个点的度数为1，那么它的匹配方案是固定的，继而我们可以去掉这一对点。通过拓扑我们可以不断去掉所有度数为1的点。
那么剩下的图中左右各有m个点，每个点度数都不小于2，且左边每个点度数都是2，而右侧总度数是2m，因此右侧只能是每个点度数都是2。这说明这个图每个连通块是个环，在环上间隔着取即可，一共两种方案。
时间复杂度O(n)。
这题的wa点在于，有很多个环，环与环之间解的合并，这一个是看了克拉丽丝的代码才发现的
其实，是对于每个环有2种方案，环和环之间
common*(X1+Y1)(X2+Y2)….*(XP+YP)=ans
一开始看不懂，以为组合数学烂，后来看这里发现，乘法分配律合并后就是这样
自己的实现方式很蠢，其实是个偶环，一遍dfs统计奇偶就好了，不过看函数名应该就能猜出是啥意思了吧
还有const的时候N和M要分开估计，很容易炸，而且炸了还不返回RTE,返回的TLE
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const LL MOD = 998244353;
const int N = 8e5 + 10;
const int M = 2e6 + 10;
struct graph{
struct Edge{
int from, to, Next, Last;
LL cost;
Edge(){Next = -1; Last = -1;}
Edge(int f, int t, LL c, int n, int l):from(f), to(t), cost(c), Next(n), Last(l){}
} edges[M];
bool vis[N];
int n, in[N], E, head[N];
inline void init(int n){
del_time = 0;
this->n = n, E = -1;
memset(in, 0, sizeof(in));
memset(vis, 0, sizeof(vis));
memset(head, -1, sizeof(head));
}
inline void addEdge(int f, int t, LL c){
//printf("addEdge(%d, %d, %lld)
", f, t, c);
edges[++E] = Edge(f, t, c, head[f], 0);
edges[head[f]].Last = E;
head[f] = E;
in[t]++;
//printf("in[%d] = %d
", t, in[t]);
}
inline void delEdge(int t){
del_time++;
//printf("delEdge(%d)
", t);
Edge &e = edges[t];
if (head[e.from] == t) head[e.from] = e.Next;
else{
edges[e.Last].Next = e.Next;
if (e.Next != -1) edges[e.Next].Last = e.Last;
}
in[e.to]--;
//printf("after delete, in[%d] = %d
", e.to, in[e.to]);
}
LL del_top(){//从度为1的点开始删
LL ans = 1;
int v;
vector <int> po;
for (int i = n/2+1; i <=n; i++) {
//printf("in[%d] = %d
", i, in[i]);
if (in[i] == 1) po.push_back(i);
}
bool flag = 0;
for (int i = 0; i < po.size(); i++){
int v = po[i];
for (int cnt = 1; in[v] == 1; cnt++){
vis[v] = 1;
//printf("v = %d
", v);
int h = head[v];
Edge &e = edges[h];
if (cnt&1) ans = (1LL * ans * e.cost) % MOD;
delEdge(h);
delEdge(h^1);
v = e.to;
}
}
//printf("base = %lld
", ans);
return ans % MOD;
}
LL get_ans(int t){
//printf("edge_num = %d
", t);
Edge e = edges[t];
LL ans = 1;
int start = e.from, last;
//printf("start = %d
", start);
for (int cnt = 1; e.to != start; cnt++){
//printf("to = %d, cost = %lld
", e.to, e.cost);
if (cnt&1) ans = (1LL * ans * e.cost) % MOD;
last = e.from;
vis[last] = 1;
vis[e.to] = 1;
e = edges[head[e.to]];
if (e.to == last) e = edges[e.Next];
}
return ans;
}
LL solve(){
LL ans = del_top();
//printf("base = %lld
", base);
for (int i = 1; i <= n; i++) if (!vis[i]){
LL x = get_ans(head[i]);
LL y = get_ans(edges[head[i]].Next);
//printf("%lld + %lld
", x, y);
ans = (1LL * ans * ((x+y)%MOD)) % MOD;
//printf("ans = %lld
", ans);
}
return ans % MOD;
}
} g;
int main(){
//freopen("in.txt", "r", stdin);
//freopen("out.txt","w", stdout);
int _, v, n;
scanf("%d", &_);
for (LL c; _--;){
scanf("%d", &n);
//printf("n = %d
", n);
g.init(n * 2);
for (int i = 1; i <= n; i++){
for (int j = 0; j < 2; j++){
scanf("%d%lld", &v, &c);
v += n;
g.addEdge(i, v, c);
g.addEdge(v, i, c);
}
}
LL ans = g.solve();
printf("%lld
", ans);
}
return 0;
}