The 2018 ACM-ICPC （宁夏赛区）部分题解
The 2018 ACM-ICPC Chinese Collegiate Programming Contest (held by Ningxia Institute of Science and Technology)
A. Maximum Element In A Stack
题意： n次操作 ， 每次操作之后 ， 找到栈中最大的值 ， 进行异或 ， 若栈为空 ， 则top()的值为0。
思路：每次往栈中插入值时 ， 从大到小排序 ， 这样每次取出时就直接取s.top()
代码：
#include <bits/stdc++.h>
#define ll long long
#define uu usigned
using namespace std;
int n , p , q , m;
uu SA , SB , SC;
stack s;
void PUSH(ll x)
{
if(s.empty()) s.push(x);
else s.push(max(x , s.top()));
}
void POP()
{
if(!s.empty()) s.pop();
}
uu rng61()
{
uu t;
SA^=SA<<16;
SA^=SA>>5;
SA^=SA<<1;
t=SA,SA=SB,SB=SC,SC^=t^SA;
return SC;
}
ll gen()
{
ll ans = 0;
scanf("%d %d %d %d %d %d" , &n , &p , &q , &SA , &SB , &SC);
for(int i = 1 ; i <= n ; i++)
{
if(rng61( )% (p+q) < p)
{
PUSH(rng61() % m + 1);
}
else
{
POP();
}
ans ^= (i*s.top());
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 1 ; i <= t ; i++)
{
while(!s.empty())s.pop();
printf("Case #%d: %lld" , i , gen());
}
return 0;
}
B. Rolling The Polygon
Q点到每个顶点之间的距离为该圆弧的半径 ， 三个相邻顶点之间的距离 ， 再利用余弦公式求出补角；
再根据 弧长 = 1/2 * 角度 * 半径。
代码：
#include<bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const int maxn = 2e3+30;
int Qx , Qy;
struct node
{
int x;
int y;
}op[maxn];
double count1(int x , int y)
{
double ans = sqrt((x-Qx)*(x-Qx) + (y-Qy)*(y-Qy));
return ans;
}
double count3(int x1 , int y1 , int x2 , int y2)
{
double ans = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
return ans;
}
double count2(double a , double b , double c)
{
double ans;
ans = acos(a*a +b*b-c*c/(2*b*a));
return PI-ans;
}
int main()
{
int t , n;
scanf("%d" , &t);
for(int k = 1 ; k <= t ; k++)
{
double ans = 0;
scanf("%d" , &n);
for(int i = 0 ; i < n ; i++)
{
scanf("%d %d" , &op[i].x , &op[i].y);
}
scanf("%d %d" , &Qx , &Qy);
for(int i = 0 ; i < n ; i++)
{
double a = count3(op[i].x,op[i].y,op[(i+1)%n].x,op[(i+1)%n].y);
double b = count3(op[(i+1)%n].x,op[(i+1)%n].y,op[(i+2)%n].x,op[(i+2)%n].y);
double c = count3(op[i].x,op[i].y,op[(i+2)%n].x,op[(i+2)%n].y);
double d = PI-acos((a*a+b*b-c*c)/(2*a*b));
double e = count1(op[(i+1)%n].x,op[(i+1)%n].y);
//cout<<d <<" " << e <<endl;
ans += d*e;
//ans += (count1(op[(i+1)%n].x,op[(i+1)%n].y) * (PI-acos((a*a+b*b-c*c)/(2*a*b))));
}
printf("Case #%d: %.3f\n" , k , ans);
}
return 0;
}
C.Caesar Cipher
ASCII码的转换 ， A 是 65 ， 先记录下已知条件中俩个字符串相差数 ， 再 ( str[i] -’A’ + num+26 )% 26 +65
要注意不管多少一定都在A ~Z之间 ， 所以要取余26；
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t , n , m;
string str1 , str2 , str3;
scanf("%d" , &t);
for(int i = 1 ; i <= t ; i++)
{
scanf("%d %d" , &n , &m);
cin >> str1 >> str2;
int num = str2[0] - str1[0];
// if(num < 0) num += 26;
cin >> str3;
printf("Case #%d: " , i);
for(int j = 0 ; j < str3.length() ; j++)
{
cout << char((str3[j]-'A'-num +26)%26 + 65);
}
printf("\n");
}
return 0;
} D. Take Your Seat
概率问题 ， 第一问，有n个人依次上飞机 ， 第一个人弄丢了牌子 ， 随机坐。后面的人如果他的位置没有被占 ， 那么他就会做到自己相应的位置上 ， 否则也将随机坐。问最后一个上飞机的人坐在自己位置上的概率。
- 如果n= 1 , P1 = 1;
- 如果n =2 ， P2 = 1/2；
- 如果n >= 3 , 第一个人如果坐上第一个位置 ， 那么剩下的人都坐在自己位置上。如果坐在第n个位置 ， 那是不对的。
如果坐在第k 个位置（k表示除了1和n 的其他位置） 那么2~k-1的人都能坐到自己相应的位置上。然后第k个人现在就相当于第一个人 ， 如果他选择第一个位置 ， 那么剩下的人都能坐上自己的位置 ， 如果选择第i个 ， 那么k ~i-1是可以坐在自己位置上。
P3 = 1/3 + 1/3 *P2 = 1/2 = P2/2；
P4 = 1/4 + 1/4*P3 + 1/4 * P2 = 1/2 = P3/3；
。
。
。
Pn = 1/n+ 1/n*pn-1......... = 1/2 = Pn/n;
所以得到递推公式：Pn = (P1+P2+.......+Pn)/n;
第二个问题 ， 同第一个问题相比只是由原先按顺序上飞机变成了随机上飞机 ， 那么每个概率前*1/m即可
Pn = (1 +P1+P2+.....+Pn) = (1/m+ 1/2m + ......+1/2m) m-1个1/2相加 = 1/m + (m-1)/2m = (m+1)/2m;
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t ;
double n , m;
scanf("%d" , &t);
for(int i = 1 ; i <= t ; i++)
{
cin >> n >> m;
double ans1 , ans2;
if(n == 1) ans1 = 1;
else ans1 = 0.5;
ans2 = (m+1)/(2*m);
printf("Case #%d: %.6f %.6f\n" , i , ans1 , ans2);
}
return 0;
} H.Fight Against Monsters
题意:
有 n 个怪物 ， 每个怪物都有v的生命值 和 w 的攻击值，现在有个英雄要为民除害 ，杀掉这些怪物。
英雄对每个怪物的伤害值都是从1 开始依次加一（比如英雄第一次伤害A ， 伤害值是1 ， 第二次是2 ，下次 ， 伤害B 是1 ，再次伤害B 是2.。。。。。。）英雄每次会受到所有活着的怪物的攻击值总和。
问英雄受到的最小攻击值是多少？
思路：
贪心 ， 由怪物的生命值可以得到英雄杀死该怪物需要的次数 ， 怪物的攻击值 / 怪物被杀的次数 ， 相当于一次所能伤害的值 ， 那么当然是这个值越大英雄就先杀谁 ， 所以按照这个比值从大到小排序 ， 然后杀杀杀就好了
（注意：1.记得开long long 2 . 比值排序有精度误差 ， 改成这样： a/b : c/d ------> a*d : b*c ）
代码：
/*
1.存下攻击每个怪兽需要的次数
2.从小到大排列 武力值/次数
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+8;
struct node
{
int v , w , time;
}a[maxn];
bool cmp(node a , node b)
{
return a.time * b.w > a.w * b.time;
}
int main()
{
int t , n;
scanf("%d" , &t);
for(int k = 1 ; k <= t ; k++)
{
scanf("%d" , &n);
ll tot = 0;
for(int j = 1 ; j <= n ; j++)
{
scanf("%d %d" , &a[j].v , &a[j].w);
tot += a[j].w;
int l = 1;
a[j].time = 0;
while(a[j].v > 0)
{
a[j].time++;//a[j].time = l;
a[j].v -= l;
l++;
}
}
sort(a+1 , a+n+1 , cmp);
ll sum = 0;//求和
for(int i = n ; i >= 1 ; i--)
{
sum += a[i].time * tot;
tot -= a[i].w;
}
printf("Case #%d: %lld\n" , k , sum);
}
return 0;
}
涂鸦智能一面5人在聊