Day4

2018-08-21

字数统计: 847字 | 阅读时长: 4min

测试

1.nember

给定一个1~n的排列，每次可以对该排列进行这样的操作：
从排列中任意拿出一个数，放在该序列的最前面。
问至少经过多少次操作，可以使该排列变为1，2，3……n-1，n。

输入：

输出：

3
0

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

n - 与 n 连续的最长长度就是答案。另可用next_permutation（a,a+n）来求全排列。

2. sort

sort

#include<bits/stdc++.h>
using namespace std;
char s[1010][1010];
int n,in[26];
struct node
{
	int ne,to;
}edge[1000000];
int head[1000],cnt,tmp;
char ans[26];
void add(int u,int v)
{
	edge[++cnt].to=v;
	edge[cnt].ne=head[u];
	head[u]=cnt;
}
void topu()
{
	priority_queue<int,vector<int>,greater<int> > q;
	for(int i=0;i<26;i++)
	if(!in[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.top();
		q.pop();
		ans[tmp++]=u+'a';
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to;
			in[v]--;
			if(!in[v]) q.push(v);
		}
	}
}
int main()
{
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%s",s[i]);
	for(int i=1;i<n;i++)
	{
		int len=strlen(s[i]);
		for(int j=0;j<len;j++)
		{
			if(s[i][j]!=s[i+1][j])
			{
				add(s[i][j]-'a',s[i+1][j]-'a');
				in[s[i+1][j]-'a']++;
				break;
			}
		}
	}
	topu();
	if(strlen(ans)<26) printf("Impossible\n");
	else printf("%s\n",ans);
	return 0;
}

这是一道topo排序的题，用小根堆维护其字典序最小。

3.seq

给定一个长度为n的序列， A与B 随机从序列中拿一个数（放回）谁的大算
谁赢，比赛三局两胜，已知A与B的比赛结果为前两局A胜，第三局B胜。求这
三局B取得数的和比A取得数的和大的概率。

输入：

3
1 2 10

输出：

0.0741（保留4位小数）

#include<bits/stdc++.h>
using namespace std;
int a[2001],maxx;
double f[10000],F[10000],ans;
int cmp(int a,int b)
{
	return a>b;
}
int main()
{
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n,cmp);
	maxx=a[1]-a[n];
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(a[i]>a[j]) f[a[i]-a[j]]++;
	for(int i=1;i<=maxx;i++)
		f[i]/=(double)(n*(n-1)/2);
	for(int i=1;i<=maxx;i++)
		for(int j=1;j<i;j++)
			F[i]+=f[i-j]*f[j];
	for(int i=1;i<=maxx;i++) F[i]+=F[i-1];//前缀和
	for(int i=1;i<=maxx;i++)
		ans+=F[i-1]*f[i];//相当于f[i]*(F[0]+F[1]+....+F[i-1]);
	printf("%.4f",ans);
	return 0;
}

概率DP题QWQ，f[i]记录第一局A比B 大i的概率，F[i]则记录第二局的。用f[i]来推F[i]，最后F[i]并枚举第三局B的得分（其实就是f[i]）;

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