1061 我想吐槽这题的题意不够清楚，不过下次得长记性，对于模糊的题意要大胆猜测，而不是固执己见
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
using namespace std;
char a[4][65];
char week[10][10] = {"MON", "TUE", "WED", "THU","FRI","SAT", "SUN"};
int main() {
map<char, int > mp;
for(int i = 0; i < 4; ++i) {
gets(a[i]);
}
char t1 = 0,t2 = 0; int t3 = 0;
int l1 = strlen(a[0]); int l2= strlen(a[1]);
int pos;
for(int i = 0; i < min(l1, l2); ++i) {
if(a[0][i] == a[1][i] && a[0][i] >= 'A' && a[0][i] <= 'G') {
t1 = a[0][i];
pos = i;
break;
// t3 = i; break;
}
}
for(int i = pos+1; i < min(l1, l2); ++i) {
if(a[0][i] == a[1][i] && ( (a[0][i] >= 'A' && a[0][i] <= 'N') || (a[0][i] >= '0' && a[0][i] <= '9')) ) {
t2 = a[0][i];
break;
// t3 = i; break;
}
}
l1 = strlen(a[2]); l2= strlen(a[3]);
for(int i = min(l1, l2)-1; i >= 0; --i) {
if(a[2][i] == a[3][i] && ( (a[2][i] >= 'a' && a[2][i] <= 'z') || (a[2][i] >= 'A' && a[2][i] <= 'Z') ) ){
t3 = i; break;
}
}
int t4;
if(t2 >= 'A' && t2 <='Z') t4 = t2-'A'+10;
else t4 = t2-'0'+0;
// printf("%c %c\n", t1,t2);
printf("%s %02d:%02d\n", week[t1-'A'], t4, t3);
return 0;
}1062
#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 = 1e5+5;
const int INF = 0x3f3f3f3f;
#define MP(x, y) make_pair(x, y)
int n, l, h;
struct Node{
int num, vir, tal;
Node(int a=0, int b=0, int c=0):num(a), vir(b), tal(c){}
}E[N];
int tot;
int jud(Node x) {
if(x.vir >= h && x.tal >= h) return 1;
else if(x.vir >= h) return 2;
else if(x.tal < h && x.tal <= x.vir) return 3;
else return 4;
}
int cmp(Node a, Node b) {
int tya = jud(a); int tyb = jud(b);
if(tya != tyb) return tya < tyb;
else if(a.vir+a.tal != b.vir+b.tal)
return a.vir+a.tal > b.vir+b.tal;
else if(a.vir != b.vir)
return a.vir > b.vir;
else return a.num < b.num;
}
int main() {
while(~scanf("%d %d %d", &n, &l, &h)) {
tot = 0;
for(int i = 0; i < n; ++i) {
int a, b, c; scanf("%d %d %d", &a, &b, &c);
if(c < l || b < l) continue;
E[++tot] = Node(a, b, c);
}
sort(E+1, E+tot+1, cmp);
printf("%d\n", tot);
for(int i = 1; i <= tot; ++i) printf("%08d %d %d\n", E[i].num, E[i].vir, E[i].tal);
}
return 0;
}1063
#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 = 1e5+5;
const int INF = 0x3f3f3f3f;
#define MP(x, y) make_pair(x, y)
set<int> st[55];
set<int> ::iterator it;
double mp[55][55];
int main() {
int n, k;
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; ++i) {
int m; scanf("%d", &m);
for(int j = 0; j < m; ++j) {
int a; scanf("%d", &a);
st[i].insert(a);
}
}
scanf("%d", &k);
set<int> s;
for(int i = 0; i < k; ++i) {
int a, b; scanf("%d %d", &a, &b);
if(a > b) swap(a, b);
if(mp[a][b] != 0) {
printf("%.1f%%\n", mp[a][b]);
continue;
}
int all = st[b].size();
for(it = st[a].begin(); it != st[a].end(); ++it) {
if(st[b].find(*it) == st[b].end()) {
all ++;
}
}
mp[a][b] = (st[a].size()+st[b].size() - all)*100.0/all;
printf("%.1f%%\n", mp[a][b]);
}
}
return 0;1064
#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 = 1e3+5;
const int INF = 0x3f3f3f3f;
#define MP(x, y) make_pair(x, y)
int n;
int a[N];
int Rank[N]; int tot;
int L[N], R[N];
void dfs(int x) {
// printf("hh %d\n", x);
if(2*x <= n) {
L[x] = 2*x; dfs(2*x);
}
if(2*x+1 <= n) {
R[x] = 2*x+1; dfs(2*x+1);
}
}
void _dfs(int x) {
// printf("%d\n", x);
if(L[x]) _dfs(L[x]);
Rank[x] = ++tot;
if(R[x]) _dfs(R[x]);
}
void bfs(int x) {
queue<int> Q;
Q.push(x);
while(!Q.empty()) {
int tt = Q.front(); Q.pop();
if(tt != x) printf(" ");
printf("%d", a[Rank[tt]]);
if(L[tt]) Q.push(L[tt]);
if(R[tt]) Q.push(R[tt]);
}
printf("\n");
}
int main() {
while(~scanf("%d", &n)) {
memset(L, 0, sizeof(L));
memset(R, 0, sizeof(R));
tot = 0;
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
sort(a+1, a+n+1);
dfs(1);
_dfs(1);
// for(int i = 1; i <= n; ++i) printf("%d ", Rank[i]); printf("\n");
bfs(1);
}
return 0;
}1065 这题偷了懒 = = ，写java也过不了就很气。其实我看网上的题解还是有缺陷的，等我又时间写个大数减法
#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 = 1e3+5;
const int INF = 0x3f3f3f3f;
#define MP(x, y) make_pair(x, y)
int main() {
int t; scanf("%d", &t);
ll a,b,c;
for(int _=1; _<=t; ++_) {
scanf("%lld %lld %lld", &a, &b, &c);
ll tmp = a+b;
printf("Case #%d: ",_);
if( (a>0 && b>0 && tmp<=0) || ( ( a + b > c) && !(a<0 && b<0 && tmp>=0) ) ) printf("true\n");
else printf("false\n");
}
return 0;
}1066avl问题，做pat历史上用的时间最多的一次，我的算法其实是自己xjb想的，有机会尝试下别人的算法
#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 = 100;
const int INF = 0x3f3f3f3f;
#define MP(x, y) make_pair(x, y)
int root;
int num[N];
int L[N], R[N], fa[N];
void insert(int x, int tag) {
// printf("tag: %d\n", x);
if(!root) {
root = tag; fa[tag] = tag; return;
}
if(num[x] > num[tag]) {
if(!L[x]) L[x] = tag, fa[tag] = x;
else insert(L[x], tag);
}else {
if(!R[x]) R[x] = tag, fa[tag] = x;
else insert(R[x], tag);
}
}
struct Node{
int po, val;
Node(int a=0, int b=0):po(a), val(b){}
}E[10];
int cmp(Node a,Node b) {
return a.val < b.val;
}
void LL(int x) {
// printf("LL\n");
int fart = fa[fa[x]];
int t1 = x; int t2 = R[x]; int t3 = fa[x];
fa[t1] = 0; fa[t2] = 0; fa[t3] = 0;
R[t1] = t3; fa[t3] = t1;
L[t3] = t2; fa[t2] = t3;
if(t3 == root) {
root = t1; fa[t1] = t1;
}else if(L[fart] == t3) {
L[fart] = t1; fa[t1] = fart;
}else R[fart] = t1, fa[t1] = fart;
}
void RR(int x) {
// printf("RR\n");
int fart = fa[fa[x]];
int t1 = x; int t2 = L[x]; int t3 = fa[x];
fa[t1] = 0; fa[t2] = 0; fa[t3] = 0;
L[t1] = t3; fa[t3] = t1;
R[t3] = t2; fa[t2] = t3;
if(t3 == root) {
root = t1; fa[t1] = t1;
}else if(L[fart] == t3) {
L[fart] = t1; fa[t1] = fart;
}else R[fart] = t1, fa[t1] = fart;
}
void LR(int x, int tag) {
// printf("LR\n");
int fart = fa[fa[x]];
int t1 = x; int t2 = R[x]; int t3 = fa[x];
int a1 = L[t2]; int a2 = R[t2];
fa[t1] = 0; fa[t2] = 0; fa[t3] = 0;
R[t1] = 0; L[t3] = 0;
L[t2] = t1; fa[t1] = t2;
R[t2] = t3; fa[t3] = t2;
if(t3 == root) {
root = t2; fa[t2] = t2;
}else if(L[fart] == t3) {
L[fart] = t2; fa[t2] = fart;
}else {
R[fart] = t2; fa[t2] = fart;
}
if(a1) insert(root, a1);
if(a2) insert(root, a2);
}
void RL(int x, int tag) {
// printf("RL\n");
int fart = fa[fa[x]];
int t1 = x; int t2 = L[x]; int t3 = fa[x];
int a1 = L[t2]; int a2 = R[t2];
L[t1] = 0; R[t3] = 0;
fa[t1] = 0; fa[t2] = 0; fa[t3] = 0;
L[t2] = t3; fa[t3] = t2;
R[t2] = t1; fa[t1] = t2;
// printf("hh %d %d %d\n", num[t1], num[t2], num[t3]);
if(t3 == root) {
root = t2; fa[t2] = t2;
}else if(L[fart] == t3) {
L[fart] = t2; fa[t2] = fart;
}else {
R[fart] = t2; fa[t2] = fart;
}
// printf("hh %d %d", fart, R[fart]);
if(a1) insert(root, a1);
if(a2) insert(root, a2);
}
void fix(int x) {
int rt = fa[fa[x]]; int fart = fa[rt];
if( (L[rt]==0) + (R[rt]==0) == 1) {
int tot = 0;
for(int i = 0, tt = x; i < 3; ++i) {
E[tot++] = Node(tt, num[tt]);
tt = fa[tt];
}
sort(E, E+tot, cmp);
L[E[1].po] = E[0].po; fa[E[0].po] = E[1].po;
R[E[1].po] = E[2].po; fa[E[2].po] = E[1].po;
L[E[0].po] = 0; R[E[0].po] = 0;
L[E[2].po] = 0; R[E[2].po] = 0;
if(root == rt) {
root = E[1].po; fa[root] = root;
}else if(L[fart] == rt) {
L[fart] = E[1].po; fa[E[1].po] = fart;
}else {
R[fart] = E[1].po; fa[E[1].po] = fart;
}
}else {
// printf("%d %d %d\n", x, rt, fa[rt]);
if (L[fa[rt]] == rt && L[rt] == fa[x] ) LL(rt);
else if(R[fa[rt]] == rt && R[rt] == fa[x] ) RR(rt);
else if(L[fa[rt]] == rt && R[rt] == fa[x] ) LR(rt, x);
else if(R[fa[rt]] == rt && L[rt] == fa[x] ) RL(rt, x);
}
}
void test(int x, int pre) {
printf("%d from %d\n", x, pre);
if(L[x]) test(L[x], x);
if(R[x]) test(R[x], x);
}
int height[N]; int tag;
void dfs(int x) {
int t1 = 0, t2 = 0;
if(L[x]) dfs(L[x]), t1 = height[L[x]];
if(R[x]) dfs(R[x]), t2 = height[R[x]];
height[x] = max(t1, t2)+1;
if( abs(t1- t2) > 1 && !tag) tag = x;
}
void solve(int x) {
// printf("do %d\n", x);
memset(height, 0, sizeof(height));
tag = 0;
dfs(root);
if(tag) {
int t1 = tag;
if(height[L[t1]] > height[R[t1]]) t1 = L[t1];
else t1 = R[t1];
if(height[L[t1]] > height[R[t1]]) t1 = L[t1];
else t1 = R[t1];
if(height[L[t1]] > height[R[t1]]) t1 = L[t1];
else if(height[L[t1]] < height[R[t1]]) t1 = R[t1];
// printf("%d %d\n", tag, t1);
fix(t1);
}
// test(root, root);
// printf("\n");
}
int main() {
int n;
while(~scanf("%d", &n)) {
root = 0;
memset(fa, 0, sizeof(fa));
memset(L, 0, sizeof(L));
memset(R, 0, sizeof(R));
for(int i = 1; i <= n; ++i) {
scanf("%d", &num[i]);
insert(root, i);
solve(i);
// fa[root] = root;
// check(root);
}
printf("%d\n", num[root]);
}
return 0;
}1067好题啊，这道，需要思考如何贪心，最后想到并查集。一个集合的算一次
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<map>
#include<set>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5+5;
typedef long long ll;
#define MP(x, y) make_pair(x, y);
int n;
int a[N];
int pre[N];
int cnt[N];
int fa(int x) {
return x==pre[x]? x: pre[x] = fa(pre[x]);
}
int main() {
while(~scanf("%d", &n)) {
memset(cnt, 0, sizeof(cnt));
int ans = 0;
for(int i = 1; i <= n; ++i) pre[i] = i;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]), a[i] ++;
int t1 = fa(a[i]); int t2 = fa(i);
if(t1 != t2) {
pre[t1] = t2;
}
}
for(int i = 1; i <= n; ++i) {
cnt[fa(i)] ++;
}
for(int i = 1; i <= n; ++i) {
if(cnt[i] > 1) ans += cnt[i]+1;
}
if(a[1] != 1) ans -= 2;
printf("%d\n", ans);
}
return 0;
}1068 dp一下就行
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<map>
#include<set>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e4+5;
typedef long long ll;
#define MP(x, y) make_pair(x, y);
int coin[N];
vector<int> dp[105];
int cmp(vector<int> &a, vector<int> &b) {
if(a.size() == 0) return 0;
else if(b.size() == 0) return 1;
for(int i = 0; i < min(a.size(), b.size()); ++i) {
if(a[i] != b[i])
return a[i] < b[i];
}
return a.size() < b.size();
}
int main() {
int n, m;
while(~scanf("%d %d", &n, &m)) {
for(int i = 1; i <= n; ++i) scanf("%d", &coin[i]);
for(int i = 1; i <= m; ++i) dp[i].clear();
sort(coin+1, coin+n+1);
vector<int> tmp;
for(int i = 1; i <= n; ++i) {
for(int j = m; j >= 1; --j) {
if(j-coin[i] > 0 ) {
if(dp[j- coin[i]].size() == 0) continue;
tmp.clear(); copy(dp[j-coin[i]].begin(), dp[j-coin[i]].end(), back_inserter(tmp));
tmp.push_back(coin[i]);
if( cmp(dp[j], tmp) == 0) dp[j].swap(tmp);
}else break;
}
tmp.clear(); tmp.push_back(coin[i]);
if(coin[i] <= m && cmp(dp[coin[i]], tmp) == 0) dp[coin[i]].swap(tmp);
}
if(dp[m].size() == 0) {
printf("No Solution\n");
continue;
}
for(int i = 0; i < dp[m].size(); ++i) {
if(i) printf(" ");
printf("%d", dp[m][i]);
}
printf("\n");
}
return 0;
} 1069
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<map>
#include<set>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e4+5;
typedef long long ll;
#define MP(x, y) make_pair(x, y);
int main() {
int n;
while(~scanf("%d", &n)) {
while(1) {
int tmp = n;
vector<int> vc;
while(tmp) {
vc.push_back(tmp%10);
tmp /= 10;
}
if(vc.size() < 4) {
int ed = 4-vc.size();
for(int i = 0; i < ed; ++i) vc.push_back(0);
}
sort(vc.begin(), vc.end());
int t1 = 0, t2 = 0;
for(int i = 0; i < vc.size(); ++i) {
t1 = t1*10 + vc[i];
}
for(int i = vc.size()-1; i >= 0; --i) {
t2 = t2*10 + vc[i];
}
int _n = t2 - t1;
n = _n;
printf("%04d - %04d = %04d\n", t2, t1, _n);
if(_n == 0 || _n == 6174) break;
}
}
return 0;
}1070
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<map>
#include<set>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e3+5;
typedef long long ll;
#define MP(x, y) make_pair(x, y);
struct Node{
double ton; double price;
}E[N];
int cmp(Node a, Node b) {
double t1 = a.ton*1.0 / a.price;
double t2 = b.ton*1.0 / b.price;
return t1 < t2;
}
int main() {
int n; double d;
while(~scanf("%d %lf", &n, &d)) {
for(int i = 0; i < n; ++i) {
scanf("%lf", &E[i].ton);
}
for(int i = 0; i < n; ++i) {
scanf("%lf", &E[i].price);
// printf("%.2f\n", E[i].ton / E[i].price);
}
// for(int i = 0; i < n; ++i) printf("%d ", E[i].ton); printf("\n");
sort(E, E+n, cmp);
double aton = 0; double pro = 0;
for(int i = 0; i < n; ++i) {
aton += E[i].ton; pro += E[i].price;
if(aton >= d) {
// printf("%d\n", aton-d)
pro -= (aton-d)*E[i].price/ E[i].ton;
break;
}
}
printf("%.2f\n", pro);
}
return 0;
}