## [递推式求解、多指针、前缀和]XATU第七届算法大赛

2021/6/17 4:07:45 人评论

### 文章目录

• 赛后感想
• 1、2题略
• 3 乐华水上梦幻乐园之拖鞋失踪案[概率论、递推式求解]
• 题意
• 分析
• 代码
• 4、5、6、7、8题略
• 9 Ugly Number[多指针]
• 题意
• 做法1[BFS with heap]
• 做法2[多指针]
• 10 怪兽大学
• 题意
• 分析
• 总结

## 3 乐华水上梦幻乐园之拖鞋失踪案[概率论、递推式求解]

### 题意

n n 个人依次找拖鞋，第 1 1 位会随机挑选一位幸运观众，此后每一位将：

• 拿走自己的拖鞋，若自己的拖鞋还在
• 随机挑选一位幸运观众，若自己的拖鞋不在了

### 分析

f ( n ) f(n) 代表第1个人坐在座位 C ( 1 ) C(1) 后第 n n 个人坐到自己座位的概率，显然有以下公式：
f ( n ) = { 1 , if  C ( 1 ) = 1 0 , if  C ( 1 ) = n g ( C ( 1 ) ) , else f(n)= \begin{cases} 1, &\text{if $C(1)=1$}\\ 0, &\text{if $C(1)=n$}&\\ g(C(1)), &\text{else} \end{cases}

g ( C ( 1 ) ) , else g(C(1)), \text{else}

g ( x ) = { 0 , if  C ( x ) = n g ( C ( x ) ) , else g(x)= \begin{cases} 0, &\text{if $C(x)=n$}&\\ g(C(x)), &\text{else} \end{cases}

f ( n ) = 1 + ∑ i = 2 n − 1 g ( i ) + 0 n f(n)=\frac{1+\sum_{i=2}^{n-1}g(i)+0}{n}
g ( x ) = ∑ i = 2 x − 1 g ( i ) x g(x)=\frac{\sum_{i=2}^{x-1}g(i)}{x}

g ( n ) = ∑ i = 2 n − 1 g ( i ) n g(n)=\frac{\sum_{i=2}^{n-1}g(i)}{n}
g ( n − 1 ) = ∑ i = 2 n − 2 g ( i ) n − 1 g(n-1)=\frac{\sum_{i=2}^{n-2}g(i)}{n-1}

n g ( n ) − ( n − 1 ) g ( n ) = g ( n − 1 ) ng(n)-(n-1)g(n)=g(n-1)

g ( n ) = g ( n − 1 ) g(n)=g(n-1)

g ( x ) = { 1 , if  x = 1 0.5 , if  x > 1 g(x)= \begin{cases} 1, &\text{if $x=1$}&\\ 0.5, &\text{if $x>1$} \end{cases}

## 9 Ugly Number[多指针]

### 做法1[BFS with heap]

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
vector<ll> list;
set<ll> vis;
void gen(int cnt)
{
priority_queue<ll, vector<ll>, greater<ll> > heap;
heap.push(1);
while (list.size() < cnt)
{
ll now = heap.top();
heap.pop();
if (vis.find(now) != vis.end())
continue;
vis.insert(now);
list.push_back(now);
heap.push(now*2);
heap.push(now*3);
heap.push(now*5);
}
}
int n;
int maxx = 0;
int main()
{
cin>>n;
for (int i = 1; i <= n; i++)
{
ll x;
cin>>x;
if (x>maxx)
maxx = x;
}
gen(2000);
if (!v)
cout<<0<<' ';
else
cout<<list[v-1]<<' ';
return 0;
}


### 做法2[多指针]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];

auto m = *max_element(a.begin(), a.end());
vector<int> dp(m + 1);
dp = 1;
int p2 = 1, p3 = 1, p5 = 1;
for (int i = 2; i <= m; i++)
{
int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
dp[i] = min(min(num2, num3), num5);
if (dp[i] == num2)
p2++;
if (dp[i] == num3)
p3++;
if (dp[i] == num5)
p5++;
}

for (int i : a)
cout << dp[i] << ' ';
return 0;
}


## 10 怪兽大学

### 分析

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
int n;
vector<int> arr;
#define N 200005
int pre[N];
#define M 1000000007
int ans;
int range(int x, int y)
{
return pre[y] - pre[x-1];
}
int main()
{
cin>>n;
for (int i  = 1; i <= n ;i++)
{
int tmp;
cin>>tmp;
arr.push_back(tmp);
}
for (auto v : arr)
pre[v]++;
for (int i = 1; i <= 200000; i++)
pre[i] += pre[i-1];
for (auto v : arr)
for (int i = 1; i*v <= 100000; i++)
{
ans += i*range(i*v, (i+1)*v-1);
ans %= M;
}
cout<<ans;
return 0;
}


暂无相关的数据...
{"ft_lang_label":"__label__zh","ft_lang_prob":0.55221605,"math_prob":0.99978775,"size":5286,"snap":"2021-43-2021-49","text_gpt3_token_len":3732,"char_repetition_ratio":0.09693298,"word_repetition_ratio":0.1456077,"special_character_ratio":0.43284148,"punctuation_ratio":0.12626262,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999461,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-21T21:41:29Z\",\"WARC-Record-ID\":\"<urn:uuid:4ae388c2-adf1-40ce-91f5-1adefe849443>\",\"Content-Length\":\"113796\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:fc28f5a6-d59a-40b7-aeb5-eb83b32dfbac>\",\"WARC-Concurrent-To\":\"<urn:uuid:1dc69e14-e370-4ee4-8aa1-a5250f60693f>\",\"WARC-IP-Address\":\"103.100.210.4\",\"WARC-Target-URI\":\"http://www.ocnr.cn/news/show-426.html\",\"WARC-Payload-Digest\":\"sha1:HW43YNAQSXMQM4YA2N7YHJDPHDRBCJGS\",\"WARC-Block-Digest\":\"sha1:AMUWMAXYNGFJHSMPP6Z56GNOXCFKXPSZ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323585441.99_warc_CC-MAIN-20211021195527-20211021225527-00475.warc.gz\"}"}