代理加盟项目_重庆关键词seo排名_卡点视频免费制作软件_杭州seo公司服务

F 期望 三分

• 采取的最优策略是做k次烟花，一次放掉，花的时间是$n\ast k+m$
• 如果这k个烟花至少有一个好的，就去休息，能休息的概率是$P=1-(1-p{)}^k$
• 能不能休息是一个伯努利分布，$x\sim B(P)$，休息期望是$E(k)=\frac{1}{P}$
• 休息前的期望时间是$f(k)=(n\ast k+m)\ast E(k)$，三分求其最小值

double n,m,p,q;
double f(double k){return (n*k+m)/(1-pow(q,k));
}
void solve(){cin>>n>>m>>p;p=p/10000.0,q=1.0-p;double l=1,r=1e9;while (r-l>2){double mid1=l+(r-l)/3,mid2=r-(r-l)/3;if(f(mid1)<=f(mid2))r=mid2;else l=mid1;}double ans=1e32+10;forr(i,l,r){ans=min(ans,f(i));}printf("%.9lf\n",ans);}

K 签到题 构造

• 相邻的必然互质
• 1和任何数都互质
• k<1 输出-1
• k>=1 除了1 再构造k-1个
  • k-1是奇数 从1开始两两交换
  • 偶数 从2开始交换

M 树形dp

• 父节点的hp从子节点中转移过来
• 一开始用魔法杀掉，就是不包含这个点
• 一个节点有 被包含1 不被包含0 两种情况
• dp[状态][节点][已经包含的节点]
• 转移$$\begin{gathered} dp[0][fa][j+k]=min(dp[0][fa][j]+min(dp[0][son][k],dp[1][son][k])),不包含fa(不用加hp[son]) \\ dp[1][fa][j+k]=min(dp[1][fa][j]+min(dp[0][son][k],dp[1][son][k]+hp[son])),包含fa \end{gathered}$$

const int N=2e3+10;
vector<int>son[N];
int dp[2][N][N],hp[N],sz[N];
void dfs(int f){sz[f]=1;for(auto s:son[f]){dfs(s);for(int j=sz[f];j>=0;j--){//父节点 包含的点个数for(int k=sz[s];k>=0;k--){//子节点 dp[0][f][j+k]=min(dp[0][f][j+k],dp[0][f][j]+min(dp[0][s][k],dp[1][s][k]));//不用+hp[s]因为父节点去掉之后不需要把权值加到父结点上dp[1][f][j+k]=min(dp[1][f][j+k],dp[1][f][j]+min(dp[0][s][k],dp[1][s][k]+hp[s]));}}sz[f]+=sz[s];//累计已经遍历的总节点数}
}
void solve(){int n;cin>>n;forr(i,1,n){son[i].clear();forr(j,1,n){dp[1][i][j]=dp[0][i][j]=1e18;}}forr(i,2,n){int f;cin>>f;son[f].push_back(i);}forr(i,1,n){cin>>hp[i];dp[0][i][0]=0;dp[1][i][1]=hp[i];}dfs(1);//包含n个点 就是删去0个点reforr(i,0,n)cout<<min(dp[0][1][i],dp[1][1][i])<<' ';cout<<endl;
}

L 模拟 离散化

必须要输入输出加速才不会超时，太神奇了

• 两个蓝壶之间的红壶一定满足$|c-a_i|<|c-b_j|$，思路就是算红壶在蓝壶之间的最大个数
• 遍历蓝壶的位置，二分查找红壶边界
  一开始没想到用二分 遍历红壶去找的 但是wa2

void solve(){int n,m;cin>>n>>m;map<int,int>r,b;forr(i,1,n){int x;cin>>x;r[x]++;}forr(i,n+1,m+n){int x;cin>>x;b[x]++;}b[1e9+10]=1;int cnt=0,mx=0,lst=0;auto ib=b.begin();for(auto ir:r){if(ir.first<ib->first&&ir.first>lst){cnt+=ir.second;// cout<<ir.first<<' ';}else if(ib->first<=ir.first){// cout<<"--"<<lst<<' '<<ib->first<<endl;mx=max(mx,cnt);lst=ib->first;cnt=0;if(ib->first<ir.first)cnt+=ir.second;ib++;if(ib==b.end())break;}}mx=max(mx,cnt);if(mx==0)cout<<"Impossible"<<endl;else cout<<mx<<endl;
}

正解代码

void solve(){int n,m;cin>>n>>m;vector<int>r(n+1),b(m+2,0);//数组记录位置 离散化forr(i,1,n)cin>>r[i];forr(i,1,m)cin>>b[i];b[m+1]=1e9+10;sort(r.begin()+1,r.end());sort(b.begin()+1,b.end());int mx=0;forr(i,0,m){//二分查找int lp=upper_bound(r.begin()+1,r.end(),b[i])-r.begin();int rp=lower_bound(r.begin()+1,r.end(),b[i+1])-r.begin()-1;// cout<<rp<<' '<<lp<<endl;mx=max(mx,rp-lp+1);}if(mx<=0)cout<<"Impossible"<<endl;else cout<<mx<<endl;
}

H dfs 鸽巢原理

• 题意要求两行或者两列有完全相同，所以先从最小的 符合题意子矩阵——两行两列 开始想
• 鸽巢原理：只考虑两行，一列有$3^2=9$个排列，超出9列就有重复的两列
• 所以max(n,m)>9，任何排列都符合
• n<=9&&m<=9 暴力dfs枚举打表

打表代码

const int M=1e9+7,N=2e3+10;
int re[12][12],tb[12][12],cl[4][12];
int ans;
int n,m;
int fpow(int a,int b){int res=1;while (b){if(b&1)res=(a*res)%M;a=(a*a)%M;b>>=1;}return res%M;
}
bool ok(int x1,int y1,int x2,int y2){return ((re[x1][y1]==re[x1][y2]&&re[x2][y1]==re[x2][y2])||(re[x1][y1]==re[x2][y1]&&re[x1][y2]==re[x2][y2]));
}
bool check(int x,int y,int c){re[x][y]=c;forr(i,1,x-1){forr(j,1,y-1){if(ok(i,j,x,y))return 0;}}return 1;
}
void dfs(int x,int y){if(x>n){ans=(ans+1)%M;return;}if(y>m){dfs(++x,1);return;}forr(i,1,3){cl[i][x]++;if(check(x,y,i)){dfs(x,y+1);}cl[i][x]--;}}
signed main()
{forr(i,1,9){forr(j,1,9){n=i,m=j;ans=0;dfs(1,1);ans=(fpow(3,n*m)-ans+M)%M;tb[n][m]=ans;}}forr(i,0,9){forr(j,0,9)cout<<tb[i][j]<<",";}return 0;
}

太邪门了 我的代码和AC代码差不多一样就是wa2，卡了一小时，太可惜了，好痛苦

int tb[10][10]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,15,339,4761,52929,517761,4767849,43046721,387420489,0,0,339,16485,518265,14321907,387406809,460338013,429534507,597431612,0,0,4761,518265,43022385,486780060,429534507,792294829,175880701,246336683,0,0,52929,14321907,486780060,288599194,130653412,748778899,953271190,644897553,0,0,517761,387406809,429534507,130653412,246336683,579440654,412233812,518446848,0,0,4767849,460338013,792294829,748778899,579440654,236701429,666021604,589237756,0,0,43046721,429534507,175880701,953271190,412233812,666021604,767713261,966670169,0,0,387420489,597431612,246336683,644897553,518446848,589237756,966670169,968803245};int n,m;
int fpow(int a,int b){int res=1;while (b){if(b&1)res=(res%M*a%M)%M;a=(a%M*a%M)%M;b>>=1;}return res%M;
}
void solve(){cin>>n>>m;if(max(n,m)>9)return cout<<1ll*fpow(3,n*m)<<endl,void();if(n==1||m==1)return cout<<0<<endl,void();cout<<tb[n][m]<<endl;}

AC代码

int tb[10][10]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,15,339,4761,52929,517761,4767849,43046721,387420489,0,0,339,16485,518265,14321907,387406809,460338013,429534507,597431612,0,0,4761,518265,43022385,486780060,429534507,792294829,175880701,246336683,0,0,52929,14321907,486780060,288599194,130653412,748778899,953271190,644897553,0,0,517761,387406809,429534507,130653412,246336683,579440654,412233812,518446848,0,0,4767849,460338013,792294829,748778899,579440654,236701429,666021604,589237756,0,0,43046721,429534507,175880701,953271190,412233812,666021604,767713261,966670169,0,0,387420489,597431612,246336683,644897553,518446848,589237756,966670169,968803245};int n,m;
int fpow(int a,int b){int res=1;while (b){if(b&1)res=res*a%M;a=a*a%M;b>>=1;}return res%M;
}
void solve(){cin>>n>>m;if(n==1||m==1)return cout<<0<<endl,void();if(max(n,m)>9)return cout<<1ll*fpow(3,m*n)<<endl,void();cout<<tb[n][m]<<endl;// if(max(n,m)>9)return cout<<1ll*fpow(3,n*m)<<endl,void();// if(n==1||m==1)return cout<<0<<endl,void();// cout<<tb[n][m]<<endl;}