安徽省年度“达内杯”程序设计大赛解题报告.docx

n

更多企业学院：
?中小企业管理全能版?
183套讲座+89700份资料

?总经理、高层管理?
49套讲座+16388份资料

?中层管理学院?
46套讲座+6020份资料 

?国学智慧、易经?
46套讲座

?人力资源学院?
56套讲座+27123份资料

?各阶段员工培训学院?
77套讲座+ 324份资料

?员工管理企业学院?
67套讲座+ 8720份资料

?工厂生产管理学院?
52套讲座+ 13920份资料

?财务管理学院?
53套讲座+ 17945份资料 

?销售经理学院?
56套讲座+ 14350份资料

?销售人员培训学院?
72套讲座+ 4879份资料

安徽省2021“达内杯〞程序设计大赛解题报告

A-幸运数字
此题只需题目描述解即可，没有任何算法和trick...

#include <iostream>
using namespace std;

int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
int t = n, s = 0;
while (t)
{
s += t % 10;
t /= 10;
}
if (n % s == 0) printf("yes\n");
else printf("no\n");
}
return 0;
}

B-转换二叉树
首先根据先序序列和中序序列建立二叉树，然后按要求先序遍历一遍二叉树即可。当然，由于建树过程实际也是在先序遍历二叉树，所以可以不用实际建树，只是模拟那个过程，然后再过程中输出即可。建树过程简单的说就是以先序序列定根节点，以中序序列和和根节点定左右子树。

#include <iostream>
#include <string.h>
using namespace std;

const int maxn = 27;

int N;
char PreOrder[maxn], InOrder[maxn];

void DFS(int PreStart, int PreEnd, int InStart, int InEnd)
{
int pos;

for (pos = InStart; PreOrder[PreStart] != InOrder[pos]; pos++) {}
if (pos != InStart)
{
printf("(");
DFS(PreStart + 1, PreStart + pos - InStart, InStart, pos - 1);
printf(")");
}
printf("%c", PreOrder[PreStart]);
if (pos != InEnd)
{
printf("(");
DFS(PreStart + pos - InStart + 1, PreEnd, pos + 1, InEnd);
printf(")");
}
}

int main()
{
int i, len;

scanf("%d", &N);
getchar();
for (i = 0; i < N; i++)
{
scanf("%s %s", PreOrder, InOrder);
len = strlen(PreOrder);
DFS(0, len - 1, 0, len - 1);
printf("\n");
}
return 0;
}

C-取石子
首先给出必胜结论，只要n != 2^x，那么先手必胜。证明：假设n = 12，将它转换为二进制那么为'1100'。先手第一次取只需把二进制中从低位数起第一个'1'取走即可。在这个例子中，先手留给后手石子数的二进制为'1000'。这样后手能取的石子数的二进制范围为'0001'-'0100'，无论后手怎么取，它都不可能把所有数字都取完，而且取了之后剩下的石子数的二进制后3位肯定有一个'1'。先手只需再次将从低位数起的第一个'1'取走即可重复上述过程直至游戏结束。而如果先手第一次面对的石子数是2^x个，由于他第一次不能把石子都取完，所以他无论如何取都会把上述必胜状态留给对手。
同样根据上述证明方法可以证明如果先手必胜，那么他第一次取的最少石子数就是石子数的二进制中，从低位数起的第一个'1'。

#include <iostream>
using namespace std;

int main()
{
int n, t;
while (scanf("%d", &n) != EOF)
{
t = 1;
while (!(n & 1))
{
n >>= 1;
t <<= 1;
}
if (n == 1) printf("lose\n");
else printf("win %d\n", t);
}
return 0;
}
D-关键词统计
这题最正确解法是先建立单词的字典树，然后再把文章中的单词一个一个抠出来进行匹配，时间复杂度是O(m+n)。m是文章长度，n是单词总长度。但是省赛时我们数据放得比拟松，只要是把单词一个一个抠出来比拟的都能过。

#include <iostream>
using namespace std;

const int maxn = 10162;
const int maxm = 200005;

struct Node
{
int next[26];
int index;

void init()
{
memset(next, -1, sizeof(next));
index = -1;
}
} tire[maxn*5];

char str[maxm], word[50];
int cunt[maxn], nxt[maxn], sz, idx;

void insert(char *s)
{
int p = 0;
while (*s)
{
int v = *s - 'a';
if (tire[p].next[v] == -1)
{
tire[p].next[v] = ++sz;
tire[sz].init();
}
p = tire[p].next[v];
s++;
}
nxt[idx] = tire[p].index;
tire[p].index = idx++;
}

void find(char *s)
{
int p = 0;
while (*s)
{
int v = *s - 'a';
if (tire[p].next[v] == -1)
return;
p = tire[p].next[v];
s++;
}
for (p = tire[p].index; p != -1; p = nxt[p])
cunt[p]++;
}

bool lowercase(const char &c)
{
return 'a' <= c && c <= 'z';
}

bool uppercase(const char &c)
{
return 'A' <= c && c <= 'Z';
}

int main()
{
int n, i, t;

gets(str);
scanf("%d%*c", &n);
memset(cunt, 0, 4 * n);
tire[0].init();
for (i = 0; i < n; i++)
{
scanf("%s", word);
insert(word);
}
for (i = t = 0; ; i++)
{
if (lowercase(str[i]))
word[t++] = str[i];
else if (uppercase(str[i]))
word[t++] = str[i] + 32;
else if (t)
{
word[t] = '\0';
find(word);
t = 0;
}
if (!str[i]) break;
}
for (i = 0; i < n; i++)
printf("%d\n", cunt[i]);

return 0;
}
E-搬书
这题很多人可能想复杂了，比赛中有的队是用DP过的。但其实只要对体积进行二分，然后暴力法测试即可。二分体积时间复杂度O(logd)，测试时间复杂度O(n+m)。所以总的时间复杂度是O((n+m)logd)，其中d是箱子体积最大可能值和最小可能值之差，n是书的数量，m是箱子的数量。

#include <iostream>
using namespace std;

const int maxn = 1000;
int v[maxn];

int main()
{
int n, m;
int maxv, minv;
int left, right, mid, cunt, ptr, leave;
while (scanf("%d %d", &n, &m) != EOF)
{
maxv = minv = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", v + i);
maxv += v[i];
if (v[i] > minv)
{
minv = v[i];
}
}
left = minv, right = maxv;
while (left < right)
{
mid = (left + right) / 2;
cunt = 0;
leave = 0;
for (ptr = 0; ptr < n && cunt <= m; ptr++)
{
if (leave >= v[ptr])
{
leave -= v[ptr];
}
else
{
leave = mid - v[ptr];
cunt++;
}
}
if (cunt <= m)
right = mid;
else
left = mid + 1;
}
printf("%d\n", left);
}
return 0;
}
F-水晶球
假设少女的相貌、智慧和财富分别是x、y和z。首先按x从大到小排序处理掉一维，然后建立一个map，它的key值是y，value值是z。然后从头到尾扫描所有少女。每扫描一个少女时，在map里找其y值的上界，如果它的上界对应的z要大于少女的z，那么说明有少女无论x、y还是z都大于她。否那么将这个少女的y值和z值插入到map里，并且将map里的无用数据删去，无论是y还是z都比少女小的值。当然这样粗略的讲，还有很多问题是被忽略过去的，比方说边界问题，两个值相同的问题，如何删去map中的无用数据等，这个大家可以参考标程。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

const int maxn = 50005;
const int inf = 1000000005;

struct Data
{
int x, y, z;

// 按x从大到小排，如果x相同，那么按y从小到大排，如果y也相同，那么按z从小到大排
bool operator < (const Data &oth) const
{
if (x != oth.x) return x > oth.x;
if (y != oth.y) return y < oth.y;
return z < oth.z;
}
} data[maxn];

int n, ans;
map<int, int> v;
typedef map<int, int>::iterator itr;

int main()
{
int i;
while (scanf("%d", &n) != EOF)
{
for (i = 0; i < n; i++)
scanf("%d", &data[i].x);
for (i = 0; i < n; i++)
scanf("%d", &data[i].y);
for (i = 0; i < n; i++)
scanf("%d", &data[i].z);

v.clear();
sort(data, data + n);
v[inf] = -inf;
v[-inf] = inf;
for (i = 0, ans = 0; i < n; i++)
{
itr x = v.upper_bound(data[i].y);
if (data[i].z < x->second)
ans++;
else
{
if (!v.count(data[i].y) || v[data[i].y] < data[i].z)
{
v[data[i].y] = data[i].z;
for (x = --v.lower_bound(data[i].y); x->second <= data[i].z; )
v.erase(x--);
}
}
}
printf("%d\n", ans);
}
return 0;
}
G-星际航行
这题是后3题中唯一有队伍过的题，其实不算很难。只要把圆的向量和长方形的向量合并，然后把题目转换成圆在动，长方形静止或者长方形在动，圆静止这样的模型。然后问题就蜕化为圆与线段〔长方形的边〕相撞的问题。

#include <iostream>
#include <cmath>
using namespace std;

#define eps (1e-8)
#define zero(x) (fabs(x)<eps)

struct point {
double x, y;
point() {}
point(double a, double b) { x=a; y=b; }
point(point p1, point p2) { x=p2.x-p1.x; y=p2.y-p1.y; }
point operator +(point p) { return point( x+p.x, y+p.y); }
};

double xmult(point p1 ,point p2) {
return p1.x*p2.y-p2.x*p1.y;
}
double xmult(point p1 ,point p2, point p0) {
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

double dmult(point p1, point p2){
return p1.x*p2.x+p1.y*p2.y;
}

double dist(point a, point b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double disptoline(point p, point l1, point l2) {
return fabs( xmult(p,l1,l2) ) / dist(l1,l2);
}

bool crossline(point o, double r, point v, point a, point b) {
if( zero(v.x) && zero(v.y) ) return false;
double d = xmult( v, point(a,b) );
if( d<=-eps ) return false;
if( d>=eps ) {
double da = xmult( v, point(o,a) );
double db = xmult( v, point(o,b) );
if( (da>=eps) ^ (db>=eps) ) return true;
point o1 = o+v;
if( disptoline(a, o, o1)-r <=-eps ) return true;
if( disptoline(b, o, o1)-r <=-eps ) return true;
return false;
}
if( disptoline(o, a, b)-r>-eps ) return false;
return dmult(v, point(o,a)) >= eps;
}

bool crossfull(point a, point b, point c, point v, point o, double r, point vo) {
point d = a+point(b,c);
point vs(v,vo);
return crossline(o, r, vs, a, c) || crossline(o, r, vs, b, d);
}

int main() {
point a, b, c, v, o, vo;
double r;
while(cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>v.x>>v.y>>o.x>>o.y>>r>>vo.x>>vo.y) {
cout<<(crossfull(a,b,c,v,o,r,vo)?"YES":"NO")<<endl;
}
return 0;
}
H-技术员BangFu
这题是状态DP，dp状态定为dp[1<<10][10][7]。第一维是二进制标记走过哪些节点，第二维是最后到达哪个节点，第三维是时间是星期几，而数组本身的值为最少花费了多少钱。最后用Spfa递推出所有状态即可。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 15;
const int D = 7;
const int INF = 1000000000;

struct Edge
{
int y, p, t;
};
struct Node
{
int s, x, d;
};

int n, m;
int dp[1<<N][N][D], mk[1<<N][N][D];
vector<Edge> v[N];
queue<Node> q;

void Init()
{
int i, j, k, x;
Edge tmp;

for (i = 0; i < n; i++)
v[i].clear();
for (i = 0; i < m; i++)
{
scanf("%d %d %d %d", &x, &tmp.y, &tmp.p, &tmp.t);
v[x].push_back(tmp);
}

for (i = 0; i < (1 << n); i++)
{
for (j = 0; j < n; j++)
for (k = 0; k < D; k++)
dp[i][j][k] = INF, mk[i][j][k] = 0;
}
}

void Solve()
{
Node now, nxt;
now.s = 1, now.x = 0, now.d = 0;
dp[now.s][now.x][now.d] = 0;
mk[now.x][now.x][now.d] = 1;
q.push(now);
while (!q.empty())
{
now = q.front();
q.pop();

int &x = now.x;
int &p = dp[now.s][now.x][now.d];
for (int i = 0; i < v[x].size(); i++)
{
int &y = v[x][i].y;
if (!(now.s & (1 << y)))
{
nxt.s = (now.s | (1 << y));
nxt.x = y;
nxt.d = (now.d + v[x][i].t + 1) % 7;

int tp = p + v[x][i].p;
if (tp < dp[nxt.s][nxt.x][nxt.d])
{
dp[nxt.s][nxt.x][nxt.d] = tp;
if (!mk[nxt.s][nxt.x][nxt.d])
{
mk[nxt.s][nxt.x][nxt.d] = 1;
q.push(nxt);
}
}
}
}
}
}

void Check()
{
int x, d, i;
int s = (1 << n) - 1;
int minp = INF;
bool flag1 = false, flag2 = false;
for (x = 1; x < n; x++)
{
for (i = 0; i < v[x].size(); i++)
{
if (v[x][i].y == 0)
{
for (d = 0; d < D; d++)
{
if (dp[s][x][d] < INF)
{
flag1 = true;
if ((d + v[x][i].t) % 7 >= 5 && minp > dp[s][x][d] + v[x][i].p)
{
minp = dp[s][x][d] + v[x][i].p;
flag2 = true;
}
}
}
}
}
}

if (!flag1) printf("It's not my thing!\n");
else if (!flag2) printf("Oh, My god!\n");
else printf("%d\n", minp);
}

int main()
{
while (scanf("%d %d", &n, &m) != EOF)
{
Init();
Solve();
Check();
}
return 0;
}