coci&&contest
&&& 这两天做了coci
#4的后三题，我表示如果让我在3个小时内做完这3题是不可能地，尽管我现在都做好了，但是时间：加上读题大概花了5个多小时，看来我跟卓亮等神牛还有很大差距地啊！3小时的话，大概我只能做前4题咯，继续努力啊！
problem4:OGRADA
题目大意：给定长度相同的两个数串A和B，要求把数列B重新排列，使得排列后的B与A相似，并且要B串中相邻两个的差的绝对值的和最大。相似的定义：同一位置与其相邻位置的大小关系要一致。即假设A[i]&A[i-1]，则B[i]&b[i-1]。
这题我想了很久，起码有1个多小时，最后才发现其实这题是比较简单的。说说我的思考过程，一看到这题，我表示没什么想法，我试图按照某种顺序来考虑B串的排列，从大到小来、从小到大？不行啊，要相似啊！要保证相似，我的第二想法是先构造出一个相似的，再来调整。怎么调整？调整不了啊！想了好一会儿也没什么好的思路，最近几个月，我学到了一种很不错的思考方法：当想不下去时，回到原点。现在我想不下去了，于是重新看一看问题。问题是什么：是要求相邻的差的绝对值的和最大，是要求这个。然后我画了一个图，把图简化（连续上升的看成一个点）以后，发现这个图是一凸一凹的，而要求的答案就是这些上凸点与下凸点的差的和最大。到了这里，问题就迎刃而解了，很容易证明应该贪心地放这些点，凸点尽量放大得，凹点尽量放小的，并且这样放好以后是能够构造出一个合法B串的。（想了这么久，一是由于画得少，二是思维不够灵敏）
problem5:BROJ
题目大意：求最小质因子为p的第n大得数，若答案&10^9就输出0
(1&=n,p&=10^9)
这题我想了更久。
初看此题，首先当然要求出一些质数，这是肯定的。接着怎么办呢？假设n比较小的话，我一步一步枚举，就每次找一个最小的扩展。问题是现在n很大，这样显然是不行的。通常这类题（类似求某个排名的排列）都能直接构造出答案，于是我想直接构造出答案。能不能二分p的次数，然后计算一下呢？似乎是不行的p的次数高的数不一定大啊！构造了很久也构造不出来。
这时我十分地无奈，还有什么路可以走呢？好吧，再重新看一看题目，这一看我忽然找到了突破口，之前我一直忽略掉的一句话：答案&10^9输出0。由于有了这句话，当p太大时显然n要比较小才能使ans&=10^9，首先若p&=sqrt(10^9）那n最大只能为1。这样p的范围就大大缩小了，sqrt（10^9）约为30000。如果p很大，那么n只能很小，那么我们就可以硬做了。
现在剩下的问题是p比较小的时候。经过估算，我发现即使p比较小时，n也不会很大的，当p=7的时候n已经是10^7级别的了，lch说当p=23时，n就要降到10^6级别的了，这个范围硬做也是可以接受的。于是我直接预处理了p&7的情况，剩下的就一步一步硬做。硬做其实有两种方法：一是每次找最小地来扩展，二是每次枚举枚举x(ans=x*p)。我采用的是方法2。方法1的时间复杂度比较有保证，找最小的时候随便用个堆什么的，时间复杂度为O(n*log(n))。方法2的时间复杂度是没什么保证的。但是其实这样做是很快的。时间复杂度的不确定是因为要判断一个x是否合法，就要判断x能否被小于p的质数整除。当p比较大时，n很小自然不成问题，当p比较小时，虽然n很大，但小于p的质数的个数是很少的。例如p=13的时候，n可以取到10^7级别，但小于p的质数只有5个，因此总的时间是很快的。
（这题卓亮好像是用一些数学方法做的<img TYPE="face" src="/blog7style/images/common/sg_trans.gif" real_src ="/uc/myshow/blog/misc/gif/E___6726EN00SIGG.gif"
ALT="coci&&contest"
TITLE="coci&&contest" />）
problem6：KRIPTOGRAM
题目大意：给定A、B两篇文章，每个单词用空格隔开，设B的单词位数为m，要求在A中找包含m个单词的子段，并且这个子段与B相似。相似的定义：在B串中相同的单词，在子段中对应位置的单词也要相同，B串中不相同的单词，在子段中对应位置也要不相同。例如aa
b aa c与zzz ccc zzz d是相似的，而aa b aa aa与zzz ccc zzz d是不相似的。
这题应该是这三题中做得最快的一题了，由于之前做了coci
day1的第一题，对这种匹配的题目比较有想法。第一想法肯定是kmp，我的第一个思路是给把单词都编个号，然后按照coci
day1的第一题那样来做。但是发现这样是不行的，因为这里的对应关系并不是大小关系。好吧，想一种新的匹配方法。当匹配到A[i]与B[j]时，怎么判断它能够匹配成功呢？由于匹配的关系是相等的相等，不等的不等，因此只要判断最近一个与A[i]相等的单词到A[i]的距离，跟最近一个与B[j]相等的单词到B[j]的距离是否相等就可以了。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。下次自动登录
现在的位置:
& 综合 & 正文
POJ 2187 Beauty Contest【旋转卡壳求凸包直径】
Beauty Contest
Time Limit: 3000MS
Memory Limit: 65536K
Total Submissions: 24254
Accepted: 7403
Description
Sample Input
Sample Output
给你 N 个点, 求所有点中最远两点距离
code1：凸包+暴力
code2：凸包+旋转卡壳
建立凸包：
lrj 《训练指南》 P272
对于个点按照 x 从小到大排序，再按照 y 点从小到大排序,删除重复的点后,得到序列 p0,p1,p2...,
把 p0 和 p1 放入凸包。 从p2开始,当新点在凸包“前进”方向的左边时继续,否则依次删除最近加入凸包的点，直到新点在左边
PS：判断用叉积即可
凸包模板：
/********************************************
计算凸包,输入点数组 p, 个数为 n , 输出点数组 ch. 函数返回凸包顶点数
输入不能有重复点。函数执行完之后输入点的顺序被破坏
如果不希望在凸包的边上有输入点,把两个 &= 改成 & 【== 表示两向量共线】
在精度要求高时建议用 dcmp 比较
const double eps = 1e-10;
int dcmp(double x)
if(fabs(x) & eps) return 0;
else return x & 0 ? -1 : 1;
********************************************/
double ConvexHull(Point* p, int n, Point* ch) /** 基于水平的Andrew算法求凸包 */
sort(p,p+n,cmp); /**先按照 x 从小到大排序, 再按照 y 从小到大排序*/
int m = 0;
for(int i = 0; i & i++) /** 从前往后找,求"下凸包" */
{/**Cross &= 0有等于，去掉 重复的点*/
while(m & 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) &= 0) m--;
ch[m++] = p[i];
for(int i = n-2; i &= 0; i--) /**从后往前找,求"上凸包" 形成完整的封闭背包*/
while(m & k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) &= 0) m--;
ch[m++] = p[i];
if(n & 1) m--; /** 起点重复 */
旋转卡壳模板：
盗版的别人博客的模板，下面会贴上大牛的关于这个算法的分析，一般是能看懂的了，如果不能看懂的，记住就好了
int rotating_calipers(Point *ch, int m) /**旋转卡壳模板*/
int q = 1;
int ans = 0;
ch[m] = ch[0]; /**凸包边界处理*/
for(int i = 0; i & i++) /**依次用叉积找出凸包每一条边对应的最高点*/
{/**同底不同高,每次用面积判断高的大小就可以了*/
while(Cross(ch[i+1]-ch[i], ch[q+1]-ch[i]) & Cross(ch[i+1]-ch[i], ch[q]-ch[i]))
q = (q+1)%m;
/**每条底上有两个点,所以要 max 两次*/
ans = max(ans, max(squarDist(ch[i], ch[q]), squarDist(ch[i+1], ch[q+1])));
/**返回的也就是凸包的直径*/
暴力：最远距离两个点一定在凸包上,建立好背包后,枚举凸包上的点就可以了
对于凸包上的点很多，暴力的话肯定是不行的了，那么就用旋转卡壳，只是名字听着神奇，其实也很好理解了
旋转卡壳：直接套模板，求直径
code1：暴力+凸包【对应于凸包上点比较少】
/********************************************
题意：给你 N 个点, 求所有点中最远两点距离
算法：凸包+暴力
思路：最远距离两个点一定在凸包上,建立好背包后,枚举凸包上的点就可以了
*********************************************/
#include&stdio.h&
#include&math.h&
#include&string.h&
#include&algorithm&
const int maxn = 50000+10;
struct Point{
double x,y;
Point(){};
Point(double _x, double _y)
Point operator - (const Point & B) const
return Point(x-B.x, y-B.y);
}p[maxn], ch[maxn];
bool cmp(Point p1, Point p2)
if(p1.x == p2.x) return p1.y & p2.y;
return p1.x & p2.x;
int squarDist(Point A, Point B) /**距离的平方*/
return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
double Cross(Point A, Point B) /**叉积*/
return A.x*B.y-A.y*B.x;
void ConvexHull() /** 求凸包 */
sort(p,p+n,cmp); /**先按照 x 从小到大排序, 再按照 y 从小到大排序*/
for(int i = 0; i & i++) /** 从前往后找"下凸包" */
while(m & 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) &= 0) m--;
ch[m++] = p[i];
for(int i = n-2; i &= 0; i--) /**从后往前找"上凸包", 形成完整的封闭背包*/
while(m & k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) &= 0) m--;
ch[m++] = p[i];
if(n & 1) m--; /** 起点重复*/
int main()
while(scanf("%d", &n) != EOF)
if(n == 0)
for(int i = 0; i & i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
ConvexHull();
int ans = 0;
for(int i = 0; i & i++)
for(int j = i+1; j & j++)
ans = max(ans,squarDist(ch[i], ch[j]));
printf("%d\n", ans);
code2：凸包+旋转卡壳【对于凸包上点比较多】
看了下面的博客，套模板来的了，对于点多时才能体现效率
/********************************************
题意：给你 N 个点, 求所有点中最远两点距离
算法：凸包+旋转卡壳
思路：最远距离两个点一定在凸包上,建立好背包后,直接套用旋转卡壳找直径
*********************************************/
#include&stdio.h&
#include&math.h&
#include&string.h&
#include&algorithm&
const int maxn = 50000+10;
struct Point{
double x,y;
Point(){};
Point(double _x, double _y)
Point operator - (const Point & B) const
return Point(x-B.x, y-B.y);
}p[maxn], ch[maxn];
bool cmp(Point p1, Point p2)
if(p1.x == p2.x) return p1.y & p2.y;
return p1.x & p2.x;
int squarDist(Point A, Point B) /**距离的平方*/
return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
double Cross(Point A, Point B) /**叉积*/
return A.x*B.y-A.y*B.x;
void ConvexHull() /** 基于水平的Andrew算法求凸包 */
sort(p,p+n,cmp); /**先按照 x 从小到大排序, 再按照 y 从小到大排序*/
for(int i = 0; i & i++) /** 从前往后找 */
while(m & 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) &= 0) m--;
ch[m++] = p[i];
for(int i = n-2; i &= 0; i--) /**从后往前找, 形成完整的封闭背包*/
while(m & k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) &= 0) m--;
ch[m++] = p[i];
if(n & 1) m--;
int rotating_calipers() /**旋转卡壳模板*/
int q = 1;
int ans = 0;
ch[m] = ch[0]; /**凸包边界处理*/
for(int i = 0; i & i++) /**依次用叉积找出凸包每一条边对应的最高点*/
while(Cross(ch[i+1]-ch[i], ch[q+1]-ch[i]) & Cross(ch[i+1]-ch[i], ch[q]-ch[i]))
q = (q+1)%m;
ans = max(ans, max(squarDist(ch[i], ch[q]), squarDist(ch[i+1], ch[q+1])));
int main()
while(scanf("%d", &n) != EOF)
if(n == 0)
for(int i = 0; i & i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
ConvexHull();
printf("%d\n", rotating_calipers());
旋转卡壳算法分析：
转载来自：
好早以前看的，现在再记下来吧，当做复习一遍。
那么，先提一下最基本最暴力的求凸包直径的方法吧---枚举。。。好吧。。很多问题都可以用 枚举 这个“万能”的方法来解决，过程很简单方便是肯定的，不过在效率上就要差很远了。
要求一个点集的直径，即使先计算出这个点集的凸包，然后再枚举凸包上的点对，这样来求点集直径的话依然会在凸包上点的数量达到O（n）级别是极大的降低它的效率，也浪费了凸包的优美性质。不过在数据量较小或者很适合时，何必要大费周折的用那些麻烦复杂的算法呢，枚举依然是解决问题的很好的方法之一。
然后就是今天的旋转卡壳算法了。（那个字念 qia 。。。搞了好久才发现读都读错了。囧。。。）
旋转卡壳可以用于求凸包的直径、宽度，两个不相交凸包间的最大距离和最小距离等。虽然算法的思想不难理解，但是实现起来真的很容易让人“卡壳”。
其实简单来说就是用一对平行线“卡”住凸包进行旋转。
被一对卡壳正好卡住的对应点对称为对踵点，对锺点的具体定义不好说，不过从图上还是比较好理解的。
可以证明对踵点的个数不超过3N/2个 也就是说对踵点的个数是O(N)的
对踵点的个数也是我们下面解决问题时间复杂度的保证。
卡壳呢，具体来说有两种情况：
一种是这样，两个平行线正好卡着两个点；
一种是这样，分别卡着一条边和一个点。
而第二种情况在实现中比较容易处理，这里就只研究第二种情况。
在第二种情况中 我们可以看到 一个对踵点和对应边之间的距离比其他点要大（借用某大神的图··）
也就是一个对踵点和对应边所形成的三角形是最大的 下面我们会据此得到对踵点的简化求法。
下面给出一个官方的说明：
Compute the polygon's extreme points in the y direction. Call them ymin and ymax. Construct two horizontal lines of support through ymin and ymax. Since this is already an anti-podal pair, compute the distance, and keep as maximum. Rotate the lines until one
is flush with an edge of the polygon. A new anti-podal pair is determined. Compute the new distance, compare to old maximum, and update if necessary. Repeat steps 3 and 4 until the anti-podal pair considered is (ymin,ymax) again. Output the pair(s) determining
the maximum as the diameter pair(s).
要是真的按这个实现起来就麻烦到吐了。。
根据上面的第二种情况，我们可以得到下面的方法：
如果qa，qb是凸包上最远两点，必然可以分别过qa，qb画出一对平行线。通过旋转这对平行线，我们可以让它和凸包上的一条边重合,如图中蓝色直线，可以注意到，qa是凸包上离p和qb所在直线最远的点。于是我们的思路就是枚举凸包上的所有边，对每一条边找出凸包上离该边最远的顶点，计算这个顶点到该边两个端点的距离，并记录最大的值。
直观上这是一个O(n2)的算法，和直接枚举任意两个顶点一样了。
然而我们可以发现 凸包上的点依次与对应边产生的距离成单峰函数（如下图：）
这个性质就很重要啦。
根据这个凸包的特性，我们注意到逆时针枚举边的时候，最远点的变化也是逆时针的，这样就可以不用从头计算最远点，而可以紧接着上一次的最远点继续计算。于是我们得到了O(n)的算法。这就是所谓的“旋转”吧！
利用旋转卡壳，我们可以在O（n）的时间内得到凸包的对锺点中的长度最长的点对。
又由于最远点对必然属于对踵点对集合 ，那么我们先求出凸包 然后求出对踵点对集合 然后选出距离最大的即可
那么具体的就很容易实现了，利用叉积，代码只有这么几行的长度：
double rotating_calipers(Point *ch,int n)
double ans=0;
ch[n]=ch[0];
for(int p=0;p&n;p++)
while(cross(ch[p+1],ch[q+1],ch[p])&cross(ch[p+1],ch[q],ch[p]))
q=(q+1)%n;
ans=max(ans,max(dist(ch[p],ch[q]),dist(ch[p+1],ch[q+1])));
其中cross()是计算叉积，因为凸包上距离一条边最远的点和这条边的两个端点构成的三角形面积是最大的。之所以既要更新(ch[p],ch[q])又要更新(ch[p+1],ch[q+1])是为了处理凸包上两条边平行的特殊情况。
旋转卡壳经典题目：
求凸包距离：
&&&&推荐文章:
【上篇】【下篇】2014牡丹江亚洲区域赛邀请赛
B题：图论题目
K题：想法题
分析：两种变化，添加和交换，首先：星号是n的话最少需要的数字是n+1，那么可以首先判断数字够不够，不够的话现在最前面添数字，如果满足的话直接模拟如果数字不够的话把当前的星号和最后一个数字交换即可。
css函数可以不用。
#include &cstdio&
#include &iostream&
#include &algorithm&
#include &vector&
int ccs(string s)
int ans=0,tmp = 0;
for(int i=0;i&s.size();i++)
if(s[i]=='*')
ans+=(2-tmp);
//printf(&YES%d\n&,i);
//printf(&NO\n&);
int check(string s,int x)
i = s.size()-1;i&x;i--)
if(s[i]!='*')
int solve(string s)
int len = s.size(),ans=0,tmp = 0;
for(int i=0;i&i++)
if(s[i]=='*')
int pps = 0;
if((tmp+tmp+1)&len)
pps = tmp+tmp+1 -
//printf(&%d %d %d\n&,tmp,ans,pps);
for(int i=0;i&s.size();i++)
if(s[i]=='*')
if(pps&=2){
int f = check(s,i);
swap(s[i],s[f]);
//cout&&s&&
int main()
//freopen(&Input.txt&,&r&,stdin);
scanf(&%d&,&T);
while(T--)
//printf(&CCS:%d\n&,ccs(s));
int ans = min(solve(s),ccs(s));
printf(&%d\n&,ans);
I题：直接套用给出的第二个公式。
#include &cstdio&
#include &iostream&
#include &algorithm&
#include &vector&
#include &cmath&
double a[200];
double solve(int x)
double ans = 0;
for(int i=1;i&=n;i++)
double tmp = 0;
if(a[i]==0)
tmp = a[i]*log2(a[i]);
else if(x==5)
tmp = a[i]*log(a[i]);
else if(x==10)
tmp = a[i]*log10(a[i]);
//printf(&TMP%lf, %lf\n&,tmp, log2(a[i]));
int main()
//freopen(&Input.txt&,&r&,stdin);
scanf(&%d&,&T);
while(T--)
cin&&n&&s;
for(int i=1;i&=n;i++){
scanf(&%d&,&x);
a[i]=(double)x/100;
double ans=0;
if(s==&bit&)
ans = solve(2);
else if(s==&nat&)
ans = solve(5);
ans = solve(10);
printf(&%.12lf\n&,-ans);
A题：水题。
求出第一个班的平均值 x 和第二个平均值 y ，如果 x 为整数则x -- ，y 变整数之后+1.就是ans
#include &cstdio&
#include &iostream&
#include &algorithm&
#include &vector&
int main()
scanf(&%d&,&T);
while(T--)
scanf(&%d%d&,&n,&m);
int sum1=0,sum2=0;
for(int i=1;i&n;i++)
scanf(&%d&,&x);
for(int i=0;i&m;i++)
scanf(&%d&,&x);
double p1 = (double)sum1 / (n-1);
double p2 = (double)sum2 /
//printf(&%.5lf %.5lf\n&,p1,p2);
int mi = p1,ma = (int)p2+1;
if(mi == p1)
printf(&%d %d\n&,min(mi,ma),max(mi,ma));
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：243185次
积分：5455
积分：5455
排名：第2128名
原创：300篇
评论：87条
(5)(10)(7)(2)(2)(8)(19)(42)(24)(37)(21)(1)(6)(17)(21)(10)(6)(1)(5)(6)(19)(3)(3)(5)(8)(2)(14)(2)
