Codeforces Round 683 (Div. 1, by Meet IT) ABCDF题解

F和D都在ABC上做过类似的，但是没打好，道心破碎。。。。

A. Knapsack

若物品质量在[(w+1)/2,w]之间做完了

否则一直贪心加

void solve(){
    int n;
    ll w;cin>>n>>w;
    int c=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>w)c--;
    }
    if(!c){
        cout<<"-1\n";
        return;
    }
    for(int i=1;i<=n;i++)if(a[i]<=w&&a[i]>=(w+1)/2){
        cout<<"1\n"<<i<<'\n';
        return;
    }
    ll ww=0;
    vector<int>ans;
    for(int i=1;i<=n;i++)if(a[i]<=w){
        ans.push_back(i),ww+=a[i];
        if(ww>=(w+1)/2){
            cout<<ans.size()<<'\n';
            for(auto x:ans)cout<<x<<' ';
            cout<<'\n';
            return;
        }
    }
    cout<<"-1\n";
}

B. Catching Cheaters

过于朴素的字符串DP

void solve(){
    int n,m;
    cin>>n>>m;
    string s,t;
    cin>>s>>t;
    s=' '+s,t=' '+t;
    int res=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        if(s[i]==t[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+2);
        else dp[i][j]=max({dp[i][j],dp[i-1][j]-1,dp[i][j-1]-1});
        res=max(res,dp[i][j]);
    }
    cout<<res<<'\n';
}

C. Xor Tree

显然的是需要先建字典树再做

然后发现，字典树若左右两边都有节点，那么一侧最多只能留一个；DP解决。

int tr[N*31][2],tot=1,sz[N*31],dp[N*31];
void ins(int x,int ii){
    int p=1;
    for(int i=30;~i;i--){
        int &s=tr[p][x>>i&1];
        if(!s)s=++tot;
        p=s,sz[s]++;
    }
}
void dfs(int p){
    int ls=tr[p][0],rs=tr[p][1];
    if(ls)dfs(ls);
    if(rs)dfs(rs);
    if(!ls&&!rs){
        dp[p]=1;
        return;
    }
    if(!ls||!rs)dp[p]=max(dp[ls],dp[rs]);
    if(ls&&rs)dp[p]=max(dp[ls],dp[rs])+1;
}
int a[N];
void ini(){
}void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],ins(a[i],i);
    dfs(1);
    cout<<n-dp[1]<<'\n';
}

D. Frequency Problem

需要一个结论：最终的答案包含整体众数。

（待补

F. Line Distance

同ABC263EX；二分答案，把点转化为与圆的切线连点，然后随便拿个DS数一下。

#import<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld pi=acosl(-1);
const int N=200013;
struct pt{
    ld x,y;
}p[N];
int n,tr[N];
void add(int x,int v){
    for(;x<N;x+=x&-x)tr[x]+=v;
}
int qry(int x){
    int r=0;
    for(;x;x-=x&-x)r+=tr[x];
    return r;
}
ld t[N];
ll chk(ld r){ll ans=0;
    memset(tr,0,sizeof tr);
    vector<ld>li;
    vector<pair<ld,ld>>seg;
    ll cnt=0;
    for(int i=1;i<=n;i++){
        auto[x,y]=p[i];
        ld d=x*x+y*y;
        if(d<r*r){
            cnt++;
            continue;
        }
        d=sqrtl(d);
        ld phi=acosl(r/d);
        ld L=t[i]-phi,R=t[i]+phi;
        if(L<-pi)L+=pi+pi;
        if(L>pi)L-=pi+pi;
        if(R<-pi)R+=pi+pi;
        if(R>pi)R-=pi+pi;
        if(L>R)swap(L,R);
        seg.emplace_back(L,R),li.push_back(L),li.push_back(R);
    }
    sort(li.begin(),li.end());
    std::sort(seg.begin(), seg.end(),[&](auto x,auto y){return x.second<y.second;});
    function<int(ld)>get=[&](ld x){return lower_bound(li.begin(),li.end(),x)-li.begin()+1;};
    int x,y;
    for(auto[L,R]:seg)x=get(L),y=get(R),ans+=qry(x),add(x+1,1),add(y,-1);
    return (ll)n*(n-1)/2-ans;
}
 
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);
    ll k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y,t[i]=atan2l(p[i].y,p[i].x);
    int C=50;
    ld L=0,R=3e4;
    while(C--){
        ld mid=(L+R)/2;
        if(chk(mid)<k)L=mid;else R=mid;
    }
    cout<<L;
}