多校第四场补题

Posted by Cww97 on 2017-08-04

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/76691494
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

好的,我是傻逼

这里写图片描述
这里写图片描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#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\n", 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#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)\n", 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\n", t, in[t]);
}

inline void delEdge(int t){
del_time++;
//printf("delEdge(%d)\n", 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\n", 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\n", 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\n", 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\n", ans);
return ans % MOD;
}

LL get_ans(int t){
//printf("edge_num = %d\n", t);
Edge e = edges[t];
LL ans = 1;
int start = e.from, last;
//printf("start = %d\n", start);
for (int cnt = 1; e.to != start; cnt++){
//printf("to = %d, cost = %lld\n", 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\n", 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\n", x, y);
ans = (1LL * ans * ((x+y)%MOD)) % MOD;
//printf("ans = %lld\n", 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", 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\n", ans);
}
return 0;
}