1021求树的直径网上一搜就有，但是我不太理解 只需要一共求两次的dfs的论调，好吧我收回这句话，好想脑补了下，第一次dfs有多个最长点，只需要搜一个就行QAQ。这么看来我写麻烦了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MP(x, y) make_pair(x, y)
#define FI first
#define SE second
const int INF = 0x3f3f3f3f;
const int N = 1e4+5;
int n;
struct Node{
int to, nx;
}E[N*N*2];
int head[N], tot;
void add(int fr, int to) {
E[tot].to = to; E[tot].nx = head[fr]; head[fr] = tot++;
}
int vis[N], dis[N];
void dfs(int x) {
for(int i = head[x]; ~i; i = E[i].nx) {
int to = E[i].to;
if(!vis[to]) {
vis[to] = 1;
dfs(to);
}
}
}
void bfs(int st) {
queue<int> Q;
memset(vis, 0, sizeof(vis));
vis[st] = 1; dis[st] = 0;
Q.push(st);
while(!Q.empty()) {
int x = Q.front(); Q.pop();
for(int i = head[x]; ~i; i = E[i].nx) {
int to = E[i].to;
if(!vis[to]) {
vis[to] = 1;
dis[to] = dis[x]+1;
Q.push(to);
}
}
}
}
void solve() {
bfs(1);
map<int, int> mp;
map<int, int>::iterator it;
int mx = -1;
for(int i = 1; i <= n; ++i) {
if(dis[i] > mx) {
mx = dis[i];
}
}
vector<int> doo;
for(int i = 1; i <= n; ++i) {
if(dis[i] == mx) {
doo.push_back(i);
}
}
// printf("%d
", mx);
int cnt = 0;
for(int i = 0; i < doo.size(); ++i) {
cnt ++;
if(cnt > 100) break;
bfs(doo[i]);
mp[doo[i]] ++;
mx = -1;
for(int j = 1; j <= n; ++j) {
if(mx < dis[j]) {
mx = dis[j];
}
}
for(int j = 1; j <= n; ++j) {
if(dis[j] == mx) {
mp[j] ++;
}
}
}
for(it = mp.begin(); it != mp.end(); ++it) {
// if(it != mp.begin()) printf(" ");
printf("%d
", it->first);
}
// printf("
");
}
int main() {
while(~scanf("%d", &n)) {
memset(head, -1, sizeof(head)); tot = 0;
for(int i = 1; i < n; ++i) {
int a,b; scanf("%d %d", &a, &b);
add(a, b); add(b, a);
}
int cnt = 0;
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; ++i) {
if(!vis[i]) {
vis[i] = 1;
dfs(i);
cnt ++;
}
}
if(cnt > 1) {
printf("Error: %d components
", cnt); continue;
}
// printf("%d
", cnt);
solve();
}
return 0;
}1022 模拟一下就行
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MP(x, y) make_pair(x, y)
#define FI first
#define SE second
map<string, vector<int> > title;
map<string, vector<int> > author;
map<string, vector<int> > publish;
map<string, vector<int> > keyword;
map<string, vector<int> > year;
int main() {
int n;
while(~scanf("%d", &n)) {
title.clear();
author.clear();
publish.clear();
keyword.clear();
year.clear();
char tmp[100];
for(int i = 0; i < n; ++i) {
int id; scanf("%d", &id);
getchar();
gets(tmp); title[tmp].push_back(id);
// printf("%s
", tmp);
gets(tmp); author[tmp].push_back(id);
gets(tmp);
int len = strlen(tmp);
string tt; tt.clear();
for(int j = 0; j <= len; ++j) {
if( tmp[j] == '
' || tmp[j] == ' ' || !tmp[j] ) {
keyword[tt].push_back(id);
tt.clear();
}else tt += tmp[j];
}
gets(tmp); publish[tmp].push_back(id);
gets(tmp); year[tmp].push_back(id);
}
int m; scanf("%d", &m);
getchar();
for(int i = 0; i < m; ++i) {
gets(tmp);
int len = strlen(tmp);
int ch = tmp[0]-'0';
for(int j = 0; j < len; ++j) {
tmp[j] = tmp[j+3];
}
tmp[len-3] = 0;
printf("%d: %s
", ch, tmp);
int fl = 0;
if(ch == 1) {
sort(title[tmp].begin(), title[tmp].end());
for(int j = 0; j < title[tmp].size(); ++j) {
printf("%07d
", title[tmp][j]); fl = 1;
}
}else if(ch == 2) {
sort(author[tmp].begin(), author[tmp].end());
for(int j = 0; j < author[tmp].size(); ++j) {
printf("%07d
", author[tmp][j]); fl = 1;
}
}else if(ch == 3) {
sort(keyword[tmp].begin(), keyword[tmp].end());
for(int j = 0; j < keyword[tmp].size(); ++j) {
printf("%07d
", keyword[tmp][j]); fl = 1;
}
}else if(ch == 4) {
sort(publish[tmp].begin(), publish[tmp].end());
for(int j = 0; j < publish[tmp].size(); ++j) {
printf("%07d
", publish[tmp][j]); fl = 1;
}
}else {
sort(year[tmp].begin(), year[tmp].end());
for(int j = 0; j < year[tmp].size(); ++j) {
printf("%07d
", year[tmp][j]); fl = 1;
}
}
if(!fl) printf("Not Found
");
}
}
return 0;1023 没啥好说
#include<bits/stdc++.h>
using namespace std;
#define sz(X) ((int)X.size())
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e4+5;
#define MP(x, y) make_pair<x, y>
char s[30];
char b[30];
char a[30];
int main() {
while(~scanf("%s", s)) {
int len = strlen(s);
int pre = 0;
for(int i = len-1; i >= 0; --i) {
int tt = (s[i]-'0') * 2 + pre;
if(tt >= 10) {
int tmp = tt;
tt = tmp%10;
pre = tmp/10;
}else pre = 0;
b[i] = tt+'0';
}
// for(int i = 0; i < len; ++i) printf("%c", b[i]); printf("
");
int ok = 0;
if(pre) printf("No
");
else {
for(int i = 0; i < len; ++i) {
a[i] = b[i];
}
sort(a, a+len);
sort(s, s+len);
int fl = 1;
for(int i = 0; i < len; ++i) {
if(a[i] != s[i]) {
fl = 0; break;
}
}
if(!fl) printf("No
");
else {
printf("Yes
"); ok = 1;
for(int j = 0; j < len; ++j) printf("%c", b[j]);
printf("
");
}
}
if(!ok) {
if(pre) printf("%d",pre);
for(int i = 0; i < len; ++i) printf("%c", b[i]);
printf("
");
}
}
return 0;
}1024 不敢乱讲，但是这题好想真的数据范围不对，按照题意不可能超ll的吧，，之后改了就对了
#include<bits/stdc++.h>
using namespace std;
#define MP(x, y) make_pair(x, y)
#define FI first
#define SE second
const int INF = 0x3f3f3f3f;
const int N = 1e4+5;
typedef long long ll;
int n[50]; int len;
char s[50];
int tmp[50];
void Print() {
for(int i = 0; i < len; ++i) printf("%d", n[i]);
}
int main() {
int k;
while(~scanf("%s %d", s, &k)) {
len = strlen(s);
for(int i = 0; i < len; ++i) n[i] = s[i]-'0';
int fl = 1;
for(int i = 0; i < len/2; ++i) {
if(n[i] != n[len-1-i]) {
fl = 0; break;
}
}
if(fl) {
Print(); printf("
0
");
continue;
}
for(int i = 1; i <= k; ++i) {
int pre = 0;
for(int j = len-1; j >= 0; --j) {
tmp[j] = n[j]+n[len-1-j]+pre;
if(tmp[j] >= 10) {
tmp[j] -= 10;
pre = 1;
}else pre = 0;
}
int cnt = 0;
if(pre) n[cnt++] = pre;
for(int j = 0; j < len; ++j) {
n[cnt++] = tmp[j];
}
len = cnt;
int fl = 1;
for(int j = 0; j < len/2; ++j) {
if(n[j] != n[len-1-j]) {
fl = 0; break;
}
}
if(fl || i == k) {
Print(); printf("
%d
",i);
break;
}
}
}
return 0;
}1025 模拟
#include<bits/stdc++.h>
using namespace std;
#define MP(x, y) make_pair(x, y)
#define FI first
#define SE second
const int INF = 0x3f3f3f3f;
const int N = 1e4+5;
typedef long long ll;
struct Node{
ll s; int grade; int loc; int locrank; int allrank;
}E[30005];
int tot;
int pretot;
int cmp(Node a, Node b) {
if(a.grade != b.grade) return a.grade > b.grade;
else return a.s < b.s;
}
int main() {
int n;
while(~scanf("%d", &n)) {
pretot = 1; tot = 0;
for(int i = 1; i <= n; ++i) {
int k; scanf("%d", &k);
for(int j = 0; j < k; ++j) {
++tot; scanf("%lld %d", &E[tot].s, &E[tot].grade);
// printf("%s
", E[tot].s);
E[tot].loc = i;
}
sort(E+pretot, E+tot+1, cmp);
for(int j = pretot; j <= tot; ++j) {
if(j != pretot && E[j].grade == E[j-1].grade) {
E[j].locrank = E[j-1].locrank;
}else E[j].locrank = j-pretot+1;
}
pretot = tot+1;
}
sort(E+1, E+tot+1, cmp);
for(int i = 1; i <= tot; ++i) {
if(i != 1 && E[i].grade == E[i-1].grade) {
E[i].allrank = E[i-1].allrank;
}else E[i].allrank = i;
}
printf("%d
", tot);
for(int i = 1; i <= tot; ++i) {
printf("%013lld %d %d %d
", E[i].s, E[i].allrank, E[i].loc, E[i].locrank);
}
}
return 0;
}1026做了半天，因为之前一直想按照前面几个题目的做法，直接对人来的时间进行排序。这题我是按照时间点进行处理，桌子来，或者人来都是时间点，对于每个时间点单独处理。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cmath>
using namespace std;
const int N = 1e4+5;
const int INF = 0x3f3f3f3f;
struct Node{
int come;
int serve;
int cost;
int vip;
int vis;
int id;
}E[N];
int cmp(Node a, Node b) {
return a.come < b.come;
}
int cmp2(Node a, Node b) {
return a.serve < b.serve;
}
int V[105];
int ans[105];
struct Pode{
int pos, tim, type, vip;
Pode(int a=0, int b=0, int c=0, int d=0):pos(a), tim(b), type(c), vip(d){}
bool operator <(const Pode &T) const {
if(tim != T.tim) return tim > T.tim;
else if(type != T.type) return type > T.type;
else if(vip != T.vip) return vip > T.vip;
else return pos > T.pos;
}
};
set<int> table;
set<int> vtable;
set<int> person;
set<int> vperson;
priority_queue<Pode> Q;
void solve(int nwtime) {
if(vperson.size() > 0 && vtable.size() > 0) {
int per = *vperson.begin();
E[per].serve = nwtime;
int ta = *vtable.begin();
Q.push(Pode(ta, nwtime+E[per].cost, 0, V[ta]));
vperson.erase(per); person.erase(per);
vtable.erase(ta); table.erase(ta);
if(nwtime < 21*3600) ans[ta] ++;
return;
}
int per = *person.begin();
E[per].serve = nwtime;
int ta = *table.begin();
Q.push(Pode(ta, nwtime+E[per].cost, 0, V[ta]));
vperson.erase(per); person.erase(per);
vtable.erase(ta); table.erase(ta);
if(nwtime < 21*3600) ans[ta] ++;
}
void put(int x) {
printf("%02d:%02d:%02d ", x/3600, (x%3600)/60, x%60);
}
int main() {
int n;
int k, m;
while(~scanf("%d", &n)) {
memset(ans, 0, sizeof(ans));
memset(V, 0, sizeof(V));
while(!Q.empty()) Q.pop();
table.clear();
vtable.clear();
person.clear();
vperson.clear();
for(int i = 1; i <= n; ++i) {
int a, b, c;
scanf("%d:%d:%d %d %d", &a, &b, &c, &E[i].cost, &E[i].vip);
E[i].come = a*3600 + b*60 + c;
E[i].cost = min(120, E[i].cost);
E[i].cost = E[i].cost*60;
E[i].id = i;
E[i].vis = 0;
}
sort(E+1, E+n+1, cmp);
scanf("%d %d", &k, &m);
for(int i = 0; i < m; ++i) {
int a; scanf("%d", &a);
V[a] ++;
}
for(int i = 1; i <= k; ++i) Q.push(Pode(i, 8*3600, 0, V[i]));
for(int i = 1; i <= n; ++i) Q.push(Pode(i, E[i].come, 1, E[i].vip));
while(!Q.empty()) {
Pode tt = Q.top(); Q.pop();
int id = tt.pos; int nwtime = tt.tim; int ty = tt.type;
// printf("%d %d %d
", id, nwtime, ty);
if(tt.type == 0) {
table.insert(id);
if(V[id]) vtable.insert(id);
if(table.size() > 0 && person.size() > 0) solve(nwtime);
}else {
person.insert(id);
if(E[id].vip) vperson.insert(id);
if(table.size() > 0 && person.size() > 0) solve(nwtime);
}
}
sort(E+1, E+n+1, cmp2);
for(int i = 1; i <= n; ++i) {
if(E[i].serve >= 21*3600) break;
put(E[i].come); put(E[i].serve);
// printf("%.3f
", (E[i].serve-E[i].come)/60.0);
printf("%.f
", round((E[i].serve-E[i].come)/60.0));
}
for(int i = 1; i <= k; ++i) {
if(i != 1) printf(" ");
printf("%d", ans[i]);
}
printf("
");
}
return 0;
}1027
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<cstdio>
using namespace std;
const int N = 1e6+5;
#define mp(A,B) make_pair(A,B)
void put(int x) {
int t[3]; int c = 0;
memset(t, 0, sizeof(t));
while(x) {
t[c++] = x%13;
x /= 13;
}
if(t[1] >= 10) printf("%c", t[1]-10+'A');
else printf("%d", t[1]);
if(t[0] >= 10) printf("%c", t[0]-10+'A');
else printf("%d", t[0]);
}
int main () {
int a, b, c;
while(~scanf("%d %d %d",&a,&b,&c)) {
printf("#");
put(a); put(b); put(c);
}
return 0;
}1028
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e6+5;
struct Node{
int id;
char name[20];
int grade;
}E[N];
int n, c;
int cmp(Node a, Node b) {
if(c == 1) return a.id < b.id;
else if(c == 2) {
int l1 = strlen(a.name); int l2 = strlen(b.name);
for(int i = 0; i < min(l1, l2); ++i) {
if(a.name[i] != b.name[i])
return a.name[i] < b.name[i];
}
if(l1 != l2) return l1 < l2;
}else if(a.grade != b.grade) return a.grade < b.grade;
return a.id < b.id;
}
int main() {
while(~scanf("%d %d", &n, &c)) {
for(int i = 1; i <= n; ++i) {
scanf("%d %s %d", &E[i].id, E[i].name, &E[i].grade);
}
sort(E+1, E+n+1, cmp);
for(int i = 1; i <= n; ++i) {
printf("%06d %s %d
", E[i].id, E[i].name, E[i].grade);
}
}
return 0;
}1029 查找中位数算法，算法导论上有
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e6+5;
typedef long long ll;
ll a[N];
int rand_partion(int l, int r) {
int randnum = (rand()%(r-l+1)) + l;
// printf("%d
", randnum);
swap(a[r], a[randnum]);
int fl = l-1;
int tag = a[r];
for(int i = l; i < r; ++i) {
if(a[i] <= tag) {
fl ++;
swap(a[fl], a[i]);
}
}
swap(a[fl+1], a[r]);
return fl+1;
}
ll getMid(int l, int r, int tar) {
// printf("%d %d %d
", l, r, tar);
if(l == r) return a[l];
int po = rand_partion(l, r);
// printf("%d:",po);
// for(int i = l; i <= r; ++i) printf("%lld ", a[i]); printf("
");
int len = po-l+1;
if(tar == len) return a[po];
else if(tar < len) return getMid(l, po-1, tar);
else return getMid(po+1, r, tar-len);
}
int main() {
int n;
srand(time(NULL));
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
int m; scanf("%d", &m);
for(int i = 1; i <= m; ++i) {
scanf("%lld", &a[i+n]);
}
n = n+m;
// printf("%d
", n);
printf("%lld
", getMid(1, n, (n+1)/2) );
}
return 0;
}1030 双参数最短路，水一水
#include<cmath>
#include<map>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 505;
const int INF = 0x3f3f3f3f;
#define MP(x, y) make_pair(x, y)
int n,m,s,d;
struct Node{
int to, nx, dis, cost;
}E[N*N*2];
int head[N], tot;
void add(int fr, int to, int dis, int cost) {
E[tot].to = to; E[tot].dis = dis; E[tot].cost = cost;
E[tot].nx = head[fr]; head[fr] = tot++;
}
struct Hode{
int pos, dis, cost;
Hode(int a=0, int b=0, int c=0):pos(a),dis(b),cost(c){}
bool operator < (const Hode &T) const {
if(dis != T.dis) return dis > T.dis;
else return cost > T.cost;
}
};
int _dis[N], _cost[N], pre[N], vis[N];
void dijkstra(int x) {
priority_queue<Hode> Q;
memset(vis, 0, sizeof(vis));
memset(_dis, INF, sizeof(_dis));
memset(_cost, INF, sizeof(_cost));
_dis[s] = 0, _cost[s] = 0;
Q.push(Hode(s, _dis[s], _cost[s]));
while(!Q.empty()) {
Hode top = Q.top(); Q.pop();
int x = top.pos; int dis = top.dis; int cost = top.cost;
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x]; ~i; i = E[i].nx) {
int to = E[i].to;
if(_dis[to] > _dis[x] + E[i].dis) {
_dis[to] = _dis[x] + E[i].dis;
_cost[to] = _cost[x] + E[i].cost;
Q.push(Hode(to, _dis[to], _cost[to]));
pre[to] = x;
}else if(_dis[to] == _dis[x] + E[i].dis && _cost[to] > _cost[x] + E[i].cost) {
_cost[to] = _cost[x] + E[i].cost;
Q.push(Hode(to, _dis[to], _cost[to]));
pre[to] = x;
}
}
}
}
void dfs(int x) {
if(x == s) {
printf("%d ", s); return;
}
dfs(pre[x]);
printf("%d ", x);
}
int main() {
while(~scanf("%d %d %d %d", &n, &m, &s, &d)) {
memset(head, -1, sizeof(head)); tot = 0;
for(int i = 0; i < m; ++i) {
int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
add(a, b, c, d);
add(b, a, c, d);
}
// printf("hh
");
dijkstra(s);
dfs(d);
printf("%d %d
", _dis[d], _cost[d]);
}
return 0;
}