各路大神齐集，题目难到奇葩。
ACRush滑铁卢500和1000都挂了……
CLJ神犇爆-25……
还有两target是0的，红色爆0一堆……
然后我一进去我的房间，就看到一个熟悉的ID：felix-halim，然后还有个人拼命YM它、YY着到底是谁，突然想起是建这个网站的人：
http://felix-halim.net/uva/hunting.php?id=29277
UVA帝啊T_T(上面是AekdyCoin的号)
不过后来他爆0了。我们房子唯一一个红的也爆0了……
最后本房一共7个人有分，其中有一个是叉人得的分。
其余都是只pass了250pt……
由于我巨慢的手速和思考速度，T_T，我的250只有122.66分了，最后在DIV1里刚刚好200名。
于是rating就涨回去了，终于从Blue Boy变回Yellow Boy了！！！上次由于插件事件爆0那rating跌得叫一个惨啊……
哎，我太蒟蒻了。
给定一个凸多边形包围住另一个凸多边形，外面的凸多边形上的每个点都向离自己的最远的在外凸多边形上的点连一条线。然后问，随意取一个在外凸多边形上的点，有多少的概率能取到对应线段与内多边形相交的点。
然后规模是TC的老规矩：50
然后算法就是暴力T_T。但是我暴力好像都写得很长。
第一步：
枚举每条外多边形上的边Point[i]->Point[i+1]，然后再枚举Point[j]和Point[k]，然后搞Point[j]->Point[k]的中垂线(这个有模板T_T)，这个中垂线跑回来和Point[i]->Point[i+1]求交点(没交点就算了)。然后将这些交点按到Point[i]的距离排个序，去重。然后对于这个交点序列，每个点到下一个点形成了线段，然后就找一个到线段离两个端点最远的Point[t]，然后这个线段对应的最远点就是Point[t]了。
第二步：
枚举外多边形上的点Point[i]，然后枚举内多边形上的点，找到一左一右两个交点L和R(可以加多一层循环判是不是所有点都在它左边或者右边)，然后向量Point[i]->L和向量Point[i]->R所夹的位置，就是能够穿过内多边形所对应的位置。然后枚举第一步求的交点序列，如果相邻交点间线段对应的最远点是Point[i]，那么就用Point[i]->L和Point[i]->R这两个直线向它求交点，然后分情况讨论一下(我这里好像显然写长了)。
T_T，幸好调对第一个样例以后就Y了，不然得Debug个半死。
【CODE】
const double eps=1e-9;
int sign(double x){
if (x<-eps) return -1;
if (x> eps) return1;
return0;
}
int m,n;
struct TPoint{
double x,y;
TPoint operator + (TPoint oth){
TPoint ret;
ret.x=x+oth.x;
ret.y=y+oth.y;
return ret;
}
TPoint operator – (TPoint oth){
TPoint ret;
ret.x=x-oth.x;
ret.y=y-oth.y;
return ret;
}
TPoint operator * (double oth){
TPoint ret;
ret.x=x*oth;
ret.y=y*oth;
return ret;
}
booloperator != (TPoint oth){
return (sign(x-oth.x)!=0 || sign(y-oth.y)!=0);
}
booloperator == (TPoint oth){
return sign(x-oth.x)==0 && sign(y-oth.y)==0;
}
doubleoperator ^ (TPoint oth){
return x*oth.y-y*oth.x;
}
}Site[55],Dep[55];
struct TLine{
double a,b,c;
};
TPoint Rot90(TPoint A){
TPoint ret;
ret.x=-A.y;
ret.y=A.x;
return ret;
}
TLine Get_Line(TPoint A,TPoint B){
TLine ret;
ret.a=A.y-B.y;
ret.b=B.x-A.x;
ret.c=B.y*A.x-B.x*A.y;
return ret;
}
TPoint jiao(TLine A,TLine B){
TPoint ret;
ret.x=(A.b*B.c-A.c*B.b)/(A.a*B.b-B.a*A.b);
ret.y=(A.c*B.a-A.a*B.c)/(A.a*B.b-B.a*A.b);
return ret;
}
double dis(TPoint A,TPoint B){
return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}
pair
TLine L2=Get_Line(A,B);
if (sign(L.a*L2.b-L2.a*L.b)==0) return ret;
else{
ret.first=jiao(L,L2);
if (sign(min(A.x,B.x)-ret.first.x)<=0 && sign(ret.first.x-max(A.x,B.x))<=0
&& sign(min(A.y,B.y)-ret.first.y)<=0 && sign(ret.first.y-max(A.y,B.y))<=0){
if (ret.first==A || ret.first==B) return ret;
ret.second=true;
return ret;
}
}
return ret;
}
vector
bool cmp(TPoint A,TPoint B){
return dis(A,Site[tttt])
void Div_part(){
int i,j,k,p;
for (i=0;i
Cut[i].push_back(Site[i]);
Cut[i].push_back(Site[(i+1)%m]);
for (j=0;j
TPoint dir=Rot90(Site[j]-Site[k]);
pair
}
tttt=i;
sort(Cut[i].begin(),Cut[i].end(),cmp);
TV.clear();
for (j=0;j
Cut[i]=TV;
best[i].clear();
for (p=0;p
for (j=1;j
now=j;
best[i].push_back(now);
}
}
}
double ans;
void Rush(){
int i,j,k,L,R;
for (i=0;i
for (k=0;k
if (check) { L=j; break; }
}
for (j=0;j
for (k=0;k
if (check) {R=j; break;}
}
for (j=0;j
pair
TPoint Rp=Cut[j][k+1];
if (crossL.second){
if (crossR.second)
ans+=dis(crossL.first,crossR.first);
else{
if (sign( (Dep[L]-Site[i])^(Lp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Lp-Site[i]) )>=0 )
ans+=dis(Lp,crossL.first);
else
ans+=dis(Rp,crossL.first);
}
}
else{
if (crossR.second){
if (sign( (Dep[L]-Site[i])^(Lp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Lp-Site[i]) )>=0 )
ans+=dis(Lp,crossR.first);
else
ans+=dis(Rp,crossR.first);
}
else{
if (sign( (Dep[L]-Site[i])^(Lp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Lp-Site[i]) )>=0
&& sign( (Dep[L]-Site[i])^(Rp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Rp-Site[i]) )>=0)
ans+=dis(Lp,Rp);
}
}
}
}
}
class Deposit {
public:
double successProbability(vector
n=depositX.size();
for (int i=0;i
Site[i].y=siteY[i];
}
for (int i=0;i
Dep[i].y=depositY[i];
}
double Sum=0;
for (int i=0;i
Div_part();
Rush();
return ans/Sum;
}
};
55555，当时在学校没法捉……
250
有n只兔子，其中k(k<=n)只说了话，说话的形式如：和我一样颜色的有A[i]只！
然后问，满足这些话的情况下，n最小能是多少。
就是A[i]一样的贪心组合在一起即可。
550
给定一个数组A[i](i=0~n-1)，假设你操作的序列是B[i](i=0~m-1)。
初始时m=1,B[0]=0
然后有3种操作:
1、将某个B[i] +1
2、将某个B[i] -1
3、选一个i然后
for (int j=m;j>i;j–) B[j]=B[j-1];
m++;
然后问最少进行多少操作，B[i]能和A[i]一样。
只要注意到复制以后，i和后面就可以断绝联系，这个区间dp的形式还是很明显的，F[i,j,k]表示区间[i,j]由一个初始时B[i]=k的复制而成至少需要多少次操作，然后枚举复制的位置和复制的长度就可以转移了。O(n^5) TC服务器无压力T_T
还有一种神贪心：
int getMinimum(vector int ret=lines[0]+lines.size()-1; for (int i=1;i if (lines[i]>lines[i-1]) ret+=lines[i]-lines[i-1]; return ret; } 暂时只证明了他的充分性，必要性不会证T_T 1000 这个我觉得是我见过最简单的1000了啊啊啊T_T。 注意它可以交换相邻两个，那么你想想冒泡排序吧，于是所有的顺序都可以排出来了。所以用数量就可以描述一个点。 Tarjan缩环(注意缩完以后已经是拓扑序的了)，然后dp求最长路就行了。每个点权就是k!/(pA! * pB! *pC! *pD!) pA表示’A’的数量……
给定一个10000*10000的区域，然后给出一些向量，要找一个最大的区域，区域中的点都满足在这个大区域内，并且对每个向量满足在其左手边。
就是裸的半平面交啊……看了ZZY的论文跟着写WA到半死。后来由叉姐精心指导下，围观了神奇的优化版，不再需要上下凸壳合并T_T(这就是ZZY那算法最容易错的地方了)
记录一下算法的流程：
一开始按atan2来极角排序，极角一样的两个半平面选择那个限制得最紧的那个，其它删掉。
然后就按顺序枚举每一个半平面把它们尝试都交起来，并用一个双端队列保存有效的半平面。
可见如果当前半平面如图所示，那么队列就要pop_back了。这个判定的标准是队尾两个半平面的交点不在当前半平面所需要的平面内。
而如果出现如图的半平面，队列就要pop_front了。这个的判定标准是队头两个半平面的交点在当前半平面所的需求之外。
然后还有一堆疑问。
1、G++ WA C++ AC
2、中间枚举删边时还必须先做pop_back再做pop_front，否则会WA。影响这个只有一种可能，就是队中只剩两个半平面，并且它们的交点在当前半平面的需求之外，先pop_front会是前面的被删掉，而先pop_back会是后面的被删掉。那么围观此图，容易发现pop_back才是正确的。
差不多就这样。
【CODE】
constdouble eps=1e-9;
inline
int sign(double x){
if (x<-eps) return -1;
if (x> eps) return 1;
return0;
}
struct TPoint{
double x,y;
inline
TPoint operator + (TPoint oth){
TPoint ret;
ret.x=x+oth.x;
ret.y=y+oth.y;
return ret;
}
inline
TPoint operator – (TPoint oth){
TPoint ret;
ret.x=x-oth.x;
ret.y=y-oth.y;
return ret;
}
inline
doubleoperator ^ (TPoint oth){
return x*oth.y-y*oth.x;
}
};
struct TLine{
TPoint p1,p2;
double angle;
};
struct abcLine{
double a,b,c;
};
inline
abcLine Get_Line(TPoint A,TPoint B){
abcLine ret;
ret.a=A.y-B.y;
ret.b=B.x-A.x;
ret.c=B.y*A.x-B.x*A.y;
return ret;
}
inline
TPoint jiao(TLine AA,TLine BB){
TPoint ret;
abcLine A=Get_Line(AA.p1,AA.p2);
abcLine B=Get_Line(BB.p1,BB.p2);
ret.x=(A.b*B.c-A.c*B.b)/(A.a*B.b-B.a*A.b);
ret.y=(A.c*B.a-A.a*B.c)/(A.a*B.b-B.a*A.b);
return ret;
}
deque
bool cmp(TLine A,TLine B){
int ret=sign(A.angle-B.angle);
if (ret>0) returntrue;
if (ret<0) returnfalse;
if (sign((B.p2-B.p1)^(A.p1-B.p1))>=0) returntrue;
elsereturnfalse;
}
inline
bool check(TLine p0,TLine p1,TLine p2){
TPoint cross=jiao(p0,p1);
return sign((p2.p2-p2.p1)^(cross-p2.p1))>0;
}
void solve(){
int i;
for (i=0;i
Q.clear();
sort(L.begin(),L.end(),cmp);
for (i=0;i
L=Q; Q.clear();
for (i=0;i
while (S>=2 && !check(Q[0],Q[1],L[i])) Q.pop_front();
Q.push_back(L[i]);
}
while (S>=2 && !check(Q[S-2],Q[S-1],Q[0])) Q.pop_back();
while (S>=2 && !check(Q[0],Q[1],Q[S-1])) Q.pop_front();
#undef S
convex.clear();
if (Q.size()<2) return;
for (int i=0;i
}
inline
void add(double x1,double y1,double x2,double y2){
TLine ret;
ret.p1.x=x1;
ret.p1.y=y1;
ret.p2.x=x2;
ret.p2.y=y2;
L.push_back(ret);
}
int main(){
double x1,y1,x2,y2;
int n;
scanf("%d",&n);
L.clear();
for (int i=0;i
add(x1,y1,x2,y2);
}
add( 0, 0,10000, 0);
add(10000, 0,10000,10000);
add(10000,10000, 0,10000);
add(0, 10000, 0, 0);
solve();
double ans=0;
if (Q.size()>2){
for (int i=0;i
}
ans/=2;
if (ans<0) ans=-ans;
printf("%.1lfn",ans);
}
一个数认定为DePrimes当且仅当该数的所有素因子之和为素数。
比如说n=p1^k1 * p2^k2 * p3^k3 那么就要求p1+p2+p3为素数。
然后给出询问a,b，问[a,b]内有多少个这个数。2<=a,b<=5000000
当然这个题目本身暴力O(n lg n)的筛预处理，顺便算出因子和就可以过。
然后记得上次看到JZP神犇blog上的有提到线性筛( O(n) )，那么考虑用到这里。
这个线性筛的基本思想是让每个数字只被它的最小素因子筛到。
下面利用本题代码写个小介绍以防忘记。
void init(){
int i,j;
memset(low,0,sizeof(low)); //low[i]里存的是i的最小素因子，特别地，若i是素数，那么low[i]=0
memset(sum,0,sizeof(sum)); //储存i的素因子和
low[0]=low[1]=1;
for (i=2;i<=5000000;i++){
if (!low[i]) {pl[cnt++]=i; sum[i]=i;} //i为素数，那么加入素数表，并令它的素因子和为i
for (j=0;j /* 这里(!low[i] || pl[j]<=low[i])就是最精髓的地方 这样保证了每次筛的新数pl[j]*i，其最小素因子是pl[j]， 所以假如x不是素数，令low为x的最小素因子，则x只能以x/low * low这种形式被筛到 */ low*i]=pl[j]; sum*i]=sum[i]; if ((low[i] && pl[j]!=low[i]) || (!low[i] && i!=pl[j])) sum*i]+=pl[j]; } } ret[0]=ret[1]=0; for (i=2;i<=5000000;i++) ret[i]=ret[i-1]+(!low[sum[i]]); } int main(){ init(); int a,b; while (1){ scanf("%d",&a); if (a==0) break; scanf("%d",&b); printf("%dn",ret[b]-ret[a-1]); } } 有了low这个数组，分解素因子也将能在O(lg n)的时间内完成。