准备每天刷两题PAT真题。（一句话题解）
1001 A+B Format
模拟输出，注意格式
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; string ans = ""; int main() {
int a, b, c, cnt = ;
cin >> a >> b;
c = a + b;
if(c == ) {
cout << << endl;
return ;
}
while(c) {
if(cnt % == && cnt != ) ans = ans + ",";
char ch = abs(c % ) + '';
ans = ans + ch;
c /= ;
cnt++;
}
reverse(ans.begin(), ans.end());
if(a + b < ) ans = "-" + ans ;
cout << ans << endl;
return ;
}
1002 A+B for Polynomials
map存数，注意系数正负。
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; map<int, double> m; int main() {
double a;
int k, n, cnt = , mx = ;
scanf("%d", &k);
for(int i = ; i <= k; i++) {
scanf("%d%lf", &n, &a);
mx = max(mx, n);
m[n] = m[n] + a;
}
scanf("%d", &k);
for(int i = ; i <= k; i++) {
scanf("%d%lf", &n, &a);
mx = max(mx, n);
m[n] = m[n] + a;
}
for(int i = mx; i >= ; i--) {
if(m[i] != ) cnt++;
}
printf("%d", cnt);
for(int i = mx; i >= ; i--) {
if(m[i] != ) printf(" %d %.1f", i, m[i]);
}
return ;
}
1003 Emergency
单调队列优化dijkstra，注意标记点，路径长度相同，当前点增加路径数目，同时更新当前点人员数目。
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = + ;
bool vis[N];
int a[N], cnt[N], sum[N], d[N];
int n, m, c1, c2;
vector< pair<int, int> > E[N]; void dijkstra() {
priority_queue< pair<int, int> > Q;
Q.push( make_pair(, c1) );
memset(d, 0x3f, sizeof(d));
d[c1] = ; cnt[c1] = ; sum[c1] = a[c1];
while(!Q.empty()) {
int u = Q.top().second;
Q.pop();
if(vis[u]) continue;
vis[u] = ;
for(int i = ; i < E[u].size(); i++) {
int v = E[u][i].first;
int w = E[u][i].second;
if(d[v] > d[u] + w) {
d[v] = d[u] + w;
cnt[v] = cnt[u];
sum[v] = sum[u] + a[v];
Q.push( make_pair(-d[v], v) );
}
else if(d[v] == d[u] + w) {
cnt[v] += cnt[u];
sum[v] = max(sum[v], sum[u] + a[v]);
Q.push( make_pair(-d[v], v) );
}
}
} } int main() {
scanf("%d %d %d %d", &n, &m, &c1, &c2);
for(int i = ; i < n; i++) {
scanf("%d", &a[i]);
}
for(int i = ; i <= m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
E[u].push_back(make_pair(v, w));
E[v].push_back(make_pair(u, w));
}
dijkstra();
printf("%d %d", cnt[c2], sum[c2]);
return ;
}
1004 Counting Leaves
遍历树，在每个深度纪录下答案。
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N=;
vector<int> E[N];
int ans[N], mx = ; void dfs(int u, int fa, int level) {
if(E[u].size()==) {
mx = max(mx, level);
ans[level]++;
return ;
}
for(int i = ; i < E[u].size(); i++){
int v = E[u][i];
if(v != fa) dfs(v, u, level + );
}
} int main() {
int n, m;
scanf("%d %d", &n, &m);
for(int i = ; i <= m; i++) {
int u, v, k;
scanf("%d %d", &u, &k);
for(int j = ; j <= k; j++) {
scanf("%d", &v);
E[u].push_back(v);
}
}
dfs(, , );
printf("%d", ans[]);
for(int i = ; i <= mx; i++){
printf(" %d", ans[i]);
}
return ;
}
1005 Spell It Right
每位数字加起来，转成英文直接输出就好，注意特判0的情况
#include <iostream>
#include <algorithm>
using namespace std; string s;
string str[]={"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
int ans[]; int main() {
int num = , cnt = ;
cin >> s;
for(int i = ; i < s.size(); i++) {
num = num + (s[i] - '');
}
if(num == ) {
cout << str[];
return ;
}
while(num) {
ans[cnt++] = num % ;
num /= ;
}
for(int i = cnt - ; i >= ; i--){
cout << str[ ans[i] ] ;
if(i != ) cout << " " ;
}
return ;
}
1006 Sign In and Sign Out
直接把时间转成数字，大小比较，更新答案。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int INF = 0x3f3f3f3f;
char s[], ans1[], ans2[]; int main() {
int n, mi = INF, mx = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
int a, b, c, d, e, f;
scanf("%s %d:%d:%d %d:%d:%d", s, &a, &b, &c, &d, &e, &f);
a = a * + b * + c;
d = d * + e * + f;
if(a < mi) {
mi = a;
strcpy(ans1, s);
}
if(d > mx) {
mx =d;
strcpy(ans2, s);
}
}
printf("%s %s", ans1, ans2);
return ;
}
1007 Maximum Subsequence Sum
最大子段和，动态规划的一个想法。一直累加，加到小于0，重置为0，从下个开始重新加。
注意坑点：全负输出最前面和最后面的数字；数字全部<=0，并至少有一个0，输出0 0 0。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
const int N = 1e4 + ;
ll a[N]; int main() {
ll k, l, r, ans = , sum = ;
scanf("%lld", &k);
for(int i = ; i <= k; i++) {
scanf("%lld", &a[i]);
}
l = a[]; r = a[k];
for(int i = ; i <= k; i++) {
sum += a[i];
if(sum < ) sum = ;
if(sum > ans) {
ans = sum;
r = a[i];
}
}
if(ans == ) {
for(int i = ; i <= k; i++) {
if(a[i] == ) {
//-1 0 -1
printf("0 0 0");
return ;
}
}
//-1 -1 -1
printf("%lld %lld %lld", ans, l, r);
return ;
}
for(int i = ; i <= k; i++) {
if(a[i] == r) {
sum = ;
for(int j = i; j >= ; j--) {
sum += a[j];
if(sum == ans) {
l = a[j];
printf("%lld %lld %lld", ans, l, r);
return ;
}
}
}
}
return ;
}
1008 Elevator
模拟一下就好了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; int main() {
int n, k, keep = , ans = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &k);
if( k > keep) {
ans += * (k - keep);
} else {
ans += * (keep - k);
}
ans += ;
keep = k;
}
printf("%d", ans);
return ;
}
1009 Product of Polynomials
按照要求算出多项式，用map存下。多项式的系数可能为负。
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int a[N];
double b[N];
map<int, double> m; int main() {
int k, c, mx = , cnt = ;
double d;
scanf("%d", &k);
for(int i = ; i <= k; i++) {
scanf("%d %lf", &a[i], &b[i]);
}
scanf("%d",&k);
for(int i = ; i <= k; i++) {
scanf("%d %lf", &c, &d);
for(int j = ; j <= k; j++) {
mx = max(mx, c + a[j]);
m[(c + a[j])] += b[j] * d;
}
}
for(int i = ; i <= mx; i++) {
if(m[i] != ) cnt++;
}
printf("%d",cnt);
for(int i = mx; i >= ; i--) {
if(m[i] != ) printf(" %d %.1f", i, m[i]);
}
return ;
}
1010 Radix
先把要判断的数，和另一个数每位上的数字处理出来，然后二分答案。右边界要开到$3*10^9$左右。这精度卡的真严谨呀。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
string s1, s2;
ll tag, radix, n1, n2;
ll a[], num = , k = , l = , r = 3e9, ans = 1e18; bool check(ll mid) {
ll res = , tmp = ;
for(int i = n2 - ; i >= ; i--) {
res = res + a[i] * tmp;
tmp *= mid;
}
if(res == num) ans = min(ans, mid);
if(res >= num || res < ) return true;
else return false;
} int main() {
cin >> s1 >> s2 >> tag >> radix;
n1 = s1.size(); n2 = s2.size(); if(tag == ) {
swap(s1, s2); swap(n1, n2);
} for(int i = n1 - ; i >= ; i--) {
if(s1[i] >= 'a' && s1[i] <= 'z') {
num = num + ( (s1[i] - 'a') + ) * k;
} else {
num = num + (s1[i] - '') * k;
}
k *= radix;
}
for(int i = n2 - ; i >= ; i--) {
if(s2[i] >= 'a' && s2[i] <= 'z') {
a[i] = 1LL * ( (s2[i] - 'a') + );
} else {
a[i] = 1LL * (s2[i] - '');
}
l = max(l, a[i] + );
}
while(l <= r) {
ll mid = (l + r) /;
if(check(mid)) r = mid - ;
else l = mid + ;
}
if(ans == 1e18) cout << "Impossible";
else cout << ans;
return ;
}
1011 World Cup Betting
按题目模拟一下，照着输出就好。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; char ans[]; int main() {
double a, b, c, res = 0.65;
for(int i = ; i <= ; i++) {
scanf("%lf %lf %lf", &a, &b, &c);
if(a >= b && a >= c) ans[i] = 'W', res *= a;
else if(b >= a && b >= c) ans[i] = 'T', res *= b;
else if(c >= a && c >= b) ans[i] = 'L', res *= c;
}
res = (res - ) * ;
for(int i = ; i <= ; i++) printf("%c ", ans[i]);
printf("%.2f", res);
return ;
}
1012 The Best Rank
结构体排序。按题目需要的优先级排序，记录下。判断的时候也按照要求的优先级判断，更新答案。注意存等级顺序的时候，相同分数的应排在同一等级。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e6;
const int INF = 0x3f3f3f3f;
struct node {
int id, c, m, e, a;
}s[N];
int A[N], C[N], M[N], E[N]; bool cmpa(node s1, node s2) {
if(s1.a == s2.a) return s1.id < s2.id;
return s1.a > s2.a;
} bool cmpc(node s1, node s2) {
if(s1.c == s2.c) return s1.id < s2.id;
return s1.c > s2.c;
} bool cmpm(node s1, node s2) {
if(s1.m == s2.m) return s1.id < s2.id;
return s1.m > s2.m;
} bool cmpe(node s1, node s2) {
if(s1.e == s2.e) return s1.id < s2.id;
return s1.e > s2.e;
} int main() {
int n, m, id;
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%d %d %d %d", &s[i].id, &s[i].c, &s[i].m, &s[i].e);
s[i].a = (s[i].c + s[i].m + s[i].e);
}
sort(s + , s + + n, cmpa);
for(int i = ; i <= n; i++) {
if(s[i].a == s[i-].a) A[s[i].id] = A[ s[i - ].id ];
else A[s[i].id] = i;
}
sort(s + , s + + n, cmpc);
for(int i = ; i <= n; i++) {
if(s[i].c == s[i-].c) C[s[i].id] = C[ s[i - ].id ];
else C[s[i].id] = i;
}
sort(s + , s + + n, cmpm);
for(int i = ; i <= n; i++) {
if(s[i].m == s[i-].m) M[s[i].id] = M[ s[i - ].id ];
else M[s[i].id] = i;
}
sort(s + , s + + n, cmpe);
for(int i = ; i <= n; i++) {
if(s[i].e == s[i-].e) E[s[i].id] = E[ s[i - ].id ];
else E[s[i].id] = i;
}
for(int i = ; i <= m; i++) {
int level = INF;
char ans;
scanf("%d", &id);
if(A[id] != && A[id] < level) level = A[id], ans = 'A';
if(C[id] != && C[id] < level) level = C[id], ans = 'C';
if(M[id] != && M[id] < level) level = M[id], ans = 'M';
if(E[id] != && E[id] < level) level = E[id], ans = 'E';
if(level == INF) printf("N/A\n");
else printf("%d %c\n", level, ans);
}
return ;
}
1013 Battle Over Cities
考虑某个顶点（k）被占领，那么我们需要把剩余的城市连接起来（这时候不考虑那些和顶点k连接的线），假设剩余的城市形成了m个集合（每个集合内的点都是连通的），我们需要m-1条边连接它们。
（代码中的cnt-2，是计算的时候把顶点k也单独看成一个集合，但是这个点不需要计算，所以再cnt-1的基础上再减去1）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int fa[N], u[N * N], v[N * N]; int fi(int x) {
return x == fa[x] ? x : fa[x] = fi(fa[x]);
} void Union(int x, int y) {
int fx = fi(x), fy = fi(y);
if(fx != fy) {
fa[fx] = fy;
}
} int main() {
int n, m, k, p;
scanf("%d %d %d", &n, &m, &k);
for(int i = ; i <= m; i++) {
scanf("%d %d", &u[i], &v[i]);
}
for(int i = ; i <= k; i++) {
int cnt = ;
scanf("%d", &p);
for(int j = ; j <= n; j++) fa[j] = j;
for(int j = ; j <= m; j++) {
if(u[j] == p || v[j] == p) continue;
else Union(u[j], v[j]);
}
for(int j = ; j <= n; j++) {
if(fa[j] == j) cnt++;
}
printf("%d\n", cnt - );
}
return ;
}
1014 Waiting in Line
队列模拟下。注意能够在17:00之前被服务到的，不管他需要办理业务多长时间，都是能够有答案的。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
queue<int> window[N];
int ans1[N], ans2[N], t[N]; int main() {
int n, m, k, q, time;
scanf("%d %d %d %d", &n, &m, &k, &q);
for(int i = ; i <= k; i++) {
int pos = ;
scanf("%d", &time);
for(int j = ; j <= n; j++) {
if(i <= n * m) {
if(window[j].size() < window[pos].size()) pos = j;
} else {
if(window[j].front() < window[pos].front()) pos = j;
}
}
t[pos] += time;
window[pos].push(t[pos]);
if(i > n * m) window[pos].pop();
if(t[pos] - time < ) ans1[i] = + t[pos] / , ans2[i] = t[pos] % ;
else ans1[i] = -;
}
for(int i = ; i <= q; i++) {
int pos;
scanf("%d", &pos);
if(ans1[pos] == -) printf("Sorry\n");
else printf("%02d:%02d\n", ans1[pos], ans2[pos]);
}
return ;
}
1015 Reversible Primes
把原来的数转换成对应进制下的逆反数。再对原来的数和逆反数进行素数判断。比如23在2进制下为10111，逆反数为11101，再转换成10进制为29。
#include <cstdio>
#include <iostream>
using namespace std; int Reverse(int n, int d) {
int res = ;
while(n) {
res = res * d + n % d;
n /= d;
}
return res;
} bool Check(int k) {
if(k <= ) return false;
for(int i = ; i * i <= k; i++) {
if(k % i == ) return false;
}
return true;
} int main() {
int n, d;
while(scanf("%d", &n) != EOF && n >= ) {
scanf("%d", &d);
if(Check(n) && Check( Reverse(n, d) )) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return ;
}
1016 Phone Bills
注意题目中给的24小时的花费是 分/分钟。所有记录放进结构体中，按优先级大小 名字的字典序 > 时间排序，因为题目中时间的唯一性和时间都是按开始到结束排序的，那么前后分别为on和off的必然是合法数据。排序完后再映射到每个人去（参考了柳神的做法，感觉很巧妙），接着计算差值，按照要求输出。
#include <map>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; int cost[];
struct node{
string name;
int time, month, day, hour, minute, stuate, status;
}rcd[];
map<string, vector<node> > customer; bool cmp(node x, node y) {
if(x.name == y.name) return x.time < y.time;
return x.name < y.name;
} int main() {
int n;
for(int i = ; i < ; i++) scanf("%d", &cost[i]), cost[] += cost[i];
scanf("%d", &n);
for(int i = ; i <= n; i++) {
string str;
cin >> rcd[i].name;
scanf("%d:%d:%d:%d", &rcd[i].month, &rcd[i].day, &rcd[i].hour, &rcd[i].minute);
cin >> str;
if(str == "on-line") rcd[i].status = ;
else rcd[i].status = ;
rcd[i].time = rcd[i].day * * + rcd[i].hour * + rcd[i].minute;
}
sort(rcd + , rcd + + n, cmp);
for(int i = ; i <= n; i++) {
if(rcd[i - ].name == rcd[i].name && rcd[i - ].status == && rcd[i].status == ) {
customer[rcd[i].name].push_back(rcd[i - ]);
customer[rcd[i].name].push_back(rcd[i]);
}
}
for(auto p : customer) {
double res = ;
vector <node> date = p.second;
cout << p.first << " ";
printf("%02d\n", date[].month);
for(int i = ; i < date.size(); i += ) {
printf("%02d:%02d:%02d ", date[i].day, date[i].hour, date[i].minute);
printf("%02d:%02d:%02d ", date[i + ].day, date[i + ].hour, date[i + ].minute);
double c1 = , c2 = ;
for(int j = ; j < ; j++) {
if(j < date[i].hour) {
c1 += cost[j] * ;
} else if(j == date[i].hour) {
c1 += date[i].day * cost[] * + 1.0 * date[i].minute * cost[j];
}
}
for(int j = ; j < ; j++) {
if(j < date[i + ].hour) {
c2 += cost[j] * ;
} else if(j == date[i + ].hour) {
c2 += date[i + ].day * cost[] * + 1.0 * date[i + ].minute * cost[j];
}
}
printf("%d $%.2f\n", date[i + ].time - date[i].time, (c2 - c1) / );
res += (c2 - c1) / ;
}
printf("Total amount: $%.2f\n", res);
} return ;
}
1017 Queueing at Bank
直接模拟。每个窗口遍历一下，找到时间最前的窗口，维护下每个窗口的时间。这题和1014很像，但是有一个区别，1014题目中说的是17:00之前（包括17:00）服务得到就服务，这题是只要你17:00之前（包括17:00）到达银行，那你就能被服务，不用管你是不是在17:00后服务的。（这个就是最后一个点的trick）（还是要仔细看题呀）。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e4 + ;
const int INF = 0x3f3f3f3f; int t[N];
struct node{
int time, cost;
}p[N]; bool cmp(node x, node y) {
return x.time < y.time;
} int main(){
int n, k, cnt = ;
double ans = ;
scanf("%d %d", &n, &k);
for(int i = ; i <= n; i++) {
int hh, mm, ss;
scanf("%d:%d:%d %d", &hh, &mm, &ss, &p[i].cost);
p[i].time = * hh + * mm + ss;
p[i].cost *= ;
}
sort(p + , p + + n, cmp);
for(int i = ; i <= k; i++) t[i] = * ;
for(int i = ; i <= n; i++) {
if(p[i].time > * ) break;
int pos = ;
for(int j = ; j <= k; j++) {
if(t[pos] > t[j]) pos = j;
}
if(p[i].time > t[pos]) {
t[pos] = p[i].time;
} else {
ans += 1.0 * (t[pos] - p[i].time);
}
t[pos] += p[i].cost;
cnt++;
}
printf("%.1f\n", ans/60.0/cnt);
return ;
}
1018 Public Bike Management
一开始我用dijkstra，一直有几个点过不去。去看了下网上的题解，发现这题数据不大可以直接用暴力DFS+剪枝过。到达终点，判断的条件需要满足最短路条件，先满足从0点拿出最少，然后满足送回0点最少。
判断顺序需要注意。还有就是DFS的时候需要回溯，标记打完记得消除。
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = ;
const int INF = 0x3f3f3f3f;
bool vis[maxn];
int c[maxn], d[maxn];
int Cmax, N, Sp, M;
///take 拿去;bring 带回
int sum = , take = , bring = ;
int ans_sum = INF, ans_take = INF, ans_bring = INF;
vector<int> path;
vector<int> ans_path;
vector< pair<int,int> > E[maxn]; void dfs(int u) {
if(ans_sum < sum ) return ;
if(u == Sp) {
if(ans_sum > sum) {
ans_sum = sum;
ans_bring = bring;
ans_take = take;
ans_path = path;
} else {
if(ans_take > take || (ans_take == take && (ans_bring > bring) )) {
ans_bring = bring;
ans_take = take;
ans_path = path;
}
}
return ;
}
for(int i = ; i < E[u].size(); i++) {
int v = E[u][i].first;
int dis = E[u][i].second;
int tmp_sum = sum, tmp_bring = bring, tmp_take = take;
if(!vis[v] && d[v] >= d[u] + dis) {
vis[v] = ;
sum += dis;
bring += (c[v] - Cmax / );
if(bring < ) take -= bring, bring = ;
path.push_back(v);
d[v] = d[u] + dis;
dfs(v);
vis[v] = ;
sum = tmp_sum;
bring = tmp_bring;
take = tmp_take;
path.pop_back();
}
} } int main(){
scanf("%d%d%d%d", &Cmax, &N, &Sp, &M);
for(int i = ; i <= N; i++) {
scanf("%d", &c[i]);
}
for(int i = ; i <= M; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
E[u].push_back(make_pair(v, w));
E[v].push_back(make_pair(u, w));
}
for(int i = ; i< maxn; i++) d[i] = INF;
d[] = ; vis[] = ;
dfs();
printf("%d 0", ans_take);
for(int i = ; i < ans_path.size(); i++) {
printf("->%d", ans_path[i]);
}
printf(" %d",ans_bring);
return ;
}
1019 General Palindromic Number
把n转换成b进制下的数，判断下该数是否回文。
#include <iostream>
#include <algorithm>
using namespace std; int a[]; int main() {
bool f = ;
int n, m, cnt = ;
cin >> n >> m;
while(n) {
a[++cnt] = n % m;
n /= m;
}
for(int i = ; i <= cnt / ; i++) {
if(a[i] != a[cnt - i + ]) {
f = ;
break;
}
}
if(f) printf("Yes\n");
else printf("No\n");
for(int i = cnt; i >= ; i--) {
printf("%d", a[i]);
if(i != ) printf(" ");
}
return ;
}
1020 Tree Traversals
前序遍历：根左右；中序遍历：左根右；后序遍历：左右根。
该题知道中序遍历和后序遍历，求层序遍历。 由后序遍历我们可以知道根节点。根据得到的根节点，去中序遍历中找到对应位置，该位置左边的就为左子树的顶点，右边的为右子树的顶点，根据长度我们可以同时在后序遍历中找到对应段。一直搜索下去，直到叶子节点，没有子树的设置-1。
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e7 + ;
int post[], in[];
int node[N]; // l1 r1 后序; l2 r2 中序
void restore(int l1, int r1, int l2, int r2, int id) {
if(l1 > r1) {
node[id] = -;
return ;
}
node[id] = post[r1];
for(int i = l2; i <= r2; i++) {
if(in[i] == node[id]) {
int len = i - l2;
restore(l1, l1 + len -, l2, i - , * id);
restore(l1 + len, r1 - , i + , r2, * id + );
}
}
} int main() {
int n;
cin >> n;
for(int i = ; i <= n; i++) cin >> post[i];
for(int i = ; i <= n; i++) cin >> in[i];
restore(, n, , n, );
queue <int> Q;
Q.push();
while(!Q.empty()) {
int u = Q.front();
Q.pop();
if(node[ * u] != -) Q.push( * u);
if(node[ * u + ] != -) Q.push( * u + );
if(u != ) cout << " ";
if(node[u] != -) cout << node[u];
}
return ;
}
1021 Deepest Root
先并查集判断下是不是树。DFS暴力跑每个顶点，求每个顶点能跑最远的距离。本来以为还要剪枝，做下标记什么的，没想到暴力一跑，A了。（数据可能比较水，暴力的时间复杂度达到O（n^2））
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e4 + ;
int fa[N], d[N];
vector <int> E[N]; int fi(int x) {
return x == fa[x] ? fa[x] : fa[x] = fi(fa[x]);
} void Union(int x, int y) {
int fx = fi(x), fy = fi(y);
if(fx != fy) {
fa[fx] = fy;
}
} void dfs(int st, int u, int F, int deep) {
d[st] = max(d[st], deep);
for(int i = ; i < E[u].size(); i++) {
int v = E[u][i];
if(v != F) dfs(st, v, u, deep + );
}
} int main() {
int n, cnt = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) fa[i] = i;
for(int i = ; i < n; i++){
int u, v;
scanf("%d %d", &u, &v);
E[u].push_back(v);
E[v].push_back(u);
Union(u, v);
}
for(int i = ; i <= n; i++) {
if(i == fa[i]) cnt++;
}
if(cnt > ) {
printf("Error: %d components", cnt);
} else {
int mx = ;
for(int i = ;i <= n; i++) {
dfs(i, i, -, );
mx = max(mx, d[i]);
}
for(int i = ; i <= n; i++) {
if(d[i] == mx) printf("%d\n", i);
}
} return ;
}
1022 Digital Library
这题就用map搞下就好了。本来想用hash，搞了一个多小时，一直过不了，就放弃了。注意输出ID的时候用%7d，一直没注意，卡了挺久的。
#include <set>
#include <map>
#include <cstdio>
#include <iostream>
using namespace std; string s;
map <string, set<int> > mp[]; int main() {
int n, m, id, pos;
cin >> n;
for(int i = ; i <= n; i++) {
cin >> id;
getchar();
for(int j = ; j <= ; j++) {
if(j == ) {
while(cin >> s) {
mp[j][s].insert(id);
char c = getchar();
if(c == '\n') break;
}
continue;
}
getline(cin, s);
mp[j][s].insert(id);
}
}
cin >> m;
for(int i = ; i <= m; i++) {
char c;
cin >> pos >> c;
getchar();
getline(cin, s);
cout << pos << ": " << s << endl;
if(mp[pos].find(s) != mp[pos].end()) {
for(auto it : mp[pos][s]) printf("%07d\n", it);
} else {
printf("Not Found\n");
}
}
return ;
}
1023 Have Fun with Numbers
把2倍的计算出来与原来的比较一下。字符串存，no的时候也要输出字符串。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; char s1[], s2[], ans[]; int main() {
int val, cnt = ;
scanf("%s", s1 + );
int len = strlen(s1 + );
for(int i = len; i >= ; i--) {
val = * (s1[i] - '') + cnt;
cnt = ;
if(val >= ) val -= , cnt++;
s2[i] = (val + ''); ans[i] = s2[i];
}
sort(s1 + , s1 + + len);
sort(s2 + , s2 + + len);
for(int i = ; i <= len; i++) {
if(s1[i] != s2[i]) {
printf("No\n");
if(cnt > ) printf("1%s", ans + );
else printf("%s", ans + );
return ;
}
}
printf("Yes\n");
printf("%s", ans + );
return ;
}
1024 Palindromic Number
考虑下最大能变成多少，每次加上翻转后的数，看成每次乘上2，那么最大的数会变成$10^10 * 2^100$。long long会爆，用string存。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll; bool check(string n) {
for(int i = , j = n.size() - ; i < j; i++, j--) {
if(n[i] != n[j]) return false;
}
return true;
} string cal(string n) {
string m = n, res = "";
reverse(n.begin(), n.end());
int cnt = ;
for(int i = m.size() - ; i >= ; i--) {
int d = (m[i] - '') + (n[i] - '') + cnt;
cnt = ;
if(d >= ) d -= , cnt++;
char c = d + '';
res = c + res;
}
if(cnt > ) res = "" + res;
return res;
} int main() {
int k;
string n;
cin >> n >> k;
for(int i = ; i <= k; i++) {
if(check(n)) {
cout << n << endl << i - << endl;
return ;
}
n = cal(n);
}
cout << n << endl << k << endl;
return ;
}
1025 PAT Ranking
结构体排序。部分先排，再全部排序。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
const int N = +;
struct node {
ll id;
int grade, fin, loc_num, loc_rank;
}p[N]; bool cmp(node x, node y) {
if(x.grade == y.grade) return x.id < y.id;
return x.grade > y.grade;
} int main() {
int n, m, cnt = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &m);
for(int j = ; j < m; j++) {
scanf("%lld %d", &p[cnt + j].id, &p[cnt + j].grade);
p[cnt + j].loc_num = i;
}
sort(p + cnt, p + cnt + m, cmp);
p[cnt].loc_rank = ;
for(int j = ; j < m; j++) {
if(p[cnt + j].grade == p[cnt + j - ].grade) {
p[cnt + j].loc_rank = p[cnt + j - ].loc_rank;
} else {
p[cnt + j].loc_rank = j + ;
}
}
cnt += m;
}
sort(p, p + cnt, cmp);
printf("%d\n", cnt);
for(int i = ; i < cnt; i++) {
if(i == || p[i].grade != p[i - ].grade) {
p[i].fin = i + ;
} else {
p[i].fin = p[i - ].fin;
}
printf("%013lld %d %d %d\n", p[i].id, p[i].fin, p[i].loc_num, p[i].loc_rank);
}
return ;
}
1027 Colors in Mars
进制转换
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; int c[]; void solve(int v) {
char c1, c2;
int a1 = v / , a2 = v % ;
if(a1 > ) c1 = 'A' + (a1 - );
else c1 = '' + a1;
if(a2 > ) c2 = 'A' + (a2 - );
else c2 = '' + a2;
cout << c1 << c2;
} int main() {
for(int i = ; i <= ; i++) cin >> c[i];
cout << "#";
for(int i = ; i <= ; i++) solve(c[i]);
return ;
}
1028 List Sorting
结构体排序，strcmp函数。（这个函数都快忘记了，-_-||）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
struct node {
int id, grade;
char name[];
}p[N]; bool cmp1(node x, node y) {
return x.id < y.id;
} bool cmp2(node x, node y) {
if( strcmp(x.name, y.name) == ) {
return x.id < y.id;
}
return strcmp(x.name, y.name) < ;
} bool cmp3(node x, node y) {
if(x.grade == y.grade) {
return x.id < y.id;
}
return x.grade < y.grade;
} int main() {
int n, k;
scanf("%d %d", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%d %s %d", &p[i].id, &p[i].name, &p[i].grade);
}
if(k == ) {
sort(p + , p + + n, cmp1);
}
else if(k == ){
sort(p + , p + + n, cmp2);
} else {
sort(p + , p + + n, cmp3);
}
for(int i = ; i <= n; i++) {
printf("%06d %s %d\n", p[i].id, p[i].name, p[i].grade);
}
return ;
}
1029 Median
最后一组卡内存。确定位置$(n+m+1)/2$，输入m个数字的同时，通过与之前输入的n个数字比较，用一个下标不断逼近位置。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 2e5 + ;
int a[N]; int main() {
int n, m, num;
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
int id = , cnt = ;
int mid = (n + m + ) / ;
for(int i = ; i <= m; i++) {
scanf("%d", &num);
while(id <= n && num > a[id]) {
cnt++;
if(cnt == mid) {printf("%d", a[id]); return ;}
id++;
}
cnt++;
if(cnt == mid) {printf("%d", num); return ;}
}
while(cnt < mid && id < n) {
cnt++;
if(cnt == mid) {printf("%d", a[id]); return ;}
id++;
}
return ;
}
1030 Travel Plan
最短路套路题+遍历路径。
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = + ;
bool vis[N];
int sum[N], d[N], pre[N];
int n, m, c1, c2; struct edge{
int u, v, dis, cost;
}; struct node{
int u, dis;
friend bool operator < (node a, node b) {
return a.dis > b.dis;
}
}; vector<edge> E[N]; void dijkstra() {
priority_queue<node> Q;
Q.push(node{c1, });
memset(d, 0x3f, sizeof(d));
d[c1] = ;
while(!Q.empty()) {
int u = Q.top().u;
Q.pop();
if(vis[u]) continue;
vis[u] = ;
for(int i = ; i < E[u].size(); i++) {
int v = E[u][i].v, w = E[u][i].dis, c = E[u][i].cost;
if(d[v] > d[u] + w) {
d[v] = d[u] + w;
sum[v] = sum[u] + c;
Q.push(node{v, d[v]});
pre[v] = u;
}
else if(d[v] == d[u] + w) {
if(sum[u] + c < sum[v]) {
sum[v] = sum[u] + c;
Q.push(node{v, d[v]});
pre[v] = u;
}
}
}
} } void print(int u){
if(u != -){
print(pre[u]);
printf("%d ", u);
}
} int main() {
scanf("%d %d %d %d", &n, &m, &c1, &c2);
for(int i = ; i <= m; i++) {
int u, v, w, c;
scanf("%d %d %d %d", &u, &v, &w, &c);
E[u].push_back(edge{u, v, w, c});
E[v].push_back(edge{v, u, w, c});
}
dijkstra();
pre[c1] = -;
print(c2);
printf("%d %d", d[c2], sum[c2]);
return ;
}
1031 Hello World for U
模拟暴力输出。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; char s[]; int main() {
scanf("%s", s);
int n = strlen(s), n1 = (n + ) / , n2 = n - * n1;
for(int i = ; i < n1 - ; i++) {
printf("%c", s[i]);
for(int j = ; j <= n2; j++) printf(" ");
printf("%c\n", s[n - i - ]);
}
for(int i = n1 - ; i <= n1 + n2; i++) {
printf("%c",s[i]);
}
return ;
}
1032 Sharing
记录下位置往后跑。重复经过的第一个位置为答案。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
int nxt[N], vis[N]; int main() {
int s1, s2, n;
scanf("%d %d %d", &s1, &s2, &n);
for(int i = ; i <= n; i++) {
int Now, Nxt;
char c;
scanf("%d %c %d", &Now, &c, &Nxt);
nxt[Now] = Nxt;
}
while(s1 != -) {
vis[s1]++;
s1 = nxt[s1];
}
while(s2 != -) {
if(vis[s2]) {
printf("%05d\n", s2);
return ;
}
vis[s2]++;
s2 = nxt[s2];
}
printf("-1\n");
return ;
}
1033 To Fill or Not to Fill
贪心策略：优先前往油价低的站，若比当前油价低，直接跑到这个站；否则前往这些站中油价最低的站。更新当前位置和油桶中的油量和最后的答案。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
const double INF = 1e18;
struct node {
double dis, price;
}sta[N]; bool cmp(node x, node y) {
return x.dis < y.dis;
} int main() {
int now_pos = , n;
double c_max, d, d_avg, ans = , now_tank = ;
scanf("%lf %lf %lf %d", &c_max, &d, &d_avg, &n);
for(int i = ; i < n; i++) {
scanf("%lf %lf", &sta[i].price, &sta[i].dis);
}
sta[n].price = ; sta[n].dis = d;
sort(sta, sta + + n, cmp);
if(sta[].dis != ) {
printf("The maximum travel distance = 0.00\n");
return ;
}
while(now_pos < n) {
int nxt_pos = -;
double min_price = INF;
for(int i = now_pos + ; i <= n && (sta[i].dis - sta[now_pos].dis) <= c_max * d_avg; i++) {
if(min_price > sta[i].price) {
min_price = sta[i].price;
nxt_pos = i;
if(min_price < sta[now_pos].price) {
break;
}
}
}
if(nxt_pos == -) break;
double need = (sta[nxt_pos].dis - sta[now_pos].dis) / d_avg;
if(min_price < sta[now_pos].price) {
if(now_tank >= need) {
now_tank -= need;
} else {
ans += (need - now_tank) * sta[now_pos].price;
now_tank = ;
}
} else {
ans += (c_max - now_tank) * sta[now_pos].price;
now_tank = c_max - need;
}
now_pos = nxt_pos;
}
if(now_pos == n) {
printf("%.2f\n", ans);
} else {
printf("The maximum travel distance = %.2f\n", sta[now_pos].dis + c_max * d_avg);
}
return ;
}
1034 Head of a Gang
并查集扔扔，map标记来标记过去，最后存起来排个序。
//1034 Head of a Gang
#include <map>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; struct node{
string name;
int cnt;
}; bool cmp(node x, node y) {
return x.name < y.name;
} const int N = ;
vector <string> v[N];
vector <node> ans;
map<string, int> m;
map<int, string> rm;
int fa[N], t[N]; int fi(int x) {
return fa[x] == x ? x : fa[x] = fi(fa[x]);
} int main() {
for(int i = ; i < N; i++) fa[i] = i;
int cnt = ;
int n, k, time;
string name1, name2, name;
cin >> n >> k;
for(int i = ; i <= n; i++) {
cin >> name1 >> name2 >> time;
if(!m[name1]) m[name1] = ++cnt, rm[cnt] = name1;
if(!m[name2]) m[name2] = ++cnt, rm[cnt] = name2;
t[m[name1]] += time;
t[m[name2]] += time;
int fx = fi(m[name1]), fy = fi(m[name2]);
if(fx != fy) {
fa[fx] = fy;
}
}
for(int i = ; i <= n; i++) {
int id = fi(i);
v[id].push_back(rm[i]);
}
for(int i = ; i <= n; i++) {
if(v[i].size() > ) {
int sum = , mx = ;
for(int j = ; j < v[i].size(); j++) {
sum += t[m[v[i][j]]];
if(mx < t[m[v[i][j]]]) {
mx = t[m[v[i][j]]];
name = v[i][j];
}
}
node tmp; tmp.cnt = v[i].size(); tmp.name = name;
if(sum > * k) ans.push_back(tmp);
}
}
sort(ans.begin(), ans.end(), cmp);
cout << ans.size() << endl;
for(int i = ; i < ans.size(); i++) {
cout << ans[i].name << " " << ans[i].cnt << endl;
}
return ;
}
1035 Password
注意输出格式。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
bool vis[N];
char s1[N][], s2[N][]; int main() {
int n, m, cnt = ;
scanf("%d", &n);
for(int i = ; i < n; i++) {
scanf("%s %s", s1[i], s2[i]);
m = strlen(s2[i]);
for(int j = ; j < m; j++) {
if(s2[i][j] == '') s2[i][j] = '@', vis[i] = ;
if(s2[i][j] == '') s2[i][j] = '%', vis[i] = ;
if(s2[i][j] == 'l') s2[i][j] = 'L', vis[i] = ;
if(s2[i][j] == 'O') s2[i][j] = 'o', vis[i] = ;
}
if(vis[i]) cnt++;
}
if(!cnt) {
if(n == ) printf("There is %d account and no account is modified\n", n);
else printf("There are %d accounts and no account is modified\n", n);
} else {
printf("%d\n", cnt);
for(int i = ; i < n; i++) {
if(vis[i]) printf("%s %s\n", s1[i], s2[i]);
}
}
return ;
}
1036 Boys vs Girls
模拟即可。
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; struct node{
string name, gender, ID;
int grade;
}ans; bool cmp(node x, node y) {
return x.grade < y.grade;
} vector <node> M, F; int main() {
int n, grade;
string name, gender, ID;
cin >> n;
for(int i = ; i <= n; i++) {
cin >> name >> gender >> ID >> grade;
if(gender == "M") M.push_back(node{name, gender, ID, grade});
else F.push_back(node{name, gender, ID, grade});
}
sort(M.begin(), M.end(), cmp);
sort(F.begin(), F.end(), cmp);
if(!M.size() || !F.size()) {
if(F.size()) {
ans = F[F.size() - ];
cout << ans.name << " " << ans.ID << endl;
} else {
cout << "Absent" << endl;
}
if(M.size()) {
ans = M[];
cout << ans.name << " " << ans.ID << endl;
} else {
cout << "Absent" << endl;
}
cout << "NA" << endl;
} else {
ans = F[F.size() - ];
grade = ans.grade;
cout << ans.name << " " << ans.ID << endl;
ans = M[];
cout << ans.name << " " << ans.ID << endl;
grade -= ans.grade;
cout << grade << endl;
}
return ;
}
1037 Magic Coupon
先排序，接着前面负的搞一次，后面正的搞一次。
//
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; int n, m;
const int N = 1e5 + ;
typedef long long ll;
ll a[N], b[N]; int main() {
ll ans = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%lld", &a[i]);
scanf("%d", &m);
for(int i = ; i <= m; i++) scanf("%lld", &b[i]);
sort(a + , a + + n);
sort(b + , b + + m);
for(int i = , j = ; i <= n && j <= m && b[j] < && a[i] < ; i++, j++) {
ans += a[i] * b[j];
}
for(int i = n, j = m; i >= && j >= && b[j] > && a[i] > ; i--, j--) {
ans += a[i] * b[j];
}
printf("%lld\n", ans);
return ;
}
1038 Recover the Smallest Number
使得数字最小，字符串排序的时候可以这样考虑，判断是s1 s2 小还是 s2 s1小即可。
//
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; vector <string> v; bool cmp(string s1, string s2) {
return s1 + s2 < s2 + s1;
} int main() {
int n;
bool vis = ;
string s;
cin >> n;
for(int i = ; i < n; i++) {
cin >> s;
v.push_back(s);
}
sort(v.begin(), v.end(), cmp);
s = "";
for(int i = ; i < n; i++) s = s + v[i];
for(int i = ; i < s.size(); i++) {
if(s[i] == '' && !vis) continue;
else {
vis = ;
cout << s[i];
}
}
if(!vis) cout << ;
return ;
}
1039 Course List for Student
map标记位置，按坑填就即可。题目中的N应该是400000吧（汗...）
#include <map>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; char s[];
map <int, int> m;
const int N = + ;
vector <int> v[N]; int cal() {
int res = (s[] - '');
res += (s[] - 'A') * ;
res += (s[] - 'A') * * ;
res += (s[] - 'A') * * * ;
return res;
} int main() {
int n, k, a, b, name, cnt = ;
scanf("%d%d", &n, &k);
for(int i = ; i <= k; i++) {
scanf("%d%d", &a, &b);
for(int j = ; j <= b; j++) {
scanf("%s", s);
name = cal() + ;
if(!m[name]) m[name] = cnt++;
v[m[name]].push_back(a);
}
}
for(int i = ; i <= cnt; i++) sort(v[i].begin(), v[i].end());
for(int i = ; i <= n; i++) {
scanf("%s", s);
name = cal() + ;
int id = m[name];
printf("%s %d", s, v[id].size());
for(int j = ; j < v[id].size(); j++) {
printf(" %d", v[id][j]);
}
printf("\n");
}
return ;
}
1040 Longest Symmetric String
从两个扩展和从一个扩展分别跑一次，更新答案。
//
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
char s[N]; int main() {
int n = , ans = ;
char c;
while(scanf("%c", &c) != EOF && c != '\n') {
s[n++] = c;
}
for(int k = ; k < n; k++) {
int tmp = ;
for(int i = ; (k - i) >= && (k + i) < n; i++) {
if(s[k - i] == s[k + i]) tmp += ;
else break;
}
ans = max(ans, tmp);
}
for(int k = ; k < n; k++) {
int tmp = ;
if(s[k] == s[k + ]) {
for(int i = ; (k - i) >= && (k + + i) < n; i++) {
if(s[k - i] == s[k + + i]) tmp += ;
else break;
}
}
ans = max(ans, tmp);
}
printf("%d\n", ans);
return ;
}
1041 Be Unique
map一下，输出计数为1的即可。否则输出None
#include <map>
#include <iostream>
using namespace std; const int N = 1e5 + ;
int a[N];
map<int, int> m; int main() {
int n;
cin >> n;
for(int i = ; i <= n; i++) {
cin >> a[i];
m[a[i]]++;
}
for(int i = ; i <= n; i++) {
if(m[a[i]] == ) {
cout << a[i] << endl;
return ;
}
}
cout << "None" << endl;
return ;
}
1042 Shuffling Machine
存放前后结果，模拟过去即可。
#include <cstdio>
using namespace std; char s[] = {'S','H','C','D','J'}; int A[], B[], in[]; int main() {
int n;
scanf("%d", &n);
for(int i = ; i <= ; i++) A[i] = i;
for(int i = ; i <= ; i++) scanf("%d", &in[i]);
for(int i = ; i < n; i++) {
for(int j = ; j <= ; j++) B[in[j]] = A[j];
for(int j = ; j <= ; j++) A[j] = B[j];
}
for(int i = ; i <= ; i++) {
if(i > ) printf(" ");
printf("%c%d", s[(B[i]-)/], (B[i]-)%+);
}
return ;
}
1043 Is It a Binary Search Tree
（学习一波柳神的写法。）由前序遍历找到左右孩子的边界。注意边界的调整，因为后序遍历是左右根，我们DFS的时候先往左搜索，搜完后把答案存下来。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
bool f = ;
int pre[N], post[N], cnt = ; void dfs(int root, int tail) {
if(root > tail) return ;
int l = root + , r = tail;
if(!f) {
while(l <= tail && pre[l] < pre[root]) l++;
while(r >= root && pre[r] >= pre[root]) r--;
} else {
while(l <= tail && pre[l] >= pre[root]) l++;
while(r >= root && pre[r] < pre[root]) r--;
}
dfs(root + , r);
dfs(l, tail);
post[++cnt] = pre[root];
} int main() {
int n;
cin >> n;
for(int i = ; i <= n; i++) cin >> pre[i];
dfs(, n);
if(cnt != n) {
cnt = ;
f = ;
dfs(, n);
}
if(cnt == n) {
cout << "YES" << endl;
for(int i = ; i <= n; i++) {
if(i == ) cout << post[i];
else cout << " " << post[i];
}
} else {
cout << "NO" << endl;
}
return ;
}
1044 Shopping in Mars
先前缀和，然后两次二分，第一次找>=m最小的。第二次二分把符合的扔进去。
//1044 Shopping in Mars
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int INF = 0x3f3f3f3f;
const int N = 1e5 + ;
int a[N];
vector< pair<int, int> > v; int main() {
int n, m;
int mi = INF;
scanf("%d %d", &n, &m);
for(int i = ; i < n; i++) {
scanf("%d", &a[i]);
if(i != ) a[i] += a[i - ];
}
for(int i = ; i < n; i++) {
int val = ;
if(i != ) val = a[i - ];
int pos = lower_bound(a + i, a + n, val + m) - a;
if((a[pos] -val) >= m) {
mi = min(mi, (a[pos] - val));
}
}
for(int i = ; i < n; i++) {
int val = ;
if(i != ) val = a[i - ];
int pos = lower_bound(a + i, a + n, val + mi) - a;
if((a[pos] -val) == mi) {
v.push_back(make_pair(i + , pos + ));
}
}
for(int i = ; i < v.size(); i++) {
printf("%d-%d\n", v[i].first, v[i].second);
}
return ;
}
1045 Favorite Color Stripe
连dp渣渣的我都会写。从后往前，先找出该点位置在a数组中对应的颜色，然后从后面的颜色转移过来。
$dp[b[i]] = max( dp[b[i]], dp[a[j]] + 1)$
//1045 Favorite Color Stripe
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
const int L = ;
int a[N], dp[N], b[L]; int main() {
int n, m, l, ans = ;
cin >> n >> m;
for(int i = ; i <= m; i++) cin >> a[i];
cin >> l;
for(int i = ; i <= l; i++) cin >> b[i];
for(int i = l; i >= ; i--) {
bool f = ;
for(int j = ; j <= m; j++) {
if(b[i] == a[j]) f = ;
if(f) {
dp[b[i]] = max(dp[b[i]] ,dp[a[j]] + );
ans = max(ans, dp[b[i]]);
}
}
}
cout << ans << endl;
return ;
}
1046 Shortest Distance
小学数学题。前缀和下，再分别顺时针和逆时针比较下。
//1046 Shortest Distance
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
int a[N]; int main() {
int n, m;
cin >> n;
for(int i = ; i <= n; i++) {
cin >> a[i];
a[i] += a[i - ];
}
cin >> m;
for(int i = ; i <= m; i++) {
int l, r;
cin >> l >> r;
if(l > r) swap(l, r);
int ans1 = a[r - ] - a[l - ];
int ans2 = (a[n] - a[r - ]) + a[l - ];
cout << min(ans1, ans2) << endl;
}
return ;
}
1047 Student List for Course
对应存就好了。
//1047 Student List for Course
#include <vector>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
char s[ * N][];
vector <int> v[N]; bool cmp(int a, int b) {
return strcmp(s[a], s[b]) < ;
} int main() {
int n, m, k, id;
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%s %d", s[i], &k);
for(int j = ; j <= k; j++) {
scanf("%d", &id);
v[id].push_back(i);
}
}
for(int i = ; i <= m; i++) sort(v[i].begin(), v[i].end(), cmp);
for(int i = ; i <= m; i++) {
printf("%d %d\n", i, v[i].size());
for(int j = ; j < v[i].size(); j++) {
printf("%s\n", s[v[i][j]]);
}
}
return ;
}
1048 Find Coins
标记，特判下m-a[i] 和a[i]相同的情况。
//1048 Find Coins
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
int a[N], index[N]; int main() {
int n, m;
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
index[a[i]]++;
}
sort(a + , a + + n);
for(int i = ; i <= n; i++) {
int other = m - a[i];
if(other == a[i] && index[other] >= ) {
printf("%d %d\n", a[i], a[i]);
return ;
}
else if(other != a[i] && index[other]) {
printf("%d %d\n", a[i], other);
return ;
}
}
printf("No Solution\n");
return ;
}
1049 Counting Ones
题意：询问从1-n有多少个1，11这样算两个。考虑按位计算，分以下三种情况：
当前位=0，左边*当前位数。
当前位=1，左边*当前位数 + 右边 + 1
当前位>1，（左边+1）*右边
//1049 Counting Ones
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll; int main() {
ll n, base = , ans = ;
cin >> n;
while(n / base) {
ll now = (n % ( * base) ) / base;
ll left = (n / ( * base) ), right = n % base;
if(now == ) ans += left * base;
else if(now == ) ans += left * base + right + ;
else ans += (left + ) * base;
base *= ;
}
cout << ans << endl;
return ;
}
1050 String Subtraction
map一下就可以了。
//1050 String Subtraction
#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e4 + ;
char s[N];
map <char, int> m; int main() {
char c;
int cnt = ;
while(scanf("%c", &s[++cnt]) != EOF && s[cnt] != '\n');
while(scanf("%c", &c) != EOF && c != '\n') {
m[c]++;
}
for(int i = ; i <= cnt; i++) {
if(!m[s[i]]) printf("%c", s[i]);
}
return ;
}
1051 Pop Sequence
模拟入栈操作，如果遍历到的数刚好和栈定元素相同，出栈一个元素，遍历位置+1，在比较直到不同，入栈过程中需要注意判断栈容量。
//1051 Pop Sequence
#include <stack>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int a[N];
stack<int> s; int main() {
int m, n, k;
scanf("%d %d %d", &m, &n, &k);
while(k--) {
int now = ;
bool f = ;
while(s.size()) s.pop();
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
for(int i = ; i <= n; i++) {
s.push(i);
if(a[now] == s.top() && s.size() <= m) {
while(s.size() && a[now] == s.top()) {
now++;
s.pop();
}
}
else if(s.size() > m) {
f = ;
break;
}
}
if(s.size()) f = ;
if(f) printf("YES\n");
else printf("NO\n");
}
return ;
}
1052 Linked List Sorting
先找到给定头节点的那条链，接着把这条链的元素拿出来按key从小到大排序。注意可能这样的链一条都没有。（输出0 -1）
//1052 Linked List Sorting
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
int run[N], vis[N];
struct node {
int key;
int now, next;
}p[N]; bool cmp(node x, node y) {
return x.key < y.key;
} void dfs(int u) {
if(u == -) return ;
vis[u] = ;
dfs(run[u]);
} int main() {
int n, head, cnt = ;
scanf("%d %d", &n, &head);
for(int i = ; i <= n; i++) {
scanf("%d %d %d", &p[i].now, &p[i].key, &p[i].next);
run[p[i].now] = p[i].next;
}
dfs(head);
sort(p + , p + + n, cmp);
for(int i = ; i <= n; i++) {
if(vis[p[i].now]) {
p[++cnt] = p[i];
}
}
if(cnt == ) {
printf("0 -1\n");
return ;
}
printf("%d %05d\n", cnt, p[].now);
for(int i = ; i < cnt; i++) {
printf("%05d %d %05d\n", p[i].now, p[i].key, p[i + ].now);
}
printf("%05d %d -1\n", p[cnt].now, p[cnt].key);
return ;
}
1053 Path of Equal Weight
存边的时候先儿子节点权值从大到小排序，DFS把所有答案搜出来。
//1053 Path of Equal Weight
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int n, m, s;
int a[N], cnt = ;
vector<int> E[N], tmp;
vector<int> res[N]; struct node{
int w,v;
}b[N]; bool cmp(node x, node y) {
return x.w > y.w;
} void dfs(int u, int sum) {
if(sum > s) return ;
tmp.push_back(a[u]);
if(sum + a[u] == s && !E[u].size()) {
res[cnt++] = tmp;
}
for(int i = ; i < E[u].size(); i++) {
dfs(E[u][i], sum + a[u]);
}
tmp.pop_back();
} int main() {
scanf("%d %d %d", &n, &m, &s);
for(int i = ; i < n; i++) scanf("%d", &a[i]);
for(int i = ; i <= m; i++) {
int u, k;
scanf("%d %d", &u, &k);
for(int j = ; j <= k; j++) {
scanf("%d", &b[j].v);
b[j].w = a[b[j].v];
}
sort(b + , b + + k, cmp);
for(int j = ; j <= k; j++) E[u].push_back(b[j].v);
}
dfs(, );
for(int i = ; i < cnt; i++) {
for(int j = ; j < res[i].size(); j++) {
if(j == res[i].size() - ) printf("%d\n", res[i][j]);
else printf("%d ", res[i][j]);
}
}
return ;
}
1054 The Dominant Color
标记颜色出现次数即可。
// 1054 The Dominant Color
#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; map<int, int> cnt; int main() {
int n, m, col;
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
scanf("%d", &col);
cnt[col]++;
if( * cnt[col] > n *m) {
printf("%d", col);
return ;
}
}
}
return ;
}
1055 The World's Richest
结构体排序下，暴力遍历，输出即可。
// 1055 The World's Richest
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
struct node {
char name[];
int age, worth;
}p[N]; bool cmp(node x, node y) {
if(x.worth == y.worth) {
if(x.age == y.age) return strcmp(x.name, y.name) < ;
return x.age < y.age;
}
return x.worth > y.worth;
} int main() {
int n, k;
scanf("%d %d", &n, &k);
for(int i = ; i < n; i++) {
scanf("%s %d %d", p[i].name, &p[i].age, &p[i].worth);
}
sort(p, p + n, cmp);
for(int i = ; i <= k; i++) {
int m, mi, mx, cnt = ;
scanf("%d %d %d", &m, &mi, &mx);
printf("Case #%d:\n", i);
for(int j = ; j < n; j++) {
if(p[j].age >= mi && p[j].age <= mx) {
cnt++;
printf("%s %d %d\n", p[j].name, p[j].age, p[j].worth);
}
if(cnt == m) break;
}
if(cnt == ) printf("None\n");
}
return ;
}
1056 Mice and Rice
用队列模拟下每次遍历组的操作。每组清空，再把质量最大的入队。排名即为当前组数+1
// 1056 Mice and Rice
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int w[N], ans[N]; queue <int> q; int main() {
int n, m, u, v, cnt;
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i++) scanf("%d", &w[i]);
for(int j = ; j <= n; j++) {
scanf("%d", &v);
q.push(v + );
}
cnt = n;
while(q.size() != ) {
int g = (cnt / m) + ( (cnt % m) > ? : );
for(int i = ; i < g; i++) {
int k = q.front();
for(int j = ; j <= m; j++) {
if(i * m + j > cnt) break;
u = q.front();
if(w[u] > w[k]) k = u;
q.pop();
ans[u] = g + ;
}
q.push(k);
}
cnt = g;
}
ans[q.front()] = ;
for(int i = ; i <= n; i++) {
printf("%d%c", ans[i], i == n ? '\n' : ' ');
}
return ;
}
1057 Stack
模拟栈操作。查询的时候二分一下，从树状数组中存的值，查找最前面出现的中值。
// 1057 Stack
#include <stack>
#include <iostream>
#include <algorithm>
#define low(i) ((i)&(-i))
using namespace std; const int N = 1e5 + ;
int c[N], n, u;
char op[];
stack <int> sta; void add(int pos, int v) {
for(int i = pos; i < N; i += low(i)) c[i] += v;
} int query(int pos) {
int res = ;
for(int i = pos; i; i -= low(i)) res += c[i];
return res;
} int PeekMedian() {
int sz = (sta.size() + ) / ;
int l = , r = N - , ans = -;
while(l <= r) {
int mid = (l + r) / ;
if(query(mid) >= sz) ans = mid, r = mid - ;
else l = mid + ;
}
return ans;
} int main() {
scanf("%d", &n);
while(n--) {
scanf("%s", op);
if(op[] == 'u') {
scanf("%d", &u);
add(u, );
sta.push(u);
}
else if(op[] == 'o') {
if(sta.empty()) printf("Invalid\n");
else {
printf("%d\n", sta.top());
add(sta.top(), -);
sta.pop();
}
} else {
if(sta.empty()) printf("Invalid\n");
else {
printf("%d\n", PeekMedian());
}
}
}
return ;
}
1058 A+B in Hogwarts
水题。
// 1058 A+B in Hogwarts
#include <cstdio>
using namespace std; int a[]; int main() { scanf("%d.%d.%d %d.%d.%d", &a[], &a[], &a[], &a[], &a[], &a[]);
if(a[] + a[] >= ) {
a[]++;
a[] -= ;
}
if(a[] + a[] >= ) {
a[]++;
a[] -= ;
}
printf("%d.%d.%d", a[] + a[], a[] + a[], a[] + a[]);
return ;
}
1059 Prime Factors
暴力sqrt（n）判断下，对应输出即可。
//1059 Prime Factors
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll; int main() {
bool f = ;
ll n;
scanf("%lld", &n);
printf("%lld=", n);
for(ll i = ; i * i <= n; i++) {
if(n % i == ) {
ll cnt = ;
while(n % i == ) {
n /= i;
cnt++;
}
if(!f) {
printf("%lld", i), f = ;
} else {
printf("*%lld", i);
}
if(cnt > ) printf("^%lld", cnt);
}
}
if(n > ) {
if(!f) {
printf("%lld", n);
} else {
printf("*%lld", n);
}
}
return ;
}
1060 Are They Equal
这题自己的写法一直只有21分（心态炸了）。搜了波题解，发现怎么还有前导0这种输入啊（妈耶），还要注意不够位要拿0去补。
//1060 Are They Equal
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; int n; string solve(string s, int& k) {
int i = , cnt = ;
string res = "";
while(s.size() && s[] == '') {
s.erase(s.begin());
}
if(s[] == '.') {
s.erase(s.begin());
while(s.size() && s[] == '') {
s.erase(s.begin());
k--;
}
} else {
while(i < s.size() && s[i] != '.') {
i++;
k++;
}
if(i < s.size()) s.erase(s.begin() + i);
}
if(s.size() == ) k = ;
i = ;
while(cnt < n) {
if(i < s.size()) res = res + s[i++];
else res = res + "";
cnt++;
}
return res;
} int main() {
int k1 = , k2 = ;
string s1, s2, s3, s4;
cin >> n >> s1 >> s2;
s3 = solve(s1, k1);
s4 = solve(s2, k2);
if(s3 == s4 && k1 == k2) {
cout << "YES " << "0." << s3 << "*10^" << k1 << endl;
} else {
cout << "NO " << "0." << s3 << "*10^" << k1 << " 0." << s4 << "*10^" << k2 << endl;
}
return ;
}
1061 Dating
按照题目要求做即可。（题目一定多读几遍，想三遍，敲一遍）。做这题的时候太急了，题还没看清就去敲，wa了好几发。
// 1061 Dating
#include <iostream>
using namespace std; string week[] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"}; int main() {
int pos = ;
string s1, s2, s3, s4;
cin >> s1 >> s2 >> s3 >> s4;
int n = min(s1.size(), s2.size());
for(int i = ; i < n; i++) {
if(s1[i] >= 'A' && s1[i] <= 'G') {
if(s1[i] == s2[i]) {
pos = i + ;
int k = (s1[i] - 'A');
cout << week[k];
break;
}
}
}
for(int i = pos; i < n; i++) {
if( (s1[i] >= 'A' && s1[i] <= 'N') || (s1[i] >= '' && s1[i] <= '') ) {
if(s1[i] == s2[i]) {
if(s1[i] >= '' && s1[i] <= '') {
cout << "" << s1[i] << ":";
} else {
int k = (s1[i] - 'A' + );
cout << " " << k << ":";
}
break;
}
}
}
n = min(s3.size(), s4.size());
for(int i = ; i < n; i++) {
if(s3[i] >= 'a' && s3[i] <= 'z' || s3[i] >= 'A' && s3[i] <= 'Z') {
if(s3[i] == s4[i]) {
if(i < ) cout << "" << i << endl;
else cout << i << endl;
break;
}
}
}
return ;
}
1062 Talent and Virtue
结构体排序，按照题目要求排序即可。
// 1062 Talent and Virtue
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 +;
struct node{
int g, id, virtue, talent, total;
}p[N]; bool cmp(node x, node y) {
if(x.g == y.g) {
if(x.total == y.total) {
if(x.virtue == y.virtue) return x.id < y.id;
return x.virtue > y.virtue;
}
return x.total > y.total;
}
return x.g < y.g;
} int main() {
int n, l, h, cnt = ;
scanf("%d%d%d", &n, &l, &h);
for(int i = ; i <= n; i++) {
scanf("%d %d %d", &p[i].id, &p[i].virtue, &p[i].talent);
p[i].total = p[i].virtue + p[i].talent;
p[i].g = ;
if(p[i].virtue < l || p[i].talent < l) continue;
cnt++;
if(p[i].virtue >= h && p[i].talent >= h) {
p[i].g = ;
}
else if(p[i].virtue >= h && p[i].talent < h) {
p[i].g = ;
}
else if(p[i].virtue < h && p[i].talent < h && p[i].virtue >= p[i].talent) {
p[i].g = ;
} else {
p[i].g= ;
}
}
sort(p + , p + + n, cmp);
printf("%d\n", cnt);
for(int i = ; i <= n; i++) {
if(p[i].g > ) break;
printf("%08d %d %d\n", p[i].id, p[i].virtue, p[i].talent);
}
return ;
}