DTOJ 10.23 测试

2019-04-14 12:19发布

站内文章 / 模拟电子
16984 0 942
T1:浮躁(fickle)
【问题描述】
阿杰在上班会数学课：“最近有些同学很浮躁……”
早已习惯的你，在想这样一个问题：
共有n 种竞赛，对于其中任意i 种竞赛(1≤i≤n)，有a_{i} 个人同时参加，问有多
少个人参加了至少一门竞赛？
阿杰还在滔滔不绝，你却陷入了深思。
【输入格式】
从文件fickle.in 中读入数据。
输入的第一行包含一个正整数n，第二行包含n个整数a_{i}。n和a_{i}的含义见问
题描述。
【输出格式】
输出到文件fickle.out 中。
输出一行一个整数，表示至少参加了一门竞赛的人数。
【样例输入】
3 1
0 3 1
【样例输出】
22 数据规模：n leq 10^5 ,a_{1} imes n leq 10^9

题解：这真TM是个沙雕 好 题: 首先可以看出，这是个组合数的东西，容斥的基本操作。 但是，这题坑点在于，他没给模数，同时 又让你求这沙雕组合数 于是，我们还注意到一点，a_{1} imes n <10^9 所以它最后答案一定小于这个数。 所以我们得加一个取模，大概是在 10^9 左右。 我加了个10^9+7（ps.不加模数爆了50pts）
#include using namespace std; #define in inline #define re register #define rep(i,a,b) for(re int i=a;i<=b;i++) #define repd(i,a,b) for(re int i=a;i>=b;i++) #define For(i,a,b) for(re int i=a;iin void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;} typedef long long ll; const int N=1e5+4;const ll mod=1e9+7; in ll qp(ll x,ll y){ ll res=1; while(y){ if(y&1) res=res*x%mod; x=x*x%mod;y>>=1; }return res%mod; } ll ans,n,a[N]; int main(){ g(n); rep(i,1,n) g(a[i]); ll C=n; rep(i,1,n){ ans+=C*((i&1)?1:-1)*a[i]%mod;(ans+=mod)%=mod; C=C*(n-i)%mod*qp(i+1,mod-2)%mod; }return !printf("%lld ",ans%mod); }
T2:想象一下(imagine)
【问题描述】
我们高大的老班举起了有半个他那么高的三角板，说：“你们想象一下——”
于是你就陷入了想象……
有一棵n 个点的树，每个叶子节点上都有一个人，他们按照每秒钟走一条边的
速度向树根（节点1）前进。
你可以运用k 次想象之力，让某一个节点（除了根节点）上的所有人瞬间（耗
时为0）转移到这个节点的父亲上。
你想知道最少需要多少时间，所有人可以到达根节点。
【输入格式】
从文件imagine.in 中读入数据。
输入的第一行包含两个整数n,k，含义见问题描述。
接下来n-1 行，第i 行一个整数fai，表示节点i 的父亲为fai。
【输出格式】
输出到文件imagine.out 中。
输出一行一个整数，表示所有人到达根节点最少需要的时间。
【样例1 输入】
6 2
1 2 2 2 4
【样例1 输出】
1
【样例1 说明】
一开始，在节点3,5,6 上分别有一个人，我们称他们为A,B,C。
时刻0，在节点6 运用想象之力，A 到达节点4。
第1 秒，A,B,C 走到节点2。
时刻1，在节点2 运用想象之力，A,B,C 到达节点1，即目的地。
共用时1 秒。 数据规模：n leq 10^5,k<n
题解： 我们可以发现，从每个叶子节点往根走的路上，若路径上的边越靠近根，则用能量走过这条边肯定会比用能量走靠近叶子节点的边更优，所以我们考虑从每个叶子节点往根走，优先用耗时走完靠近叶子的边，用能量走完靠近根的边。
#include using namespace std; #define in inline #define re register #define rep(i,a,b) for(re int i=a;i<=b;i++) #define repd(i,a,b) for(re int i=a;i>=b;i++) #define For(i,a,b) for(re int i=a;iin void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;} const int N=5e5+4; int n,k; struct E{ int to,nxt; }e[N<<1]; int head[N],tot,d[N],fa[N],dep[N],ans;queueq; in void ins(int x,int y){e[++tot]=E{y,head[x]},head[x]=tot;} int main(){ g(n),g(k); rep(i,2,n){int x;g(x);ins(x,i);d[x]++;fa[i]=x;} rep(i,1,n) if(!d[i]) q.push(i),dep[i]=1; int cnt=0; while(!q.empty()&&cnt
T3:超简单(super)
【问题描述】
有一个n 面的骰子，第i 面的数是vi，朝上的概率是pi。
教室的最后一排有一个人，不停地抛这个骰子，直到某一面朝上了两次，就停
止抛骰子，但他不知道所有朝上的面的数字的和的期望E 是多少。
老班一脸嘲讽：“这不是超简单嘛。”
【输入格式】
从文件super.in 中读入数据。
输入的第一行包含一个正整数n。
输入的第二行包含n 个正整数，表示vi。
输入的第三行包含n 个非负整数，表示模998244353 意义下的pi，保证所有
pi 的和为1。
n,vi,pi 的含义见问题描述。 【输出格式】 输出到文件super.out 中。
输出一行一个非负整数E 表示模998244353 意义下的E。 【样例输入】
2 1    2 332748118 665496236 【样例输出】 961272344 数据范围： n leq 500  v_{i},p_{i} <998244353
 题解： 考虑暴力： 我们可以枚举两次朝上的第几面，假设它是第i面，则剩下的就是一个含i的序列，答案就是： ans=sum_{i=1}^{n} (1....n)中含i的子集ssum (p_{i} imes P_{s})(v_{i} + V_{s}) P_{s} 是s中所有p_{i }的乘积，V_{s}是s中所有v_{i}的乘积 这样效率肯定是过不去的。 于是我们考虑以下DP: 设f_{i,j} 表示在前i面中选中j面的期望， h_{i,j}则表示表示在前i面中选中j面的概率。 考虑那个暴力式子,假设已经算完前i-1位，当计算到第i位时，并且加入到当前序列设为s中： p_{i}*P_{s}*v_{i}+V_{s}*p_{i}*P_{s}=h_{i-1,j-1} imes v_{i} imes p_{i}+f_{i-1,j-1} imes p_{i} h_{i,j}=h_{i-1,j} imes p_{i} 再加上当第i位不算到当前序列中，可以得到： f_{i,j}=f_{i-1,j} + f_{i-1,j-1} imes p_{i}+h_{i-1,j-1} imes p_{i} imes v_{i} h_{i,j}=h_{i-1,j}+h_{i-1,j-1}*p_{i} 于是通过这个DP,我们求出来了这个P_{s},V_{s} 于是我们来考虑以下这可爱的ans(QAQ)： 我们来枚举对于哪个面出现了两次，计算就类似暴力的式子，即： ans=sum_{i=1}^{n} sum_{j=1}^{n} (f_{n-1,j} *p_{i}^2+h_{n-1,j}*p_{i}^2 imes 2 ims v_{i}) imes (j+1)! 并且为了算出f_{n-1,j},对于那个DP式做了个方程, f_{n-1,j}=f_{n,j}-f_{n-1,j-1} imes p_{i}-h_{i-1,j-1} imes p_{i} imes v_{i} h_{n-1,j}=h_{n,j}-h_{n-1,j-1} imes p_{i} 细节见代码。
#include using namespace std; #define in inline #define re register #define rep(i,a,b) for(re int i=a;i<=b;i++) #define repd(i,a,b) for(re int i=a;i>=b;i++) #define For(i,a,b) for(re int i=a;iin void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;} typedef long long ll; const int N=504; const ll mod=998244353; ll v[N],p[N],n,f[N][N],h[N][N],fac[N],ans; int main(){ g(n); rep(i,1,n) g(v[i]); rep(i,1,n) g(p[i]); fac[0]=1; rep(i,1,n) fac[i]=fac[i-1]*i%mod; rep(i,0,n) h[i][0]=1; rep(i,1,n){ rep(j,1,i){ f[i][j]=f[i-1][j]+f[i-1][j-1]*p[i]%mod+h[i-1][j-1]*p[i]%mod*v[i]%mod; (f[i][j]+=mod)%=mod; h[i][j]=(h[i-1][j]+h[i-1][j-1]*p[i]%mod)%mod; (h[i][j]+=mod)%=mod; } } rep(i,1,n){ ll P=p[i],V=v[i]; rep(j,1,n){ f[n-1][j]=f[n][j]-f[n-1][j-1]*P%mod-h[n-1][j-1]*P%mod*V%mod; (f[n-1][j]+=mod)%=mod; h[n-1][j]=h[n][j]-h[n-1][j-1]*P%mod; (h[n-1][j]+=mod)%=mod; }n--; rep(j,0,n){ ll tmp=f[n][j]*P%mod*P%mod; tmp%=mod; tmp=tmp+h[n][j]*P%mod*P*2%mod*V%mod; tmp%=mod; ans=ans+fac[j+1]*tmp%mod; ans%=mod; }n++; } return !printf("%lld ",(ans%mod+mod)%mod); }  

热门文章