NOIP模拟测试4「礼物·通讯·奇袭」
礼物、
首先见到期望一定要想dp,看到n的范围无脑想状压,
然后我就只想到这了。
dp方程式还是比较好想的,但是我依然想不出来
略经思考 颓题解
依然不会,随便写了个式子
i状态中不含j
$f[i]=\sum_\limits{j=1}^{j<=n} {f[j]\times p[j] }(买到之前没有的) $$+(1-p[i])\times {f[i]}(由自己转移过来(买到已经买过的)) $
$+1(什么也不买)$
显然不是i吖
然后
$f[i]=\sum_\limits{j=1}^{j<=n} {f[j]\times p[j] }(买到之前没有的) $ $+$ $(1-$$\sum_\limits{j=1}^{j<=n}p[j] )$ $\times f[i]+1(店员什么也没拿)$
观察,等式右面也有fi,如果我们楞做就是高斯消元了
那么移项得
$f[i]=$ $\frac{\sum_\limits{j=1}^{j<=n}f[j]\times p[j]+1} {\sum_\limits{j=1}^{j<=n} p[j]}$
转移就完了
代码
#include<bits/stdc++.h>
#define ll long long
#define A 1<<24
double f[A],p[A];
ll n,m,sum=0,Smily;
void turn(ll x,ll n)
{
ll t=x,num=0,xx[100];
while(x) xx[num++]=x%2,x/=2;
for(ll i=num;i<n;i++)printf("0");
for(ll i=num-1;i>=0;i--)printf("%lld",xx[i]);
puts("");
}
using namespace std;
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
scanf("%lf%lld",&p[i],&Smily);
sum+=Smily;
}
printf("%lld\n",sum);
for(ll i=(1<<n)-2;i>=0;i--){
double now=0;
for(ll j=1;j<=n;j++){
if(!((1<<(j-1))&i))
f[i]+=f[i|(1<<(j-1))]*p[j],now+=p[j];
}
// printf("f=%lf now=%lf\n",f[i],now);
f[i]++;
f[i]/=now;
}
// for(ll i=1;i<=(1<<n)-1;i++)
// {
// printf("%lf\n",f[i]);
// }
printf("%.3lf\n",f[0]);
}
通讯
(有向图)有环不花费,没环有花费,求使所有点连通最小花费。(保证从0节点可以到达任何节点&&图是连通的)
一眼秒错解!!!!!!!
打了个缩点+kuskal,然后自己以为能AC然后完美得到10分
题解
正解,贪心+缩点。
因为保证0可以到任何节点
每次取出当前点入边最小值,得到图依然保持连通,所以贪心正确。
代码懒得放
奇袭
题解
https://blog.csdn.net/sadnohappy/article/details/52199051
https://www.cnblogs.com/12mango/p/7465667.html
耐心看完这两篇博客相信你已经大概理解了。
以下是我自己的一些理解,
首先
$n^3$算法
无脑维护前缀和
MLE+TLE
#include<bits/stdc++.h>
#define ll long long
#define A 10100
using namespace std;
ll a[A][A];
bool b[A][A];
ll n,m,ans=0;
const int L=1<<20|1;
char buffer[L],*S,*T;
#define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)
inline int Read(){
register int ret;
register char r;
while(r=getchar(),r<'0'||r>'9');ret=r-48;
while(r=getchar(),r>='0'&&r<='9')ret=ret*10+r-48;
return ret;
}
void dfs(ll k)
{
if(k==n) return ;
for(ll i=1;i<=n-k+1;i++)
for(ll j=1;j<=n-k+1;j++){
if(a[i+k-1][j+k-1]+a[i-1][j-1]-a[i-1][j+k-1]-a[i+k-1][j-1]==k)
ans++/*,printf("k=%lld i=%lld j=%lld a[%lld][%lld]=%lld a[%lld][%lld]=%lld a[%lld][%lld]=%lld a[%lld][%lld]=%lld\n",k,i,j,i+k-1,j+k-1,a[i+k-1][j+k-1],i-1,j-1,a[i-1][j-1],i-1,j+k-1,a[i-1][j+k-1],i+k-1,j-1,a[i+k-1][j-1])*/;
}
dfs(k+1);
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
ll xx=Read(),yy=Read();
b[xx][yy]++;
}
for(ll i=1;i<=n;i++)
for(ll j=1;j<=n;j++)
{a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];}
// cout<<a[2][4]<<endl;
dfs(2);
cout<<ans+n+1<<endl;
}
$n^2$
略微思考,发现可以把它转换为一维的,行列不重复,所以可以用一个a数组存下来值 a[i]就下标代表第一行,具体存的数就代表第j列
那么我们发现从a[i]-a[j]中a中最大值减a中最小如果为j-i那么就符合题目中所说的子矩阵
维护ST表或单调队列维护,严格$n^2$
约55--64分,看你常数大小
减减枝91
$n\times log n$
一个非常玄学做法,
建议结合代码来看,虽然我知道你不想看代码
玄学二分加桶
这还是我第一次遇到这样的题
事实上该做法是$n^2$的一个优化,思路和它类似a[i]-a[j]中a中最大值减a中最小如果为j-i那么就符合题目中所说的子矩阵。
那么我们二分一个区间时有如下情况
1,当前枚举区间最大值最小值都在mid左面
2,当前枚举区间最大值最小值都在mid右面
3,最小值在左面,最大值在右面
4,最大值在右面,最小值在左面
对于1,我们要做的是扫一遍mid以左就完了,我们max-min+i就是当前区间,要判断j是否>mid 因为即使符合<=mid的情况也会在二分时解决(因为全部在左区间),我们找的最大值最小值都在mid左面,并不一定全在左面,有部分在右面
对于2,做法同1
对于3,我们首先先找到了mid以左最小,以及最大,设mid以左最小minl,最大maxl
我们定义两个指针一个minn指针,一个maxx指针,当前指针都指向mid 因为maxx<=maxl我们要满足3最大值在右面只能往右搜。我们需要找到minn>minl最大位置(因为minn往右搜只会越来越小满足单调性),maxx>ml最小位置(maxx越搜只会越来越大满足单调性)。
找到指针指向位置我们可以断定mid--maxx之间所有方案都不符合3,mid--minn之间可能符合3。
宗上那么maxx--minn之间值可能符合3;
对于”“思路和它类似a[i]-a[j]中a中最大值减a中最小如果为j-i那么就符合题目中所说的子矩阵”“ 这句话 移项
maxx-r==minn-l 我们在桶里存maxx-r 然后找到minn-l对应就完了。
对于4,做法同3
以下是本人丑陋的代码
代码
#include<bits/stdc++.h>
#define ll long long
#define A 1100000
using namespace std;
ll tong[A],lmax[A],lmin[A],rmax[A],rmin[A];
ll a[A];
ll n;
ll work(ll l,ll r,ll mid){
ll w=0;
lmax[mid]=a[mid];lmin[mid]=a[mid];
rmax[mid+1]=a[mid+1];rmin[mid+1]=a[mid+1];
for(ll i=mid-1;i>=l;i--){
lmax[i]=max(lmax[i+1],a[i]);
lmin[i]=min(lmin[i+1],a[i]);
}
for(ll i=mid+2;i<=r;i++){
rmax[i]=max(rmax[i-1],a[i]);
rmin[i]=min(rmin[i-1],a[i]);
}
for(ll i=l;i<=mid;i++){
ll j=i+lmax[i]-lmin[i];
if(j>mid&&rmax[j]<lmax[i]&&rmin[j]>lmin[i]) w++;
}
ll p1=mid+1,p2=mid;
while(p1<=r&&rmax[p1]<lmax[l]) tong[rmax[p1]-p1]--,p1++;
while(p2<r&&rmin[p2+1]>lmin[l]) p2++,tong[rmax[p2]-p2]++;
for(ll i=l;i<=mid;i++){
while(p1>mid+1&&rmax[p1-1]>lmax[i]) p1--,tong[rmax[p1]-p1]++;
while(p2>mid&&rmin[p2]<lmin[i]) tong[rmax[p2]-p2]--,p2--;
w+=max(tong[lmin[i]-i],0ll);
}
for(ll i=mid+1;i<=r;i++){
tong[rmax[i]-i]=0;
}
return w;
}
ll solve(ll l,ll r){
if(l==r) return 1;
ll mid=(l+r)>>1;
ll zz=solve(l,mid)+solve(mid+1,r);
zz+=work(l,r,mid);
reverse(a+l,a+r+1);
if((r-l+1)&1) mid--;
zz+=work(l,r,mid);
reverse(a+l,a+r+1);
return zz;
}
int main(){
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
ll xx,yy;
scanf("%lld%lld",&xx,&yy);
a[xx]=yy;
}
cout<<solve(1,n);
}
最新文章
- 责任链模式/chain of responsibility/行为型模式
- linux tar命令的使用
- JQ实现右下角scrollTop()事件
- phpmyadmin中访问时出现2002 无法登录 MySQL 服务器
- java 对象序列化
- sysfs接口整理
- Qss All
- String类中几个简单的常用方法
- tcp断开连接,4次握手,为什么wireshark 只能抓到3个包?
- geoR文档翻译
- 分布式配置管理平台XXL-CONF
- [Swift]LeetCode172. 阶乘后的零 | Factorial Trailing Zeroes
- FTP服务器的安装与配置
- sql截取日期/时间的单独部分,比如年、月、日、小时、分钟等等
- transition,过渡效果
- 2018中国大学生程序设计竞赛 - 网络选拔赛 Dream hdu6440 Dream 给出一个(流氓)构造法
- vue中indexDB的应用
- 关于windows中在env中执行django-admin.py出现Access is denied.的解决办法
- javascript瀑布流效果
- WebGL常用数学公式