关键词：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int n;
int ws(ll x)
{
	int ret=0;
	while(x)++ret,x/=10;
	return ret;
}
struct Num
{
	ll a,b;
	void easy()
		{
			ll d=__gcd(a,b);
			a/=d;b/=d;
		}
	void output()
		{
			easy();
			if(b==1){printf("%lld\n",a);return;}
			ll k=a/b;a-=k*b;
			int blk=ws(k),ss=max(ws(a),ws(b));
			for(int i=1;i<=blk;++i)putchar(' ');
			printf("%lld\n",a);
			printf("%lld",k);
			for(int i=1;i<=ss;++i)putchar('-');putchar('\n');
			for(int i=1;i<=blk;++i)putchar(' ');
			printf("%lld\n",b);
		}
}f[50];
Num operator+(Num a,Num b)
{
	ll d=a.b/__gcd(a.b,b.b)*b.b;
	return (Num){a.a*(d/a.b)+b.a*(d/b.b),d};
}
Num operator*(Num a,Num b)
{
	Num c=(Num){a.a*b.a,a.b*b.b};
	c.easy();
	return c;
}
int main()
{
	n=read();
	f[0]=(Num){0,1};
	for(int i=1;i<=n;++i)
	{
		f[i]=f[i-1]+(Num){1,1};
		f[i]=f[i]+(Num){i-1,n-i+1};
	}
	f[n].output();
	return 0;
}

●洛谷p1291[shoi2002]百事世界杯之旅

题链：https://www.luogu.org/recordnew/show/5861351题解：dp，期望 定义dp[i]表示还剩下i个盖子没收集时，期望还需要多少次才能手机完。 初始值：dp[0]=0 显然对于一个状态，我们随机得到一个盖子，有两种可能： 1.得到了曾经没有的盖子... 查看详情

洛谷p1291百事世界杯之旅

P1291百事世界杯之旅题目描述“……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背包，随声听，更克赴日韩... 查看详情

p1291[shoi2002]百事世界杯之旅(代码片段)

...星的名字。只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背包，随声听，更克赴日韩观看世界杯。还不赶快行动！”你关上电视，心想：假设有n个不同的球星名字，每个名字出现的概率相同... 查看详情

luogup1291[shoi2002]百事世界杯之旅

题目链接luoguP1291[SHOI2002]百事世界杯之旅题解设\(f[k]\)表示还有\(k\)个球员没有收集到的概率再买一瓶，买到的概率是\(k/n\)，买不到的概率是\((n-k)/k\)那么\(f[k]=f[k]*(n-k)/n+f[k-1]*k/n+1\)移向一下\(f[k]=f[k-1]+n/k\)代码#include<cstdio>#inclu... 查看详情

p1291[shoi2002]百事世界杯之旅（概率）(代码片段)

P1291[SHOI2002]百事世界杯之旅设$f(n,k)$表示共n个名字,剩下k个名字未收集到，还需购买饮料的平均次数则有：$f(n,k)=fracn-kn*f(n,k)+frackn*f(n,k+1)+1$移项整理，可得：$f(n,k)=f(n,k+1)+fracnk$根据递推式，可得：$f(n,0)=nsum_k=1^nfrac1k$蓝后g 查看详情

p1291[shoi2002]百事世界杯之旅(代码片段)

传送门期望DP设f[i]表示还有i个名字没得到，集齐所有名字的期望购买次数考虑一次购买的影响：　　如果得到以前没有的名字f[i-1] -> f[i]，如果得到有的名字f[i]->f[i]那么可以得到f[i]=f[i-1]*(n-i)/n +f[i]*i/n+1（+1是因... 查看详情

p1291[shoi2002]百事世界杯之旅-期望

设f[i]表示还剩i个没买，那么可以有式子f[i]=(n-i)/n*f[i]+i/n*f[i-1]+1抽到已经抽到过的，或者是没抽到过的这个状态其实也可以某方面地说成，抽i个的期望花费，但是我这里抽i个不是随便抽i个，而是说如果存在一种方案，这个方案... 查看详情

cogs1224.[shoi2002]百事世界杯之旅（期望概率）

COGS1224.[SHOI2002]百事世界杯之旅★  输入文件：pepsi.in  输出文件：pepsi.out   简单对比 时间限制：1s  内存限制：128MB 【问题描述】 “……在2002年6月之前购买的百事任何饮料的瓶盖上都... 查看详情

shoi2002百事世界杯之旅(代码片段)

题目链接：戳我看到期望，想着不要从前转移。一次后能买到不同种类的概率为\(\fracn-in\)两次后能买到不同种类的概率为\(\fracin\times\fracn-in\)n次后能买到不同种类的概率为\((\fracin)^n\times\fracn-in\)设总期望为\(E=\fracn-in\times1+\fracin\... 查看详情

shoi2002百事世界杯之旅|概率论(代码片段)

题目：SHOI2002若当前已经有了x种，再买一个买到不一样的概率为(n-x)/n，要使这个概率变成1，则至少再买n/(n-x)瓶。1#include<cstdio>2#include<string>34longlongmax(longlongx,longlongy)5returny<x?x:y;678longlonggcd(longlongx,longlongy 查看详情

动态规划

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持... 查看详情

luogu动态规划1动态规划的引入(代码片段)

P1216数字三角形每个节点的值只受左上，右上两节点影响。索引从1开始，避免处理边界问题。intn,ans,a[1005][1005],dp[1005][1005];//pull:dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+dp[i][j];intmain(void) ios::sync_with_stdio(false); cin.tie(0);cout.tie 查看详情

luogu关卡2-16线性动态规划（2017年10月）

任务说明：这也是基础的动态规划。是在线性结构上面的动态规划，一定要掌握。  P1020导弹拦截 导弹拦截 合唱队形 尼克的任务 石子合并 低价购买 多米诺骨牌 查看详情

动态规划合唱队形luogu-(代码片段)

分析做两遍最长上升子序列，在遍历一下，取最大值。AC代码#include<bits/stdc++.h>usingnamespacestd;#definems(a,b)memset(a,b,sizeof(a))typedeflonglongll;inta[105];intdp1[105],dp2[105];inlineintread()intX=0,w=0;charch=0;while 查看详情

algo-17乘积最大（动态规划）(代码片段)

问题描述　　今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。... 查看详情

luogu1472奶牛家谱cowpedigrees[动态规划](代码片段)

一时暴搜一时爽一直暴搜一直爽 cxl居然和我写的同款dfs，天呢菜鸡开始对这题并没有什么想法状态方程死活想不出来还是暴搜好1#include<bits/stdc++.h>2usingnamespacestd;3#definelllonglong4#definergregister5constintN=200,K=100,P=9901;6intn,k,f[K+5... 查看详情

luogu关卡2-15动态规划的背包问题（2017年10月）

任务说明：这是最基础的动态规划。不过如果是第一次接触会有些难以理解。加油闯过这个坎。P1060开心的金明小明的妈妈给小明N元钱，小明想买m件物品，每个物品价值为价格*重要度，求出不超过N元钱的情况下，最多能买多少... 查看详情

luogu3856tjoi2008公共子串[动态规划](代码片段)

[TJOI2008]公共子串f[i][j][k]表示a数组前i个值b数组前j个值c数组前k个值中的本质不同的公共字串有多少个N3 每次都重新计算1#include<bits/stdc++.h>2usingnamespacestd;3#definergregister4constintN=100+5,inf=0x3f3f3f3f;5intn=0,la,lb,lc;6chara[ 查看详情