Day18

2018-08-21

字数统计: 1.9k字 | 阅读时长: 8min

1．魔法少女小焰

(flame.cpp)
【时空限制】
时间限制：1s
空间限制：128MB
【问题描述】
“谁都无法相信未来，谁都无法接受未来。”
“越是重复，就越是偏离你和我生活过的时间。心意也相互偏离，言语也渐渐无法相通。
我想我大概早已经迷路了。
“要拯救你，这是我最初的心意，而到如今，这是最后留下的唯一路标。”
“轮回，无论几次，我依然选择轮回，无数次的探寻，寻找唯一的出口，寻找能将你从
绝望命运中拯救出来的道路。鹿目圆，我唯一的朋友，为了你，即使陷入永恒的迷宫，我也
会毫不介意！”
“这才是人类情感的极致，比希望更火热，比绝望更深切的东西——是爱。”
晓美焰为了拯救自己唯一的朋友鹿目圆，使之避免称为魔法少女的命运，在平行时空中
不断地穿梭轮回。
假设有 N 个平行时空，每时空都有一个维数，编号为 i 的时空的维数是𝑎௜，为了避免
跨越维数相差较大的时空引起自身的毁灭，晓美焰每次只能跨越维数相差不超过 D 的时空。
晓美焰可以从任意一个时空开始跨越，且只能从编号较小的时空跨越到编号较大的时空，
求她能跨越的最大时空数。
【输入格式】
第一行两个正整数 N,D
第二行 N 个整数表示编号为 i 的时空的维度𝑎௜
【输出格式】
一个整数表示答案
【输入输出样例 1】
flame.in 
6 3
5 7 3 6 10 9
flame.out
4
【输入输出样例 2】
flame.in 
8 6
4 7 9 5 8 1 9 10
flame.out
7
【数据范围】
对于 30%的数据，N ≤ 10
对于 60%的数据，N ≤ 2000
对于 100%的数据，N, |𝑎i| ≤ 10^5, 0 ≤ D ≤ 100//注意a可小于零

n^2dp(60分)

#include<bits/stdc++.h>
using namespace std;
int n,d;
int a[100010];
int dp[100010];
int main()
{
	freopen("flame.in","r",stdin);
	freopen("flame.out","w",stdout);
	scanf("%d %d",&n,&d);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)dp[i]=1;
	for(int i=1;i<=n;i++)
	for(int j=1;j<i;j++)
	{
		if(abs(a[i]-a[j])<=d) dp[i]=max(dp[i],dp[j]+1);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	ans=max(ans,dp[i]);
	printf("%d\n",ans);
	return 0;
}

nd pd(100分)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+1;
int dp[N*2];
int n,d;
int a[N],mx;
int ans;
int main()
{
	freopen("flame.in","r",stdin);
	freopen("flame.out","w",stdout);
	scanf("%d %d",&n,&d);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]+=N,mx=max(a[i],mx);
	for(int i=1;i<=n;i++)
	{
		dp[a[i]]++;
		for(int j=a[i]-d;j<=a[i]+d&&j<=mx;j++)
		if(j!=a[i]&&j>0)dp[a[i]]=max(dp[a[i]],dp[j]+1);
	}
	for(int i=1;i<=mx;i++) ans=max(ans,dp[i]);
	printf("%d\n",ans);
	return 0;
}

2．尼伯龙根之歌

(deathsong.cpp)
【时空限制】
 时间限制：1s
 空间限制：128MB
【问题描述】
尼伯龙根，又称“死人之国”，这里的一切都是没有生命的存在。
三年前，楚子航与父亲楚天骄在此遭遇龙王奥丁，楚天骄牺牲自己使楚子航得以逃离。
机缘巧合之下，路明非从 10 号高架路进入了尼伯龙根，被困于此，与此同时，奥丁持
昆古尼尔跨八足骏马前去追杀陈墨瞳，为拯救师姐，路明非必须走出尼伯龙根。
整个尼伯龙根可视为一张 n 个结点，m 条边的有向无环图，1 号结点为路明非当前所在
的高架桥，n 号结点为尼伯龙根的出口，路明非不知道出口的位置，所以每到一个结点，他
会随机选出一条边走下去，若无路可走就只能被永远地困在尼伯龙根里。
求路明非走出尼伯龙根的概率，答案对 998244353 取模。
【输入格式】
第一行：两个整数 n,m
接下来 m 行：每行两个整数 x,y 表示 x 到 y 有一条单向边
【输出格式】
一个整数，表示路明非走出尼伯龙根的概率在模 998244353 意义下的值
注：模意义下，除以一个数等于乘上这个数的逆元,根据费马小定理可求逆元
【输入输出样例 1】
deathsong.in 
5 5
1 2
1 3
2 5
3 4
3 5
deathsong.out
249561089
【输入输出样例 2】
deathsong.in 
10 10
1 5
1 7
4 2
3 7
5 4
3 9
9 7
1 2
7 2
5 10
deathsong.out
166374059
【数据范围】
对于 30%的数据，n ≤ 20
对于 60%的数据，n ≤ 2000
对于 100%的数据，n ≤ 100000，m ≤ 5n

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+1;
int p = 998244353;
int n,m;
struct node
{
	int ne,to;
}edge[5*N];
int head[N],cnt,fr[N];
ll to[N];
template<typename T>
void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){a=a*10+s-'0';s=getchar();}
	a*=f;
}
void add(int u,int v) 
{
	edge[++cnt].to=v;
	edge[cnt].ne=head[u];
	head[u]=cnt;
}
//ll madd(ll a,ll b){return (a+b>p)?(a+b-p):(a+b);}
ll mul(ll a,int b)
{
	ll c=1;
	while(b)
	{
		if(b&1) c*=a,c%=p;
		a*=a;
		a%=p;
		b>>=1;
	}
	return c;
}
ll ans[N];
double gl[N];
void dfs(int sta)
{
	queue<int> q;
	q.push(sta);
	ans[sta]=1;
	gl[sta]=1;
	for(int i=2;i<=n;i++)
	{
		if(!fr[i])
		q.push(i);
//		for(int j=head[i];j;j=edge[j].ne)
//		fr[edge[j].to]--;
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to;
			fr[v]--;
			ans[v]+=(ans[u]*mul(to[u],p-2))%p,gl[v]+=gl[u]/to[u];
			ans[v]%=p;
			if(!fr[v]) q.push(v);
		}
	}
	printf("%lld\n",ans[n]%p);
//	printf("%.10lf\n",gl[n]);
}
int main()
{
	freopen("deathsong.in","r",stdin);
	freopen("deathsong.out","w",stdout);
	read(n);read(m);
	for(int i=1,u,v;i<=m;i++)
	{
		read(u);read(v);
		to[u]++,fr[v]++;
		add(u,v);
	}
	dfs(1);
	return 0;
}

题解：

考虑在BFS中，只要一个点入度不为零。这个点的概率就没有更新完。所以按照拓扑序来更新概率。

3．随机游走

  (run.cpp) 
【时空限制】
    时间限制：1.5s
    空间限制：128MB
【问题描述】
给定一棵n个点的无根树，再给定m个询问
每次询问给定起点和终点，从起点开始XJB走到终点的期望步数是多少？
定义XJB走为：每次完全随机选择一条出边走出去，可以走回头路
【输入格式】
    第一行两个整数n,m
    接下来n-1行每行两个整数x,y表示x到y有一条树边
    接下来m行每行两个整数x,y表示询问从x到y的期望步数
【输出格式】
    共m行，每行一个整数表示每次询问的答案
【输入输出样例1】
5 3
1 2
1 3
1 5
3 4
1 4
2 3
1 3	


12
6
5
【输入输出样例2】
10 5
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 5
7 5
7 1
3 9
9 4	


26
23
6
30
1

数据范围

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/5db47501.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！