【题解】西南民族大学第十一届程序设计竞赛（同步赛）
A、川川教练的困惑
若要找到三个能力值之和大于m，并且最大使得能力值之和最大，可以直接找到能力值最大的三者，求和后再和m比较是否满足条件即可。
#include<cstdio>
#include<algorithm>
using namespace std;
int a[10];
int main() {
int n, m, x;
// freopen("7.in", "r", stdin);
// freopen("7.out", "w", stdout);
scanf("%d %d", &n, &m);
for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
sort(a, a + n);
x = a[n - 1] + a[n - 2] + a[n - 3];
if(x > m) printf("%d\n", x);
else printf("Waiver!\n");
return 0;
}
B、都说小镇的切糕贵
题意：
给一个长度为n（1 ≤ n ≤ 100 000）的字符串，它由英文字母表中的大写字母和小写字母组成，让我找到字符串中包含所有出现过的字符区间，要使得这个区间长度最短。
思路：
首先让我们找出所有不同的字母，它们存在于给定的字符串中。我们首先遍历字符串找到所有不同的字符数量，利用map和尺取维护这个数量，然后更新答案即可。
代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<string>
#include<climits>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int maxn = 1e5 + 5;
map<char, int> mp;
int main(){
int n;
char s[maxn];
while(~scanf("%d", &n)){
mp.clear();
scanf("%s", s + 1);
for(int i = 1; i <= n; i++){
mp[s[i]]++;
}
int num = mp.size();
int ans = n;
int l = 1, r = 1;
int now = num;
mp.clear();
while(mp.size() != num){
mp[s[r]]++;
r++;
}
r--;
while(l <= n - num + 1 && r <= n){
if(now == num){
ans = min(ans, r - l + 1);
mp[s[l]]--;
if(mp[s[l]] == 0) now--;
l++;
}
if(now < num){
r++;
if(mp[s[r]] == 0) now++;
mp[s[r]]++;
}
}
printf("%d\n", ans);
}
}
C、Guard the empire
题意：
给出n头骨龙的坐标（只会在第一、第二象限），在X轴上放置武器，每个武器都有相同的固定打击范围D，问最少需要多少武器可以将所有骨龙覆盖，如果不能覆盖所有骨龙则输出-1.
思路：
贪心。要求武器的打击范围能够覆盖所有骨龙，若可以覆盖，则以每头骨龙的坐标为圆心，以D为半径，必定与X轴相交与2个可以重合的点。将武器放置在两点间的任意一处都可以覆盖到此骨龙，因此计算出所有骨龙与X轴相交的两个点，按照左端点（或右端点）排序，遍历所有骨龙，判断最右边的武器是否能够覆盖当前遍历到的骨龙，如果不能覆盖，则添置一个新武器于当前骨龙与X轴交点的最右端。
标程：
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#define l first
#define r second
#define Pff pair<float, float>
using namespace std;
const int maxn = 1e3 + 5;
int n;
float d;
Pff P[maxn];
int ans;
inline void cal(int &x, int &y, int &i){
P[i].l = (float)x - sqrt(d * d - y * y);
P[i].r = (float)x + sqrt(d * d - y * y);
}
inline void work(){
sort(P + 1, P + 1 + n);
float now = P[1].r;
ans = 1;
for(int i = 2; i <= n; ++i){
if(P[i].l > now){
++ans;
now = P[i].r;
}
else{
if(P[i].r < now) now = P[i].r;
}
}
printf("%d\n", ans);
}
int main(){
int cast = 1;
while(~scanf("%d %f", &n, &d) && n && d){
bool flag = 0;
int x, y;
for(int i = 1; i <= n; ++i){
scanf(" %d %d", &x, &y);
if(d < y|| flag) {
flag = 1;
continue;
}
cal(x, y, i);
}
printf("Case %d: ", cast++);
if(flag) printf("-1\n");
else work();
}
return 0;
}
D、kth的自拍照
简简单单的矩阵旋转.
自己写一个3*3 或者4*4的矩阵旋转一下就可以发现规律了
int main(){
int n;scanf("%d",&n);
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
scanf("%d",&a[i][j]);
}
}
for(int i = 1 ; i <= n ; i++){
for(int j = n ; j >= 1 ; j--){
printf("%d ",a[j][i]);
}
printf("\n");
}
}
//(1,1) -> (1,n)
//(1,n) -> (n,n)
//(n,n) -> (n,1)
//(n,1) -> (1,1)
E、HJ又种花啦
签到题，很容易想到 k >= 2 任何时候都是满足的，只需要特判一种情况：n = 1 && m = 1的时候，k=1也满足情况。
#include<iostream>
using namespace std;
int main()
{
int n, m, k; cin >> n >> m >> k;
if(n + m == 2 || k >= 2) cout << "Beautiful flowers!" << endl;
else cout << "Oh! My poor HJ!" << endl;
return 0;
}
F、Incompetent Fury of a Single Dog
根据题意，每个字母只能出现一次，所以处理后的文件长度不会超过26。那么只需要记录每个字母第一次出现的位置，再根据出现位置的先后顺序排序输出。
int n;
char s[MaxN];
string ans;
bool vis[30];
int main()
{
cin >> n;
scanf(" %s",&s);
int len = strlen(s);
for(int i = 0; i < len; i++){
if(vis[s[i]-'a'])continue;
else {
vis[s[i]-'a'] = 1;
ans += s[i];
}
}
printf("%d\n",ans.length());
cout << ans << endl;
return 0;
}
G、We are singers
题解：首先将读音和简谱利用Map建立映射关系，在读入读音的过程中通过先前建立的映射判断读音是否正确，错误计数即可。
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
int n, ans, Nmn[maxn];
map<string, int> mp;
string now, pro[8] = {"", "do", "re", "mi", "fa", "sol", "la", "si"};
int main() {
cin >> n;
for(int i = 1; i <= 7; ++i) mp[pro[i]] = i;
for(int i = 1; i <= n; ++i) cin >> Nmn[i];
for(int i = 1; i <= n; ++i) {
cin >> now;
ans += mp[now] != Nmn[i];
}
cout << ans << endl;
return 0;
}
H、Magic necklace
数据范围最大就到n = 11,dfs爆搜即可得到答案，由于题面是多组，需要预处理出答案以免TLE。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,Ans,t;
int vis[105],ans[15];
void dfs(int cur,int fa,int cnt,int x){
if(cnt == x && cur != 2){
Ans++;
return ;
}
else if(cnt == x) return;
for(int i = 1;i <= x; i++){
if(vis[i]) continue;
if(i == fa || i == cur) continue;
if(abs(i - cur) == 1) continue;
vis[i] = 1;
dfs(i,cur,cnt + 1,x);
vis[i] = 0;
}
}
void init(int x){
for(int i = 1;i <= n; i++) vis[i] = 0;
vis[1] = 1;
Ans = 0;
dfs(1,0,1,x);
ans[x] = Ans / 2;
}
int main()
{
for(int i = 1;i <= 11; i++) init(i);
ans[1] = 1;
ans[0] = 0;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%d\n",ans[n]);
}
}
另外，你也可以用next_permutation函数：
int nums[20], ans[20];
int main()
{
for(int n = 1; n <= 11; n++){
for(int i = 1; i <= n; i++) nums[i] = i;
int cnt = 0;
do{
nums[n+1] = nums[1];
bool f = 0;
for(int i = 1; i <= n; i++) if(abs(nums[i] - nums[i+1]) == 1) { f = 1; break; }
if(!f) cnt++;
}while(next_permutation(nums + 1, nums + n + 1));
ans[n] = cnt / n / 2;
}
ans[1] = 1;
int T; scanf("%d", &T);
while(T--){
int n; scanf("%d", &n);
printf("%d\n", ans[n]);
}
return 0;
}
I、恋爱之子
N2暴力枚举线段是否相交，将相交的线段用并查集维护，最后集合的个数就是答案。或者建图跑搜索也可以。
标程：
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define db double
#define gcd __gcd
#define pb push_back
#define lowbit(x) (x & (-x))
#define PII pair<int, int>
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << " = " << x << endl
#define rep(i, a, b) for(__typeof(b) i = a; i <= (b); i++)
#define Rep(i, a, b) for(__typeof(a) i = a; i >= (b); i--)
#define Mod(a,b) a<b?a:a%b+b
template<class T> inline T qmin(T a, T b) { return a < b ? a : b; }
template<class T> inline T qmax(T a, T b) { return a > b ? a : b; }
typedef long long ll;
typedef unsigned long long ull;
const db PI = acos(-1);
const int inf = 0x3f3f3f3f;
const int mod = (int)1e9 + 1;
const int maxn = (int)1e5 + 5;//remember to modify it, No RE&nbs***bsp;MLE
const ll INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
#define cross(p1, p2, p3) ((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y))
#define cross0p(p1, p2, p3) sign(cross(p1,p2,p3))
const db eps = 1e-9;
inline int sign(db a) { return a < -eps ? -1: a > eps; }
inline int cmp(db a, db b) { return sign(a-b); }
struct P{
db x, y;
P() {}
P(db _x, db _y): x(_x), y(_y) {}
P operator+(P p) { return {x + p.x, y + p.y}; }
P operator-(P p) { return {x - p.x, y - p.y}; }
P operator*(db d) { return {x * d, y * d}; }
P operator/(db d) { return {x / d, y / d}; }
bool operator<(P p)const {
int c = cmp(x, p.x);
if(c) return c == -1;
return cmp(y, p.y) == -1;
}
bool operator==(P o) const {
return cmp(x, o.x) == 0 && cmp(y, o.y) == 0;
}
db distTo(P p) { return (*this - p).abs(); }
db abs() { return sqrt(abs2()); }
db abs2() { return x * x + y * y; }
db dot(P p) { return x * p.x + y * p.y; }
db det(P p) { return x * p.y - y * p.x; }
};
bool intersect(db l1, db r1, db l2, db r2)
{
if(l1 > r1)swap(l1, r1); if(l2 > r2) swap(l2, r2);
return !( cmp(r1, l2) == -1 || cmp(r2, l1) == -1);
}
bool isSS(P p1, P p2, P q1, P q2){
return intersect(p1.x, p2.x, q1.x, q2.x) && intersect(p1.y, p2.y, q1.y, q2.y) && cross0p(p1, p2, q1) * cross0p(p1, p2, q2) <= 0 && cross0p(q1, q2, p1) * cross0p(q1, q2, p2) <= 0;
}
int f[maxn];
int find(int x)
{
if(f[x] == x)return x;
return f[x] = find(f[x]);
}
void Union(int x, int y)
{
int fx = find(x), fy = find(y);
if(fx != fy)f[fx] = fy;
}
int main()
{
int n;
P p[10005], q[10005];
scanf("%d", &n);
for(int i = 1 ; i <= n ; i++){
f[i] = i;
scanf("%lf %lf %lf %lf", &p[i].x, &p[i].y, &q[i].x, &q[i].y);
}
for(int i = 1 ; i <= n ; i++){
for(int j = i + 1 ; j <= n ; j++){
if(isSS(p[i], q[i], p[j], q[j]))Union(i, j);
}
}
int ans = 0;
for(int i = 1 ; i <= n ; i++)if(f[i] == i)ans++;
printf("%d\n", ans);
return 0;
}
J、敢敢单单的斐波那契数列
本题考查对空间滚动的理解与掌握，如果直接开maxn个空间的Int数组，显然有很多空间是浪费的，本题只需要开3个int重复使用即可。
Std:
const int mod = (int)1e9 + 7;
int main()
{
int n; while(~scanf("%d",&n)){
int x = 1, y = 1, ans = 1;
for(int i = 3; i <= n; i++){
ans = x + y;
x = y;
y = ans;
if(x >= mod) x -= mod;
if(y >= mod) y -= mod;
if(ans >= mod) ans -= mod;
}
printf("%d\n",ans);
}
return 0;
}
K、集训队的依赖关系
本题考察对基本树形依赖背包的掌握。
首先可以确定如果存在一个环S，那么指向S里任意一个元素的人我们都不会选择
那么考虑除开这些环还剩下什么，很显然就是一片森林
那么做法就很显然了：直接对于森林中的每一棵树单独考虑进行背包就好了，但是这样不太好写，所以我们可以建一个虚根，虚根的点权为0，对森林中每棵树的根都和这个虚根连一条边，那么现在问题就变成了以虚根为根的一棵树，让你在上面跑一个树形依赖背包就好啦
Std:
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = (int)5e3 + 5;//remember to modify it, No RE&nbs***bsp;MLE
ll dp[maxn][maxn];
int n, m, S;
ll val[maxn];
bool vis[maxn];
vector<int> G[maxn];
int cost[maxn], ind[maxn];
void dfs(int u, int sum){
int Min;
for(int v : G[u]){
Min = sum + cost[v];
if(Min <= S) {
for(int j = 0; j < Min; ++j) dp[v][j] = -INF;
for(int j = S; j >= Min; --j) dp[v][j] = dp[u][j - cost[v]] + val[v];
dfs(v, Min);
for(int j = 0; j <= S; ++j) dp[u][j] = max(dp[u][j], dp[v][j]);
}
}
return ;
}
int main()
{
scanf("%d %d %d", &n, &S, &m);
for(int i = 1; i <= n; i++) scanf("%d", val + i);
for(int i = 1; i <= n; i++) scanf("%d", cost + i);
for(int i = 1; i <= m; i++){
int u, v; scanf("%d %d", &u, &v);
G[v].push_back(u);
++ind[u];
}
for(int i = 1; i <= n; i++) if(ind[i] == 0) G[0].push_back(i);
dfs(0, 0);
printf("%lld\n", dp[0][S]);
return 0;
}
L、金牌厨师HiLin与HJGG
因为答案具有比较明显的单调性，很容易看出这是一道二分的题目，首先预处理二维前缀和，复杂度为O(n^2)，然后二分答案，因为预处理了二维前缀和，所以每次check当前答案的复杂度为O(n^2)，总体复杂度为O(n^2*logn)，即可通过该题。
#include <cstdio>
using namespace std;
const int MaxN = 2e3 + 5;
long long a[MaxN][MaxN] , k ;
int n ;
void inti(){
for(int i = 1 ; i <= n ; ++i){
for(int j = 1; j <= n ; ++j){
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
}
}
bool check(int x){
long long res ;
for(int i = x ; i <= n ; ++i){
for(int j = x ; j <= n ; ++j){
res = a[i][j] - a[i - x][j] - a[i][j - x] + a[i - x][j - x];
if(res >= k)return true;
}
}
return false;
}
int main(){
scanf("%d %lld",&n,&k);
for(int i = 1; i <= n ; ++i){
for(int j = 1;j <= n ; ++j)scanf("%lld",&a[i][j]);
}
inti();
int l = 1 , r = n , ans = 0;
while(l <= r){
int mid = l + r >> 1;
if(check(mid)){
ans = mid ;
r = mid - 1;
}
else l = mid + 1;
}
if(!ans)puts("I'm a Gold Chef!");
else printf("%d\n",ans);
return 0 ;
}
M、简单快乐棋
本题主要考察STL容器的使用以及代码能力。
我们需要做的就是记录空位置、各个英雄的位置、各个英雄的星级，分别使用优先队列、map、set（比较推荐set，因为是自动排序）或者vector就可以实现在使用妮蔻之助前的状态变化了。
由于本题为了简化，我们限定优先对更容易升星的英雄使用道具，并且妮蔻之助的数量较少，所以只需要按顺序依次对用1个、2个、3个妮蔻能升星的英雄进行操作即可。
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define pb push_back
typedef long long LL;
using namespace std;
const int maxn = 1E5 + 5;
const int inf = (1 << 30);
int n, m, k;
string id, ans[maxn];
priority_queue<int, vector<int>, greater<int> > rem;
map<string, int> cnt;
map<string, vector<int> > pos;
int now;
set<string> three, two, one, all;
set<string>::iterator it;
void up(int to, int ned){
if(to == 3){
it = two.begin();
while(k >= ned && it != two.end()){
if(cnt[*it + "**"] == 2 && 3 - cnt[*it] == ned){
for(int i = 0; i < pos[*it + "**"].size(); ++i){
ans[pos[*it + "**"][i]] = '#';
rem.push(pos[*it + "**"][i]);
}
for(int i = 0; i < pos[*it].size(); ++i){
ans[pos[*it][i]] = '#';
rem.push(pos[*it][i]);
}
pos[*it + "**"].clear();
pos[*it].clear();
now = rem.top(); rem.pop();
three.insert(*it);
ans[now] = *it + "***";
k -= ned;
}
it++;
}
}
else if(to == 2){
it = one.begin();
while(k >= ned && it != one.end()){
if(3 - cnt[*it] == ned){
for(int i = 0; i < pos[*it].size(); ++i){
ans[pos[*it][i]] = '#';
rem.push(pos[*it][i]);
}
pos[*it].clear();
now = rem.top(); rem.pop();
ans[now] = *it + "**";
k -= ned;
}
it++;
}
}
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; ++i){
cin >> id;
ans[i] = id;
if(id[0] == '#') rem.push(i);
else{
cnt[id]++;
one.insert(id);
all.insert(id);
pos[id].pb(i);
}
}
while(m--){
cin >> id;
if(three.count(id)) continue;
if(cnt[id] == 2){
ans[pos[id][0]] = '#';
ans[pos[id][1]] = '#';
rem.push(pos[id][0]);
rem.push(pos[id][1]);
one.erase(id);
cnt[id] -= 2;
pos[id].clear();
id += "**";
cnt[id]++;
if(cnt[id] == 3){
cnt[id] -= 3;
ans[pos[id][0]] = '#';
ans[pos[id][1]] = '#';
rem.push(pos[id][0]);
rem.push(pos[id][1]);
now = rem.top(); rem.pop();
pos[id].clear();
two.erase(id);
id += '*';
ans[now] = id;
three.insert(id.substr(0, id.length() - 3));
}else{
now = rem.top(); rem.pop();
ans[now] = id;
pos[id].pb(now);
two.insert(id.substr(0, id.length() - 2));
}
}else{
if(rem.empty()) continue;
now = rem.top(); rem.pop();
one.insert(id);
all.insert(id);
cnt[id]++;
ans[now] = id;
pos[id].pb(now);
}
}
up(3, 1);
up(3, 2);
up(3, 3);
up(2, 1);
up(2, 2);
up(2, 3);
it = all.begin();
while(k > 0 && it != all.end()){
if(rem.empty()) break;
if(three.count(*it)){
it++;
continue;
}
now = rem.top(); rem.pop();
ans[now] = *it;
it++;
--k;
}
cout << three.size() << endl;
for(it = three.begin(); it != three.end(); it++){
cout << *it << endl;
}
for(int i = 1; i <= n; ++i){
cout << ans[i] << ' ';
}
cout << endl;
return 0;
}
