1001.Typhoon
计算几何
题意
依次给定 $n$ 个坐标 $P$ ，预测的台风路线为按顺序两两连接给定坐标所得的折线
现在有 $m$ 个庇护所的坐标 $S$ ，求每个庇护所到台风路线的最短距离
解题思路
对于每个庇护所坐标，求它到每个路线线段的距离，再取最短即可
常见的错误为计算了点到线段所在直线的距离，而非到线段的距离（别问我怎么知道的）
问题转移到如何计算点到线段的距离
可以考虑将线段表示为向量，记为 $vec$ ;点到线段两端的向量记为 $vec1,vec2$
如果 $vec1,vec2$ 与 $vec$ 的点积同时大于 $0$ 或同时小于 $0$ ，则距离在端点取到，否则距离为点到直线的距离//
具体说明可以参考代码注释
时间复杂度
$O(nm)$
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| vector<pll> typh,shel;
vector<double> frac,dist;
double cal_dist(pll s,pll t1,pll t2){
ll x,y,x1,y1,x2,y2,p1,p2;
pll vec,vec1,vec2;double re;
x=s.first;y=s.second;
x1=t1.first;y1=t1.second;
x2=t2.first;y2=t2.second;
vec={x2-x1,y2-y1};vec1={x-x1,y-y1};vec2={x-x2,y-y2};
p1=vec.first*vec1.first+vec.second*vec1.second;
p2=vec.first*vec2.first+vec.second*vec2.second;
if(p1<=0&&p2>0||p1>0&&p2<=0){
double frac=(double)sqrt((y2-y1)*(y2-y1)+(x1-x2)*(x1-x2));
re=(double)fabs((y2-y1)*x+(x1-x2)*y-y2*x1+x2*y1)/frac;
}else{
double dist1=(double)sqrt(vec1.first*vec1.first+vec1.second*vec1.second);
double dist2=(double)sqrt(vec2.first*vec2.first+vec2.second*vec2.second);
re=min(dist1,dist2);
}
return re;
}
void solve()
{
ll n,m;
cin >> n >> m;
typh.resize(n);shel.resize(m);dist.resize(m);
for(auto &[x,y]:typh) cin >> x >> y;
for(auto &[x,y]:shel) cin >> x >> y;
FORLL(i,0,m-1){dist[i]=INF;
FORLL(j,0,n-2)
dist[i]=min(dist[i],cal_dist(shel[i],typh[j],typh[j+1]));}
for(double i:dist) {print_float(i,4);cout << endl;}
}
|
1006.Touhou Red Red Blue
贪心/DP
题意
你将依次收到 $n$ 个物品，他们具有颜色红、绿或蓝，记为 $R,G,B$
你有一个大小为 $2$ 的物品栏。每当你收到一个物品，你可以考虑将其放入物品栏或直接丢弃
物品栏是一个栈，这意味着如果你决定放入物品但物品栏是满的，你将丢弃更早放入的那个物品，并将手上的物品放入
下面是物品的得分和消除规则：
- 如果手上和物品栏中共 $3$ 个物品颜色相同，则消除这 $3$ 个物品，得到 $1$ 分（这是唯一的得分方式），并在物品栏得到 $1$ 个颜色由你决定的新物品
- 如果手上和物品栏中共 $3$ 个物品颜色各不相同，则消除这 $3$ 个物品，并在物品栏得到 $2$ 个颜色由你决定的新物品
求对于给定的物品序列，可以得到的最高分是多少
解题思路
官方给出的做法是DP，但是考虑所有的状态转移略显繁琐，难以不重复、不遗漏
相比起来我还是更喜欢直接贪心的方法//
决定一种游戏策略前，先掌握游戏核心机制
首先，在贪心的思想下，物品栏的栈特性可以不考虑//因为如果需要被迫丢弃物品，大可以在拿到这个物品时就直接丢弃//
其次，注意到颜色任选的物品可以不立刻考虑，作为任意物品即可
考虑消除过程中的特点：
- 规则 $2$ 消除后得到 $2$ 个
任意物品，可以配合规则 $1$ ，直接和下一个物品（若有）合成得分
- 规则 $1$ 消除后留下 $1$ 个
任意物品。这意味着如果有得分，最后一定会留下 $1$ 个任意物品
借助上面两个特点，单独考虑第一次消除，后续消除借助前面得到的任意物品，具体可以参考代码注释
计数直到满足条件消除，即视为取需要的物品，并直接丢弃无帮助的物品，重新计数即可
时间复杂度
$O(n)$
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| int RGB(char c){
switch (c)
{
case 'R':return 1;
case 'G':return 2;
default:return 3;
}return 0;
}
void solve()
{
string s;cin >> s;
ll n=s.length(),res=0;
int cur=0,cnt[4]={0};
FORLL(i,0,n-1){
cur=RGB(s[i]);cnt[cur]++;
if(res){
if(cnt[1]&&cnt[2]||cnt[1]&&cnt[3]||cnt[2]&&cnt[3]){
if(i+1==n) break;
i++;res++;
cnt[1]=cnt[2]=cnt[3]=0;
}else if(cnt[1]==2||cnt[2]==2||cnt[3]==2){
res++;cnt[1]=cnt[2]=cnt[3]=0;
}
}else{
if(cnt[1]&&cnt[2]&&cnt[3]){
if(i+1==n) break;
i++;res++;
cnt[1]=cnt[2]=cnt[3]=0;
}else if(cnt[1]==3||cnt[2]==3||cnt[3]==3){
res++;cnt[1]=cnt[2]=cnt[3]=0;
}
}
}cout << res << endl;
}
|
1007.Expectation (Easy Version)
数学期望
题意
玩 $n$ 次游戏，每次游戏胜利的概率为 $\dfrac{a}{b}$
对于给定的 $m$ ，每次游戏胜利将获得 $k^m$ 分，其中 $k$ 是当前总胜利局数，失败得 $0$ 分
最终得分为 $n$ 次游戏的得分之和，求最终得分的期望
解题思路
从全局角度考虑得分情况，游戏输赢概率满足二项分布，记获胜概率为 $p=\dfrac{a}{b}$
在 $n$ 局游戏中赢 $k$ 局的概率为： $C_n^k\cdot p^k(1-p)^{n-k}$
赢 $k$ 局游戏可以获得的最终得分记为 $score(k)$ ： $score(k)=\sum\limits_{i=1}^k i^m$
故最终得分期望为： $E=\sum\limits_{i=1}^n C_n^k\cdot p^k(1-p)^{n-k}\cdot score(k)$
分别预处理阶乘、乘方、得分数组，求和取模即可
时间复杂度
乘方、阶乘、求和取模： $O(n)$
得分（快速幂+前缀和）： $O(n\log m)$
总时间复杂度： $O(n\log m)$
参考代码
参考代码为已AC代码主干，其中功能请读者自行实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| vector<ll> powp,pownp,score;
void solve()
{
ll n,m,a,b,re=0;
cin >> n >> m >> a >> b;
ll p=mul(a,inv(b));
ll np=Get_Mod(1-p);
powp.clear();pownp.clear();score.clear();
powp.resize(n+1);pownp.resize(n+1);score.resize(n+1);
powp[0]=pownp[0]=1;score[0]=0;
FORLL(i,1,n){
powp[i]=mul(powp[i-1],p);
pownp[i]=mul(pownp[i-1],np);
score[i]=add(score[i-1],qcpow(i,m));}
FORLL(i,1,n)
re=add(re,mul(score[i],mul(Get_Combination(n,i),mul(powp[i],pownp[n-i]))));
cout << re << endl;
}
|
1012.Counting Stars
计数
题意
定义 $k$ 星状图：一个 $k+1$ 个节点， $k$ 条边的无向图，中心节点与其他 $k$ 个节点之间各有一条边，其他节点之间没有边
给定一个无向图 $G=(V,E),|V|=n,|E|=m$ ，记其中不同的 $k$ 星状图的数量为 $cnt_k$
求对于 $2\le k\le n-1$ ，所有 $cnt_k$ 的异或和： $cnt_2\oplus cnt_3\oplus \cdots \oplus cnt_{n-1}$
解题思路
对于某个节点 $i$ ，记它的度为 $deg_i$ ，考虑以它作为中心节点的情况
简单的组合问题，以 $i$ 为中心节点的 $k$ 星图数量即 $C_n^k$
遍历 $n$ 个节点，在每个节点处对 $2\le k\le deg_i$ 的 $k$ 星图计数取模
最终把所有结果做异或和即可
时间复杂度
预处理阶乘（计算组合数）： $O(n)$
遍历节点：$O(n+m)$
异或和：$O(n)$
总时间复杂度：$O(n+m)$
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector<ll> deg,cnt;
void solve()
{
ll n,m;
cin >> n >> m;
deg.clear();deg.resize(n+1);cnt.clear();cnt.resize(n+1);
ll u,v;
FORLL(i,1,m){
cin >> u >> v;
deg[u]++;deg[v]++;
}
FORLL(i,1,n)
FORLL(j,2,deg[i])
cnt[j]=Get_Mod(cnt[j]+Get_Combination(deg[i],j));
ll re=0;
FORLL(i,2,n-1) re^=cnt[i];
cout << re << endl;
}
|
