2019ICPC银川网络赛&2018宁夏邀请赛
Problem A Maximum Element In A Stack题意: 题意真难懂。。。大致是给你一段代码，然后求 ⨁ i = 1 n ( i ∗ a i ) \bigoplus_{i = 1}^{n}(i * ai) ⨁i=1n(i∗ai)的值，ai是每次操作完后ai的最大值。
思路: 题意知道后，就很好做了，开一个单调栈模拟就可以了。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
int n, p, q, m;
unsigned int SA, SB, SC;
int sum = 0, cnt = 0;
unsigned int rng61() {
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
void gen() {
long long ans = 0;
stack <int> S;
scanf("%d%d%d%d%u%u%u", &n, &p, &q, &m, &SA, &SB, &SC);
for (int i = 1; i <= n; i++) {
if (rng61() % (p + q) < p) {
if (S.size()) {
unsigned int s = S.top();
S.push(max(rng61() % m + 1, s));
}
else S.push(rng61() % m + 1);
}
else {
if (S.size())
S.pop();
}
if (S.size())
ans ^= 1ll * i * S.top();
}
printf("%lld\n", ans);
}
int main() {
int t, kase = 0;
scanf("%d", &t);
while (t--) {
sum = 0, cnt = 0;
printf("Case #%d: ", ++kase);
gen();
}
return 0;
}
Problem B Rolling The Polygon
题目链接：https://nanti.jisuanke.com/t/41286
题意: 一个多边形滚动，一个点q在多边形的内部或者边上，以每个点为圆心滚动，问滚动一周后，q点经过的路径。
思路: 每三个点会构成一个角，向量点乘求出角度(其滚动的角度为 π \pi π-三点的夹角)，然后两点公式求出半径，根据弧长=角度*半径，求出弧长，总弧长即为所求答案。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
struct point {
double x, y;
point() {}
point(double x, double y) : x(x), y(y) {}
}q, p;
point operator-(point a, point b) {
return point(a.x - b.x, a.y - b.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 Cross(point a, point b) {
return a.x * b.x + a.y * b.y;
}
double Crea(point a, point b, point c) {
double ans = acos(Cross(b - a, c - a) / (dist(a, b) * dist(a, c)));
return dist(q, a) * (acos(-1) - ans);
}
int main() {
int t, n, m, kase = 0;
scanf("%d", &t);
while (t--) {
double ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lf%lf", &p.x, &p.y);
scanf("%lf%lf", &q.x, &q.y);
p = p, p = p;
for (int i = 1; i <= n; i++)
ans += Crea(p, p, p);
printf("Case #%d: %.3lf\n", ++kase, ans);
}
return 0;
}
Problem C Caesar Cipher
题目链接：https://nanti.jisuanke.com/t/41287
题意: 现在你有一个明文和它的密文，还有另一个用相同方法加密的密文，请把它解密。
思路: 首先根据明文和它的密文求出移位的大小，然后将加密的密文减去这个值就行了，注意不要超出A~Z这个范围。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
char sa, sb, sc;
int main() {
int t, n, m, kase = 0;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
scanf("%s%s%s", sa, sb, sc);
int cnt = (sb - sa + 26) % 26;
printf("Case #%d: ", ++kase);
for (int i = 0; sc; i++)
printf("%c", (sc - 'A' - cnt + 26) % 26 + 'A');
printf("\n");
}
return 0;
}
Problem D Take Your Seat
题目链接：https://nanti.jisuanke.com/t/41288
题意: 问题一：飞机上一共有n个座位，每个座位都有自己的编号，一共有n个乘客，杜哈就是其中之一，每个乘客都有一个票，用来找自己所在的位置，但是杜哈的票丢了，所以他只好上飞机后随便做，原先位置的主人发现自己的位置被别人占了后，他也只好随便坐，杜哈是第一个上飞机的。问，最后一个上飞机的乘客能够做到自己的座位的概率是多少？
问题二：题干和问题一相同，唯一不同是这次杜哈不一定是第一个上飞机的人了，乘客都是随机上机，问最后一个上飞机的乘客能够做到自己的座位的概率是多少？
思路: 当 n = 1 时概率为 p 1 = 1 p_1 = 1 p1=1，当 n = 2 时概率为 p 2 = 1 / 2 p_2 = 1 / 2 p2=1/2。
当 n ≥ 3 时，如果 1 坐到 1 上，那么后面所有人都会坐对，如果杜哈坐到 n上，那么 n 肯定不能坐对。
如果 1 坐到 k 上，那么 2、3、· · · 、k − 1 都会坐对，此时 k 相当于一开始的 1，而人数变为 n − k + 1。因此 p n = ( 1 + p 2 + p 3 + ⋅ ⋅ ⋅ + p n − 1 ) / n p_n = (1+p_2+p_3+···+p_{n-1})/n pn=(1+p2+p3+⋅⋅⋅+pn−1)/n.
，可得 p n = 1 / 2 p_n = 1 / 2 pn=1/2。
第二问：等概率随机一个排列相当于等概率随机杜哈的登机时刻。
如果杜哈是第i个登机的，那么登机的前i−1人都能坐对，此时 i 相当于一开始的 1，人数变为n − i + 1。
杜哈第几次登机的概率为1/m，由第一问可知只要疯子不是最后一个上去，其坐对的概率为1/2，疯子最后上，则前面的人都坐对，疯子只剩自己的座位了，也会坐对。
故当杜哈不是最后上概率为 ( 1 / m ) ∗ ( m − 1 ) ∗ ( 1 / 2 ) = ( m − 1 ) / ( 2 ∗ m ) (1/m)*(m-1)*(1/2)=(m-1)/(2*m) (1/m)∗(m−1)∗(1/2)=(m−1)/(2∗m)
(也就是说，只要不是最后上，概率就是1/2，而杜哈在第几次登机是不确定的，有m-1种选择，而杜哈第i次登机的概率都为1/m，所以概率就为(1/m)(m-1)(1/2));
当杜哈是最后一个上的时候，概率为 1 1 1.
因此总概率为 ( ( m − 1 ) / ( 2 ∗ m ) + 1 = ( m + 1 ) / ( 2 ∗ m ) ((m-1)/(2*m)+1=(m+1)/(2*m) ((m−1)/(2∗m)+1=(m+1)/(2∗m);
综上，第一问n==1时答案为1，其他始终为1/2, 第二问为(m+1)/(m*2)。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int main() {
int t, n, m, kase = 0;
double cnta, cntb;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
if (n != 1)
cnta = 1.0 / 2;
else cnta = 1;
cntb = (m + 1) * 1.0 / (m * 2);
printf("Case #%d: %lf %lf\n", ++kase, cnta, cntb);
}
return 0;
}
Problem F Moving On
题目链接：https://nanti.jisuanke.com/t/41290
题意: 两个人住在城市u，每天要去城市v,但是要经过一些城市和街道，而且每个城市都有抢劫等的概率，要求找一条路的从城市u到城市v而且抢劫率不超过w的最短路径。
思路: Floyd变形。一开始用的Dijastra算法，但是每次询问都要调用一次会严重超时，所以后面想了想还是用Floyd算法，将各城市的危险值从小到大排序。
mp表示从城市i到城市j借助排序后的前k个城市可以取到的最小距离，所以状态转换方程为: m p [ k ] [ i ] [ j ] = m i n ( m p [ k − 1 ] [ i ] [ j ] , m p [ k − 1 ] [ i ] [ i d [ k ] ] + m p [ k − 1 ] [ i d [ k ] ] [ j ] ) mp = min(mp, mp] + mp]) mp=min(mp,mp]+mp]).
Accepted Code:/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200 + 5;
const int inf = 0x3f3f3f3f;
int mp;
struct edge {
int id, w;
bool operator < (const edge &s) const {
return s.w > w;
}
}spt;
void Floyd(int n) {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
mp = min(mp, mp.id] + mp.id]);
}
int main() {
int kase = 0;
int t, n, q, a, b, c;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
spt.id = i;
scanf("%d", &spt.w);
}
sort(spt + 1, spt + n + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &mp);
Floyd(n);
printf("Case #%d:\n", ++kase);
while (q--) {
scanf("%d%d%d", &a, &b, &c);
int l = 1;
while (spt.w <= c && l <= n)
l++;
printf("%d\n", mp[--l]);
}
}
return 0;
}
Problem H Fight Against Monsters
题目链接：https://nanti.jisuanke.com/t/41292
题意: 现在有 n 只怪兽，每只怪兽有一个体力值 HPi 和一个***值 ATKi。英雄需要同时和这 n 只怪兽进行战斗。在每一秒，首先英雄会被当前未被打倒的所有怪兽***，受到与这些怪兽的***值之和等量的伤害。然后他要选择一只未被打倒的怪兽进行***。对同一只怪物进行的第 i 次***能对其造成 i 点伤害。当怪兽的体力值 ≤ 0 的时候就会倒下，当所有怪兽都被打倒时战斗立即结束。英雄需要合理地进行***以使战斗过程中受到的伤害之和最小，请你求出这个伤害总量。
思路: 很明显的贪心，要想使伤害小，那么就需要将单位次数伤害高的先解决掉。s表示杀死当前怪物所需要的***次数，按照t与s的比值从大到小进行杀怪。注意排序的时候，将除变成乘。
Accepted Code:/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
struct edge {
int h, t, s;
bool operator < (const edge &p) const {
return p.t * s < t * p.s;
}
}spt;
int slove(int x) {
int a = 0, ans = 0;
while (x > 0) {
ans++;
x -= ++a;
}
return ans;
}
int main() {
int t, n, kase = 0;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &spt.h, &spt.t);
spt.s = slove(spt.h);
}
sort(spt, spt + n);
long long ans = 0, cnt = 0;
for (int i = 0; i < n; i++) {
cnt += spt.s;
ans += cnt * spt.t;
}
printf("Case #%d: %lld\n", ++kase, ans);
}
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_15302000/3240569
页:
[1]