A. 比大小
思路：直接比较大小关系，模拟题意输出
#include <iostream>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
if (a > b)
cout << '>' << endl;
if (a < b)
cout << '<' << endl;
if (a == b)
cout << '=' << endl;
return 0;
}B. 不满的大臣
思路：可以证明，找k个大臣一定比找k+1个大臣最优，因为每次只能最先见一个人，如果找k+1个大臣，会比找k个大臣使得重复第一个面见同一个人的概率增加。以此类推，每次找一个大臣是最优的方案，那么只需要每次都找一个还没满意的大臣使他满意即可，答案为大臣数量
#include <iostream>
using namespace std;
int main()
{
long n;
cin >> n;
cout << n << endl;
return 0;
}C. 众字母
思路：读取字符串时，不能使用cin，因为cin无法读入空格，要使用getline，在处理字符串的时候用一个字符型变量存储答案。
#include <bits/stdc++.h>
using namespace std;
string s;
map <char, int> mp;
int main()
{
getline(cin, s);
int ans = 0;
char c;
for (int i = 0; i < s.size(); i++)
{
if ((s[i] < 'a' || s[i]>'z') && (s[i] < 'A' || s[i]>'Z')) continue;
mp[s[i]]++;
if (mp[s[i]] > ans)
{
ans = mp[s[i]];
c = s[i];
}
else if (mp[s[i]] == ans && s[i] < c)
{
c = s[i];
}
}
printf("%c", c);
}D. 好数
思路：本题方法与新生训练题2中的水仙花数方法基本一致，用到了枚举法，然后再按题意处理即可。
#include <iostream>
using namespace std;
int main()
{
int t, l, r, ans;
cin >> t;
while (t--)
{
cin >> l >> r;
ans = 0;
for (int i = l; i <= r; i++)
{
if ((i / 100) * (i / 10) % 10 == i % 10)
ans++;
}
cout << ans << endl;
}
return 0;
}E. 完美数
思路：本题用到了贪心算法，易知需要找最大的数位和最小的数位，判断是否能够用若干个完美数得到答案，如果可以，用最大的数位除以2就是答案（向上取整）
补充：为了简化本题，n的范围上限只设置了1e18，算法能够解决的数据范围远远大于此。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
int main()
{
ios::sync_with_stdio(false);
cin >> s;
int maxx = -1;
int minn = 11;
for (int i = 0; i < s.size(); i++)
{
maxx = max(maxx, s[i] - '0');
minn = min(minn, s[i] - '0');
}
if (minn * 2 < maxx)
{
cout << -1 << endl;
return 0;
}
int ans = maxx / 2;
if (maxx & 1) ans++;
cout << ans << endl;
}
F. 劳累的造物主
思路：假如第一个地盘净出生人数大于0，那么它一定通过2-n转世过来，无论通过那边转世过来，一定会经过2，那么就等价于是2转世过来的，再给2地盘的数量减去第一个地盘的净出生人数即可，以此类推扩展到其他地盘。若第一个地盘净死亡人数大于0，也可以用同样的方法得到同样的结论。
#include <iostream>
using namespace std;
#define ll long long
int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
if (n == 0) break;
ll ans = 0;
ll last = 0;
for (int i = 1; i <= n; i++)
{
ll tmp;
scanf("%lld", &tmp);
ans += abs(last);
last += tmp;
}
printf("%lld\n", ans);
}
}G. 游戏
思路：我们先来看看最后一步，假设最后一步是Bob操作，那么无论剩下两个数的奇偶性如何，他都可以把数变成偶数，这对应了初始奇数个数字的情况。换句话说，当n为奇数时，Bob必胜（n=1要根据唯一的数字的奇偶性特判）。否则，最后一步是Alice操作，除了两个数字都是偶数的情况，Alice都能把最后的结果变成奇数。那我们在意的是每时每刻剩下多少个偶数，Alice每次操作最多可以消灭一个偶数，Bob每次操作最多可以生成一个偶数。所以如果初始的偶数数目至少有两个，那么Alice是赢不了的（无论什么时候Alice消灭偶数，如果此时有两个奇数，bob都能生成一个偶数。如果alice消灭偶数后仅剩1个或0个奇数，bob可以转而消灭那个奇数，这样所有的数字都是偶数了。）。当初始偶数小于2个时，Alice必胜（Bob没办法让最后的偶数个数达到2个）。
标程：
#include <iostream>
#include <cstdio>
#include <set>
#include <string.h>
#include <algorithm>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <queue>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int ji = 0, ou = 0;
for (int i = 1; i <= n; i++)
{
int tmp;
scanf("%d", &tmp);
if (tmp & 1) ji++;
else ou++;
}
if (ji == 2 && ou == 0) { printf("0\n"); }
else if ((ou >= 2) || (ou == 1 && ji % 2 == 0) || (ou == 0 && (ji != 1 && (ji & 1))))
{
printf("1\n");
}
else printf("0\n");
}优秀选手代码：
#include<iostream>
#include<cstdio>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n, s, a, b;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &s);
if (s & 1) ++a;
else ++b;
}
if (n == 1) {
if (a) printf("0");
else printf("1");
return 0;
}
if (n & 1) {
printf("1");
return 0;
}
for (int i = 1; i < (n - 1); i += 2) {
if (b) --b;
else --a;
a -= 2, ++b;
}
if (a > 0) printf("0");
else printf("1");
return 0;
}H. 诸侯鼎立
思路：枚举+搜索回溯
#include <bits/stdc++.h>
using namespace std;
int n;
int a[65];
bool vis[65];
int sum = 0;//记录士兵的能力值
//枚举可能的答案，如果sum%i==0答案才有可能正确，否则直接跳过
//并且答案一定比最大的士兵能力值要大
void init()
{
memset(a, 0, sizeof(a));
memset(vis, 0, sizeof(vis));
sum = 0;
}
bool cmp(int x, int y)
{
return x > y;
}
bool dfs(int k, int step, int len, int rest)//k为已经分配好的士兵数量，len为诸侯能力值，rest为剩余待招募士兵能力值
{
if (k - 1 == n && rest == 0) return true;//士兵用完，并且诸侯能力值达到
else if (rest == 0)//诸侯能力值达到了，士兵还没用完
{
rest = len;//找一个新的士兵来招募
step = 0;
}
else if (k - 1 == n)//士兵用完了，诸侯的能力值不符合要求，说明这个答案是错误的，没法拼凑好诸侯的能力
return false;
for (int i = step + 1; i <= n; i++)
{
if (!vis[i] && a[i] <= rest)//如果士兵没用过并且用上这个士兵以后不会使整个木棒长度大于len
{
vis[i] = true;
if (dfs(k + 1, i, len, rest - a[i])) return true;
vis[i] = false;
if (len == rest || a[i] == rest) //头尾剪枝
break;
while (a[i] == a[i + 1]) i++;//换用的新士兵一定不能跟之前淘汰的士兵一样
}
}
return false;//如果枚举完以后都没有拼接成功，说明失败了
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
init();
scanf("%d", &n);
for (int i = 1; i <= n;)
{
scanf("%d", &a[i]);
sum += a[i]; i++;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = a[1]; i <= sum; i++)//由于要求的是最小诸侯能力值，所以从最小可能答案一直枚举到最大可能答案
{
if (sum % i != 0) continue;
if (dfs(1, 0, i, i))//dfs检验这个答案是否正确，接下来完成dfs函数的编写
//如果正确，直接输出这个答案并且跳出循环
{
printf("%d\n", i);
break;
}
}
}
}I. 温馨的集训队
思路：最小生成树+按题意模拟即可
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int a[10010];
struct ty
{
int s, t, l;
}edge[100010];
int n, p;
int fa[10010];
bool comp(ty a, ty b)
{
return a.l < b.l;
}
int findfa(int x)
{
return fa[x] == x ? x : fa[x] = findfa(fa[x]);
}
void merge(int x, int y)
{
int fx = findfa(x);
int fy = findfa(y);
fa[fx] = fa[fy];
}
int kruskal()
{
for (int i = 1; i <= n; i++)
fa[i] = i;
sort(edge + 1, edge + 1 + p, comp);
int sum = 0, cnt = 0;
for (int i = 1; i <= p; i++)
{
int x = edge[i].s, y = edge[i].t;
if (findfa(x) != findfa(y))
{
merge(x, y);
sum += edge[i].l;
cnt++;
}
if (cnt >= n - 1) break;
}
return sum;
}
int main()
{
while (scanf("%d%d", &n, &p) != EOF && n != 0 && p != 0)
{
int minn = 0x7f7f7f7f;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
minn = min(a[i], minn);
}
for (int i = 1; i <= p; i++)
{
scanf("%d%d%d", &edge[i].s, &edge[i].t, &edge[i].l);
edge[i].l = edge[i].l * 2 + a[edge[i].s] + a[edge[i].t];
}
printf("%d\n", kruskal() + minn);
}
return 0;
}
京公网安备 11010502036488号