北京市专业网站建设,自己办网站审批流程,网站建设的几种结构,做招聘网站的风投第一题#xff1a;最大波动 小明正在利用股票的波动程度来研究股票。 小明拿到了一只股票每天收盘时的价格#xff0c;他想知道#xff0c;这只股票连续几天的最大波动值是多少#xff0c;即在这几天中某天收盘价格与前一天收盘价格之差的绝对值最大是多少。 输入格式 输入…第一题最大波动 小明正在利用股票的波动程度来研究股票。 小明拿到了一只股票每天收盘时的价格他想知道这只股票连续几天的最大波动值是多少即在这几天中某天收盘价格与前一天收盘价格之差的绝对值最大是多少。 输入格式 输入的第一行包含了一个整数 n表示小明拿到的收盘价格的连续天数。 第二行包含 n 个正整数依次表示每天的收盘价格。 输出格式 输出一个整数表示这只股票这 n 天中的最大波动值。 数据范围 对于所有评测用例2≤n≤1000。 股票每一天的价格为 1 到 10000 之间的整数。 输入样例 6
2 5 5 7 3 5输出样例 4样例解释 第四天和第五天之间的波动最大波动值为 |3−7|4。 解题思路
枚举每一天求出这一天和前一天的差值取最大值即可。 以下是代码
c
#includeiostreamusing namespace std;const int N 1010;
int n;
int a[N];
int res 0;int main()
{cin n;for(int i 0;i n;i ){cin a[i];if(i) res max(res , abs(a[i] - a[i - 1]));}cout res endl;return 0;
}
第二题火车购票 请实现一个铁路购票系统的简单座位分配算法来处理一节车厢的座位分配。 假设一节车厢有 20 排、每一排 5 个座位。 为方便起见我们用 1 到 100 来给所有的座位编号第一排是 1 到 5 号第二排是 6 到 10 号依次类推第 20 排是 96 到 100 号。 购票时一个人可能购一张或多张票最多不超过5张。 如果这几张票可以安排在同一排编号相邻的座位则应该安排在编号最小的相邻座位。 否则应该安排在编号最小的几个空座位中不考虑是否相邻。 假设初始时车票全部未被购买现在给了一些购票指令请你处理这些指令。 输入格式 输入的第一行包含一个整数 n表示购票指令的数量。 第二行包含 n 个整数每个整数 p 在 1 到 5 之间表示要购入的票数相邻的两个数之间使用一个空格分隔。 输出格式 输出 n 行每行对应一条指令的处理结果。 对于购票指令 p输出 p 张车票的编号按从小到大排序。 数据范围 对于所有评测用例1≤n≤100所有购票数量之和不超过 100。 输入样例 4
2 5 4 2输出样例 1 2
6 7 8 9 10
11 12 13 14
3 4样例解释 购 2 张票得到座位 1、2。购 5 张票得到座位 6 至 10。购 4 张票得到座位 11 至 14。购 2 张票得到座位 3、4。 解题思路
枚举每一个位置每一次拿出一行元素进行判断如果可以放在同一排那么直接输出编号反之从小到大进行枚举如果有空位即可放入。
以下是代码
c
#includeiostream
#includecstringusing namespace std;const int N 110;
bool st[N];
int n;int main()
{memset(st , 0 , sizeof st);cin n;while(n --){int x;cin x;bool f false;for(int i 1;i 100;i 5){for(int h 0;h 5;h ){int cnt 0;for(int j h;j 5 ;j )if(!st[j i]) cnt ;else break;if(cnt x){for(int j 0;j x;j )cout j i h , st[j i h] true;cout endl;f true;break;}}if(f) break;}if(!f){for(int i 1;i 100 x;i )if(!st[i]){x --;st[i] true;cout i ;}cout endl;}}return 0;
}
第三题炉石传说 《炉石传说魔兽英雄传》Hearthstone: Heroes of Warcraft简称炉石传说是暴雪娱乐开发的一款集换式卡牌游戏如下图所示。 游戏在一个战斗棋盘上进行由两名玩家轮流进行操作本题所使用的炉石传说游戏的简化规则如下 玩家会控制一些角色每个角色有自己的生命值和攻击力。当生命值小于等于 00 时该角色死亡。角色分为英雄和随从。玩家各控制一个英雄游戏开始时英雄的生命值为 3030攻击力为 00。当英雄死亡时游戏结束英雄未死亡的一方获胜。玩家可在游戏过程中召唤随从。棋盘上每方都有 77 个可用于放置随从的空位从左到右一字排开被称为战场。当随从死亡时它将被从战场上移除。游戏开始后两位玩家轮流进行操作每个玩家的连续一组操作称为一个回合。每个回合中当前玩家可进行零个或者多个以下操作 1) 召唤随从玩家召唤一个随从进入战场随从具有指定的生命值和攻击力。 2) 随从攻击玩家控制自己的某个随从攻击对手的英雄或者某个随从。 3) 结束回合玩家声明自己的当前回合结束游戏将进入对手的回合。该操作一定是一个回合的最后一个操作。当随从攻击时攻击方和被攻击方会同时对彼此造成等同于自己攻击力的伤害。受到伤害的角色的生命值将会减少数值等同于受到的伤害。例如随从 X 的生命值为 HX、攻击力为 AX随从 Y 的生命值为 HY、攻击力为 AY如果随从 X 攻击随从 Y则攻击发生后随从 X 的生命值变为 HX−AY随从 Y 的生命值变为 HY−AX。攻击发生后角色的生命值可以为负数。 本题将给出一个游戏的过程要求编写程序模拟该游戏过程并输出最后的局面。 输入格式 输入第一行是一个整数 n表示操作的个数。 接下来 n 行每行描述一个操作格式如下 action arg1 arg2 ... 其中 action 表示操作类型是一个字符串共有 3 种summon 表示召唤随从attack 表示随从攻击end 表示结束回合。 这 3 种操作的具体格式如下 summon position attack health当前玩家在位置 position 召唤一个生命值为 health、攻击力为 attack 的随从。其中 position 是一个 1 到 7 的整数表示召唤的随从出现在战场上的位置原来该位置及右边的随从都将顺次向右移动一位。attack attacker defender当前玩家的角色 attacker 攻击对方的角色 defender。attacker 是 1 到 7 的整数表示发起攻击的本方随从编号defender 是 0 到 7 的整数表示被攻击的对方角色0 表示攻击对方英雄1 到 7 表示攻击对方随从的编号。end当前玩家结束本回合。 注意随从的编号会随着游戏的进程发生变化当召唤一个随从时玩家指定召唤该随从放入战场的位置此时原来该位置及右边的所有随从编号都会增加 1。而当一个随从死亡时它右边的所有随从编号都会减少 1。任意时刻战场上的随从总是从 1 开始连续编号。 输出格式 输出共 5 行。 第 1 行包含一个整数表示这 n 次操作后以下称为 T 时刻游戏的胜负结果1 表示先手玩家获胜−1 表示后手玩家获胜0 表示游戏尚未结束还没有人获胜。 第 2 行包含一个整数表示 T 时刻先手玩家的英雄的生命值。 第 3 行包含若干个整数第一个整数 p 表示 T 时刻先手玩家在战场上存活的随从个数之后 p 个整数分别表示这些随从在 T 时刻的生命值按照从左往右的顺序。 第 4 行和第 5 行与第 2 行和第 3 行类似只是将玩家从先手玩家换为后手玩家。 数据范围 操作的个数 0≤n≤1000。 随从的初始生命值为 1 到 100 的整数攻击力为 0 到 100 的整数。 保证所有操作均合法包括但不限于 召唤随从的位置一定是合法的即如果当前本方战场上有 m 个随从则召唤随从的位置一定在 1 到 m1 之间其中 1 表示战场最左边的位置m1 表示战场最右边的位置。当本方战场有 7 个随从时不会再召唤新的随从。发起攻击和被攻击的角色一定存在发起攻击的角色攻击力大于 0。一方英雄如果死亡就不再会有后续操作。 数据约定 前 20% 的评测用例召唤随从的位置都是战场的最右边。前 40% 的评测用例没有 attack 操作。前 60% 的评测用例不会出现随从死亡的情况。 输入样例 8
summon 1 3 6
summon 2 4 2
end
summon 1 4 5
summon 1 2 1
attack 1 2
end
attack 1 1输出样例 0
30
1 2
30
1 2样例解释 按照样例输入从第 2 行开始逐行的解释如下 先手玩家在位置 1 召唤一个生命值为 6、攻击力为 3 的随从 A是本方战场上唯一的随从。先手玩家在位置 2 召唤一个生命值为 2、攻击力为 4 的随从 B出现在随从 A 的右边。先手玩家回合结束。后手玩家在位置 1 召唤一个生命值为 5、攻击力为 4 的随从 C是本方战场上唯一的随从。后手玩家在位置 1 召唤一个生命值为 1、攻击力为 2 的随从 D出现在随从 C 的左边。随从 D 攻击随从 B双方均死亡。后手玩家回合结束。随从 A 攻击随从 C双方的生命值都降低至 2。 解题思路
使用结构体存储随从和英雄的血量和攻击力使用k表示当前是谁进行操作其中k0位先手当opsummon时右移放入随从结构体存入血量和攻击力当opattack时双方的随从同时收到伤害如果血量低于0那么左移覆盖掉之前的记录最后统计胜负即比较最后的英雄血量输出对应英雄的随从即可 以下是代码
c
#includeiostream
#includecstring
#includealgorithmusing namespace std;struct Role
{int a, h;
}m[2][10];void remove(int pos1, int pos2)
{// 左移for(int i pos2;i 7;i )m[pos1][i] m[pos1][i 1];
}
int main()
{m[0][0].h m[1][0].h 30;int n;cin n;int k 0; // 判断谁先出while(n --){string op;cin op;if(op summon){int pos , a , h;cin pos a h;// 右移for(int i 7;i pos 1;i --) m[k][i] m[k][i - 1];m[k][pos].a a, m[k][pos].h h;}else if(op attack){int a , b;cin a b;// a的随从血量降低降低b随从的攻击力m[k][a].h - m[!k][b].a;// b的随从血量降低降低a随从的攻击力m[!k][b].h - m[k][a].a;// 小于0的表示死亡// 左移if(a m[k][a].h 0) remove(k,a);if(b m[!k][b].h 0) remove(!k, b);}else k !k;}// 判断胜负int cnt;if(m[0][0].h 0) puts(-1);else if(m[1][0].h 0) puts(1);else puts(0);// 输出随从cout m[0][0].h endl;cnt 0;for(int i 1;i 7;i )if(m[0][i].h) cnt ;cout cnt ;for(int i 1;i cnt;i ) cout m[0][i].h ;cout endl;cout m[1][0].h endl;cnt 0;for(int i 1;i 7;i )if(m[1][i].h) cnt ;cout cnt ;for(int i 1;i cnt;i ) cout m[1][i].h ;cout endl;return 0;
} 第四题 交通规划 G 国国王来中国参观后被中国的高速铁路深深的震撼决定为自己的国家也建设一个高速铁路系统。 建设高速铁路投入非常大为了节约建设成本G 国国王决定不新建铁路而是将已有的铁路改造成高速铁路。 现在请你为 G 国国王提供一个方案将现有的一部分铁路改造成高速铁路使得任何两个城市间都可以通过高速铁路到达而且从所有城市乘坐高速铁路到首都的最短路程和原来一样长。 请你告诉 G 国国王在这些条件下最少要改造多长的铁路。 输入格式 输入的第一行包含两个整数 n,m分别表示 G 国城市的数量和城市间铁路的数量。所有的城市由 1 到 n 编号首都为 1 号。 接下来 m 行每行三个整数 a,b,c表示城市 a 和城市 b 之间有一条长度为 c 的双向铁路。这条铁路不会经过 a 和 b 以外的城市。 输出格式 输出一行表示在满足条件的情况下最少要改造的铁路长度。 数据范围 对于 20% 的评测用例1≤n≤101≤m≤50 对于 50% 的评测用例1≤n≤1001≤m≤5000 对于 80% 的评测用例1≤n≤10001≤m≤50000 对于 100% 的评测用例1≤n≤100001≤m≤1000001≤a,b≤n1≤,≤1≤c≤1000。 输入保证每个城市都可以通过铁路达到首都。 两个城市之间可能存在不止一条铁路。 输入样例 4 5
1 2 4
1 3 5
2 3 2
2 4 3
3 4 2输出样例 11 解题思路
首先使用堆优化的迪杰斯特拉算法求出1号点到其他点的最短距离。
其次遍历除了1号点的其他所有节点遍历该节点的每一个相连的节点计算出最短的可以到达该点的边即我们需要的高速公路
最后求出这些距离的最短距离和即可得到结果。 以下是代码
c
#includeiostream
#includequeue
#includecstringusing namespace std;const int N 10010 , M 200010 , INF 0x3f3f3f3f;
typedef pairint , intPII;
int n , m;
int e[M] , h[M] , w[M] , ne[M] , idx;
int dist[M];
int res 0;void add(int a , int b , int c)
{e[idx] b , w[idx] c , ne[idx] h[a] , h[a] idx ;
}void dj()
{dist[1] 0;priority_queuePII , vectorPII , greaterPIIhasp;hasp.push({0 , 1});while(!hasp.empty()){auto t hasp.top();hasp.pop();int y t.second;for(int i h[y];~i;i ne[i]){int j e[i];if(dist[j] dist[y] w[i]){dist[j] dist[y] w[i];hasp.push({dist[j] , j});}}}
}int main()
{memset(dist , 0x3f , sizeof dist);memset(h , -1 , sizeof h);cin n m;while(m --){int a , b , c;cin a b c;add(a , b , c) , add(b , a , c);}dj();for(int i 2;i n;i ){int _min INF;for(int j h[i];~j;j ne[j]){int b e[j];if(dist[i] dist[b] w[j])_min min(_min , w[j]);}res _min;}cout res endl;return 0;
}
第五题祭坛 使用线段树 离散化求解 #include iostream
#include algorithm
#include cstring
#include cstdio
#include vector //离散化用#define x first
#define y secondusing namespace std;typedef pairint, int PII;const int N 3e5 10;int n, m;
PII q[N]; //表示所有点
int down[N], up[N]; //表示某个点下面的点数和上面的点数
vectorint xs; //存横坐标离散化之后的值
int best; //全局最优解struct Node //线段树结点
{int l, r;int maxvalue, sum; //所有点上下点数最小值的最大值和区间的总和
}tr[N * 4];int find(int x) //求一下离散化之后的x在数组xs中的下标所对应的值
{return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
}bool cmp(PII a, PII b) // 排序函数先按纵坐标排纵坐标相同的话再按横坐标排
{if(a.y ! b.y) return a.y b.y; //如果纵坐标不同的话纵坐标较小的在前return a.x b.x; //纵坐标相同横坐标较小的在前
}void pushup(int u)
{Node l tr[u 1], r tr[u 1 | 1];tr[u].maxvalue max(l.maxvalue, r.maxvalue);tr[u].sum l.sum r.sum;
}void modify(int u, int x) //修改某个点
{if(tr[u].l tr[u].r) //如果区间只有一个点直接修改{tr[u].maxvalue min(down[x], up[x]);tr[u].sum (tr[u].maxvalue best);return;}int mid tr[u].l tr[u].r 1;if(x mid) modify(u 1, x);else modify(u 1 | 1, x);pushup(u);
}//查询函数可能查区间最大值也可能查区间和,pair的first返回区间最大值second返回区间和
PII query(int u, int l, int r)
{//如果查询区间在当前区间内那就直接返回if(tr[u].l l tr[u].r r) return {tr[u].maxvalue, tr[u].sum};int mid tr[u].l tr[u].r 1;PII res(-1, 0); if(l mid) res query(u 1, l, r);if(r mid){PII t query(u 1 | 1, l, r);res.x max(res.x, t.x);res.y t.y;}return res;
}void build(int u, int l, int r)
{tr[u] {l, r};if(l r) tr[u].maxvalue tr[u].sum 0;else{int mid l r 1;build(u 1, l, mid), build(u 1 | 1, mid 1, r);pushup(u);}
}int main()
{scanf(%d%d, n, m);for(int i 0; i n; i ){scanf(%d%d, q[i].x, q[i].y);xs.push_back(q[i].x); //将所有横坐标放入离散化的数组中}//离散化标准操作排序、去重sort(xs.begin(), xs.end());xs.erase(unique(xs.begin(), xs.end()), xs.end());for(int i 0; i n; i ){q[i].x find(q[i].x);down[q[i].x] ; //从上向下枚举一开始所有点都在下面所以先统计下面有多少个点}sort(q, q n, cmp); //从上往下一行一行枚举需要先将所有点排序排序函数需要我们自己实现build(1, 0, xs.size() - 1); //建立线段树//从前往后枚举每一行for(int i 0; i n; i ){int j i;while(j n q[j].y q[i].y) //同一行{int x q[j ].x; //先找出横坐标down[x] -- , up[x] ; //做完这行下面的点数会减1上面的点数会多1modify(1, x); //更新当前点的结果}//算一下最大值for(int k i; k 1 j; k ){if(q[k].x 1 q[k 1].x - 1) //如果当前区间不为空的话,就查询一下这个区间的结果{PII t query(1, q[k].x 1, q[k 1].x - 1);best max(best, min(t.x, min(k - i 1, j - k - 1)));}}i j - 1; //跳过这个区间}if(m 1) printf(%d\n, best);else {//求完best后再做一遍,此时down和up的值相当于交换了一下memcpy(down, up, sizeof up); //将up的值赋回down中memset(up, 0, sizeof up); //再清空upbuild(1, 0, xs.size() - 1); //重新建立线段树//重复上面的for循环同时满足左右两边的值都要大于best//从前往后枚举每一行int res 0;for(int i 0; i n; i ){int j i;while(j n q[j].y q[i].y) //同一行{int x q[j ].x; //先找出横坐标down[x] -- , up[x] ; //做完这行下面的点数会减1上面的点数会多1modify(1, x); //更新当前点的结果}//算一下最大值for(int k i; k 1 j; k ){if(k - i 1 best j - k - 1 best q[k].x 1 q[k 1].x - 1) //如果当前区间不为空的话,就查询一下这个区间的结果{PII t query(1, q[k].x 1, q[k 1].x - 1);res t.y;}}i j - 1; //跳过这个区间}printf(%d\n, res);}return 0;
} 文章转载自： http://www.morning.kkjlz.cn.gov.cn.kkjlz.cn http://www.morning.ytfr.cn.gov.cn.ytfr.cn http://www.morning.wwjft.cn.gov.cn.wwjft.cn http://www.morning.wdykx.cn.gov.cn.wdykx.cn http://www.morning.hghhy.cn.gov.cn.hghhy.cn http://www.morning.qcwck.cn.gov.cn.qcwck.cn http://www.morning.wqkfm.cn.gov.cn.wqkfm.cn http://www.morning.gghhmi.cn.gov.cn.gghhmi.cn http://www.morning.tbnn.cn.gov.cn.tbnn.cn http://www.morning.qmkyp.cn.gov.cn.qmkyp.cn http://www.morning.hngmg.cn.gov.cn.hngmg.cn http://www.morning.dycbp.cn.gov.cn.dycbp.cn http://www.morning.tfei69.cn.gov.cn.tfei69.cn http://www.morning.wjqbr.cn.gov.cn.wjqbr.cn http://www.morning.cjsnj.cn.gov.cn.cjsnj.cn http://www.morning.hcbky.cn.gov.cn.hcbky.cn http://www.morning.yfddl.cn.gov.cn.yfddl.cn http://www.morning.zgztn.cn.gov.cn.zgztn.cn http://www.morning.hxcuvg.cn.gov.cn.hxcuvg.cn http://www.morning.mhbcy.cn.gov.cn.mhbcy.cn http://www.morning.fbnsx.cn.gov.cn.fbnsx.cn http://www.morning.xrct.cn.gov.cn.xrct.cn http://www.morning.kpzbf.cn.gov.cn.kpzbf.cn http://www.morning.nmwgd.cn.gov.cn.nmwgd.cn http://www.morning.smjyk.cn.gov.cn.smjyk.cn http://www.morning.ysfj.cn.gov.cn.ysfj.cn http://www.morning.msbpb.cn.gov.cn.msbpb.cn http://www.morning.ggnjq.cn.gov.cn.ggnjq.cn http://www.morning.fhyhr.cn.gov.cn.fhyhr.cn http://www.morning.qnlbb.cn.gov.cn.qnlbb.cn http://www.morning.thpns.cn.gov.cn.thpns.cn http://www.morning.qcdhg.cn.gov.cn.qcdhg.cn http://www.morning.qjbxt.cn.gov.cn.qjbxt.cn http://www.morning.ygztf.cn.gov.cn.ygztf.cn http://www.morning.brfxt.cn.gov.cn.brfxt.cn http://www.morning.srzhm.cn.gov.cn.srzhm.cn http://www.morning.pthmn.cn.gov.cn.pthmn.cn http://www.morning.bztzm.cn.gov.cn.bztzm.cn http://www.morning.tbjtp.cn.gov.cn.tbjtp.cn http://www.morning.qpmmg.cn.gov.cn.qpmmg.cn http://www.morning.ntgrn.cn.gov.cn.ntgrn.cn http://www.morning.khclr.cn.gov.cn.khclr.cn http://www.morning.bwttp.cn.gov.cn.bwttp.cn http://www.morning.bnygf.cn.gov.cn.bnygf.cn http://www.morning.mhlkc.cn.gov.cn.mhlkc.cn http://www.morning.bwhcl.cn.gov.cn.bwhcl.cn http://www.morning.jbfzx.cn.gov.cn.jbfzx.cn http://www.morning.gmgyt.cn.gov.cn.gmgyt.cn http://www.morning.dxqwm.cn.gov.cn.dxqwm.cn http://www.morning.qcztm.cn.gov.cn.qcztm.cn http://www.morning.cspwj.cn.gov.cn.cspwj.cn http://www.morning.bxgpy.cn.gov.cn.bxgpy.cn http://www.morning.wqgr.cn.gov.cn.wqgr.cn http://www.morning.piekr.com.gov.cn.piekr.com http://www.morning.kdnrc.cn.gov.cn.kdnrc.cn http://www.morning.syglx.cn.gov.cn.syglx.cn http://www.morning.wzyfk.cn.gov.cn.wzyfk.cn http://www.morning.ydzly.cn.gov.cn.ydzly.cn http://www.morning.nqbcj.cn.gov.cn.nqbcj.cn http://www.morning.dpdns.cn.gov.cn.dpdns.cn http://www.morning.lqgtx.cn.gov.cn.lqgtx.cn http://www.morning.fjmfq.cn.gov.cn.fjmfq.cn http://www.morning.kggxj.cn.gov.cn.kggxj.cn http://www.morning.fcftj.cn.gov.cn.fcftj.cn http://www.morning.jwqqd.cn.gov.cn.jwqqd.cn http://www.morning.fksdd.cn.gov.cn.fksdd.cn http://www.morning.cpljq.cn.gov.cn.cpljq.cn http://www.morning.kpwcx.cn.gov.cn.kpwcx.cn http://www.morning.rnzgf.cn.gov.cn.rnzgf.cn http://www.morning.bpwz.cn.gov.cn.bpwz.cn http://www.morning.ssrjt.cn.gov.cn.ssrjt.cn http://www.morning.hwprz.cn.gov.cn.hwprz.cn http://www.morning.yrmpz.cn.gov.cn.yrmpz.cn http://www.morning.nqbcj.cn.gov.cn.nqbcj.cn http://www.morning.ndmh.cn.gov.cn.ndmh.cn http://www.morning.rwnx.cn.gov.cn.rwnx.cn http://www.morning.hnk25076he.cn.gov.cn.hnk25076he.cn http://www.morning.bfgbz.cn.gov.cn.bfgbz.cn http://www.morning.djxnw.cn.gov.cn.djxnw.cn http://www.morning.ssxlt.cn.gov.cn.ssxlt.cn
