| Solved | Pro.ID | Title | Ratio(Accepted / Submitted) |
| 1001 | Rikka with Quicksort | 25.85%(38/147) | |
 |
1002 | Rikka with Cake | 31.69%(379/1196) |
| 1003 | Rikka with Mista | 5.57%(45/808) | |
| 1004 | Rikka with Geometric Sequence | 9.52%(2/21) | |
| |
1005 | Rikka with Game | 35.29%(866/2454) |
| |
1006 | Rikka with Coin | 7.16%(358/5003) |
| |
1007 | Rikka with Travels | 21.46%(85/396) |
| |
1008 | Rikka with Stable Marriage 字典树+贪心 | 17.02%(8/47) |
| 1009 | Rikka with Traffic Light | 0.00%(0/24) | |
| 1010 | Rikka with Defensive Line | 0.00%(0/20) | |
| 1011 | Rikka with Segment Tree | 39.39%(13/33) |
1007 Rikka with Travels
思路：
一棵树上最长链处理，分出两种情况，一种是（a,b）各占一个端点，还有一种情况a占整条链，b是全踩在非最长链。
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert>
#include <unordered_map>
// #include<bits/extc++.h>
// using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define fi first
#define se second
#define debug(x) cerr<<#x << " := " << x << endl;
#define bug cerr<<"-----------------------"<<endl;
#define FOR(a, b, c) for(int a = b; a <= c; ++ a)typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f;
const int mod = ;template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
}
/**********showtime************/
const int maxn = 1e5+;
int n;
vector<int>mp[maxn];
int vis[maxn];
int dis[maxn];
vector<int>lian;
///扣出最长链
void koulian() {
for(int i=; i<=n; i++) dis[i] = inf;
dis[] = ;
queue<int>que; que.push();
int t = ;
while(!que.empty()) {
int u = que.front(); que.pop();
if(dis[u] > dis[t])t = u;
for(int v : mp[u]) {
if(dis[v] > dis[u] + ) {
dis[v] = dis[u] + ;
que.push(v);
}
}
} for(int i=; i<=n; i++) dis[i] = inf;
dis[t] = ;
que.push(t);
int s = t;
while(!que.empty()) {
int u = que.front(); que.pop();
if(dis[u] > dis[s])s = u;
for(int v:mp[u]) {
if(dis[v] > dis[u] + ) {
dis[v] = dis[u] + ;
que.push(v);
}
}
}
lian.pb(s);
vis[s] = ;
while(s != t) {
for(int v : mp[s]) {
if(dis[v] + == dis[s]) {
s = v;
lian.pb(s);
vis[s] = ;
break;
}
}
}
} int dpa[maxn], dpb[maxn][], pre[maxn];
int dppre[maxn], dpback[maxn];
///求出以最长链上一个点为根节点的不经过最长链的最大深度
void dfs1(int u, int fa) {
dpa[u] = ;
for(int v : mp[u]) {
if(v == fa || vis[v]) continue;
dfs1(v, u);
dpa[u] = max(dpa[u], dpa[v] + );
}}
void dfs2(int u, int fa) {
dpb[u][] = dpb[u][] = ;
///dpb[0]表示包含根节点的最长链
///dpb[1]表示包含根节点的次长链
pre[u] = ;
for(int v : mp[u]) {
if(vis[v] || v == fa) continue;
dfs2(v, u);
pre[u] = max(pre[u], pre[v]); if(dpb[u][] <= dpb[v][] + ){
dpb[u][] = dpb[v][] + ;
if(dpb[u][] < dpb[u][]) {
swap(dpb[u][], dpb[u][]);
}
}
}
pre[u] = max(pre[u], dpb[u][] + dpb[u][] - );
}
int hei[maxn];
int main(){
int T; scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(int i=; i<n; i++) {
int u, v;
scanf("%d%d", &u, &v);
mp[u].pb(v);
mp[v].pb(u);
}
for(int i=; i<=n; i++) vis[i] = , hei[i] = , pre[i] = , dppre[i] = ,dpback[i] = ; koulian();
for(int i=; i<lian.size(); i++) {
int v = lian[i];
dfs1(v, v);
if(i)dppre[i] = max(dppre[i-], dpa[v] + i);
else dppre[i] = dpa[v];
for(int p : mp[v]) {
if(vis[p]) continue;
dfs2(p, p);
pre[v] = max(pre[v], pre[p]);
}
pre[v] = max(pre[v], pre[lian[max(, i-)]]);
}
int cc = ;
for(int i=lian.size()-; i>=; i--) {
if(i == lian.size() - ) dpback[i] = dpa[lian[i]];
else dpback[i] = max(dpback[i+], dpa[lian[i]] + cc);
cc++;
}
int all = lian.size();
hei[all] = pre[lian[all-]];
hei[pre[lian[all-]]] = all; for(int i=lian.size() - ; i>=; i--) {
int v = lian[i];
int a = dppre[i-];
int b = dpback[i];
hei[a] = max(hei[a], b);
hei[b] = max(hei[b], a);
}
ll sum = ;
int c = ; for(int i=all; i>=; i--) {
c = max(c, hei[i]);
sum = sum + c;
}
printf("%lld\n", sum);
lian.clear();
for(int i=; i<=n; i++) mp[i].clear();
}
return ;
}
/*
10
9
1 2
2 3
3 4
4 5
5 8
3 6
3 7
7 914
1 2
2 3
3 4
4 5
5 6
6 7
3 8
3 9
4 10
4 11
11 14
5 12
5 13
= 36
*/
1008 Rikka with Stable Marriage
思路：
就是字典树+贪心，和第五场那个贪心顺序反一下就行了
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize(4)
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert>
// #include<bits/extc++.h>
// using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define fi first
#define se second
#define debug(x) cerr<<#x << " := " << x << endl;
#define bug cerr<<"-----------------------"<<endl;
#define FOR(a, b, c) for(int a = b; a <= c; ++ a)typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f;
const int mod = ;template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
}/**********showtime************/
const int maxn = 1e5+;
int a[maxn],b[maxn];
int tot[],rt[];
int bz[];
struct node{
int ch[];
int fa;
int sz;
void init(int f) {
ch[] = ch[] = ;
fa = f;
sz = ;
}
}tree[][maxn * ];
int shu[]; void add(int p, int len, int flag) {
if(len == ){
tree[flag][p].sz++;
return;
} if(tree[flag][p].ch[shu[len]] == )
{
tree[flag][p].ch[shu[len]] = ++ tot[flag];
tree[flag][tot[flag]].init(p);
}
int nx = tree[flag][p].ch[shu[len]];
add(nx, len-, flag);
int lc = tree[flag][p].ch[];
int rc = tree[flag][p].ch[];
tree[flag][p].sz = tree[flag][lc].sz + tree[flag][rc].sz;
}
void insert(int val, int flag) {
int len = ;
for(int i=; i<=; i++) shu[++len] = val % , val /= ;
add(rt[flag], , flag);
}
void display(int rt, int flag) {
if(rt == ) return ;
// cout<<tree[flag][rt].sz<<endl;
display(tree[flag][rt].ch[], flag);
display(tree[flag][rt].ch[], flag);
}
vector<int>vec;
void find(int a, int b, int cen, int val) {
if(cen == ) {
vec.pb(val);
tree[][a].sz--;
tree[][b].sz--;
return;
}
if(tree[][tree[][a].ch[]].sz && tree[][ tree[][b].ch[]].sz){
find(tree[][a].ch[], tree[][b].ch[], cen-, val + bz[cen-]);
}
else if(tree[][tree[][a].ch[]].sz && tree[][ tree[][b].ch[]].sz){
find(tree[][a].ch[], tree[][b].ch[], cen-, val + bz[cen-]);
}
else if(tree[][ tree[][a].ch[] ].sz && tree[][ tree[][b].ch[]].sz ) {
find(tree[][a].ch[], tree[][b].ch[], cen-, val);
}
else if(tree[][ tree[][a].ch[] ].sz && tree[][ tree[][b].ch[]].sz) {
find(tree[][a].ch[], tree[][b].ch[], cen-, val);
} tree[][a].sz = tree[][tree[][a].ch[]].sz + tree[][tree[][a].ch[]].sz;
tree[][b].sz = tree[][tree[][b].ch[]].sz + tree[][tree[][b].ch[]].sz; }
int main(){
int T; scanf("%d", &T);
bz[] = ;
for(int i=; i<=; i++) bz[i] = * bz[i-];
while(T--) {
tot[] = tot[] = ;
rt[] = ++tot[];
tree[][rt[]].init();
rt[] = ++tot[];
tree[][rt[]].init(); int n; scanf("%d", &n);
for(int i=; i<=n; i++) scanf("%d", &a[i]), insert(a[i], );
for(int i=; i<=n; i++) scanf("%d", &b[i]), insert(b[i], ); vec.clear();
for(int i=; i<=n; i++) {
find(rt[], rt[], , );
}
ll sum = ;
for(int i=; i<vec.size(); i++) sum += vec[i];
printf("%lld\n", sum);
}
return ;
}
