A-Temporarily unavailable
这题麻烦地方就在于情况有点多，包括圆含不含左右端点这些。其实稍微整理一下就行。
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=200050;
int n;
int main()
{
int Test;cin>>Test;
while(Test--)
{
int a,b,c,r;
cin>>a>>b>>c>>r;
if(a>b)swap(a,b);
int ans1=max(min(b,c-r)-a,0);
int ans2=max(b-max(a,c+r),0);
cout<<ans1+ans2<<endl;
}
return 0;
}
B1-K for the Price of One (Easy Version)
B2-K for the Price of One (Hard Version)
直接说Hard Version吧...
其实我也没怎么看这题，xydg出的
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=200050;
int n,p,k;
int ans;
int a[N],z[N],s[N];
int main()
{
int Test;cin>>Test;
while(Test--)
{
ans=0;
scanf(
for(int i=1;i<=n;++i)
{
scanf(
}
sort(a+1,a+n+1);
for(int i=0;i<=n+5;++i)z[i]=s[i]=0;
for(int i=1;i<=k;++i)s[i]=a[i];
for(int i=2;i<=k;++i)s[i]+=s[i-1];
s[k]=a[k];
int now=0;
for(int i=1;i<=n;++i)
{
int pos=
z[pos]+=a[i];
if(i>=k)
{
now=z[pos]+s[pos]-a[pos];
}
else now=s[i];
if(now<=p)ans=i;
}
cout<<ans<<endl;
}
return 0;
}
C-Petya and Exam
嘛这题其实就按照$t_i$从小到大贪心就行了......
总的来说，一个思路是先做简单题再做大题，这样必须做的题就变少了，当然具体怎么做还是要贪贪的......
我们在$t_i-1$处离开考场是可以更优的，因为你少做一道必须的题，而之前的题你都能做，所以花费的总时间也算得出来，所以就这么贪就行......
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=200050;
int n;
ll T;
ll a,b;
struct problems
{
int type;
ll t;
}p[N];
bool cmp(const problems &x,const problems &y)
{
return x.t<y.t;
}
int cntEasy,cntHard;
int ans;
int main()
{
int Test;scanf(
while(Test--)
{
scanf(
cntEasy=cntHard=ans=0;
for(int i=1;i<=n;++i)
{
scanf(
if(p[i].type)cntHard++;
else cntEasy++;
}
for(int i=1;i<=n;++i)
{
scanf(
p[i].t--;
}
sort(p+1,p+n+1,cmp);
p[n+1].t=T;
int ans=0,tmp=0;
int cnt1=0,cnt2=0;
for(int i=1;i<=n+1;++i)
{
ll now=p[i].t-(a*cnt1+b*cnt2);
tmp=(cnt1+cnt2);
if(now>=0)
{
ll t1=min(now/a,(ll)cntEasy-cnt1);
tmp+=t1;now-=t1*a;
ll t2=min(now/b,(ll)cntHard-cnt2);
tmp+=t2;now-=t2*b;
ans=max(ans,tmp);
}
if(p[i].type==1)cnt2++;else cnt1++;
}
printf(
}
return 0;
}
D-Enchanted Artifact
交互题都是人类智慧，还好这题不难。
一种构造方案是，先构造一个长度为$300$的全是a的串，这样可以问出串中b的个数。同样的道理，可以问出串中a的个数，这样串长就确定了。
然后就让答案串和询问串先全设为a，然后第i次询问将第i个a变为b，看编辑距离是增加还是减少，这样可以确定这个位置的答案。
另外，最后那个位置其实是不需要询问的，因为可以通过前面a的个数和b的个数直接得出来，这样就做完了。
#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define ls id<<1
#define rs id<<1|1
using namespace std;
int cnta,cntb,n;
char ans[305];
char s[305];
int main()
{
for(int i=0;i<300;++i)s[i]='a';
printf(
int d;scanf(
if(d==0)
{
printf(
fflush(stdout);
return 0;
}
cnta=300-d;
for(int i=0;i<300;++i)s[i]='b';
printf(
scanf(
if(d==0)
{
printf(
fflush(stdout);
return 0;
}
n=cnta+cntb;
s[n]='\0';
for(int i=0;i<n;++i)
{
s[i]=ans[i]='a';
}
int D=cntb;
for(int i=0;i<n-1;++i)
{
s[i]='b';
printf(
int now;scanf(
if(now==0)
{
printf(
fflush(stdout);
return 0;
}
if(now<D)ans[i]='b';
else ans[i]='a';
s[i]='a';
}
for(int i=0;i<n-1;++i)
{
if(ans[i]=='a')cnta--;
else cntb--;
}
if(cnta)ans[n-1]='a';else ans[n-1]='b';
printf(
return 0;
}
E-The Cake Is a Lie
（蛋糕是个谎言！）
这题其实思路很简单......就是实现有点麻烦。
如果我们把三角形抽象为点，这题要好写一些。
观察到最后的图形，有若干个三角形，其中最外层的三角形（即删除后剩下的图形还是一个凸多边形）一定与剩下的多边形只有一个公共边，将三角形抽象为点后，发现这个点的度数为1，于是剩下的工作就是建图，然后做一遍拓扑排序，就可以解决第二问。
第一问的话我的解法是：不把三角形抽象为点，而是顶点为点，像这样动态加边，因为最外层的三角形的一个顶点出现次数一定为1（因为只有一个三角形以其为顶点），所以我们就可以把这个点删除后，与这个顶点相连的两个点各加一条边。但加边是有限制的，如果这两个点已经在同一连通分量里面，那就不加这条边。像这样，用一个队列进行bfs的话，最后加出来的图一定是一条链，这样就解决了第一问。
代码先留着，后面再补。
Comments NOTHING