Jan.19th
注：黑粗体为超链接
一开始强行Floyd
然后发现这样的话会忽略掉大的不能放到小的上的限制
然后就用记忆化搜索
Fn,s,t表示把n个盘子从第s根柱子移到第t根柱子所需的最小代价
然后每次搜索的时候因为最下面那个盘子不能随便换，
所以考虑它怎么移到目标位置
有两种方法：
第一种就是直接移到目标柱子
还有一种就是移到另一根柱子，再移到目标柱子
就这样咯
C++ Code
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int n,d[4][4]; ll f[45][4][4]; ll Solve(int n,int s,int t){ if (~f[n][s][t]) return f[n][s][t]; if (n==1) return f[n][s][t]=min(d[s][t],d[s][6-t-s]+d[6-t-s][t]); ll met1=Solve(n-1,s,6-t-s)+d[s][t]+Solve(n-1,6-t-s,t); ll met2=Solve(n-1,s,t)+d[s][6-t-s]+Solve(n-1,t,s)+d[6-t-s][t]+Solve(n-1,s,t); return f[n][s][t]=min(met1,met2); } int main(){ Rep(i,1,3) Rep(j,1,3) d[i][j]=IN(); n=IN(); memset(f,-1,sizeof f); printf("%I64d\n",Solve(n,1,3)); } |
基础二维DP
我错了……我只是看到yb和阳神做了这题也去做做看……然后发现是比大小 :-D
$F_{i,j}$表示以$i$为最后一个数的和为$j$的连续子序列有多少种
$Ans=\sum_{i=1}^{n}F_{i,0}$
我们可以发现排序中的最小数在它的这个排序的价值中出现的次数就是包含它的子串数量
然后我们必须让这个数量尽量小
所以这个最小数必须放最左边或者最右边
然后第二小也要放剩下的序列中最左边或者最右边
然后依次递归就行了
C++ Code
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } ll zs[55],m; int a[55],n; void Solve(int l,int r,ll m,int now){ if (now==n+1) return; if (m<=zs[r-l]){ a[l]=now; Solve(l+1,r,m,now+1); } else{ a[r]=now; Solve(l,r-1,m-zs[r-l],now+1); } } int main(){ scanf("%d%I64d",&n,&m); zs[1]=1;Rep(i,2,n) zs[i]=zs[i-1]*2ll; Solve(1,n,m,1); Rep(i,1,n) printf("%d ",a[i]); } |
枚举第二大数记为x
然后分为两种情况
一种就是最大的比x大，剩下的都≤x，其中有至少一个等于x
这种情况可以枚举最大的 然后概率就是
P ( 最大的大于x ) * ( P ( 剩下的全都≤x ) - P ( 剩下的全都<x )
第二种就是最大的也等于x，那么至少有2个x
概率就是↓
P ( 全都≤x ) -P ( 全都<x ) - P ( 一个恰好为x，另外的全都<x )
然后相信大家都会了XD
C++ Code
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int n,l[6],r[6]; double Solve(int val){ double ret=0; Rep(i,1,n){ if (r[i]<val) continue; bool f1=1,f2=0; Rep(j,1,n) if (j!=i){ if (l[j]<=val&&r[j]>=val) f2=1; if (l[j]>val) f1=0; } if (!f1||!f2) continue; double Prob=l[i]>val?1:1.0*(r[i]-val)/(r[i]-l[i]+1); double Prob1=1,Prob2=1; Rep(j,1,n){ if (r[j]<val||j==i) continue; Prob1*=1.0*(val-l[j]+1)/(r[j]-l[j]+1); Prob2*=1.0*(val-l[j])/(r[j]-l[j]+1); } ret+=(Prob1-Prob2)*Prob; } return ret; } double Solve2(int val){ bool f1=1,f2=0; Rep(i,1,n){ if (l[i]<=val&&r[i]>=val) f2=1; if (l[i]>val) f1=0; } if (!f1||!f2) return 0; double Prob1=1.0,Prob2=1.0,Prob3=0; Rep(i,1,n){ if (r[i]<val) continue; Prob1*=1.0*(val-l[i]+1)/(r[i]-l[i]+1); Prob2*=1.0*(val-l[i])/(r[i]-l[i]+1); } Rep(i,1,n){ if (l[i]<=val&&val<=r[i]){ double tsg=1.0/(r[i]-l[i]+1); Rep(j,1,n){ if (j==i||r[j]<val) continue; tsg*=1.0*(val-l[j])/(r[j]-l[j]+1); } Prob3+=tsg; } } return Prob1-Prob2-Prob3; } int main(){ n=IN(); int Max=0; Rep(i,1,n) l[i]=IN(),r[i]=IN(),Max=max(Max,r[i]); double Ans=0; Rep(i,1,Max) Ans+=(Solve(i)+Solve2(i))*i; printf("%.13lf\n",Ans); } |
一开始想用$O(1)$的没想出来
然后干脆直接枚举每一行把它圆内最外围的点坐标算出来搞一搞就好了
时间复杂度$O(n)$
C++ Code
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int n; int main(){ n=IN(); if (n==0) return puts("1"),0; ll lx=n,Ans=0; double sqn=1.0*n*n; Rep(y,1,n){ int x=(int)sqrt(sqn-1.0*y*y); if (x==lx) Ans++; else Ans+=lx-x; lx=x; } printf("%I64d\n",Ans*4); } |
状压+概率DP……蛋炸
状压ntni表示哪几个串i这几位是一模一样的
dpi表示问成i这几位都知道的概率
具体见代码 不是很说得清
C++ Code
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #include<cmath> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } ll mi[51],ntn[(1<<20)+5]; double dp[(1<<20)+5]; int n,len; char s[55][25]; int Count(ll x){ int ret=0; while (x){ret++;x&=(x-1);} return ret; } int main(){ mi[0]=1;Rep(i,1,50) mi[i]=mi[i-1]<<1; n=IN(); Rep(i,0,n-1) gets(s[i]); len=strlen(s[0]); Rep(i,0,n-2) Rep(j,i+1,n-1){ int same=0; Rep(k,0,len-1) if (s[i][k]==s[j][k]) same|=mi[k]; ntn[same]|=mi[i]|mi[j]; } Per(i,mi[len]-1,0) Rep(j,0,len-1) if (i&mi[j]) ntn[i^mi[j]]|=ntn[i]; double Ans=0; dp[0]=1; Rep(i,0,mi[len]-1){ Ans+=dp[i]*Count(ntn[i]); int cnt=Count(1ll*i); if (ntn[i]) Rep(j,0,len-1) if (!(i&mi[j])) dp[i|mi[j]]+=dp[i]/(len-cnt); } printf("%.15lf\n",Ans/n); } |
Jan 27, 2024 05:32:12 PM
JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.