百度之星2015初赛#1

正文索引 [隐藏]

题解
题解
题解
题解

超级赛亚ACMer

百小度是一个ACMer，也是一个超级赛亚人，每个ACMer都有一个战斗力，包括百小度。 所谓超级赛亚人的定义，是说如果在对抗中刚好接近极限状态，那就会激发斗志，实力提升。
具体来说，就是百小度现在要接受一些ACMer的挑战了，这些ACMer有n个人，第i个人的战斗力是a[i]。
百小度接下来可以自主安排与这n个ACMer的PK顺序，他要想在PK赛中赢过另外一个ACMer，就必须使得自己的战斗力不小于对方（平局情况他会按照百小度字典上的规则把自己排在第一）。
如果百小度的战斗力大于对方，那么百小度就会轻易获胜，得不到锻炼并且骄傲起来，他以后的战斗力将保持在这个值，再也不会发生改变。 如果百小度的战斗力等于对方，那么百小度在获胜的同时也会感到很吃力，但是这会激发百小度的斗志，使得他刻苦刷题，在下场PK赛之前，战斗力最多提升k点（即可以提升0~k点任意值）。
k是百小度的潜力提升上限，会被给定一个初始值，这个潜力提升上限k在后面的比赛中会下降。
每战胜一个ACMer，这个潜力上限k将减少1（因为超级赛亚人百小度也会感到累），但k最低只会减少到0，即不会出现战斗力下降的情况 。也就是第一次比赛如果激发了百小度的斗志，他能把战斗力提升0~k的任一值，如果第二次比赛继续被激发斗志，他能在第一次提升后的基础上，把战斗力再提升0 max(0,k−1),依次类推……
m是百小度的初始战斗力上限，也就是百小度第一次进行PK赛的时候，可以选择0~m的任意一个值作为他的战斗力。
现在希望你编写程序，判断一下百小度是否战胜所有的ACMer。

Case #1:
why am I so diao?
Case #2:
madan!

Case #1:

why am I so diao?

Case #2:

madan!

Hint

第一组样例解释 5个ACMer，初始战斗力选择范围是[0,11],接下来每场战斗力提升上限是3,2,1,0,0,…,0 百小度首先使得自己的初始战斗力为10，打败战斗力为10的第一个ACMer，然后选择战斗力提升3，变成13，打败战斗力为13的第二个ACMer，然后选择战斗力提升2，变成15，打败战斗力为15的第三个ACMer，之后再以任意顺序打败剩下的ACMer

题解

玛雅!Orz 看错题目了、、一开始、我就说怎么觉得看似贪心但是仔细一想有不对、
把所有人拍个序，我们每次贪心的取能取到的最大的能激发潜力的人。

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,k,T,flag;
long long num[10010];
int main(){
    scanf("%d",&T);
    for (int Rt=1;Rt<=T;Rt++){
        cout<<"Case #"<<Rt<<':'<<endl;
        scanf("%d%d%d",&n,&m,&k);flag=0;
        for(int i=1;i<=n;i++) scanf("%I64d",&num[i]);
        sort(num+1,num+n+1);
        long long s=0,c,i;
        for(i=1;i<=n;i++)
            if(num[i]>m) break;
        if(i==1){
            cout<<"madan!"<<endl;
            continue;
        }
        s=i-1,c=num[s];
        for(int i=k;i>=0;i--){
            int j=s;
            if(num[j+1]-num[j]>k) break;
            if(num[n]<=c+i){
                cout<<"why am I so diao?"<<endl;
                flag=1;
                break;
            }
            while(num[j]<=c+i) j++;
            j--;
            s=j;c=num[j];
        }
        if(!flag) cout<<"madan!"<<endl;
    }
    return 0;
}

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

using namespace std;

int n,m,k,T,flag;

long long num[10010];

int main(){

scanf("%d",&T);

for (int Rt=1;Rt<=T;Rt++){

cout<<"Case #"<<Rt<<':'<<endl;

scanf("%d%d%d",&n,&m,&k);flag=0;

for(int i=1;i<=n;i++) scanf("%I64d",&num[i]);

sort(num+1,num+n+1);

long long s=0,c,i;

for(i=1;i<=n;i++)

if(num[i]>m) break;

if(i==1){

cout<<"madan!"<<endl;

continue;

}

s=i-1,c=num[s];

for(int i=k;i>=0;i--){

int j=s;

if(num[j+1]-num[j]>k) break;

if(num[n]<=c+i){

cout<<"why am I so diao?"<<endl;

flag=1;

break;

}

while(num[j]<=c+i) j++;

j--;

s=j;c=num[j];

}

if(!flag) cout<<"madan!"<<endl;

}

return 0;

}

找连续数

题解

这到题目每个询问暴力枚举区间，前缀和维护区间和，ST表维护区间最小值，然后暴力处理某一区间是否有重复的数，这样每个询问加起来是O（n）的。于是O（NM）就行了！「如果吧ST表当作O（1）。。。」然后区间内无重复的数，且区间和和用最小值计算出来的一样那么就是一个合法的答案。

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
const int Maxn=10010;
int m,n,k,Ans;
int flag;
long long num[Maxn];
long long minNum,sumNum;
map<long long,int> Hash;
long long tHash[Maxn*2];
int tot;
long long sum[Maxn];
int vis[Maxn*2];
long long stTableMin[Maxn][35],preLog2[Maxn];
void StPrepare(){
  preLog2[1]=0;
  for(int i=2;i<=n;i++){
    preLog2[i]=preLog2[i-1];
    if((1<<preLog2[i]+1)==i) preLog2[i]++;
  }
  for(int i=n;i>=0;--i){
    stTableMin[i][0]=num[i];
    for(int j=1;(i+(1<<j)-1)<=n;++j)
      stTableMin[i][j]=min(stTableMin[i][j-1],stTableMin[i+(1<<j-1)][j-1]);
  }
}
int queryMin(int l,int r){
  int len=r-l+1,k=preLog2[len];
  return min(stTableMin[l][k],stTableMin[r-(1<<k)+1][k]);
}
int main(){
    printf("Case #1:\n");
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%I64d",&num[i]);
    for (int i=1;i<=n;i++) {tHash[i*2-1]=num[i];tHash[i*2]=num[i]+1;}
    sort(tHash+1,tHash+n*2+1);
    tHash[0]=-1;
    for (int i=1;i<=n*2;i++){
        if (tHash[i]!=tHash[i-1])Hash[tHash[i]]=++tot;
    }
    for (int i=1;i<=n;i++) num[i]=Hash[num[i]];
    sum[0]=0;
    for (int i=1;i<=n;i++) sum[i]+=sum[i-1]+num[i];
    StPrepare();
    for (int i=1;i<=m;i++){
        scanf("%d",&k);
        Ans=0;flag=0;
        memset(vis,0,sizeof(vis));
        for (int j=1;j<=k;j++){
            vis[num[j]]++;
            if (vis[num[j]]==2) flag++;
        }
        if (!flag){
            minNum=queryMin(1,k);
            sumNum=sum[k]-sum[0];
            if (sumNum==(long long)(minNum+minNum+k-1)*(long long)k/(long long)2) Ans++;
            //printf("True\n");
        }
        for (int left=2;left<=n;left++){
            int right=left+k-1;
            if (right>n) break;
            vis[num[left-1]]--;
            if (vis[num[left-1]]==1) flag--;
            vis[num[right]]++;
            if (vis[num[right]]==2) flag++;
            if (!flag){
                minNum=queryMin(left,right);
                sumNum=sum[right]-sum[left-1];
                if (sumNum==(long long)(minNum+minNum+k-1)*(long long)k/(long long)2) Ans++;
            }
        }
        printf("%d\n",Ans);
    }
    return 0;
}

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<cstring>

using namespace std;

const int Maxn=10010;

int m,n,k,Ans;

int flag;

long long num[Maxn];

long long minNum,sumNum;

map<long long,int> Hash;

long long tHash[Maxn*2];

int tot;

long long sum[Maxn];

int vis[Maxn*2];

long long stTableMin[Maxn][35],preLog2[Maxn];

void StPrepare(){

preLog2[1]=0;

for(int i=2;i<=n;i++){

preLog2[i]=preLog2[i-1];

if((1<<preLog2[i]+1)==i) preLog2[i]++;

}

for(int i=n;i>=0;--i){

stTableMin[i][0]=num[i];

for(int j=1;(i+(1<<j)-1)<=n;++j)

stTableMin[i][j]=min(stTableMin[i][j-1],stTableMin[i+(1<<j-1)][j-1]);

}

int queryMin(int l,int r){

int len=r-l+1,k=preLog2[len];

return min(stTableMin[l][k],stTableMin[r-(1<<k)+1][k]);

}

int main(){

printf("Case #1:\n");

scanf("%d%d",&n,&m);

for (int i=1;i<=n;i++) scanf("%I64d",&num[i]);

for (int i=1;i<=n;i++) {tHash[i*2-1]=num[i];tHash[i*2]=num[i]+1;}

sort(tHash+1,tHash+n*2+1);

tHash[0]=-1;

for (int i=1;i<=n*2;i++){

if (tHash[i]!=tHash[i-1])Hash[tHash[i]]=++tot;

}

for (int i=1;i<=n;i++) num[i]=Hash[num[i]];

sum[0]=0;

for (int i=1;i<=n;i++) sum[i]+=sum[i-1]+num[i];

StPrepare();

for (int i=1;i<=m;i++){

scanf("%d",&k);

Ans=0;flag=0;

memset(vis,0,sizeof(vis));

for (int j=1;j<=k;j++){

vis[num[j]]++;

if (vis[num[j]]==2) flag++;

}

if (!flag){

minNum=queryMin(1,k);

sumNum=sum[k]-sum[0];

if (sumNum==(long long)(minNum+minNum+k-1)*(long long)k/(long long)2) Ans++;

//printf("True\n");

}

for (int left=2;left<=n;left++){

int right=left+k-1;

if (right>n) break;

vis[num[left-1]]--;

if (vis[num[left-1]]==1) flag--;

vis[num[right]]++;

if (vis[num[right]]==2) flag++;

if (!flag){

minNum=queryMin(left,right);

sumNum=sum[right]-sum[left-1];

if (sumNum==(long long)(minNum+minNum+k-1)*(long long)k/(long long)2) Ans++;

}

printf("%d\n",Ans);

}

return 0;

}

序列变换

题解

二分答案，然后我们贪心验证就好、、

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int Maxn=100000+10;
int num[Maxn],n,T,tmp[Maxn];
inline bool check(int l){
    for(int i=1;i<=n;i++)
    tmp[i]=num[i];
    tmp[1]=num[1]-l;
    for(int i=2;i<=n;i++)
        if(num[i]+l<=tmp[i-1])
            return false;
        else
            tmp[i]=max(num[i]-l,tmp[i-1]+1);
    return true;
}
int main(){
    scanf("%d",&T);
    for (int Rt=1;Rt<=T;Rt++){
        scanf("%d",&n);
        cout<<"Case #"<<Rt<<':'<<endl;
        for(int i=1;i<=n;i++) scanf("%d",&num[i]);
        int l=0,r=1000000,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)){
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

using namespace std;

const int Maxn=100000+10;

int num[Maxn],n,T,tmp[Maxn];

inline bool check(int l){

for(int i=1;i<=n;i++)

tmp[i]=num[i];

tmp[1]=num[1]-l;

for(int i=2;i<=n;i++)

if(num[i]+l<=tmp[i-1])

return false;

else

tmp[i]=max(num[i]-l,tmp[i-1]+1);

return true;

}

int main(){

scanf("%d",&T);

for (int Rt=1;Rt<=T;Rt++){

scanf("%d",&n);

cout<<"Case #"<<Rt<<':'<<endl;

for(int i=1;i<=n;i++) scanf("%d",&num[i]);

int l=0,r=1000000,ans=0;

while(l<=r){

int mid=(l+r)>>1;

if(check(mid)){

ans=mid;

r=mid-1;

}else{

l=mid+1;

}

cout<<ans<<endl;

}

return 0;

}

KPI

有大约100组数据。
每组数据第一行有一个n(1≤n≤10000)，代表服务记录数。
接下来有n行，每一行有3种形式 “in x”: 代表重要值为x(0≤x≤109)的请求被推进管道。 “out”: 代表服务拉取了管道头部的请求。 “query: 代表我想知道当前管道内请求重要值的中间值. 那就是说，如果当前管道内有m条请求, 我想知道，升序排序后第floor(m/2)+1th 条请求的重要值.
为了让题目简单，所有的x都不同，并且如果管道内没有值，就不会有”out”和”query”操作。

题解

评测机一定是开O2了、、、直接Vector就水过去了、、

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
vector<int> V;
int n;
char ord[10];
int num;
int stack[10010];
int l,r;
int siz;
inline void solve(){
    V.clear();
    V.reserve(n+10);
    r=0;
    l=1;
    siz=0;
    for (int i=1;i<=n;i++){
        scanf("%s",ord);
        if (ord[0]=='i') scanf("%d",&stack[++r]);
        if (ord[0]=='i'){
            siz++;
            //printf("Insert %d\n",stack[r]);
            V.insert(upper_bound(V.begin(),V.end(),stack[r]),stack[r]);
        }else if (ord[0]=='o'){
            //printf("Out %d\n",stack[l]);
            V.erase(lower_bound(V.begin(),V.end(),stack[l]));
            l++;
            siz--;
        }else{
            //printf("Siz:%d\n",siz);
            printf("%d\n",V[siz/2]);
        }
    }
}
int T;
int main(){
    while(scanf("%d",&n)!=EOF){
        T++;
        printf("Case #%d:\n",T);
        solve();
    }
    return 0;
}

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

#include<vector>

using namespace std;

vector<int> V;

int n;

char ord[10];

int num;

int stack[10010];

int l,r;

int siz;

inline void solve(){

V.clear();

V.reserve(n+10);

r=0;

l=1;

siz=0;

for (int i=1;i<=n;i++){

scanf("%s",ord);

if (ord[0]=='i') scanf("%d",&stack[++r]);

if (ord[0]=='i'){

siz++;

//printf("Insert %d\n",stack[r]);

V.insert(upper_bound(V.begin(),V.end(),stack[r]),stack[r]);

}else if (ord[0]=='o'){

//printf("Out %d\n",stack[l]);

V.erase(lower_bound(V.begin(),V.end(),stack[l]));

l++;

siz--;

}else{

//printf("Siz:%d\n",siz);

printf("%d\n",V[siz/2]);

}

int T;

int main(){

while(scanf("%d",&n)!=EOF){

T++;

printf("Case #%d:\n",T);

solve();

}

return 0;

}

矩形面积

题解

旋转卡壳+凸包！（其实我并不会做见BZOJ1185

//WNJXYK
//while(true) RP++;
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#define MAXN 51000
#define EPS 1e-10
using namespace std;
int n;
double minsqr;
int dcmp(double x){
    if(fabs(x)<EPS) return 0;
    if(x>-EPS) return 1;
    return -1;
}
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y):x(_x),y(_y){}
    void read(){
        scanf("%lf%lf",&x,&y);
        //cout<<x<<" "<<y<<endl;
    }
}points[MAXN],stack[MAXN<<1],ans[10]; //ans保存最小覆盖矩形的四个顶点
Point operator-(Point a,Point b){
    return Point(a.x-b.x,a.y-b.y);
}
Point operator*(Point a,double b){
    return Point(a.x*b,a.y*b);
}
Point operator+(Point a,Point b){
    return Point(a.x+b.x,a.y+b.y);
}
double cross(Point a,Point b,Point c){
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dot(Point a,Point b,Point c){
    return (b.x-a.x)*(c.x-b.x)+(b.y-a.y)*(c.y-b.y);
}
double dist(Point a,Point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int top=0;
bool cmp(Point a,Point b){
    if(!dcmp(a.x-b.x)) return a.y<b.y;
    return a.x<b.x;
}
bool operator<(Point a,Point b){
    if(!dcmp(a.y-b.y)) return a.x<b.x;
    return a.y<b.y;
}
void Graham(){
    sort(points+1,points+n+1,cmp);
    for(int i=1;i<=n;i++) {
        while(top>=2&&dcmp(cross(stack[top-1],stack[top],points[i])<=0)) top--;
        stack[++top]=points[i];
    }
    int tmp=top;
    for(int i=n-1;i>=1;i--) {
        while(top>=tmp+1&&dcmp(cross(stack[top-1],stack[top],points[i])<=0)) top--;
        stack[++top]=points[i];
    }
    top--;
}
void rotcalip(){
    int left=1,right=1,up=1;
    for(int i=1;i<=top;i++){
        while(dcmp(cross(stack[up+1],stack[i],stack[i+1])-cross(stack[up],stack[i],stack[i+1]))>=0) up=up%top+1;
        while(dcmp(dot(stack[right+1],stack[i+1],stack[i])-dot(stack[right],stack[i+1],stack[i]))>=0) right=right%top+1;
        if(i==1) left=right;
        while(dcmp(dot(stack[left+1],stack[i],stack[i+1])-dot(stack[left],stack[i],stack[i+1]))>=0) left=left%top+1;
        double L=dist(stack[i],stack[i+1]);
        double H=cross(stack[i+1],stack[up],stack[i])/L;
        double bottom=(fabs(dot(stack[i],stack[i+1],stack[left])/L)+fabs(dot(stack[i],stack[i+1],stack[right])/L));
        double nowsqr=bottom*H;
        if(nowsqr<minsqr) {
            minsqr=nowsqr;
            ans[0]=stack[i]+(stack[i+1]-stack[i])*((fabs(dot(stack[i],stack[i+1],stack[right]))/L+L)/L);
            ans[1]=ans[0]+(stack[right]-ans[0])*(H/dist(stack[right],ans[0]));
            ans[2]=ans[1]+(stack[up]-ans[1])*(bottom/dist(stack[up],ans[1]));
            ans[3]=ans[2]+(stack[left]-ans[2])*(H/dist(stack[left],ans[2]));
        }
    }
}
int solve(){
    minsqr=1e12;
    scanf("%d",&n);
    n*=4;top=0;
    for(int i=1;i<=n;i++)
        points[i].read();
    Graham();
    rotcalip();
    int Ans=(int)(minsqr+0.5);
    printf("%d\n",Ans);
    return 0;
}
int T;
int main(){
    scanf("%d",&T);
    for (int i=1;i<=T;i++){
        printf("Case #%d:\n",i);
        solve();
    }
}

100

101

102

103

104

105

//WNJXYK

//while(true) RP++;

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<iostream>

#define MAXN 51000

#define EPS 1e-10

using namespace std;

int n;

double minsqr;

int dcmp(double x){

if(fabs(x)<EPS) return 0;

if(x>-EPS) return 1;

return -1;

}

struct Point{

double x,y;

Point(){}

Point(double _x,double _y):x(_x),y(_y){}

void read(){

scanf("%lf%lf",&x,&y);

//cout<<x<<" "<<y<<endl;

}

}points[MAXN],stack[MAXN<<1],ans[10]; //ans保存最小覆盖矩形的四个顶点

Point operator-(Point a,Point b){

return Point(a.x-b.x,a.y-b.y);

}

Point operator*(Point a,double b){

return Point(a.x*b,a.y*b);

}

Point operator+(Point a,Point b){

return Point(a.x+b.x,a.y+b.y);

}

double cross(Point a,Point b,Point c){

return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);

}

double dot(Point a,Point b,Point c){

return (b.x-a.x)*(c.x-b.x)+(b.y-a.y)*(c.y-b.y);

}

double dist(Point a,Point b){

return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

int top=0;

bool cmp(Point a,Point b){

if(!dcmp(a.x-b.x)) return a.y<b.y;

return a.x<b.x;

}

bool operator<(Point a,Point b){

if(!dcmp(a.y-b.y)) return a.x<b.x;

return a.y<b.y;

}

void Graham(){

sort(points+1,points+n+1,cmp);

for(int i=1;i<=n;i++) {

while(top>=2&&dcmp(cross(stack[top-1],stack[top],points[i])<=0)) top--;

stack[++top]=points[i];

}

int tmp=top;

for(int i=n-1;i>=1;i--) {

while(top>=tmp+1&&dcmp(cross(stack[top-1],stack[top],points[i])<=0)) top--;

stack[++top]=points[i];

}

top--;

}

void rotcalip(){

int left=1,right=1,up=1;

for(int i=1;i<=top;i++){

while(dcmp(cross(stack[up+1],stack[i],stack[i+1])-cross(stack[up],stack[i],stack[i+1]))>=0) up=up%top+1;

while(dcmp(dot(stack[right+1],stack[i+1],stack[i])-dot(stack[right],stack[i+1],stack[i]))>=0) right=right%top+1;

if(i==1) left=right;

while(dcmp(dot(stack[left+1],stack[i],stack[i+1])-dot(stack[left],stack[i],stack[i+1]))>=0) left=left%top+1;

double L=dist(stack[i],stack[i+1]);

double H=cross(stack[i+1],stack[up],stack[i])/L;

double bottom=(fabs(dot(stack[i],stack[i+1],stack[left])/L)+fabs(dot(stack[i],stack[i+1],stack[right])/L));

double nowsqr=bottom*H;

if(nowsqr<minsqr) {

minsqr=nowsqr;

ans[0]=stack[i]+(stack[i+1]-stack[i])*((fabs(dot(stack[i],stack[i+1],stack[right]))/L+L)/L);

ans[1]=ans[0]+(stack[right]-ans[0])*(H/dist(stack[right],ans[0]));

ans[2]=ans[1]+(stack[up]-ans[1])*(bottom/dist(stack[up],ans[1]));

ans[3]=ans[2]+(stack[left]-ans[2])*(H/dist(stack[left],ans[2]));

}

int solve(){

minsqr=1e12;

scanf("%d",&n);

n*=4;top=0;

for(int i=1;i<=n;i++)

points[i].read();

Graham();

rotcalip();

int Ans=(int)(minsqr+0.5);

printf("%d\n",Ans);

return 0;

}

int T;

int main(){

scanf("%d",&T);

for (int i=1;i<=T;i++){

printf("Case #%d:\n",i);

solve();

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

百度之星2015初赛#1

超级赛亚ACMer

Problem Description

Input

Output

Sample Input

Sample Output

Hint

题解

找连续数

Problem Description

Input

Output

Sample Input

Sample Output

题解

序列变换

Problem Description

Input

Output

Sample Input

Sample Output

题解

KPI

Problem Description

Input

Output

Sample Input

Sample Output

题解

矩形面积

Problem Description

Input

Output

Sample Input

Sample Output

题解

扫一扫支付

评论 放弃治疗

评论放弃治疗