时间有点短，做到后面稍微有点慌
怎么就想不到应该用什么算法呢。。。
赛时估计：$100+30+0$
赛后测试：$100+30+0$
赛后一看，还真没难题
T1 购物
直接模拟即可
T2 第 k 小
想的是将所有区间排序，顺着区间统计数量，该区间结束就在下一个区间的这个位置接着跑
但是值域 $2\times10^9$ 跑不过啊 
做的时候一直在想怎么缩小值域去统计结果（
最后打了个暴力就跑路了
应该但没意识到这个答案具有二分性质，即小于第 $k$ 小的数都比第 $k$ 小的数小（什么废话
但是一看题解就发现了。。。呜
令 $x$ 表示第 $k$ 小的数，二分 $x$
check 的时候扫一遍所有区间统计小于等于 $x$ 的数的个数 $s$
如果 $s \ge K$ 则表示 $x$ 取大了
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
| #include<bits/stdc++.h>
using namespace std;
const int maxN = 1e5;
struct Segment {
int l, r;
friend bool operator < (Segment A, Segment B) {
if (A.l != B.l) return A.l < B.l;
return A.r > B.r;
}
} A[maxN];
int N, K;
bool check(int k) {
int cnt = 0;
for (int i = 1; i <= N; i++) {
if (A[i].l <= k) cnt += min(k, A[i].r) - A[i].l + 1;
}
return cnt >= K;
}
int main() {
freopen("thekth.in", "r", stdin);
freopen("thekth.out", "w", stdout);
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
int l, r;
scanf("%d%d", &A[i].l, &A[i].r);
}
scanf("%d", &K);
int l = -1e9;
int r = 1e9;
int ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
printf("%d", ans);
return 0;
}
|
T3 最大半连通子图
考的时候在要不要略过 T2 之间摇摆不定导致只剩半小时写这道题了…寄！
半小时糊了一个实际上思路正确但被我写挂了的TLE做法
将所有的 scc 缩成一个点，那么最大半联通子图实际上就是找缩完点形成的这张 DAG 上的最长链
使用拓扑排序更新最长链的长度，如果成功更新，那么重置长度最大值及个数；如果当前长度与最长链长度相同，则更新最长链个数。
Lg 上这么就能过了，但是 Lemon 测的时候还得卡卡常才能过（
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
| #include<bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 10;
int MOD;
vector<int> G[maxN];
int N, M;
stack<int>s;
int ins[maxN];
int dfn[maxN];
int low[maxN];
int cnt = 0;
int sccNum = 0;
int sccSiz[maxN];
int scc[maxN];
void tarjan(int u) {
cnt++;
dfn[u] = cnt;
low[u] = cnt;
s.push(u);
ins[u] = 1;
for (auto i : G[u]) {
int v = i;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (ins[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
ins[u] = 0;
sccNum++;
scc[u] = sccNum;
sccSiz[sccNum] = 1;
while (s.top() != u) {
int sT = s.top();
scc[sT] = sccNum;
ins[sT] = 0;
sccSiz[sccNum]++;
s.pop();
}
s.pop();
}
return;
}
vector<int> G2[maxN];
int inD[maxN];
inline void reBuid() {
unordered_set<long long> S;
for (int i = 1; i <= N; i++) {
for (auto j : G[i]) {
long long H = 100000ll * scc[i] + scc[j];
if (S.count(H)) continue;
if (scc[i] != scc[j]) {
G2[scc[i]].push_back(scc[j]);
inD[scc[j]]++;
}
S.insert(H);
}
}
}
int dp[maxN];
int num[maxN];
inline void Topo() {
queue<int> Q;
for (int i = 1 ; i <= sccNum; i++) {
if (inD[i] == 0) Q.push(i);
dp[i] = sccSiz[i];
num[i] = 1;
}
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (auto i : G2[u]) {
if (dp[i] < dp[u] + sccSiz[i]) {
dp[i] = dp[u] + sccSiz[i];
num[i] = num[u];
} else if (dp[i] == dp[u] + sccSiz[i]) {
num[i] = (num[u] % MOD + num[i] % MOD) % MOD;
}
if (--inD[i] == 0) Q.push(i);
}
}
}
int main() {
ios :: sync_with_stdio(false);
freopen("semi.in", "r", stdin);
freopen("semi.out", "w", stdout);
cin >> N >> M >> MOD;
for (int i = 1; i <= M; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
}
for (int i = 1; i <= N; i++) if (!dfn[i]) tarjan(i);
reBuid();
Topo();
int dis = -1;
int ans = -1;
for (int i = 1; i <= sccNum; i++) {
if (dp[i] > dis) {
dis = dp[i];
ans = num[i];
} else if (dp[i] == dis) {
ans = (ans % MOD + num[i] % MOD) % MOD;
}
}
printf("%d\n%d", dis, ans);
return 0;
}
|
简单总结
稳一点
觉得算法不行的时候考虑考虑题目具有的性质
别急，急也没用.jpg
码力不太够，表现在代码细节出现令人智熄的离谱错误