1001 A+B Format (20 分)
题目大意：计算a+b，结果按照西方的那种写数字的方式输出，从三个数一个逗号那种。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a, b, c;
string s, ans, flag;
cin >> a >> b;
c = a + b;
if (c < 0) flag = "-";
s = to_string (c);
reverse (s.begin(), s.end ());
for (int i = 0;i < s.size() && s[i] != '-';i ++) {
if (i % 3 == 0 && i) ans += ",";
ans += s[i];
}
reverse (ans.begin (), ans.end ());
cout << flag;
cout << ans << endl;
return 0;
}
1002 A+B for Polynomials (25 分)
题目大意：两个多项式相加，每一行第一个数表示多项式的非零项个数，后面跟着非零项，第一个是阶数，第二个是系数。最后以相同的格式输出相加后的多项式，保留小数点后1位。
我是蠢蛋，杀鸡用了宰牛刀……
#include<bits/stdc++.h>
#define PID pair <int, double>
using namespace std;
const int N = 1100;
vector <PID> ans;
int ka, kb, a, mx = 0, mn = N;
double c1[N], c2[N], b;
bool cmp (PID x, PID y) {
return x.first > y.first;
}
int main()
{
cin >> ka;
for (int i = 0;i < ka;i ++) {
cin >> a >> b;
c1[a] = b;
mn = min (a, mn), mx = max (a, mx);
}
cin >> kb;
for (int i = 0;i < kb;i ++) {
cin >> a >> b;
c2[a] = b;
mn = min (a, mn), mx = max (a, mx);
}
for (int i = mn;i <= mx;i ++)
if (c1[i] + c2[i] != 0) ans.push_back ({i, c1[i] + c2[i]});
sort (ans.begin (), ans.end (), cmp);
cout << ans.size();
for (int i = 0;i < ans.size();i ++)
printf (" %d %.1lf", ans[i].first, ans[i].second);
return 0;
}
我的代码：
#include<bits/stdc++.h>
#define PID pair <int, double>
using namespace std;
int ka, kb, e;
double c;
vector <PID> ita, itb, ans;
bool cmp (PID a, PID b) {
return a.first > b.first;
}
int main()
{
cin >> ka;
for (int i = 0;i < ka;i ++) cin >> e >> c, ita.push_back ({e, c});
cin >> kb;
for (int i = 0;i < kb;i ++) cin >> e >> c, itb.push_back ({e, c});
sort (ita.begin (), ita.end (), cmp);
sort (itb.begin (), itb.end (), cmp);
for (int i = 0, j = 0;i < ka;i ++) {
while (j < kb && itb[j].first > ita[i].first) ans.push_back (itb[j]), j ++;
if (j < kb && itb[j].first == ita[i].first) {
if (itb[j].second != -ita[i].second)
ans.push_back ({ita[i].first, ita[i].second + itb[j].second});
j ++;
} else {
ans.push_back (ita[i]);
}
while (i == ka-1 && j < kb) {
ans.push_back (itb[j]);
j ++;
}
}
cout << ans.size();
for (int i = 0;i < ans.size(); i++)
printf (" %d %.1lf", ans[i].first, ans[i].second);
return 0;
}
1003 Emergency (25 分)
题目大意：每个点存在一定的人数，每条边存在长度，问从s到t最短路个数，在保证路径最短的基础上能遇到最多多少个人。
写了三遍都没AC，看了柳神的发现小错误（注释部分），这里错过第二回了这是。
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m, s, t;
int a, b, c, ans;
int e[N][N];
int g[N]; // i点处的人数
int h[N]; // s到i最多聚集的人数
int st[N]; // 是否以i节点松弛过
int d[N]; // s到i的最短距离
int p[N]; // s到i最短路径的个数
void Dijkstra () {
memset (d, 0x3f, sizeof d);
d[s] = 0;
p[s] = 1;
h[s] = g[s];
int T = n;
while (-- T) {
int k = -1;
for (int i = 0;i < n;i ++)
if (!st[i] && (k == -1 || d[i] < d[k]))
k = i;
st[k] = 1;
for (int i = 0;i < n;i ++) {
if (!st[i] && e[k][i]) {
if (d[i] > d[k] + e[k][i]) {
d[i] = d[k] + e[k][i];
h[i] = h[k] + g[i];
p[i] = p[k]; // ！ 不是设置为1
} else if (d[i] == d[k] + e[k][i]) {
p[i] += p[k]; // ！ 不是等于 p[k] + 1
h[i] = max (h[i], h[k] + g[i]);
}
}
}
}
}
int main()
{
cin >> n >> m >> s >> t;
for (int i = 0;i < n;i ++) cin >> g[i];
while (m --) {
cin >> a >> b >> c;
e[a][b] = c;
e[b][a] = c;
}
Dijkstra ();
cout << p[t] << ' ' << h[t];
return 0;
}
1004 Counting Leaves (30 分)
题目大意：先输入节点个数n和下面要输入的行数m；每行先输入一个节点编号，再输入该节点的直接子节点数，再输入子节点编号。最后输出树的每一层的叶子节点数量。
#include<bits/stdc++.h>
using namespace std;
const int N = 500;
int n, m, root, maxdp;
int q[N], dp[N], ans[N], st[N];
vector <int> a[N];
void bfs () {
int tt = -1, hh = 0;
q[++ tt] = root;
dp[root] = 1;
while (tt >= hh) {
int t = q[hh ++];
maxdp = max (dp[t], maxdp);
for (int i = 0;i < a[t].size();i ++) {
q[++ tt] = a[t][i];
dp[a[t][i]] = dp[t] + 1;
}
}
}
int main()
{
cin >> n >> m;
while (m --) {
int id, k, child;
cin >> id >> k;
while (k --) cin >> child, a[id].push_back (child), st[child] = 1;
}
for (int i = 1;i <= n;i ++) if (!st[i]) root = i;
bfs ();
for (int i = 1;i <= n;i ++)
if (!a[i].size())
ans[dp[i]] ++;
int flag = 0;
for (int i = 1;i <= maxdp;i ++) {
if (flag) cout << ' ';
flag = 1;
cout << ans[i];
}
return 0;
}
1005 Spell It Right (20 分)
题目大意：将输入的数的每一位加起来，得到和后从高位到低位输出和的每一位对应的英语单词。
坑点：和为0，要输出zero。
#include<bits/stdc++.h>
using namespace std;
string mp[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
int sum;
string s;
vector <string> ans;
int main()
{
cin >> s;
for (int i = 0;i < s.size();i ++)
sum += s[i] - '0';
while (sum) {
ans.push_back (mp[sum % 10]);
sum /= 10;
}
reverse (ans.begin (), ans.end ());
if (ans.size()) {
cout << ans[0];
for (int i = 1;i < ans.size();i ++)
cout << ' ' << ans[i];
} else {
cout << "zero"; // 一个测试点
}
return 0;
}
1006 Sign In and Sign Out (25 分)
题目大意：输入n表示人数，每个人输入编号、进入时间、出去时间，问哪个人最先进入，哪个人最后出去。
#include<bits/stdc++.h>
using namespace std;
int n;
string id;
int hi, mi, si, ho, mo, so;
struct Time {
string a;
int b, c, d;
bool operator > (const Time& t) {
if (b != t.b) return b > t.b;
if (c != t.c) return c > t.c;
return d > t.d;
}
};
Time first = {"", 100, 100, 100};
Time last = {"", -1, -1, -1};
int main()
{
cin >> n;
while (n --) {
cin >> id;
scanf ("%d:%d:%d", &hi, &mi, &si);
scanf ("%d:%d:%d", &ho, &mo, &so);
Time tin = {id, hi, mi, si};
if (first > tin) first = tin;
Time tout = {id, ho, mo, so};
if (tout > last) last = tout;
}
cout << first.a << ' ' << last.a << endl;
return 0;
}
1007 Maximum Subsequence Sum (25 分)
最大子串和，同时记录子串起点即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, mx = -1;
int a[N], f[N], s[N];
int main()
{
cin >> n;
for (int i = 1;i <= n;i ++) cin >> a[i];
for (int i = 1;i <= n;i ++) {
f[i] = a[i];
s[i] = i;
if (f[i-1] > 0) f[i] += f[i-1], s[i] = s[i-1]; // 严格大于0才更新
mx = max (f[i], mx);
}
if (mx < 0) cout << 0 << ' ' << a[1] << ' ' << a[n] << endl;
else {
cout << mx << ' ';
int i;
for (i = 1;i <= n;i ++) if (f[i] == mx) break;
cout << a[s[i]] << ' ' << a[i] << endl;
}
return 0;
}
1008 Elevator (20 分)
题目大意：输入n，再输入n个数，表示每次要到哪个楼层接人，电梯开始在0层，每上升一层花费6，每下降一层花费4，假如某层有人，电梯会停5，电梯按照输入顺序接人，问最终花费。
我开始根本没读懂题，连样例的答案都算不出来，表述太垃圾了（或者我英语太垃圾），以为再考个电梯算法啥的，结果这电梯神了，随意改变运动方向！
#include<bits/stdc++.h>
using namespace std;
#define STOP 5
#define DOWN 4
#define UP 6
int main()
{
int n, x, level = 0, ans = 0;
cin >> n;
for (int i = 0;i < n;i ++) {
cin >> x;
ans += STOP + abs (level - x) * (level > x ? DOWN : UP);
level = x;
}
cout << ans << endl;
return 0;
}
1009 Product of Polynomials (25 分)
#include<bits/stdc++.h>
#define PID pair <int, double>
using namespace std;
const int N = 1e6+10;
const double eps = 0.01;
vector <PID> ans;
int na, nb, ea[N], eb[N], st[N];
double cb[N], ca[N], ce[N];
int main()
{
cin >> na;
for (int i = 0;i < na;i ++) cin >> ea[i] >> ca[i];
cin >> nb;
for (int i = 0;i < nb;i ++) cin >> eb[i] >> cb[i];
for (int i = 0;i < na;i ++)
for (int j = 0;j < nb;j ++) {
int e = ea[i] + eb[j];
double c = ca[i] * cb[j];
ce[e] += c;
st[e] = 1;
}
for (int i = N-1;i >= 0;i --)
if (st[i] && fabs (ce[i] - 0) > eps)
ans.push_back ({i, ce[i]}); // 注意系数为0时不要输出，一个测试点
cout << ans.size ();
for (int i = 0;i < ans.size();i ++) printf (" %d %.1lf", ans[i].first, ans[i].second);
return 0;
}
1010 Radix (25 分)
题解链接
1011 World Cup Betting (20 分)
#include<bits/stdc++.h>
using namespace std;
double getmax (double a, double b, double c) {
if (a > b && a > c) return cout << "W ", a;
if (b > a && b > c) return cout << "T ", b;
if (c > a && c > b) return cout << "L ", c;
}
int main()
{
double a, b, c, x, y, z, i, j, k;
cin >> a >> b >> c;
cin >> x >> y >> z;
cin >> i >> j >> k;
printf ("%.2lf", (getmax (a, b, c) * getmax (x, y, z) * getmax (i, j, k) * 0.65 - 1) * 2.0);
return 0;
}
1012 The Best Rank (25 分)
题解链接
1013 Battle Over Cities (25 分)
题解链接
1014 Waiting in Line (30 分)
要模拟赛了，赶紧刷几道题。
#include<bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
const int N = 25, M = 1e3+10;
void convert_time (int x) {
printf ("%02d:%02d\n", 8+x/60, x%60);
return ;
}
queue<PII> que[N];
int sum[N], serve_time[M], a[M];
int main()
{
int n, m, k, q;
cin >> n >> m >> k >> q;
for (int i = 0;i < k;i ++) cin >> a[i];
for (int i = 0;i < n*m && i < k;i ++) que[i%n].push({i, a[i]});
int kk = n*m;
while (1) {
int t = -1;
for (int i = 0;i < n;i ++)
if (que[i].size() && (t == -1 || que[i].front().second < que[t].front().second))
t = i;
if (t == -1) break; // 没有一个人了
int com = que[t].front().second;
for (int i = 0;i < n;i ++)
if (que[i].size())
que[i].front().second -= com;
if (sum[t] >= 540) serve_time[que[t].front().first] = -1;
else sum[t] += a[que[t].front().first], serve_time[que[t].front().first] = sum[t];
que[t].pop ();
if (kk < k) que[t].push ({kk, a[kk]}), kk ++;
}
while (q --) {
int t;
cin >> t;
t --;
if (serve_time[t] == -1) puts("Sorry");
else convert_time(serve_time[t]);
}
return 0;
}
1015 Reversible Primes (20 分)
没读懂。。。
给出一个正整数N和D，如果N是素数且N的D进制，逆序，再转回十进制也是素数，那么就输出Yes 否则No
#include<bits/stdc++.h>
using namespace std;
bool isprime (int x) {
if (x <= 1) return false;
for (int i = 2;i <= x/i;i ++)
if (x % i == 0) return false;
return true;
}
int main()
{
int n, d;
while (1) {
cin >> n;
if (n < 0) break;
else cin >> d;
if (!isprime(n)) {
puts("No");
continue;
}
int a[100], cnt = 0, res = 0, base = 1;
while (n) {
a[cnt ++] = n % d;
n /= d;
}
for (int i = cnt-1;i >= 0;i --, base *= d)
res += a[i] * base;
if (isprime(res)) puts("Yes");
else puts("No");
}
return 0;
}
1019 General Palindromic Number (20 分)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
LL a[N];
int cnt;
bool check () {
for (int i = 0;i < cnt;i ++)
if (a[i] != a[cnt-1-i]) return false;
return true;
}
int main()
{
LL n, b;
cin >> n >> b;
LL m = n;
while (m) {
a[cnt ++] = m % b;
m /= b;
}
if (check ()) puts ("Yes");
else puts ("No");
for (int i = cnt-1, flag = 0;i >= 0;i --) {
if (flag) cout << ' ';
flag = 1;
cout << a[i];
}
return 0;
}
1020 Tree Traversals (25 分)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N], b[N], t[N];
void build (int x, int l1, int r1, int l2, int r2) {
if (l1 <= r1) t[x] = a[r1];
if (l1 >= r1) return ;
int p = l2;
while (p <= r2) {
if (b[p] == t[x]) break;
p ++;
}
int ln = p - l2;
build (x << 1, l1, l1 + ln - 1, l2, p-1);
build (x << 1 | 1, l1 + ln, r1-1, p+1, r2);
}
int main()
{
int n;
cin >> n;
for (int i = 0;i < n;i ++) cin >> a[i];
for (int i = 0;i < n;i ++) cin >> b[i];
build (1, 0, n-1, 0, n-1);
int flag = 0;
for (int i = 0;n;i ++) {
if (t[i]) {
if (flag) cout << ' ';
flag = 1;
cout << t[i];
n --;
}
}
return 0;
}
1021 Deepest Root (25 分)
并查集+dfs
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10, M = 1e5+10;
int n, maxdp, maxv, ans;
int e[M], ne[M], h[N], idx;
int st[N], fa[N];
vector<int> v;
void add (int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs (int x, int dp) {
maxdp = max (maxdp, dp);
for (int i = h[x];~i;i = ne[i]) {
int j = e[i];
if (st[j]) continue;
st[j] = 1;
dfs (j, dp+1);
}
}
int find (int x) {
return fa[x] == x ? x : fa[x] = find (fa[x]);
}
void join (int x, int y) {
int rx = find (x), ry = find (y);
if (rx != ry) fa[rx] = ry;
}
int main()
{
memset (h, -1, sizeof h);
cin >> n;
for (int i = 1;i <= n;i ++) fa[i] = i;
for (int i = 1;i < n;i ++) {
int a, b;
cin >> a >> b;
add (a, b);
add (b, a);
join (a, b);
}
for (int i = 1;i <= n;i ++)
ans += (fa[i] == i);
if (ans == 1) {
for (int i = 1;i <= n;i ++) {
maxdp = 0;
memset (st, 0, sizeof st);
st[i] = 1;
dfs (i, 1);
if (maxdp >= maxv) {
if (maxdp > maxv) v.clear ();
v.push_back (i);
maxv = maxdp;
}
}
for (int i = 0;i < v.size(); i++) cout << v[i] << endl;
} else printf ("Error: %d components", ans);
return 0;
}
1022 Digital Library (30 分)
#include<bits/stdc++.h>
using namespace std;
int n, T;
string s;
map <string, set <string> > mp[6];
int main()
{
cin >> n;
for (int i = 0;i < n;i ++) {
string id;
cin >> id; getchar ();
for (int j = 1;j <= 5;j ++) {
getline (cin, s);
if (j != 3) mp[j][s].insert(id);
else {
string tmp = "";
for (int k = 0;k < s.size();k ++) {
if (s[k] == ' ') mp[j][tmp].insert (id), tmp = "";
else tmp += s[k];
}
if (tmp != "") mp[j][tmp].insert (id);
}
}
}
cin >> T;getchar ();
while (T --) {
getline (cin, s);
cout << s << endl;
string op = s.substr (0, s.find(':'));
string str = s.substr (s.find(' ')+1);
int flag = 0;
for (auto item : mp[atoi(op.c_str())][str])
flag = 1, cout << item << endl;
if (!flag) puts ("Not Found");
}
return 0;
}
1023 Have Fun with Numbers (20 分)
#include<bits/stdc++.h>
using namespace std;
int num[10], cnt[10];
string x, y;
string mul (string s) {
string res = "";
reverse (s.begin (), s.end ());
int n = s.size();
vector <int> c(n+20);
for (int i = 0;i < n;i ++) {
c[i] += (s[i] - '0') * 2;
c[i+1] += c[i] / 10;
c[i] %= 10;
}
while (c[n]) c[n+1] += c[n]/10, c[n] %= 10, n ++;
for (int i = n-1;i >= 0;i --) res += c[i] + '0';
return res == "" ? "0" : res;
}
int main()
{
cin >> x;
string y = mul (x);
for (int i = 0;i < x.size();i ++)
cnt[x[i] - '0'] ++;
for (int i = 0;i < y.size();i ++)
num[y[i] - '0'] ++;
for (int i = 0;i < 9;i ++)
if (cnt[i] != num[i])
return cout << "No" << endl << y << endl, 0;
cout << "Yes" << endl << y << endl;
return 0;
}
1024 Palindromic Number (25 分)
高精度，好像long long 也不行
#include<bits/stdc++.h>
using namespace std;
string s, ans1;
int k, ans2;
bool check (string s) {
int l = 0, r = s.size()-1;
while (l < r) {
if (s[l] != s[r]) return false;
l ++, r --;
}
return true;
}
string add (string s) {
string res = "";
int n = s.size();
vector <int> c(n+1);
for (int i = 0;i < n;i ++) {
c[i] += (s[i] - '0') + (s[n-i-1] - '0');
c[i+1] += c[i] / 10;
c[i] %= 10;
}
if (c[n]) n ++;
for (int i = n-1;i >= 0;i --) res += c[i] + '0';
return res == "" ? "0" : res;
}
int main()
{
cin >> s >> k;
ans1 = s, ans2 = k;
for (int i = 0;i < k;i ++ ) {
if (check (s)) {
ans2 = i;
break;
}
s = add (s);
ans1 = s;
}
cout << ans1 << endl << ans2 << endl;
return 0;
}
1025 PAT Ranking (25 分)
题目大意：有N个测试点，每个测试点有k个学生的注册号和成绩，请你输出所有学生的总排名和所在测试点以及在在该测试点的排名。
要求对每组学生内部排序后再总体排序。主要考察结构体和排序。
因为一个测试点的学生是连续输入的，因此可以直接对连续的一段排序，无需另设数据结构保存了。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e4+10;
struct node {
string name;
int tp;
int s;
} stu[N];
map<string, int> all_rank, test_rank;
bool cmp1 (node a, node b) {
if (a.s != b.s) return a.s > b.s;
return a.name < b.name;
}
int n, k, cnt;
int main()
{
cin >> n;
for (int i = 0;i < n;i ++) {
cin >> k;
for (int j = 0;j < k;j ++) {
cin >> stu[cnt].name >> stu[cnt].s;
stu[cnt].tp = i+1;
cnt ++;
}
sort (stu+cnt-k, stu+cnt, cmp1);
test_rank[stu[cnt-k].name] = 1;
for (int i = cnt-k+1, rk = 2;i < cnt;i ++, rk ++)
if (stu[i].s == stu[i-1].s) test_rank[stu[i].name] = test_rank[stu[i-1].name];
else test_rank[stu[i].name] = rk;
}
sort (stu, stu+cnt, cmp1);
all_rank[stu[0].name] = 1;
for (int i = 1;i < cnt;i ++)
if (stu[i].s == stu[i-1].s) all_rank[stu[i].name] = all_rank[stu[i-1].name];
else all_rank[stu[i].name] = i+1;
cout << cnt << endl;
for (int i = 0;i < cnt;i ++) {
cout << stu[i].name << ' ' << all_rank[stu[i].name] << ' ' << stu[i].tp << ' ' << test_rank[stu[i].name] << endl;
}
return 0;
}
1027 Colors in Mars (20 分)
#include<bits/stdc++.h>
using namespace std;
char mp (int x) {
if (x >= 10) return ('A' + x - 10);
return x + '0';
}
int main()
{
cout << "#";
for (int i = 0;i < 3;i ++) {
int x;
cin >> x;
string res = "";
while (x) {
res += mp (x % 13);
x /= 13;
}
reverse (res.begin (), res.end());
while (res.size() < 2) res = "0" + res;
cout << res;
}
return 0;
}
1028 List Sorting (25 分)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, op;
struct node {
int id;
string name;
int s;
} a[N];
bool cmp (node a, node b) {
if (op == 2) {
if (a.name != b.name) return a.name < b.name;
} else if (op == 3) {
if (a.s != b.s) return a.s < b.s;
}
return a.id < b.id;
}
int main()
{
cin >> n >> op;
for (int i = 0;i < n;i ++)
cin >> a[i].id >> a[i].name >> a[i].s;
sort (a, a+n, cmp);
for (int i = 0;i < n;i ++)
printf ("%06d", a[i].id),
cout << ' ' << a[i].name << ' ' << a[i].s << endl;
return 0;
}
1030 Travel Plan (30 分)
#include<bits/stdc++.h>
#define PII pair <int, int>
using namespace std;
const int N = 1e3+10;
int n, m, s, tar;
PII e[N][N];
int d[N], path[N], c[N], st[N];
void printpath (int x) {
if (x == s) {
printf ("%d", x);
return ;
}
printpath (path[x]);
printf (" %d", x);
}
void Dijkstra () {
memset (d, 0x3f, sizeof d);
memset (c, 0x3f, sizeof c);
memset (path, -1, sizeof path);
d[s] = 0;
path[s] = -1;
c[s] = 0;
int T = n;
while (T --) {
int t = -1;
for (int i = 0;i < n;i ++) {
if (!st[i] && (t == -1 || d[i] < d[t]))
t = i;
}
st[t] = 1;
for (int i = 0;i < n;i ++) {
if (!st[i] && e[t][i].first != 0) {
if (d[i] > d[t] + e[t][i].first || (d[i] == d[t] + e[t][i].first && c[i] > c[t] + e[t][i].second)) {
d[i] = d[t] + e[t][i].first;
c[i] = c[t] + e[t][i].second;
path[i] = t;
}
}
}
}
}
int main()
{
cin >> n >> m >> s >> tar;
while (m --) {
int a, b, dist, cost;
cin >> a >> b >> dist >> cost;
e[a][b] = e[b][a] = {dist, cost};
}
Dijkstra();
printpath (tar);
cout << ' ' << d[tar] << ' ' << c[tar] << endl;
return 0;
}
1031 Hello World for U (20 分)
n1=n3<=n2而且n1尽可能大
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
void print (int n2) {
int n1 = (n - n2 + 2) / 2;
for (int i = 0;i < n1-1;i ++) {
cout << s[i];
for (int j = 1;j <= n2-2;j ++) cout << ' ';
cout << s[n-1-i] << endl;
}
for (int i = 0;i < n2;i ++)
cout << s[i + n1-1];
}
int main()
{
cin >> s;
n = s.size();
for (int i = 3;i <= n;i ++)
if ((n-i) % 2 == 0 && i - (n-i+2)/2 >= 0)
return print (i), 0;
return 0;
}
1033 To Fill or Not to Fill (25 分)
题解链接
1034 Head of a Gang (30 分)
题解链接
1035 Password (20 分)
#include<bits/stdc++.h>
using namespace std;
#define PSS pair <string, string>
vector <PSS> v;
int n, flag;
string id, pas;
string change (string s) {
for (int i = 0;i < s.size();i ++)
if (s[i] == 'l') s[i] = 'L';
else if (s[i] == '1') s[i] = '@';
else if (s[i] == 'O') s[i] = 'o';
else if (s[i] == '0') s[i] = '%';
return s;
}
int main()
{
cin >> n;
for (int i = 0;i < n;i ++) {
cin >> id >> pas;
string after_pas = change (pas);
if (after_pas != pas)
v.push_back ({id, after_pas});
}
if (!v.size()) {
if (n == 1) printf ("There is 1 account and no account is modified");
else printf ("There are %d accounts and no account is modified", n);
} else {
cout << v.size() << endl;
for (int i = 0;i < v.size();i ++)
cout << v[i].first << ' ' << v[i].second << endl;
}
return 0;
}
1036 Boys vs Girls (25 分)
#include<bits/stdc++.h>
using namespace std;
string name, fname, mname;
string gender;
string id, fid, mid;
int n, score, fscore = -1, mscore = 101;
int main()
{
cin >> n;
for (int i = 0;i < n;i ++) {
cin >> name >> gender >> id >> score;
if (gender == "F") {
if (score > fscore) {
fscore = score;
fid = id;
fname = name;
}
} else {
if (score < mscore) {
mscore = score;
mid = id;
mname = name;
}
}
}
if (fname == "") puts("Absent");
else cout << fname << ' ' << fid << endl;
if (mname == "") puts("Absent");
else cout << mname << ' ' << mid << endl;
if (fname == "" || mname == "") cout << "NA";
else cout << fscore - mscore << endl;
return 0;
}
1037 Magic Coupon (25 分)
题目大意：nc个优惠券，np个商品。若用价格为a的优惠券购买价格为b的商品，则用户可以得到a * b的返现，求用户能够得到的最大返现额。每种商品最多可以购买一次，每种优惠券最多使用一次。
最初思路：正的尽可能匹配，负的尽可能匹配， 且绝对值大的相乘。
最终思路：a、b中负数的个数的最小值限制了匹配负数对答案的贡献，同理，a、b中正数的个数的最小值限制了匹配正数对答案的贡献。所以，负数的匹配数就是min(a中负数个数,b中负数个数)，正数同理，零不用管。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, m, ans;
int a[N], b[N];
int main()
{
cin >> n;
for (int i = 0;i < n;i ++) cin >> a[i];
cin >> m;
for (int i = 0;i < m;i ++) cin >> b[i];
sort (a, a+n);
sort (b, b+m);
for (int i = 0;i < n && i < m && a[i] < 0 && b[i] < 0;i ++)
ans += a[i] * b[i];
for (int i = 0;i < n && i < m && a[n-i-1] > 0 && b[m-i-1] > 0;i ++)
ans += a[n-i-1] * b[m-i-1];
cout << ans << endl;
return 0;
}
1038 Recover the Smallest Number (30 分)
题解链接
1039 Course List for Student (25 分)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, m, k, id;
string name;
map<string, set<int> > cou;
int main()
{
cin >> n >> k;
while (k --) {
cin >> id >> m;
while (m --) {
cin >> name;
cou[name].insert (id);
}
}
while (n --) {
cin >> name;
cout << name << ' ' << cou[name].size();
for (int item : cou[name]) cout << ' ' << item;
cout << endl;
}
return 0;
}
1040 Longest Symmetric String (25 分)
#include<bits/stdc++.h>
using namespace std;
string s;
bool ishw (string s) {
int n = s.size();
for (int i = 0;i < n/2;i ++)
if (s[i] != s[n-i-1]) return false;
return true;
}
int main()
{
getline(cin, s);
int n = s.size();
for (int len = n;len >= 1;len --)
for (int i = 0;i <= n - len;i ++)
if (ishw (s.substr (i, len))) return cout << len << endl, 0;
return 0;
}
1041 Be Unique (20 分)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int cnt[N], n, a[N];
int main()
{
cin >> n;
for (int i = 0;i < n;i ++) {
cin >> a[i];
cnt[a[i]] ++;
}
for (int i = 0;i < n;i ++) {
if (cnt[a[i]] == 1) return cout << a[i] << endl, 0;
}
cout << "None" << endl;
return 0;
}
1042 Shuffling Machine (20 分)
这道题的意思居然是按照给定的全排列进行排列，不是插入操作。
#include<iostream>
#include<string>
using namespace std;
int main()
{
string start[55] = { "","S1","S2","S3","S4","S5","S6","S7","S8","S9","S10","S11","S12","S13","H1","H2","H3","H4","H5","H6","H7","H8","H9","H10","H11","H12","H13","C1","C2","C3","C4","C5","C6","C7","C8","C9","C10","C11","C12","C13","D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","D13","J1","J2" };
int next[55];
string end[55];
int n;
cin >> n;
for (int i = 1; i <= 54; i++) cin >> next[i];//输入牌操作后的位置
for (int i = 0; i < n; i++)
{
for (int j = 1; j < 55; j++) end[next[j]] = start[j];//将第j个牌放到位置next[j]上
for (int j = 1; j < 55; j++) start[j] = end[j];//更新，以便下一次洗牌。
}
cout << end[1];
for (int i = 2; i < 55; i++) cout << " " << end[i];
return 0;
}
1043 Is It a Binary Search Tree (25 分)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, a[N];
vector <int> v;
bool check (int l, int r, int m) {
if (l >= r) {
if (l == r) v.push_back (a[l]);
return true;
}
int rt = a[l];
int i = l+1;
while (i <= r) {
if ((a[i] >= rt) ^ m) break;
i ++;
}
int p = i-1;
while (i <= r) {
if ((a[i] < rt) ^ m) return false;
i ++;
}
bool res = check (l+1, p, m);
res &= check (p+1, r, m);
v.push_back (rt);
return res;
}
int main()
{
cin >> n;
for (int i = 0;i < n;i ++) cin >> a[i];
if (check (0, n-1, 0)) {
puts ("YES");
for (int i = 0, flag = 0;i < v.size();i ++) {
if (flag) cout << ' ';
flag = 1;
cout << v[i];
}
return 0;
}
v.clear ();
if (check (0, n-1, 1)){
puts ("YES");
for (int i = 0, flag = 0;i < v.size();i ++) {
if (flag) cout << ' ';
flag = 1;
cout << v[i];
}
} else puts ("NO");
return 0;
}
1044 Shopping in Mars (25 分)
题解链接
1045 Favorite Color Stripe (30 分)
记录每个数的位置，将第三行中的数换成它们的位置后计算最长不下降子序列长度。
好像这个题不用考虑第二行中出现重复数字的情况。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, x, k, cnt, ans, b[N], a[N], f[N];
int main()
{
cin >> n;
cin >> k;
for (int i = 1;i <= k;i ++) cin >> x, b[x] = i;
cin >> k;
for (int i = 0;i < k;i ++) {
cin >> x;
if (!b[x]) continue;
a[cnt ++] = b[x];
}
for (int i = 0;i < cnt;i ++) {
f[i] = 1;
for (int j = 0;j < i;j ++)
if (a[i] >= a[j])
f[i] = max (f[i], f[j] + 1);
ans = max (ans, f[i]);
}
cout << ans << endl;
return 0;
}
1046 Shortest Distance (20 分)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, m, a[N], sum, x, y;
int main()
{
cin >> n;
for (int i = 1;i <= n;i ++) cin >> x, a[i+1] = a[i] + x, sum += x;
cin >> m;
while (m--) {
cin >> x >> y;
if (x < y) swap (x, y);
cout << min (a[x] - a[y], sum - (a[x] - a[y])) << endl;
}
return 0;
}
1047 Student List for Course (25 分)
乖乖用vector吧，map、set不是超时就是错误。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e3+10;
int n, k, c, cc;
vector<string> course [N];
string name;
int main()
{
cin >> n >> k;
for (int i = 0;i < n;i ++) {
cin >> name;
scanf ("%d", &c);
for (int j = 0;j < c;j ++) {
scanf ("%d", &cc);
course[cc].push_back (name);
}
}
for (int i = 1;i <= k;i ++) {
printf ("%d %d\n", i, course[i].size());
sort (course[i].begin(), course[i].end());
for (string name : course[i])
printf ("%s\n", name.c_str());
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, pay, a[N];
int main()
{
cin >> n >> pay;
for (int i = 0;i < n;i ++) cin >> a[i];
sort (a, a+n);
for (int i = 0;i < n;i ++) {
int p = lower_bound (a+i+1, a+n, pay - a[i]) - a;
if (p < n && a[p] + a[i] == pay) return cout << a[i] << ' ' << a[p] << endl, 0;
}
cout << "No Solution" << endl;
return 0;
}
1049 Counting Ones (30 分)
题解链接
1050 String Subtraction (20 分)
#include<bits/stdc++.h>
using namespace std;
string s1, s2;
int st[10000];
int main()
{
getline (cin , s1);
getline (cin , s2);
for (int i = 0;i < s2.size();i ++)
st[s2[i]] = 1;
for (int i = 0;i < s1.size();i ++)
if (st[s1[i]]) continue;
else cout << s1[i];
return 0;
}
