SZU寒训day1
introduction
day1的主要内容是贪心、二分、三分、快速幂。本文纯属做个回顾。
贪心
贪心就是用当前最优来替代整体最优啦。但是不是所有地方都可以这么用，要自行证明当前最优时整体解必然最优。
二分
二分查找
时间复杂度：O（logn） 当然很多时候还需要一个O（nlogn）的快排
二分答案
用于答案有一定范围？验证答案的函数是单调的？（比如求minimax或maximin）
时间复杂度：O（k*nlogn）(k是验证答案的时间)
emmm...基本上弱爆了吧
三分
上面说了二分是在单调函数里找某个值，那三分就是在凹函数或者凸函数里面找极值
若f(x)是凸函数，f(M1)>f(M2)时，R取M2，f(M1)<f(M2)时，L取M1。
快速幂
首先来看看求的一般写法。
ans=1; for(int i=0;i<b;i++) ans*=a;
但当要求b超级无敌大的时候，这种三行的代码就显得那么的苍白无力，于是在二进制的启发下有了快速幂。
首先先看一个例子。求怎么做才会快呢？
先拆成乘法，看看有哪些重复运算，把他去掉。
ans=3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 显然这里是一个重复运算，我们算一次
代进去就好
ans=9 * 9 * 9 * 9 显然这里是重复运算，我们算一次
代进去就好
ans=81 * 81=6561
这样我们用了3次乘法就解决了本来8次乘法的问题了。废话就说到这了
上代码
ans=1;
while(b)
{
if(b&1)ans=ans*a;//b&1等价于b%2
b>>=1;//右移1位，等价于b/=2
a=a*a;
} 原理
把b化为二进制数，如果是奇数就证明有一个单独的a不能做重复乘法，所以就把它乘了。于是剩下的a是偶数个，可以化为^(b/2)，此时a*a要重复b遍。所以干脆a=a * a，b/=2，于是就可以变成
，发现没有，又是
。于是就是递归啦！
balabala完了看题
HDU 2037
题意
给你一堆电视节目开始结束时间，输出能完整看到的电视节目的个数。
分析
也就是求没有交集的最多区间，冥冥中有种贪心的感觉。
贪啥呢？贪结束时间，先看结束时间早的（让影响后面的节目最少），然后找这个节目结束后开始的结束时间最早的，循环~
解
按结束时间排序 O（nlogn）
遍历一边 O（n）
总时间复杂度 O（nlogn）
HDU - 5969
题意
给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。
其中|表示按位或。
分析
要研究一下或运算，有1则1，零零得0。
一开始我的想法是让x=r，让y为[l,r)中最大一个，这样y在二进制下就是比r小一位，每位都是1的数，那x|y=2^(k+1)-1显然是最大的。但很快我就发现了一个问题，要是[l,r)中没有
怎么办，显然我的答案只是特殊情况。
解
当[l,r)中没有时，也就是说l跟r二进制下位数相同，那l跟r的二进制形式肯定有左t位相同，第t+1位，r为1，l为0。[l,r]中所有数前t位都会相同，由于|的结果有1则1，r第t+1位为1，|后第t+1位也是1.所以我们只要让y从t+2位开始都是1，而前t+1位与l相同就行。r|y就是答案。（为什么y∈[l,r]呢？）
其实当[l,r)中有时，这个
也是上面所说y的特殊情况。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
unsigned long long n,e[61]={1};
for(int i=1;i<60;i++)
e[i]=e[i-1]<<1;
cin>>n;
while(n--)
{
unsigned long long l,r,w;
cin>>l>>r;
w=(l^r);//使用异或求l，r第一位不同的出现在哪
int wsize=0;
while(w)
{
w>>=1;
wsize++;
}
if(wsize)cout<<((e[wsize-1]-1)|r)<<endl;//前t+1位相同，所以没必要加上了
else cout<<r<<endl;
}
return 0;
} HDU - 1969
题意
我有n个大小不一的蛋糕，f+1个人分，每个人只吃一块the same size的蛋糕。问最多每个人能吃多少？
分析
乍一看就想平均分了，但是不行，人家宁愿扔了剩下的，也只吃从一个蛋糕上来的一块。好像直接没法求一个人能吃多少。但是要是告诉我每个人吃了多少，我可以求出蛋糕够不够吃。
解
二分答案，范围(0,maxpiesize]，但是这一题卡精度卡得十分难受。
代码
#include<stdio.h>
#include<algorithm>
#define PI 3.14159265359//少一位都凉
using namespace std;
double v[10001];
bool comp(double x,double y)
{
return x>y;
}
int main()
{
int n,f,m;
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&n,&f);
f++;
for(int i=1;i<=n;i++)
{
scanf("%lf",&v[i]);
v[i]=v[i]*v[i];
}
sort(v+1,v+n+1,comp);
n=min(n,f);//饼比人数多时，扔掉
double l=0,m,r=v[1];
int cnt;
while(r-l>1e-6)//少一位也凉
{
m=(r+l)/2;
cnt=0;
for(int i=1;i<=n;i++)
if(v[i]>=m)
{
cnt+=v[i]/m;
}
else break;
if(cnt>=f)l=m;
else r=m;
}
printf("%.4f\n",m*PI);
}
} ZOJ - 3203
题意
如图，已知H，h，D，求max（L）
[外链图片转存失败(img-EkK67Ox9-1564909497651)(http://acm.zju.edu.cn/onlinejudge/showImage.do?name=light_bulb_1037_ddd01.gif)]
分析
搞出他的函数出来，发现是凸函数。
解
三分
代码
#include<bits/stdc++.h>
using namespace std;
double H,h,d;
double fi(double x)
{
return (h*d+H*x-d*x-x*x)/(H-x);
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>H>>h>>d;
double l=0,r=h,m1=l+(r-l)/3,m2=m1+(r-l)/3,fim1=fi(m1),fim2=fi(m2);
while(abs(fim1-fim2)>1e-6)
{
if(fim1>fim2)r=m2;
else l=m1;
m1=l+(r-l)/3;
m2=m1+(r-l)/3;
fim1=fi(m1);
fim2=fi(m2);
}
printf("%.3lf\n",fim2);
}
} POJ - 1995
题意
分析
由于数很大，所以要用以下公式
ab%m=(a%m)(b%m)%m
(a+b)%m=a%m+b%m
解
快速幂
代码
#include<iostream>
using namespace std;
int main()
{
int z;
cin>>z;
while(z--)
{
int m,h,a,b,ans=0;
cin>>m>>h;
for(int i=0;i<h;i++)
{
cin>>a>>b;
if(a==0)continue;
int s=1;
a=a%m;
while(b)
{
if(b&1)s=s*a%m;
b>>=1;
a=a*a%m;
}
ans=(ans+s)%m;
}
cout<<ans<<endl;
}
} UVALive - 5009
题意
F(x) = max(Si(x)), i = 1 . . . n. The domain of x is [0, 1000]. Si(x) is a quadric function.
求the minimum of F(x)（x∈[0,1000]）
分析
画画图就知道F(x)是凹函数，于是就可以三分啦。
求f(x)要算一次n个函数，求最大值。
代码
#include<bits/stdc++.h>
#define nmax 10001
int a[nmax],b[nmax],c[nmax],t,n;
using namespace std;
double fi(double x)
{
double ans=a[0]*x*x+b[0]*x+c[0],now;
for(int i=1;i<n;i++)
{
now=a[i]*x*x+b[i]*x+c[i];
if(now>ans)ans=now;
}
return ans;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i]>>b[i]>>c[i];
double l=0.0,r=1000.0,m1=l+(r-l)/3,m2=m1+(r-l)/3,fim1=fi(m1),fim2=fi(m2);
while(abs(fim1-fim2)>1e-6)
{
if(fim1<fim2)r=m2;
else l=m1;
m1=l+(r-l)/3;
m2=m1+(r-l)/3;
fim1=fi(m1);
fim2=fi(m2);
}
printf("%.4lf\n",fim1);
}
} HRBUST - 2176
题意
有N个人口不一的城市要选举，Mac做了M个投票箱。求他制作投票箱的容量最少是多少，才能让每个城市每个人都可以投票。
分析
跟上面分蛋糕差不多，直接好像没法求。那就逆向思维，猜一个投票箱容量，验证一下行不行。
解
二分
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500001];
int main()
{
while(cin>>n>>m&&n!=-1)
{
int max=0,ans;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]>max)max=a[i];
}
int l=1,r=max,mid;
while(l<r)
{
int need=0;
mid=(l+r)>>1;
for(int i=0;i<n;i++)
{
need+=a[i]/mid;
if(a[i]%mid!=0)++need;
}
if(need<=m)r=mid;
else l=mid+1;
}
cout<<l<<endl;
}
} POJ 3641
题意
给出p，a两个数，问p是不是关于a的伪素数（即不是素数但符合费马小定理）
分析
费马小定理 emmm~什么东西？别管，按题目模拟就完事儿。
解
快速幂+判素数
注意要开long long
代码
#include<iostream>
#include<cmath>
using namespace std;
int isprime(long long x)
{
if(x==1)return false;
long long sqr=sqrt(x);
for(long long i=2;i<=sqr;i++)
{
if(x%i==0)return false;
}
return true;
}
int main()
{
long long p,a;
while(cin>>p>>a&&p)
{
if(isprime(p))
{
cout<<"no"<<endl;
continue;
}
long long mod=p,s=1,aa=a;
while(p)
{
if(p&1)s=s*a%mod;
p>>=1;
a=a*a%mod;
}
if(s==aa)cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
} HDU - 1575
题意
A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），求Tr(A^k)%9973。
分析
矩阵快速幂裸题
代码
#include<cstdio>
struct ooo{
int v[15][15];
}A;
int n,k;
ooo square(ooo Y,ooo Z)
{
ooo per;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
per.v[i][j]=0;
for(int k=0;k<n;k++)
per.v[i][j]=(per.v[i][j]+Y.v[i][k]*Z.v[k][j])%9973;
}
return per;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&A.v[i][j]);
ooo ans;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
ans.v[i][j]=0;
ans.v[i][i]=1;
}
while(k)
{
if(k&1)ans=square(ans,A);
k>>=1;
A=square(A,A);
}
int sum=0;
for(int i=0;i<n;i++)
sum=(sum+ans.v[i][i])%9973;
printf("%d\n",sum);
}
} 最后
第一天水题为主。
由于本蒟蒻水平有限，本文仅供参考。（有错轻喷 ）
京公网安备 11010502036488号