a 大杂烩
题目描述
石头、剪刀和布是好朋友。 有一天，他们看到电视上播着一个新游戏：石头剪刀布。他们感到非常不高兴，于是他们决定研究该游戏的进阶版：超级英雄大乱斗。 该游戏的玩法和标准的石头剪刀布非常类似，不过有一点不同，这个游戏不是简单的石头、剪刀和布，而是由十个不同的超级英雄进行对打！下面是十个超级英雄分别对打的结果（如果a行b列的值是1的话，表示a能战胜b；如果a行b列的值是-1的话，表示b能战胜a；如果是0，表示平局）：
接下来，石头和剪刀玩了很多把游戏，我们知道了他们各把游戏出的超级英雄牌，我们需要计算出石头赢了多少把，剪刀赢了多少把。
对于10%的数据，N=1。 对于50%的数据，石头只会打出SPIDER牌。 对于100%的数据，N<=100000。
输入格式
第一行一个正整数N，表示玩的局数。 接下来N行，每行两个字符串，分别表示石头和剪刀在这一局中出的超级英雄牌。
输出格式
一行两个整数，表示石头和剪刀分别赢的把数。
输入样例
1 SPIDER SPIDER
输出样例
0 0
解题思路(模拟+打表)
大水题。不要打错表，不要打错超级英雄的名字。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
map <string, int> M;
int compare[
15][
15] = {
{
0,
1,
1,
1,
1,
1,
1,
1,
1,
1},
{-
1,
0,
1, -
1,
1, -
1,
1, -
1,
1, -
1},
{-
1, -
1,
0,
1,
1, -
1,
1,
1, -
1,
1},
{-
1,
1, -
1,
0,
1, -
1,
1, -
1,
1, -
1},
{-
1, -
1, -
1, -
1,
0,
1,
1,
1,
1, -
1},
{-
1,
1,
1,
1, -
1,
0,
1, -
1, -
1, -
1},
{-
1, -
1, -
1, -
1, -
1, -
1,
0,
1,
1,
1},
{-
1,
1, -
1,
1, -
1,
1, -
1,
0,
1, -
1},
{-
1, -
1,
1, -
1, -
1,
1, -
1, -
1,
0,
1},
{-
1,
1, -
1,
1,
1,
1, -
1,
1, -
1,
0}
};
int n, cnt1, cnt2;
string A, B;
int main(){
M[
"SPIDER"] =
0;
M[
"HULK"] =
1;
M[
"CA"] =
2;
M[
"IRON"] =
3;
M[
"THOR"] =
4;
M[
"DD"] =
5;
M[
"DOOM"] =
6;
M[
"KP"] =
7;
M[
"RS"] =
8;
M[
"HYDRA"] =
9;
cin >> n;
for(
int i =
1; i <= n; i++){
cin >> A >> B;
if(compare[M[A]][M[B]] ==
1) cnt1 ++;
else if(compare[M[A]][M[B]] == -
1) cnt2 ++;
}
printf(
"%d %d\n", cnt1, cnt2);
return 0;
}
b 瓜分领土
题目描述
石头、剪刀和布闹别扭了，他们要分家。 他们生活在一个离散的一维空间里，简单点说，他们拥有在一条直线上的N间房子，每间房子有一个风水值（有正有负）。 然后，他们决定将这N间房子分成非空的三个连续段，从左到右数，第一段的房子全部属于石头，第二段的房子全部属于剪刀，第三段的房子全部属于布。 由于他们希望公平，并且又由于剪刀是他们的老大哥，他们决定根据这些条件制定了一个评判标准： 设石头拥有的房子的风水值和为a，剪刀拥有的房子的风水值和为b，布拥有的房子的风水值和为c，剪刀拥有n间房子。 那么通过给定一个参数x。 那么，这种分配的合理值就是max(a,b,c)-min(a,b,c)+x*n. 合理值越小，表示这种分配越合理。 因此，我们现在就是要求出这个最小的合理值。
对于30%的数据，N<=10. 对于70%的数据，N<=1000. 对于100%的数据，N<=100000,保证所有运算结果在long long范围内。
输入格式
第一行一个正整数N。 第二行有N个整数，表示房子的风水值，按从左到右的顺序给出。 第三行一个整数x。
输出格式
一行一个整数，表示最小的合理值。
输入样例
4 1 1 1 1 -1
输出样例
-1
解题思路(枚举+线段树+离散化+二分+数学分类)
本题线段树好题。
暴力枚举断点
O(n2)
有70分，然而我没用long long炸成60。正解就是只枚举一重，设剪刀拥有的最后一间房子的位置为
i
，然后前面石头的最后一间房子j就用线段树找。
至于具体如何做就要分成6种不同情况，消去min和max(解不等式，具体见代码)，变成一个和变量
i，j
(包括
sum[i],sum[j]
)有关的函数，同时确定
sum[j]
的范围(连续一段)。通过枚举固定
i
，离散化sum[j]，用线段树维护最小的与j有关的那部分，用公式计算，然后就可以
O(nlogn)
搞定了。
考试时我想到过只枚举
i
，然后解不等式分成6种情况讨论。但是我没有立刻去解上下界，导致我没有想到线段树，我想的是二分。然而前面的sum[j]都是离散的一些点，不连续，是没有单调性的，所以我就弃了交暴力。但离散化将离散的点变成连续的一段，就可以作为下标用线段树等一维数据结构维护。这个常见的方法我以后一定要牢记。
为什么还要二分呢？假如我们预处理离散化
sum
数组，后面解出的上下界中可能在原数组中没有，这时就要二分
L
，R在线段树底层的位置，就是找后继与前趋。倘若不二分也可以，搞出所有上下界后再离散化或者在线段树里加哨兵也行。另外一些细节，比如解出上下界要向哪边取整，线段树中开一个大小为6的数组维护不同值(每种情况算式不同)或每做一次清空一次之类的实现方法，就具体见代码吧。
ps：这题我调试了一个晚上，反复对照数学公式，反复检查线段树，最后发现是二分写错了！找后继的代码复制了找前趋的，然后修改时傻了，将找后继一开始的
L=n,R=0
，搞得我一晚上连爆了3次零。。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define N 100010
#define oo 1e18
using namespace std;
typedef
long long LL;
int n;
LL x, a[N],
sum[N], f[N], ans;
struct Ab{
int id; LL val;} P[N];
int rank[N], H;
struct Tnode{
LL v[
6];
}tree[N<<
2];
bool cmp(Ab A, Ab B){
return A.val < B.val;}
void build(
int root,
int L,
int R){
if(L == R){
for(
int i =
0; i <
6; i++) tree[root].v[i] = oo;
return;
}
int mid = (L + R) >>
1, Lson = root <<
1, Rson = root <<
1 |
1;
build(Lson, L, mid);
build(Rson, mid+
1, R);
for(
int i =
0; i <
6; i++) tree[root].v[i] = oo;
}
void update(
int root,
int L,
int R,
int x,
int op, LL val){
if(x > R || x < L)
return;
if(L == x && x == R){
tree[root].v[op] = (tree[root].v[op] > val) ? val : tree[root].v[op];
return;
}
int mid = (L + R) >>
1, Lson = root <<
1, Rson = root <<
1 |
1;
update(Lson, L, mid, x, op, val);
update(Rson, mid+
1, R, x, op, val);
tree[root].v[op] = (tree[Lson].v[op] < tree[Rson].v[op]) ? tree[Lson].v[op] : tree[Rson].v[op];
}
LL query(
int root,
int L,
int R,
int x,
int y,
int op){
if(x > R || y < L)
return oo;
if(x <= L && y >= R)
return tree[root].v[op];
int mid = (L + R) >>
1, Lson = root <<
1, Rson = root <<
1 |
1;
LL temp1 = query(Lson, L, mid, x, y, op);
LL temp2 = query(Rson, mid+
1, R, x, y, op);
return (temp1 < temp2) ? temp1 : temp2;
}
int Find_p(LL x){
int L =
1, R = n +
1;
while(L +
1 < R){
int mid = (L + R) >>
1;
if(P[mid].val <= x) L = mid;
else R = mid;
}
return rank[P[L].id];
}
int Find_s(LL x){
int L =
0, R = n;
while(L +
1 < R){
int mid = (L + R) >>
1;
if(P[mid].val >= x) R = mid;
else L = mid;
}
return rank[P[R].id];
}
void Work0(
int i){
if(i !=
1){
LL L =
2 *
sum[i] -
sum[n], R =
sum[i] /
2;
if(L > R || R < P[
1].val || L > P[n].val)
return;
L = Find_s(L); R = Find_p(R);
f[i] = min(f[i],
sum[n] -
sum[i] + x * (LL)i + query(
1,
1, H, L, R,
0));
}
update(
1,
1, H, rank[i],
0, -
sum[i] - x * (LL)i);
}
void Work1(
int i){
if(i !=
1){
LL L = (
sum[i] +
1) /
2, R =
sum[n] -
sum[i];
if(L > R || R < P[
1].val || L > P[n].val)
return;
L = Find_s(L); R = Find_p(R);
f[i] = min(f[i],
sum[n] -
2 *
sum[i] + x * (LL)i + query(
1,
1, H, L, R,
1));
}
update(
1,
1, H, rank[i],
1,
sum[i] - x * (LL)i);
}
void Work2(
int i){
if(i !=
1){
LL L = (
sum[i] +
1) /
2, R =
2 *
sum[i] -
sum[n];
if(L > R || R < P[
1].val || L > P[n].val)
return;
L = Find_s(L); R = Find_p(R);
f[i] = min(f[i],
sum[i] -
sum[n] + x * (LL)i + query(
1,
1, H, L, R,
2));
}
update(
1,
1, H, rank[i],
2,
sum[i] - x * (LL)i);
}
void Work3(
int i){
if(i !=
1){
LL L = P[
1].val, R = min(
2 *
sum[i] -
sum[n],
sum[n] -
sum[i]);
if(L > R || R < P[
1].val || L > P[n].val)
return;
L = Find_s(L); R = Find_p(R);
f[i] = min(f[i],
sum[i] + x * (LL)i + query(
1,
1, H, L, R,
3));
}
update(
1,
1, H, rank[i],
3, -
2 *
sum[i] - x * (LL)i);
}
void Work4(
int i){
if(i !=
1){
LL L =
sum[n] -
sum[i], R =
sum[i] /
2;
if(L > R || R < P[
1].val || L > P[n].val)
return;
L = Find_s(L); R = Find_p(R);
f[i] = min(f[i],
2 *
sum[i] -
sum[n] + x * (LL)i + query(
1,
1, H, L, R,
4));
}
update(
1,
1, H, rank[i],
4, -
sum[i] - x * (LL)i);
}
void Work5(
int i){
if(i !=
1){
LL L = max(
2 *
sum[i] -
sum[n],
sum[n] -
sum[i]), R = P[n].val;
if(L > R || R < P[
1].val || L > P[n].val)
return;
L = Find_s(L); R = Find_p(R);
f[i] = min(f[i], -
sum[i] + x * (LL)i + query(
1,
1, H, L, R,
5));
}
update(
1,
1, H, rank[i],
5,
2 *
sum[i] - x * (LL)i);
}
int main(){
scanf(
"%d", &n);
for(
int i =
1; i <= n; i++) scanf(
"%lld", &a[i]);
sum[
0] =
0;
for(
int i =
1; i <= n; i++)
sum[i] =
sum[i-
1] + a[i];
for(
int i =
1; i <= n; i++){
P[i].id = i;
P[i].val =
sum[i];
}
sort(P+
1, P+n+
1, cmp);
rank[P[
1].id] =
1;
for(
int i =
2; i <= n; i++){
rank[P[i].id] = rank[P[i-
1].id];
if(P[i].val != P[i-
1].val) rank[P[i].id] ++;
}
H = rank[P[n].id];
build(
1,
1, H);
for(
int i =
2; i < n; i++) f[i] = oo;
scanf(
"%lld", &x);
for(
int i =
1; i < n; i++){
Work0(i);
Work1(i);
Work2(i);
Work3(i);
Work4(i);
Work5(i);
}
ans = oo;
for(
int i =
2; i < n; i++) ans = min(ans, f[i]);
printf(
"%lld\n", ans);
return 0;
}
c 进击的石头
题目描述
石头一不小心掉进了一个复杂的地图里！ 这个地图是一个由N个节点、M条边组成的连通无向图，可能会有重边,但没有自环，节点编号从1到N。石头一开始在1号节点。由于石头非常害怕，于是开始等概率地随机游走（举个例子，比如说如果当前节点有K条边，那么以1/K的概率走其中一条边），并走了很久很久很久。 突然，石头停下来了，想要知道现在自己在哪个节点。 于是，石头希望你告诉他，他在各个节点的概率。如果不确定的话，输出“-1”。
对于30%的数据，N<=10,M<=20. 对于90%的数据，N<=300,M<=10000. 对于100%的数据，N<=2000，M<=50000.
输入格式
第一行两个正整数N,M。 接下来M行每行两个正整数x,y.表示存在一条(x,y)的无向边。
输出格式
一行N个整数，表示停在各个节点的概率，保留六位小数。如果不确定，只输出一行一个-1.
输入样例
3 3 1 2 2 3 3 1
2 1 1 2
输出样例
0.333333 0.333333 0.333333
-1
解题思路(求概率+判断二分图)
这题我的初次得分是70分，原因是因为不会判断输出-1的情况。
这题有两种做法，先说一说比较暴力的那种。那就是建好图，然后按题目描述的去做，每走完一步就可以得到当前点的概率，然后不断迭代，直到上一次这个点的概率与这次十分接近为止。就是说，频率稳定在一个数附近，我们就认为这个数是概率。当做了足够多的次数频率扔无法稳定时，就代表概率确定，输出-1。这样做能够拿90分。另外一个点会超时。我们设置上一次此点概率
f
与本次此点概率g，满足
|f−g|<Eps
时就认为稳定。当所有点都稳定时就退出迭代。所以
Eps
要取一个适当的值。一般8位~9位比较恰当。
然而我考试的时候并没有去想这种类似于“实验求概率”的方法，我利用了一条数学学方程
E(∑xi)=∑E(xi)
。学过数学的都知道，这是期望的线性性质。然而类比期望，其实单求概率也是有同样的性质。我们将题目改一下：每个点有一个分数，分数都为1，求石头最后在每个点的期望得分。这样，由于权值是1，期望与概率在数值上就相等了！于是我们便可以用这条方程解题。
这样做有什么好处呢？我们注意到方程左边求得是和的期望，右边是期望的和。左边考虑的是整体，右边对每个变量独立考虑并直接线性相加。在此题中，我们只考虑每个点独立的概率，由于走了无穷多步，所以开始从哪里出发并不重要了，按理说从哪出发最后概率都是一样的。于是这就相当于上一个点可以在任意位置，到达这个点只能通过这个点连出去的边到达。而每个点都有这样连出去的边。于是到达每个点的概率就等于
每个点的度数总度数
。于是我们直接统计度数就可以求到所有点的概率了。
这样做是70分的，因为如何判断-1呢？像上面说的，如果对于从每个点出发概率不一样，那么就没有确定的概率。还有一种角度，我们模拟时类似于分层图上的遍历，如果从奇数层出发和从偶数层出发，概率不一样的话，就没有确定的概率。实在不好理解可以从样例入手。我们从1出发，到达2，再不断下去，和从2出发下去的“最终”情形是不同的！
在实验了多组数据后，我们发现一个结论，从1开始染色一种确定的颜色，有两种颜色，每相邻两层换色。如果最后每个点只能染一种颜色，则没有确定的概率！于是我们就是在找二分图！二分图的最小着色数是2，所以1确定了染色，整幅图的颜色就唯一确定了。此时就是-1的情况。
这是为什么呢？lzh大佬没有留下明确的结论。因为这有点涉及数学了。其实我们可以这样理解，如果最后停在任意的点，在此之前走了奇数步和走了偶数步的概率不同，那就没有概率了(频率永远无法稳定)！因为我们不知道停下的时候，走了奇数步或偶数步，我们不知道最后停在了二分图的左边那层还是右边那层。这样从不同点出发，概率也就不同了。数学中，无穷大是没有奇偶性的。于是我们总算勉强说服了自己去求二分图了，二分图的求法很简单，直接dfs模拟染色过程就行了。
时间复杂度
O(n)
。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 2010
using namespace std;
int n, m;
int deg[N];
bool to[N][N], odd[N], even[N];
void dfs(
int now){
for(
int i =
1; i <= n; i++){
if(!to[now][i])
continue;
if(odd[now] && !even[i]){
even[i] =
true;
dfs(i);
}
if(even[now] && !odd[i]){
odd[i] =
true;
dfs(i);
}
}
}
int main(){
scanf(
"%d%d", &n, &m);
int a, b;
for(
int i =
1; i <= m; i++){
scanf(
"%d%d", &a, &b);
to[a][b] = to[b][a] =
true;
deg[a] ++;
deg[b] ++;
}
odd[
1] =
true;
dfs(
1);
for(
int i =
1; i <= n; i++)
if(!odd[i] || !even[i]){
printf(
"-1\n");
return 0;
}
int sum =
0;
for(
int i =
1; i <= n; i++) sum += deg[i];
for(
int i =
1; i <= n; i++){
double possibility = (
double)deg[i] / (
double)sum;
printf(
"%.6lf ", possibility);
}
printf(
"\n");
return 0;
}
总结
本次考试并不理想，主要是第二题long long没注意，对线段树的应用有些生疏，第三题也没好好去想和分析样例，数学基础不够扎实。
以后要多巩固复习，数据结构和期望、概率等方面一定要加强弥补。
