Problem B. Balanced Diet
其实就是对每种糖果从大到小的排序后，计算前缀和后再 \(O(n)\) 处理，由于最多只有 \(n\) 个糖果，所以最大复杂度是 \(O(nlogn)\)。对于题目给的每种糖果的限制 \(limit\) ，就把当前小于 \(limit\) 的贡献加到 \(max(limit,i)\) 上。
vector<int>g[N];
void solve(){
int n=read(),m=read();
vector<int>lim(m+1),f(n+1);
for(int i=1;i<=m;i++){
lim[i]=read();
g[i].clear();
}
for(int i=1;i<=n;i++){
int x=read(),y=read();
g[y].push_back(x);
}
for(int i=1;i<=m;i++){
sort(g[i].begin(),g[i].end());
reverse(g[i].begin(),g[i].end());
}
for(int i=1;i<=m;i++){
int sum=0;
for(int j=0;j<g[i].size();j++){
f[max(j+1,lim[i])]+=g[i][j];
}
}
for(int i=1;i<=n;i++){
f[i]+=f[i-1];
}
int ansx=0,ansy=1;
for(int i=1;i<=n;i++){
if(ansx*i<ansy*f[i]){
ansx=f[i];
ansy=i;
}
}
int g=__gcd(ansx,ansy);
cout<<ansx/g<<"/"<<ansy/g<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
Problem C. Line-line Intersection
哈哈哈哈，赛时很搞的一道题。 \(Xishui\) 敲的按照斜率排序，我敲的计数，交上去 \(wa2\) 。然后换 \(afeng\) 写了一版还是 \(wa2\) 。一直卡了 \(2\) 个小时，然后我写了点样例把 \(eps\) 从 \(1e-10\) 调到 \(1e-22\) 就过了。
做法也确实很简单，两两配对的可能情况是 \(n*(n-1)/2\) 。两条直线平行时若斜率相同的直线数 \(tmp\) ，那么对于当前的斜率的情况数为 \(tmp*(tmp-1)/2\) 。若有 \(sam\) 条直线重合于一起，那么对于当前的重合情况配对数为 \(sam*(sam-1)/2\) 。最后 \(O(n)\) 计算一下就好。
struct node{
int a,b,c,d;
double k,jj;
void set_k(){
if(c-a!=0)k=(d-b)*1.0/(c-a);
else k=inf;
}
void set_jj(){
if(c-a!=0)jj=b-a*k;
else jj=a;
}
friend bool operator<(const node&a,const node&b){
if(fabs(a.k-b.k)<eps)return a.jj<b.jj;
return a.k<b.k;
}
}vec[N];
void solve(){
int n=read();
for(int i=1;i<=n;i++){
vec[i].a=read();
vec[i].b=read();
vec[i].c=read();
vec[i].d=read();
vec[i].set_k();
vec[i].set_jj();
}
sort(vec+1,vec+1+n);
int ans=n*(n-1)/2,sam=1,tol=1,tmp=0;
for(int i=2;i<=n;i++){
if(fabs(vec[i].k-vec[i-1].k)>=eps){
tmp+=sam*(sam-1)/2;
ans-=tol*(tol-1)/2-tmp;
tol=1,sam=1,tmp=0;
}else if(fabs(vec[i].jj-vec[i-1].jj)<eps){
tol++;
sam++;
}else {
tmp+=sam*(sam-1)/2;
sam=1;tol++;
}
}
tmp+=sam*(sam-1)/2;
ans-=tol*(tol-1)/2-tmp;
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
Problem E. Minimum Spanning Tree
显然对于原图建新图再跑最小生成树是不行的，那么一定存在规律。
由于给的是树，对于每个节点的子边与父边，一起构成了一张完全图。在完全图上找最小生成树就是找一个最小的点权（原图的边权），一直与其他边连接。那么对于每个节点计算一下就好，其中度为 \(1\) 和 \(2\) 的时候特判。
想起来，我训练写的时候忘记给最小值乘次数 \(wa\) 了一发，后来自己写的时候还是忘记 \(wa\) 了一发。
vector<PII>G[N];
void solve(){
int n=read();
for(int i=1;i<=n;i++){
G[i].clear();
}
vector<int>d(n+1);
for(int i=1;i<n;i++){
int x=read(),y=read(),w=read();
G[x].push_back({y,w});d[x]++;
G[y].push_back({x,w});d[y]++;
}
int ans=0;
for(int i=1;i<=n;i++){
if(d[i]==1)continue;
if(d[i]==2){
for(auto it:G[i]){
ans+=it.second;
}
continue;
}
int minn=inf;
for(auto it:G[i]){
minn=min(it.second,minn);
ans+=it.second;
}
ans+=minn*(d[i]-2);
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
Problem F. Mini-game Before Contest
赛场上没做出来（想法完全错的），后来淡然哥教的。
首先对于出度为 \(0\) 的点，总是存在必胜态和必败态。由这些点去建反图跑 \(bfs\) ,如果到达一个点的父节点中有必胜态，那么队伍一定会走必胜态，状态确定。若没有必胜态而存在状态未确定的点就说明有环的存在，队伍为避免失败会走这种平局点，若只有必败态那也状态确定。所以有建立一个 \(f[i][3]\) 表示三种状态，开始用 \(bfs\) 跑反图进行状态转移。
vector<int>G[N];
int f[N][7],d[N][7],b[N],rea[N];
int pre(int x){
if(x==1)return 6;
return x-1;
}
void solve(){
int n=read(),m=read();
memset(f,-1,sizeof f);
memset(d,0,sizeof d);
for(int i=0;i<=n;i++){
G[i].clear();
}
for(int i=1;i<=m;i++){
int a=read(),b=read();
G[b].push_back(a);
for(int j=1;j<=6;j++){
d[a][j]++;
}
}
string s,t;
cin>>s>>t;
s=' '+s;t=' '+t;
for(int i=1;i<=6;i++){
rea[i]=s[i]-'A';
b[i]=(t[i]-'0')^rea[i];
}
queue<PII>q;
for(int i=1;i<=n;i++){
if(d[i][1]==0){
for(int j=1;j<=6;j++){
if(s[j]=='A'){
f[i][j]=1;
q.push({i,j});
}else {
f[i][j]=0;
q.push({i,j});
}
}
}
}
while(q.size()){
auto x=q.front();
q.pop();
for(auto e:G[x.first]){
if(f[e][pre(x.second)]!=-1)continue;
if(f[x.first][x.second]==b[pre(x.second)]){
f[e][pre(x.second)]=b[pre(x.second)];
q.push({e,pre(x.second)});
}else {
d[e][pre(x.second)]--;
if(d[e][pre(x.second)]==0){
f[e][pre(x.second)]=b[pre(x.second)]^1;
q.push({e,pre(x.second)});
}
}
}
}
for(int i=1;i<=n;i++){
if(f[i][1]==-1)cout<<"D";
if(f[i][1]==0)cout<<'A';
if(f[i][1]==1)cout<<'B';
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
Problem G. Radar Scanner
赛时是 \(afeng\) 用两次二分写的，实际上不需要二分。
横纵坐标之间没有关系可以分开计算，那么先考虑横坐标上的移动。
显然这样的移动要找所有竖着的线的中位线，如果偶数指定两条中的一条即可。中位线到各条线之间的距离和就是答案的两倍，好吧，并不是，因为对于一个矩形真正的贡献只有一条边到中位线的距离，而我们算了两条边到中位线的距离，要先减去所有矩形的长再除以 \(2\) 。对纵坐标也是同样的方法计算。
void solve(){
int n=read(),ans=0;
vector<int>x(n*2+1),y(n*2+1);
for(int i=1;i<=n;i++){
int a=read(),b=read(),c=read(),d=read();
ans-=d-b+c-a;
x[i]=a;x[i+n]=c;y[i]=b;y[i+n]=d;
}
sort(x.begin()+1,x.end());
sort(y.begin()+1,y.end());
int finx=x[n],finy=y[n];
for(int i=1;i<=2*n;i++){
ans+=abs(x[i]-finx)+abs(y[i]-finy);
}
cout<<ans/2<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
Problem H. Skyscraper
\(Xishui\) 好像用的树状数组搞了搞过的。我赛后用 \(BowTen\) 教的线段树补了。
对于每一个严格单峰（先单调增，后单调减）的答案是最高点的高度。那么对于两个线段合并的时候，如果没有破坏这个单峰性就答案不变，否则答案就是两个单峰的高度和减去左边线段的右端和右边线段的左端的更低高度，需要减是因为两个单峰合并的时候单峰的底部是可以共用的。感觉比什么差分数组直观啊。
int a[N];
struct node{
int rm,lm,cnt;
int tag;
node operator+(const node e)const{
node ret=*this;
ret.cnt=ret.cnt+e.cnt-min(ret.rm,e.lm);
ret.rm=e.rm;
ret.tag=0;
return ret;
}
}tr[N<<2];
void up(int id){
tr[id]=tr[lson]+tr[rson];
}
void build (int id,int l,int r){
tr[id].tag=0;
if(l==r){
tr[id].cnt=tr[id].rm=tr[id].lm=a[l];
return ;
}
int mid=l+r>>1;
build(lson,l,mid);
build(rson,mid+1,r);
up(id);
}
void settag(int id,int x){
tr[id].cnt+=x;
tr[id].lm+=x;
tr[id].rm+=x;
tr[id].tag+=x;
}
void down(int id){
settag(lson,tr[id].tag);
settag(rson,tr[id].tag);
tr[id].tag=0;
}
void modify(int id,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr){
settag(id,x);
return ;
}
if(tr[id].tag) down(id);
int mid=l+r>>1;
if(qr<=mid){
modify(lson,l,mid,ql,qr,x);
}else if(ql>mid){
modify(rson,mid+1,r,ql,qr,x);
}else {
modify(lson,l,mid,ql,qr,x);
modify(rson,mid+1,r,ql,qr,x);
}
up(id);
}
node query(int id,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tr[id];
}
if(tr[id].tag){
down(id);
}
int mid=l+r>>1;
if(qr<=mid){
return query(lson,l,mid,ql,qr);
}else if(ql>mid){
return query(rson,mid+1,r,ql,qr);
}else {
return query(lson,l,mid,ql,qr)+query(rson,mid+1,r,ql,qr);
}
}
void solve(){
int n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
build(1,1,n);
while(m--){
int op=read(),l=read(),r=read();
if(op==1){
int k=read();
modify(1,1,n,l,r,k);
}else {
cout<<query(1,1,n,l,r).cnt<<'\n';
}
}
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
Problem J. Time Limit
按照题目模拟一下就好。
我好像写的时候还 \(wa2\) 了一下，是先定义了 \(vector\) 数组然后才读入 \(n\) ，本地居然没测出来。
感觉一方面是改用这样定义数组才没几天，另一方面是有点紧张。
void solve(){
int ans,n=read();
for(int i=1;i<=n;i++){
int x=read();
if(i==1)ans=x*3;
ans=max(ans,x+1);
}
if(ans%2)ans++;
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}