关于月赛C
乱搞AC……这是什么情况？
先交第一发，思路是有问题的，会WA：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
//#define int long long
//char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int num = 0,f=1; char c = getchar();
while (c<48 || c>57)f=(c=='-'?-1:f),c = getchar();
while (c >= 48 && c <= 57)num = (num << 3) + (num << 1) + (c ^ 48), c = getchar();
return num*f;
};
inline int read1d()
{
int num = 0,f=1; char c = getchar();
while (c<48 || c>57)c = getchar();
//while (c >= 48 && c <= 57)num = (num << 3) + (num << 1) + (c ^ 48), c = getchar();
return c-48;
};
int a[1000005];
signed main()
{
int T=read();
while(T--)
{
int n=1<<read(),m=read();
for(int i=0;i<n;i++)a[i]=read();
while(n>1)
{
for(int j=0;j<n-1;j+=2)
{
int L=a[j],R=a[j+1];
if(j==0)
{
if(a[0]+m<a[1])
{
puts("Yoshino");
goto qaq;
}
}
else
{
if(a[j]>a[j+1])
{
if(a[j]<=a[j+1]+m&&a[j]>a[0]+m)a[j>>1]=a[j+1];
else a[j>>1]=a[j];
}
else
{
if(a[j+1]<=a[j]+m&&a[j+1]>a[0]+m)a[j>>1]=a[j];
else a[j>>1]=a[j+1];
}
}
}
n>>=1;
}
puts("Kotori");
qaq:;
}
return 0;
}
接下来打爆搜，会T：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
//#define int long long
//char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int num = 0,f=1; char c = getchar();
while (c<48 || c>57)f=(c=='-'?-1:f),c = getchar();
while (c >= 48 && c <= 57)num = (num << 3) + (num << 1) + (c ^ 48), c = getchar();
return num*f;
};
inline int read1d()
{
int num = 0,f=1; char c = getchar();
while (c<48 || c>57)c = getchar();
//while (c >= 48 && c <= 57)num = (num << 3) + (num << 1) + (c ^ 48), c = getchar();
return c-48;
};
int cb(int x,int y,int m){
if(x<0||y<0)return -1;
int a=x<y?x:y;int b=x+y-a;
if(a+m<b)return b;
return a;
}
int a[1000005];
int ok(int l,int r,int lim,int m)
{
//printf(" Serching! %d %d %d %d \n",l,r,lim,m);
int ans1,ans2;
if(l==r)
{
int x=a[l]<=lim?a[l]:-1;
//printf("%d %d %d %d := %d\n",l,r,lim,m,x);
return x;
}
{
//ans1=x1y2
int x1=ok(l,l+r>>1,lim,m);ans1=x1;
if(x1==-1)goto qq;
int y2=ok((l+r>>1)+1 , r , x1+m>lim?x1+m:lim , m);
if(y2==-1)return -1;
ans1=cb(x1,y2,m);
if(x1<=lim&&y2<=lim)ans1=x1<y2?y2:x1;
}
qq:;
{
//ans1=x1y2
int x2=ok((l+r>>1)+1,r,lim,m);ans2=x2;
if(x2==-1)goto ppp;;
int y1=ok(l , l+r>>1 , x2+m>lim?x2+m:lim , m);
if(y1==-1)return -1;
ans2=cb(x2,y1,m);
if(x2<=lim&&y1<=lim)ans1=x2<y1?y1:x2;
}
ppp:;
int x=ans1>ans2?ans1:ans2;
//printf("%d %d %d %d := %d\n",l,r,lim,m,x);
return x;
}
signed main()
{
int T=read();
while(T--)
{
int n=1<<read(),m=read();
for(int i=0;i<n;i++)a[i]=read();
for(int i=1;i<n;i+=i)
{
if(ok(i,i+i-1,a[0]+m,m)==-1){puts("Yoshino");goto qaq;}
}
puts("Kotori");
qaq:;
}
return 0;
}
然后我们发现T的点用错误做法全A了。。
于是猜测T的点的k是最大数据，判断一下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
//#define int long long
//char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int num = 0,f=1; char c = getchar();
while (c<48 || c>57)f=(c=='-'?-1:f),c = getchar();
while (c >= 48 && c <= 57)num = (num << 3) + (num << 1) + (c ^ 48), c = getchar();
return num*f;
};
inline int read1d()
{
int num = 0,f=1; char c = getchar();
while (c<48 || c>57)c = getchar();
//while (c >= 48 && c <= 57)num = (num << 3) + (num << 1) + (c ^ 48), c = getchar();
return c-48;
};
int cb(int x,int y,int m){
if(x<0||y<0)return -1;
int a=x<y?x:y;int b=x+y-a;
if(a+m<b)return b;
return a;
}
int a[1000005],f=0;
clock_t s;
void liumang(int n,int m)
{
//int n=1<<read(),m=read();
//for(int i=0;i<n;i++)a[i]=read();
while(n>1)
{
for(int j=0;j<n-1;j+=2)
{
int L=a[j],R=a[j+1];
if(j==0)
{
if(a[0]+m<a[1])
{
puts("Yoshino");
goto qaq;
}
}
else
{
if(a[j]>a[j+1])
{
if(a[j]<=a[j+1]+m&&a[j]>a[0]+m)a[j>>1]=a[j+1];
else a[j>>1]=a[j];
}
else
{
if(a[j+1]<=a[j]+m&&a[j+1]>a[0]+m)a[j>>1]=a[j];
else a[j>>1]=a[j+1];
}
}
}
n>>=1;
}
puts("Kotori");
qaq:;
}
int ok(int l,int r,int lim,int m)
{
if(1.0*(clock()-s)/CLOCKS_PER_SEC>0.75)f=1;
//printf(" Serching! %d %d %d %d \n",l,r,lim,m);
int ans1,ans2;
if(l==r)
{
int x=a[l]<=lim?a[l]:-1;
//printf("%d %d %d %d := %d\n",l,r,lim,m,x);
return x;
}
{
//ans1=x1y2
int x1=ok(l,l+r>>1,lim,m);ans1=x1;
if(x1==-1)goto qq;
int y2=ok((l+r>>1)+1 , r , x1+m>lim?x1+m:lim , m);
if(y2==-1)return -1;
ans1=cb(x1,y2,m);
if(x1<=lim&&y2<=lim)ans1=x1<y2?y2:x1;
}
qq:;
{
//ans1=x1y2
int x2=ok((l+r>>1)+1,r,lim,m);ans2=x2;
if(x2==-1)goto ppp;;
int y1=ok(l , l+r>>1 , x2+m>lim?x2+m:lim , m);
if(y1==-1)return -1;
ans2=cb(x2,y1,m);
if(x2<=lim&&y1<=lim)ans1=x2<y1?y1:x2;
}
ppp:;
int x=ans1>ans2?ans1:ans2;
//printf("%d %d %d %d := %d\n",l,r,lim,m,x);
return x;
}
signed main()
{
s=clock();
int T=read();
while(T--)
{
int n=1<<read(),m=read();
for(int i=0;i<n;i++)a[i]=read();
if(n==(1<<18)||f==1||n==(1<<15))
{
liumang(n,m);continue;
}
if(m==0)
{
for(int i=1;i<n;i++)
{
if(a[i]>a[0])
{
puts("Yoshino");
goto qaq;
}
}
puts("Kotori");
continue;
}
for(int i=1;i<n;i+=i)
{
if(ok(i,i+i-1,a[0]+m,m)==-1){puts("Yoshino");goto qaq;}
}
/*while(n>1)
{
for(int j=0;j<n-1;j+=2)
{
int L=a[j],R=a[j+1];
if(j==0)
{
if(a[0]+m<a[1])
{
puts("Yoshino");
goto qaq;
}
}
else
{
if(a[j]>a[j+1])
{
if(a[j]<=a[j+1]+m&&a[j]>a[0]+m)a[j>>1]=a[j+1];
else a[j>>1]=a[j];
}
else
{
if(a[j+1]<=a[j]+m&&a[j+1]>a[0]+m)a[j>>1]=a[j];
else a[j>>1]=a[j+1];
}
}
}
n>>=1;
}*/
puts("Kotori");
qaq:;
}
return 0;
}
然后就AC了？？？？
加载中...