#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int a[N], b[N], sz, n;
int insert(){
int i=2;
while( i<=n && b[i-1]<=b[i] ) i++;
int j = i;
while( i<=n && a[i]==b[i] ) i++;
if( i==n+1 ) return j;
return -1;
}
void down(int u){
int l=u<<1, r=u<<1|1;
int t = u;
if( l<=sz && b[l]>b[t] ) t = l;
if( r<=sz && b[r]>b[t] ) t = r;
if( t!=u ){
swap(b[t], b[u]);
down(t);
}
}
void pop(){
swap(b[1], b[sz--]);
down(1);
}
int main(){
scanf("%d", &n);
for( int i=1; i<=n; i++ ) scanf("%d", &a[i]);
for( int i=1; i<=n; i++ ) scanf("%d", &b[i]);
int j = insert();
if( j>1 ){
puts("Insertion Sort");
for( int i=1; i<j; i++ ){
if( b[i]>b[j] ) swap(b[i], b[j]);
if( i>1 ) printf(" ");
printf("%d", b[i]);
}
while( j<=n ) printf(" %d", b[j++]);
puts("");
}
else{
puts("Heap Sort");
sz = n;
while( b[sz]>b[1] ) sz--;
pop();
for( int i=1; i<=n; i++ ){
if( i>1 ) printf(" ");
printf("%d", b[i]);
}
puts("");
}
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 10010;
int e[N], ne[N], h1, h2=-1;
bool st[M];
int main(){
memset(ne, -1, sizeof ne);
int n, addr, x, next;
scanf("%d %d", &h1, &n);
for( int i=0; i<n; i++ ){
scanf("%d %d %d", &addr, &x, &next);
e[addr]=x, ne[addr]=next;
}
int t = e[h1];
if( t<0 ) t=-t;
st[t] = true;
int pre = h1; //pre表示p1所指向的结点前一个不重复的结点
int p1=ne[h1], p2=-1;
while( p1!=-1 ){
t = e[p1];
if( t<0 ) t=-t;
if( !st[t] ) st[t]=true, pre=ne[pre]; //结点不重复，pre可以向后移动
else{ //否则重复结点加到链表2中
if( p2==-1 ) p2=p1, h2=p1; //表头
else ne[p2] = p1, p2=ne[p2];
ne[pre] = ne[p1]; //pre的下一个指向p1的下一个
}
p1 = ne[p1];
}
ne[p2] = -1; //最后把链表2的尾巴设为-1
p1 = h1, p2 = h2;
while( p1!=-1 ){//地址5位数
printf("%05d %d ", p1, e[p1]);
p1 = ne[p1];
if( p1==-1 ) puts("-1");
else printf("%05d\n", p1);
}
while( p2!=-1 ){//地址5位数
printf("%05d %d ", p2, e[p2]);
p2 = ne[p2];
if( p2==-1 ) puts("-1");
else printf("%05d\n", p2);
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 10010, M = 90010;
vector<unordered_set<int>> e(N);
int gender[N];
PII res[M];
int cnt;
int main(){
int n, m, a, b;
scanf("%d %d", &n, &m);
string s1, s2;
while( m-- ){
cin >> s1 >> s2;
a = stoi(s1), b = stoi(s2);
if( s1[0]=='-' ) a=-a, gender[a]=1;
if( s2[0]=='-' ) b=-b, gender[b]=1;
e[a].insert(b), e[b].insert(a);
}
scanf("%d", &m);
while( m-- ){
scanf("%d %d", &a, &b);
if( a<0 ) a=-a;
if( b<0 ) b=-b;
cnt = 0;
for( auto i: e[a] ){
if( i==b || gender[i]!=gender[a] ) continue;
for( auto j: e[i] ){
if( j==a || gender[j]!=gender[b] ) continue;
if( e[b].count(j) ){
res[cnt++] = {i, j};
}
}
}
sort(res, res+cnt, [](const auto& i, const auto& j){
if( i.first!=j.first ) return i.first < j.first;
return i.second < j.second;
});
printf("%d\n", cnt);
for( int i=0; i<cnt; i++ ) printf("%04d %04d\n", res[i].first, res[i].second);
}
return 0;
}
因为红黑树是二叉搜索树，可以在输入数据后直接插入树中
#include <iostream>
#include <cstring>
using namespace std;
const int N = 35;
int n, k, x;
int tr[N], l[N], r[N], idx;
int clr[N];
void insert(int a){ //插入结点
int p = 0, t = a;
if( t < 0 ) t = -t;
while( clr[p]>0 ){ //已设置颜色
if( t<tr[p] ){
if( l[p]==-1 ) l[p]=++idx;
p = l[p];
}
else{
if( r[p]==-1 ) r[p]=++idx;
p = r[p];
}
}
tr[p] = t;
clr[p] = a<0? 1: 2; //红色1 黑色2
}
int dfs(int u, int fa){ //返回子树的黑色结点数量
if( !clr[u] ) return 0; //未设置颜色返回0
if( clr[u]==1 && clr[fa]==1 ) return -1; //父子都是红色返回错误：-1
int left = dfs(l[u], u);
int right = dfs(r[u], u);
if( left==-1 || right==-1 || left!=right ) return -1; //有一个返回错误则全部返回错误
if( clr[u]==2 ) return left+1; //该结点是黑色结点，数量加上1
return left; //该结点是红色结点
}
int main(){
scanf("%d", &k);
while( k-- ){
scanf("%d", &n);
/**********初始化***********/
idx = 0;
memset(l, -1, sizeof l);
memset(r, -1, sizeof r);
memset(clr, 0, sizeof clr);
/***************************/
for( int i=0; i<n; i++ ) scanf("%d", &x), insert(x);
if( dfs(0, 0)!=-1 ) puts("Yes");
else puts("No");
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 10010, M = 1000010, T = 110;
int h[N], ea[M], eb[M], ne[M], line[M], w[M], idx;
int stop[T], dist[N], cnte[N];
bool st[N];
vector<vector<int>> path(N);
vector<int> ans, tmp;
void add(int a, int b, int c, int d){
ea[idx]=a, eb[idx]=b, line[idx]=c, w[idx]=d, ne[idx]=h[a], h[a]=idx++;
//a->b 线路编号为c 经过站点数为d
}
int dijkstra(int src, int des){
if( src==des ) return 0;
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist); //站点数
memset(cnte, 0x3f, sizeof cnte); //经过的边数
dist[src] = 0;
cnte[src] = 0;
priority_queue<PII, vector<PII>, greater<PII>> hp;
hp.push({0, src});
while( hp.size() ){
auto t = hp.top();
hp.pop();
int d = t.first, u = t.second;
if( st[u] ) continue;
st[u] = true;
for( int i=h[u]; ~i; i=ne[i] ){
int j = eb[i];
if( dist[j] > d + w[i] ){
dist[j] = d + w[i];
hp.push({dist[j], j});
path[j].clear();
path[j].push_back(i); //用i来记录路径 a=ea[i], b=eb[i], id=line[i]
}
else if( dist[j] == d + w[i] ){
if( cnte[j] > cnte[u] + 1 ){ //距离相等选择换乘最少也就是经过边数最少的路线
cnte[j] = cnte[u] + 1;
path[j].clear();
path[j].push_back(i);
}
else if( cnte[j] == cnte[u] + 1 ){
path[j].push_back(i);
}
}
}
}
return dist[des];
}
void dfs(int u, int src){ //倒搜路径
if( ans.size() && tmp.size()>ans.size() ) return;
if( u==src ){
if( ans.empty() || ans.size() > tmp.size() ){
ans = tmp;
}
return;
}
for( auto i: path[u] ){
tmp.push_back(i);
dfs(ea[i], src);
tmp.pop_back();
}
}
void printPath(int src, int des){ //打印路径
if( ans.empty() ) return;
int j = ans.back();
int u = src, id = line[j];
for( int i=ans.size()-2; i>=0; i-- ){
if( id==line[ans[i]] ) continue;
printf("Take Line#%d from %04d to %04d.\n", id, u, ea[ans[i]]);
u = ea[ans[i]], id = line[ans[i]];
}
printf("Take Line#%d from %04d to %04d.\n", id, u, des);
}
int main(){
memset(h, -1, sizeof h);
int n, m;
scanf("%d", &n);
for( int i=1; i<=n; i++ ){
scanf("%d", &m);
for( int j=0; j<m; j++ ) scanf("%04d", &stop[j]);
for( int j=0; j<m; j++ ){
for( int k=j+1; k<m; k++ ){
int len = k-j;
if( stop[0]==stop[m-1] ) len = min(len, m-1-k+j); //环路取最短
add(stop[j], stop[k], i, len);
add(stop[k], stop[j], i, len);
}
}
}
scanf("%d", &m);
while( m-- ){
int src, des;
scanf("%04d %04d", &src, &des);
int t = dijkstra(src, des);
printf("%d\n", t);
ans.clear();
dfs(des, src);
printPath(src, des);
}
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
const int N = 35;
int pre[N], post[N], loc[N], n;
int l[N], r[N];
bool f = true;
int build(int l1, int r1, int l2, int r2){
if( l1==r1 ) return pre[l1];
int u = pre[l1];
if( pre[l1+1]==post[r2-1] ){
f = false;
l[u] = build(l1+1, r1, l2, r2-1);
}
else{
int t = loc[post[r2-1]];
int sr = r1 - t + 1;
l[u] = build(l1+1, r1-sr, l2, r2-sr-1);
r[u] = build(r1-sr+1, r1, r2-sr, r2-1);
}
return u;
}
void dfs(int u){
if( u==0 ) return;
dfs(l[u]);
if( !f ) f = true;
else printf(" ");
printf("%d", u);
dfs(r[u]);
}
int main(){
scanf("%d", &n);
for( int i=0; i<n; i++ ) scanf("%d", &pre[i]), loc[pre[i]]=i;
for( int i=0; i<n; i++ ) scanf("%d", &post[i]);
build(0, n-1, 0, n-1);
if( f ) puts("Yes");
else puts("No");
f = false;
dfs(pre[0]);
puts("");
return 0;
}
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int tr[N][3], idx, maxL; //tr[i][0]结点值 tr[i][1]左孩子下标 tr[i][2]右孩子下标
int lvl[N]; //每层结点数
void insert(int x){
int p = 0, k = 0;
while( tr[p][0] != INF ){
if( x<=tr[p][0] ){ //x小于等于该结点值
if( tr[p][1]==INF ){ //左孩子为空，赋下标
tr[p][1]=++idx;
p = tr[p][1];
k++;
break;
}
p=tr[p][1]; //否则向左孩子走
}
else{ //x大于该结点值
if( tr[p][2]==INF ){ //右孩子为空，赋下标
tr[p][2]=++idx;
p = tr[p][2];
k++;
break;
}
p=tr[p][2]; //否则向右孩子走
}
k++;
}
tr[p][0] = x; //当前点值设为x
lvl[k]++; //k层结点数加1
if( maxL<k ) maxL=k; //最深层高
}
int main(){
int n, x;
scanf("%d", &n);
memset(tr, 0x3f, sizeof tr);
while( n-- ){
scanf("%d", &x);
insert(x);
}
n = lvl[maxL], x = lvl[maxL-1]; //倒数一二两层
printf("%d + %d = %d", n, x, n+x);
return 0;
}
#include <iostream>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 10010;
int p[M], sz[M];
double Area[M], Sets[M];
bool st[M];
struct Res{
int id, num;
double ss, ar;
}res[M];
int find(int x){
if( p[x]!=x ) p[x]=find(p[x]);
return p[x];
}
void merge(int a, int b){
a=find(a), b=find(b);
if( a!=b ){
p[a] = b;
sz[b] += sz[a];
}
}
int main(){
for( int i=0; i<M; i++ ) p[i]=i, sz[i]=1;
int n;
scanf("%d", &n);
set<int> pp;
int id, mom, dad, k, kid;
double ss, ar;
while( n-- ){
scanf("%04d %04d %04d %d", &id, &mom, &dad, &k);
pp.insert(id);
if( mom!=-1 ) merge(id, mom), pp.insert(mom);
if( dad!=-1 ) merge(id, dad), pp.insert(dad);
while( k-- ) scanf("%04d", &kid), pp.insert(kid), merge(id, kid);
scanf("%lf %lf", &ss, &ar);
Sets[id]+=ss;
Area[id]+=ar;
}
int cnt = 0;
for( auto i: pp ){
int j = find(i);
if( !st[j] ){
st[j] = true;
for( auto t: pp ){
if( t!=j && find(t)==j ){
Sets[j] += Sets[t];
Area[j] += Area[t];
}
}
res[cnt++] = {i, sz[j], Sets[j]/(double)sz[j], Area[j]/(double)sz[j]};
}
}
sort(res, res+cnt, [](const auto& a, const auto& b){
if( a.ar!=b.ar ) return a.ar > b.ar;
return a.id < b.id;
});
printf("%d\n", cnt);
for( int i=0; i<cnt; i++ ){
printf("%04d %d %.3lf %.3lf\n", res[i].id, res[i].num, res[i].ss, res[i].ar);
}
return 0;
}
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], p[N][N];
int dist[N];
bool st[N];
vector<vector<int>> path(N);
vector<int> ans1, ans2, tmp;
int n, m, src, des;
int cost = INF;
int dijkstra(int c[][N]){ //c[][] 手动选择用距离/时间计算
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[src] = 0;
priority_queue<PII, vector<PII>, greater<PII>> hp;
hp.push({0, src});
while( hp.size() ){
auto u = hp.top();
hp.pop();
int d = u.first, t = u.second;
if( st[t] ) continue;
st[t] = true;
for( int i=0; i<n; i++ ){
if( dist[i] > d + c[t][i] ){
dist[i] = d + c[t][i];
hp.push({dist[i], i});
path[i].clear();
path[i].push_back(t);
}
else if( dist[i] == d + c[t][i] ){
path[i].push_back(t);
}
}
}
return dist[des];
}
void dfs1(int u, int time){ //逆序遍历最短路的最短时间
if( u==src ){
if( time < cost ){
ans1 = tmp;
cost = time;
}
return;
}
tmp.push_back(u);
for( auto t: path[u] ){
dfs1(t, time+p[t][u]); //p[t][u]不要写反，因为是倒着找路径的
}
tmp.pop_back();
}
void dfs2(int u){ //逆序遍历最短时间经过的最少点
if( u==src ){
if( ans2.empty() || tmp.size() < ans2.size() ){
ans2 = tmp;
}
return;
}
tmp.push_back(u);
for( auto t: path[u] ){
dfs2(t);
}
tmp.pop_back();
}
int main(){
memset(g, 0x3f, sizeof g);
memset(p, 0x3f, sizeof p);
scanf("%d %d", &n, &m);
int a, b, f, len, t;
while( m-- ){
scanf("%d %d %d %d %d", &a, &b, &f, &len, &t);
if( len<g[a][b] ){ //重复边取最小
g[a][b] = len;
if( !f ) g[b][a]=len;
}
if( t<p[a][b] ){
p[a][b] = t;
if( !f ) p[b][a]=t;
}
}
scanf("%d %d", &src, &des);
a = dijkstra(g);
dfs1(des, 0);
b = dijkstra(p);
dfs2(des);
bool eq = true;
if( ans1.size() != ans2.size() ) eq = false;
if( eq ){
for( int i=0; i<ans1.size(); i++ ){
if( ans1[i] != ans2[i] ){
eq = false;
break;
}
}
}
if( !eq ){
printf("Distance = %d: %d", a, src);
for( int i=ans1.size()-1; i>=0; i-- ){
printf(" -> %d", ans1[i]);
}
puts("");
printf("Time = %d: %d", b, src);
for( int i=ans2.size()-1; i>=0; i-- ){
printf(" -> %d", ans2[i]);
}
puts("");
}
else{
printf("Distance = %d; Time = %d: %d", a, b, src);
for( int i=ans1.size()-1; i>=0; i-- ){
printf(" -> %d", ans1[i]);
}
puts("");
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int p[N], sz[N], cnt, res[N], idx;
int hb[N];
bool st[N];
int find(int x){
if( p[x]!=x ) p[x]=find(p[x]);
return p[x];
}
void merge(int a, int b){
a=find(a), b=find(b);
if( a!=b ){
p[a] = b;
sz[b] += sz[a];
cnt--;
}
}
int main(){
for( int i=1; i<N; i++ ) p[i]=i, sz[i]=1;
int n;
scanf("%d", &n);
cnt = n;
for( int i=1; i<=n; i++ ){
int k, x;
scanf("%d: ", &k);
for( int j=0; j<k; j++ ){
scanf("%d", &x);
if( hb[x]!=0 ) merge(i, hb[x]);
hb[x] = i;
}
}
printf("%d\n", cnt);
for( int i=1; i<=n; i++ ){
int t = find(i);
if( !st[t] ){
st[t] = true;
res[idx++] = sz[t];
}
}
sort(res, res+idx, greater<int>());
for( int i=0; i<idx; i++ ){
if( i ) printf(" ");
printf("%d", res[i]);
}
puts("");
return 0;
}
