比赛链接
({frak{A. Temporarily unavailable}})
求两条线段交的长度。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=3e3+5,p=998244353;
int a,b,c,r;
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
int main()
{
int t=in();
while(t--){
a=in(),b=in(),c=in(),r=in();
if(a>b) swap(a,b);
int L=c-r,R=c+r;
if(L<=b&&R>=a) printf("%d
",(b-a)-(min(b,R)-max(a,L)));
else printf("%d
",b-a);
}
return 0;
}
({frak{B. K for the Price of One}})
考虑购买(n)个物品，排序，先选第(n-k+1)到(n)个物品，花费(v_n)，再购买物品(n-k)，以此推类，最后再一个个购买物品(1)到(n\% k)。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+5;
int n,k,p,a[N],ans,res,sum;
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
int main()
{
int t=in();
while(t--){
n=in(),p=in(),k=in(),ans=0;
for(int i=1;i<=n;++i) a[i]=in();
sort(a+1,a+n+1);
for(int i=0;i<k;++i){
res=(p-=a[i]),sum=i;
if(res<0) break;
for(int j=i+k;j<=n;j+=k)
if(res>=a[j]) res-=a[j],sum+=k;
else break;
ans=max(sum,ans);
}
printf("%d
",ans);
}
return 0;
}
({frak{C. Petya and Exam}})
以(t)为关键字排序，不严谨地说，对于前(forall i in left[ 1,n-1 ight])个任务，应在(min(t_{i+1}-1,t_i,T))内完成，特别的，所有任务应在(min(t_n,T))内完成，若时间有剩余，则贪心选择之后的(n-i)个任务完成。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+5;
struct hh{
LL t,op;
bool operator<(const hh &a) const{
return t<a.t;}
}a[N];
LL n,k,p[N],d[2],T,ans,res,sum,n0,n1,pre[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
int main()
{
int t=in();
while(t--){
n=in(),T=in(),d[0]=in(),d[1]=in();n0=n1=ans=0;
for(int i=1;i<=n;++i) a[i].op=in();
for(int i=1;i<=n;++i) a[i].t=in();
sort(a+1,a+n+1);
for(int i=1;i<=n;++i) pre[i]=pre[i-1]+d[a[i].op];
if(pre[n]<=T){ans=n;goto dd;}
for(int i=n-1;~i;--i){
sum=i;if(a[i+1].op) ++n1;else ++n0;
if(a[i].t==a[i+1].t) continue;
LL s=a[i+1].t-1;s=min(s,T);
if(pre[i]>s) continue;
res=s-pre[i];
if(n0*d[0]<=res){
res-=n0*d[0],sum+=n0;
if(n1*d[1]<=res) sum+=n1;
else sum+=res/d[1];
}
else sum+=res/d[0];
ans=max(sum,ans);
}
dd:printf("%lld
",ans);
}
return 0;
}
({frak{D. Enchanted Artifact}})
先猜(a)，得到(n)，再猜(n)个(b)，一次可以推出字符串中(a)与(b)的个数，再每次换一个字母猜(n-1)次，最后一次输出答案，共猜了(n+2)次。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=3e2+3;
int n,m,na,nb;
char c[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
int main()
{
puts("a"),fflush(stdout);
if(!(n=in())) return 0;
memset(c+1,'b',n),puts(c+1),fflush(stdout);
if(!(m=in())) return 0;
c[++n]='b',na=m;
for(int i=1;i<n;++i){
c[i]='a',puts(c+1),fflush(stdout);
if((m=in())<na) --na;else c[i]='b';
if(!na) return 0;
}
c[n]='a',puts(c+1),fflush(stdout),m=in();
return 0;
}
({frak{E. The Cake Is a Lie}})
。。。CF的题解是什么鬼啊，对偶图是什么鬼啊。。。码风太毒瘤了啊。。。
显然，多边形的边必然只会出现(1)次，其他的边会出现(2)次，用(map)将其存起，就解决了序列(p)。
将每个点出现的次数存入(deg)中，取出(deg=1)的点拓扑排序，得到序列(q)（对于(deg_i=1)，必然会切出(i)左右的点与(i)组成的三角形）。
({frak{code:}})
#include<bits/stdc++.h>
#define IL inline
#define MP make_pair
#define pb push_back
#define mem(a) memset(a+1,0,4*n)
using namespace std;
const int N=1e5+3;
struct hh{int a,b,id;};
struct kk{int to,nxt;}e[N<<1];
map<pair<int,int>,int>mp;
vector<hh>a[N];
queue<int>q;
int n,num,fir[N],deg[N],vis[N],bel[N];
IL int in(){
char c;int f=1;
while((c=getchar())<'0'||c>'9')
if(c=='-') f=-1;
int x=c-'0';
while((c=getchar())>='0'&&c<='9')
x=x*10+c-'0';
return x*f;
}
IL void add(int x,int y){
e[++num]=(kk){y,fir[x]},fir[x]=num;
e[++num]=(kk){x,fir[y]},fir[y]=num;
}
IL void pre(){
num=0,mp.clear(),mem(fir),mem(deg),mem(vis),mem(bel);
for(int i=1;i<=n;++i) a[i].clear();
while(q.size()) q.pop();
}
void solve(){
int b[3],u;n=in();pre();
for(int i=1;i<=n-2;++i){
for(int j=0;j<3;++j) ++deg[b[j]=in()];
sort(b,b+3);
a[b[0]].pb((hh){b[1],b[2],i}),
a[b[1]].pb((hh){b[0],b[2],i}),
a[b[2]].pb((hh){b[0],b[1],i}),
++mp[MP(b[0],b[1])],
++mp[MP(b[0],b[2])],
++mp[MP(b[1],b[2])];
}
map<pair<int,int>,int>::iterator it;
for(it=mp.begin();it!=mp.end();++it)
if(it->second==1) add(it->first.first,it->first.second);
u=1;
while(!vis[u]){
printf("%d ",u),vis[u]=1;
for(int i=fir[u],v;v=e[i].to;i=e[i].nxt) if(!vis[v]) u=v;
}
printf("
");
for(int i=1;i<=n;++i) if(deg[i]==1) q.push(i);
for(int i=1;i<=n-2;++i){
u=q.front();q.pop(),vis[u]=2;
for(int i=0;i<a[u].size();++i)
if(vis[a[u][i].a]^2&&vis[a[u][i].b]^2){
printf("%d ",a[u][i].id);bel[a[u][i].id]=1;
int l=a[u][i].a,r=a[u][i].b;
if(--deg[l]==1) vis[l]=2,q.push(l);
if(--deg[r]==1) vis[r]=2,q.push(r);
break;
}
}
for(int i=1;i<=n-2;++i) if(!bel[i]) printf("%d ",i);
printf("
");
}
int main()
{
int t=in();
while(t--) solve();
return 0;
}