手速狗从西安回来一只浑浑噩噩，好不容易迎来一场送饭比赛体验一把河南的优势，结果被高中生狂虐，无缘奖金。。我的奖品梦就这样一次次被打破。。。。
最后半小时lzq送(抢)来代码，据说只能翻转一次，嗯，于是结合数据优势变成了shabi题，直接暴力模拟找最小值。
#define ll long long
const ll inf=0x3f3f3f3f3f3f3f3f;
ll a[10010];
ll solve(ll n,ll k)
{
ll i,j,ans=inf,len=min(k+1,n);
if(!k)
{
ans=0;
for(i=1; i<=n; i++)
ans+=a[i];
return ans;
}
for(i=1; i<=len; i++)
{
ll sum=0;
if((n-(i+k))%(2*k+1)>=(k+1)||(n-(i+k))%(2*k+1)<=0)
{
for(j=i; j<=n; j+=2*k+1) sum+=a[j];
ans=min(ans,sum);
}
}
return ans;
}
int main()
{
ll n,k;
while(scanf("%lld%lld",&n,&k)!=EOF)
{
ll i,j;
for(i=1; i<=n; i++)
scanf("%lld",&a[i]);
printf("%lld\n",solve(n,k));
}
return 0;
}
B题dp题交给腿队友吧。。
C
-- 咸鱼魔法记
再次回想起错失一血的痛苦，一个裸滑动窗(也称尺取法）竟然犯了个shibi错误T了三发，简直石乐志。。。也许，啪，没有也许，这不是差两个小时的罚时错失奖金的借口。。
const int N=1e6+10;
int a[N];
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k))
{
a[0]=0;
int x;
for(int i=1; i<=n; i++)
{
a[i]=a[i-1];
scanf("%d",&x);
if(!x) a[i]++;
}
int len=0,j=1;//比赛的时候把j定义在里面，导致TLE。。石乐志
for(int i=1; i<=n; i++)
{
while(j<=n&&a[j]-a[i-1]<=k) j++;
len=max(len,j-i);
}
printf("%d\n",len);
}
return 0;
}
无奈改成二分秒A。
const int N=3e5+10;
int n,k,a[N];
int find(int len)
{
for(int i=len; i<=n; i++)
if(a[i]-a[i-len]<=k)
return 1;
return 0;
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
a[0]=0;
int x,len=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&x);
a[i]=a[i-1];
if(!x) a[i]++;
else len=1;
}
int l=0,r=n;
while(l<=r)
{
int mid=(l+r)/2;
if(find(mid))
{
l=mid+1;
len=mid;
}
else r=mid-1;
}
printf("%d\n",len);
}
return 0;
}
D -- 咸鱼商店
再次膜腿队友3s。这个题和以前做的一个01背包+路径打印很像，于是队友改改我再debug一下A了。
推荐题： UVA624
- CD 01背包+路径打印
const int maxn=1e3+5;
const double eps=1e-4;
int n,m,k,a[maxn],d[maxn],v[maxn][maxn],b[maxn];
int ans;
int judge(int mid)
{
memset(d,0,sizeof(d));
memset(v,0,sizeof(v));
for(int i=0; i<n; i++)
{
if(b[i]<mid) continue;
for(int j=m; j>=a[i]; j--)
{
if(d[j]<d[j-a[i]]+b[i])
{
d[j]=d[j-a[i]]+b[i];
v[i][j]=1;
}
}
}
if(d[m]>=k)
{
int Min=inf;
for(int i=n,j=m; i>=0; i--)//找路径中最小的价值
if(v[i][j])
{
Min=min(Min,b[i]);
j-=a[i];//推锅：队友把a[i]打成b[i]导致无脑RE。。。
}
ans=max(ans,Min);//更新ans最大值
return 1;
}
else
return 0;
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&k))
{
ans=-1;
for(int i=0; i<n; i++)
scanf("%d%d",&a[i],&b[i]);
int l=0,r=1000010;
while(l<=r)
{
int mid=(l+r)>>1;
if(judge(mid))
l=mid+1;
else
r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}
E -- 咸鱼旅行
很不明白为什么很多人要用二分，也许是我没入坑，也许是上天安排，做过类似的题，但这个题数据范围较大，于是直接想到SPFA或者dij+堆优化。但看到边m的范围，加之我对SPFA的一种天生抵抗，于是直接上手dij。1A。
const int N=1e6+10;
int n,m,s,t;
int tot,head[N],d[N],vis[N];
struct edge
{
int to,next,c;
}e[N];
struct node
{
int to,c;
friend bool operator <(node a,node b)
{
return a.c>b.c;
}
};
priority_queue<node>q;
void add(int u,int v,int c)
{
e[tot].to=v,e[tot].c=c;
e[tot].next=head[u];
head[u]=tot++;
}
void init()
{
tot=0;
for(int i=1;i<=n;i++)
{
d[i]=INF;
head[i]=-1;
vis[i]=0;
}
while(!q.empty()) q.pop();
}
void dij()
{
q.push(node{s,d[s]});
while(!q.empty())
{
node tmp=q.top();
q.pop();
int u=tmp.to;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i+1;i=e[i].next)
{
int v=e[i].to,c=e[i].c;
int tt=c;
if(u!=s) tt=max(d[u],c);
if(d[v]>tt)
{
d[v]=tt;
q.push(node{v,tt});
}
}
}
if(d[t]==INF) puts("-1");
else printf("%d\n",d[t]);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
int u,v,c;
while(m--)
{
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);
add(v,u,c);
}
scanf("%d%d",&s,&t);
if(s==t)
{
puts("0");
continue;
}
dij();
}
return 0;
}
F -- 咸鱼文章
切完那几道大众题后于是瞄准了这道题，群里各种吐槽，于是发现是shabi题，上手用栈来了一发果然不负这通过率直接PE。队友发来捷报说已经A了，于是用队友代码交过了，然后中场rejudge，瞬间PE一大半，无脑又rejudge结果第一发A了，第二发PE。终榜竟然还有这个题的罚时，管理员你出来我们谈谈。。。
char s[N];//感觉是改数据了。。
int main()
{
while(gets(s))
{
stack<char>q;
while(!q.empty()) q.pop();
for(int i=0;s[i]!='\0';i++)
{
if(isalpha(s[i]))
{
while(isalpha(s[i]))
{
q.push(s[i]);
i++;
}
while(!q.empty())
{
printf("%c",q.top());
q.pop();
}
i--;
}
else printf("%c",s[i]);
}
puts("");
}
return 0;
}
G -- 咸鱼拷问
这道题就是上题说过的大众题，做完最短路那道于是瞄准了这道题，发现好像是RMQ板子，但我这只连板子都不想敲的废鱼直接把划分树板子粘过来改改又A了。。。
推荐题：POJ2104 kuangbin模板不谢。
const int N=1e5+5;
const double eps=1e-4;
const double PI=acos(-1.0);
int tree[20][N],t_l[20][N];
int a[N],b[N];
void build(int l,int r,int id)
{
if(l==r) return ;
int mid=(l+r)/2;
int same=mid-l+1;
for(int i=l;i<=r;i++) if(tree[id][i]<a[mid]) same--;
int lp=l,rp=mid+1;
for(int i=l;i<=r;i++)
{
if(tree[id][i]<a[mid]) tree[id+1][lp++]=tree[id][i];
else if(tree[id][i]==a[mid]&&same>0) tree[id+1][lp++]=tree[id][i],same--;
else tree[id+1][rp++]=tree[id][i];
t_l[id][i]=t_l[id][l-1]+lp-l;
}
build(l,mid,id+1);
build(mid+1,r,id+1);
}
int query(int l,int r,int k,int L,int R,int id)
{
if(l==r) return tree[id][l];
int mid=(L+R)/2;
int cnt=t_l[id][r]-t_l[id][l-1];
if(cnt>=k)
{
int newl=L+t_l[id][l-1]-t_l[id][L-1];
int newr=newl+cnt-1;
return query(newl,newr,k,L,mid,id+1);
}
else
{
int newr=r+t_l[id][R]-t_l[id][r];
int newl=newr-(r-l-cnt);
return query(newl,newr,k-cnt,mid+1,R,id+1);
}
}
int main()
{
int n,m;
while(~scanf("%d",&n))
{
memset(tree,0,sizeof(tree));
for(int i=1;i<=n;i++)
{
scanf("%d",&tree[0][i]);
a[i]=tree[0][i];
}
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
sort(a+1,a+n+1);
build(1,n,0);
for(int i=1;i<=n;i++)
{
int r=i,l=i-b[i]+1;
ll mi=ll(query(l,r,1,1,n,0));
ll ma=ll(query(l,r,r-l+1,1,n,0));
printf("%lld\n",mi*ma);//注意此题数据范围
}
}
return 0;
}
H -- 喵哈哈村的战斗魔法师丶坏坏い月
啊呀，石乐志！当时直接想到主席树上去了，然而我这只废鱼只会划分树板子。腿队友说分块可以写，于是这个题交给队友写，那我干嘛呢，当然是打打酱油啦，有这么强的队友躺着都能赢。好吧，事实是队友写了很久样例各种没问题但就是WA了，我们出的样例简直无脑。无奈后三个小时没能做出来。后来看荣神用线段树过了才恍然大悟。线段大法好哇。
很迷当时为什么直接想到主席树上去了。。。
const int N=1e5+5;
int n,m;
struct node
{
int l,r;
ll ma,add;
} a[N<<2];
void pushdown(int k)
{
if(a[k].add)
{
a[k*2].add+=a[k].add;
a[k*2+1].add+=a[k].add;
a[k*2].ma+=a[k].add;
a[k*2+1].ma+=a[k].add;
a[k].add=0;
}
}
void pushup(int k)
{
a[k].ma=max(a[k*2].ma,a[k*2+1].ma);
}
void build(int l,int r,int k)
{
a[k].l=l,a[k].r=r;
a[k].ma=a[k].add=0;
if(l==r)
{
scanf("%lld",&a[k].ma);
return ;
}
int mid=(l+r)/2;
build(l,mid,2*k);
build(mid+1,r,2*k+1);
pushup(k);
}
void update(int l,int r,ll c,int k)
{
if(l<=a[k].l&&a[k].r<=r)
{
a[k].add+=c;
a[k].ma+=c;
return ;
}
pushdown(k);
int mid=(a[k].l+a[k].r)/2;
if(l<=mid) update(l,r,c,2*k);
if(r>mid) update(l,r,c,2*k+1);
pushup(k);
}
ll query(int l,int r,ll c,int k)
{
if(a[k].l==l&&a[k].r==r&&a[k].l==a[k].r)
{
if(a[k].ma>=c) return a[k].l;
return -1;
}
pushdown(k);
int mid=(a[k].l+a[k].r)/2;
if(r<=mid) return query(l,min(mid,r),c,2*k);
if(l>mid) return query(max(mid+1,l),r,c,2*k+1);
else
{
int ans=query(l,mid,c,2*k);
if(ans==-1) return query(mid+1,r,c,2*k+1);
return ans;
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
build(1,n,1);
int op,l,r;
ll c;
while(m--)
{
scanf("%d%d%d%lld",&op,&l,&r,&c);
if(op==1) printf("%lld\n",query(l,r,c,1));
else update(l,r,c,1);
}
}
return 0;
}
J -- 喵哈哈村的几何大师╰☆莣メ誋こ月
腿队友在写分块的时候我和zp一直在看这个题，但D题过的人越来越多于是zp去读D题，我继续推这个题。无脑毫无思路，在作辅助线求关系的路上渐行渐远，于是找已经退役的祥琨大神和青龙大神帮我解解。姜果然老的辣，昆神很快就给出了思路，然后我这只废鱼磨蹭半天才出代码，却被卡精度了，于是绝望之际xjb改成了用acos就过了。。。。
不过这个题倒是挺有趣的。等腰三角形 给你a,b,c,d求E。
。
来看看昆神给的思路：
两幅图简单明了，不愧是我最敬佩的昆神。当然青龙大哥也很好，专门从考研自习室过来给我讲解这道题，感动！
从图中可以看出只要知道了腰或者底边，那么x，y就可以算出来，从而可以推出横跨边z。然而上面已经讲过WA了，因为有太多的sqrt了， 精度损失。。
于是在这种思路的基础上能不能尽量少用sqrt呢，于是我们观察到要求横跨边z肯定要开方，而底边b怎么来的呢，其实我们可以随便设一个值，如果设腰来求底边的话还是要开方的，所以直接设底边b=10.0，不大不小刚好。于是我们可以算出x,y。但从角AB出发的那条边 e 和从角CD出发的那条边 f 都是未知的，所以我们可以根据余弦定理算出来e^2,已知x，已知e^2，z^2也可以根据顶角用余弦定理算出来.于是用角E作余弦定理就正好解决了，再用acos函数就可以知道E角所对应的pi值了。
const double pi=acos(-1.0);
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
double A,B,C,D;
scanf("%lf%lf%lf%lf",&A,&B,&C,&D);
A=A*pi/180.0;//转化成pi进制下的值便于计算
C=C*pi/180.0;
D=D*pi/180.0;
B=B*pi/180.0;
double tmp=cos(pi-A-B-C-D);
double b=10.0;//设底边为10，大小无所谓
double x=b*sin(D)/sin(pi-D-B-A);
double y=b*sin(B)/sin(pi-D-B-C);
double a=5.0/cos(A+B);//求出腰
double z=(a-x)*(a-x)+(a-y)*(a-y)-2*tmp*(a-x)*(a-y);//这里的z实际上是z*z,防止精度丢失
double e=y*y+100-20*y*cos(C+D);//其实是e*e
double tt=sqrt(z*e);//只开方一次，无脑AC
printf("%.2f\n",acos((z+e-x*x)/(2*tt))*180.0/pi);
// printf("%.2f\n",asin(x*sin(A)/z)/pi*180.0);//第一种方法WA 。。。
}
return 0;
}
总结：高中生也算高校？C题shabi错误简直石乐志。。