JZSIM 3.2

Author Avatar
空気浮遊 2019年03月02日
  • 在其它设备中阅读本文章

爆零大赛
WA CE 没写 三开花

T1 Pair

结论 + 构造一组合法方案

跟重心和贪心有关

然后某个循环的判断打错了（一个非运算（一个感叹号）） 100 -> 0

这已经不是我第一次犯这种错误了所以我认了... 不对这就是我第一次犯这种错误啊

为什么，为什么过了样例？为什么我没造样例？

nmd，wsm

// Code by ajcxsu
// Problem: pair

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0; x=0;
    while(!isdigit(ch)) pl=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}
template<typename T, typename ...Args> inline void gn(T &x, Args &...args) { gn(x), gn(args...); }

const int N=1e5+10;
int h[N], to[N<<1], nexp[N<<1], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
int con[N], siz[N], S, maxn, hvy;
int spe[N];
void dfs(int x, int fr) {
    siz[x]=spe[x];
    int ma=0;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr) dfs(to[u], x), siz[x]+=siz[to[u]], ma=max(siz[to[u]], ma);
    ma=max(ma, S-siz[x]);
    if(ma<maxn) hvy=x, maxn=ma;
}
struct Stack {
    int a[N];
    int t=0;
    int top() { return a[t]; }
    void push(int x) { a[++t]=x; }
    void pop() { t--; }
    bool empty() { return !t; }
    int size() { return t; }
} unfin, fin, deal, cac;
int tag[N], idx;

void add(int x, int fr) {
    if(spe[x]) deal.push(x), tag[x]=idx;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr) add(to[u], x);
}
void link(int a, int b) { con[a]=b, con[b]=a; }
void dfs2(int x) {
    for(int u=h[x];u;u=nexp[u]) {
        ++idx;
        add(to[u], x);
        while(!unfin.empty() && !deal.empty()) {
            link(deal.top(), unfin.top());
            cac.push(unfin.top()), cac.push(deal.top()), deal.pop(), unfin.pop();
        }
        int nt=fin.t;
        while(nt && deal.size()>=2) {
            int v=con[fin.a[nt]];
            if(tag[v]!=idx) {
                link(fin.a[nt], deal.top()), cac.push(deal.top()), deal.pop();
                link(v, deal.top()), cac.push(deal.top()), deal.pop();
            }
            nt--;
        }
        while(!deal.empty()) unfin.push(deal.top()), deal.pop();
        while(!cac.empty()) fin.push(cac.top()), cac.pop();
    }
    if(!unfin.empty()) link(x, unfin.top());
}

int main() {
    #ifndef LOCAL
    freopen("pair.in","r",stdin);
    freopen("pair.out","w",stdout);
    #endif
    int n, k;
    gn(n, k);
    int u, v, w;
    for(int i=0; i<n-1; i++) gn(u, v, w), ins(u, v), ins(v, u);
    for(int i=0; i<k; i++) gn(u), spe[u]=1;
    dfs(1, 0), S=siz[1], maxn=0x3f3f3f3f, dfs(1, 0);
    dfs2(hvy);
    for(int i=1; i<=n; i++)
        if(spe[i]) printf("%d %d\n", i, con[i]), spe[con[i]]=0;
    return 0;
}

T2 Rank

五年 OI 一场空...

为什么头文件要打 "hpp"？
为什么我没有想到可以排序 +cmp？
为什么我没有想到 cmp 可以只用一次 ask？
为什么我不知道有折半插入排序这种东西？

nmd，wsm

顺便，stable_sort 的比较次数竟然跟插入排序很接近...

可以发现根据复读人的类别变成这样：$AAA123BBB$，也就是分成五类人。

每次询问一对人，分四种情况讨论得到的询问组合，其中三种情况一定能分出至少一个人到 $A,B$，剩下一种情况是 $1,2,3$ 互相问。

然后对 $A,B$ 做插入排序即可。次数本地 10000 左右。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include "rank.h"
namespace test
{
int n,rk[1234],qry=0;
}
char ask(int a,int b)
{
    using namespace test; ++qry;
    if(!(0<=a&&a<n&&0<=b&&b<n&&a!=b))
    {
        puts("invalid query!");
        printf("%d %d\n",a,b);
        exit(-1);
    }
    char s=(rk[a]<rk[b])?'b':'g';
    if(rk[a]<1)
        return (s=='g')?'n':s;
    if(rk[a]==1) return 'n';
    if(rk[a]==2)
        return (rk[b]==3)?s:'n';
    if(rk[a]==3)
        return (s=='g')?'n':s;
    return (s=='b')?'n':s;
}
int main()
{
    freopen("rank.in","r",stdin);
    using namespace test;
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d",rk+i);
    std::vector<int> v=work(n);
    if((int)v.size()!=n)
    {
        puts("wrong length");
        exit(-1);
    }
    for(int i=0;i<n;++i)
        if(v[i]!=rk[i])
        {
            puts("wrong answer");
            exit(-1);
        }
    printf("Good job! You used %d queries.\n",qry);
}

#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rint(int l, int r) { return rng()%(r-l+1)+l; }

const int N=1001, M=N*N;
vector<int> unc, A, B;
int rk[N], rel[N][N];
int h[N], to[M], nexp[M], in[N], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, in[b]++, p++; }
// 0 n 1 b 2 g
// meask(
inline int mea(int a, int b) {
    if(a==b) return -1;
    if(rel[a][b]!=-1) return rel[a][b];
    char x=ask(a, b);
    if(x=='n') return rel[a][b]=0;
    if(x=='b') return rel[a][b]=1;
    if(x=='g') return rel[a][b]=2;
    return -1;
}
bool cmp(const int &a, const int &b) {
    return !mea(a, b);
} // a<b
bool cmp2(const int &a, const int &b){
    return mea(a, b);
}
vector<int> insert_sort(vector<int> arr, int a=-1, int b=-1) {
    vector<int> res;
    for(int x:arr)
        if(x!=a && x!=b)
            res.insert(lower_bound(res.begin(), res.end(), x, a==-1?cmp:cmp2), x);
    return res;
}
vector<int> work(int n)
{
    vector<int> ans;
    memset(rel, -1, sizeof(rel));
    for(int i=0; i<n; i++)
        unc.push_back(i);
    bool a[3];
    int x, y, na, nb;
    while(unc.size()>1) {
        x=rint(0, unc.size()-1), y=rint(0, unc.size()-1);
        if(x>y) swap(x, y);
        na=unc[x], nb=unc[y];
        if(unc.size()==2 && rel[na][nb]!=-1) break;
        if(x==y || rel[na][nb]!=-1) continue;
        a[0]=a[1]=a[2]=0;
        int t1, t2;
        a[t1=mea(na, nb)]=a[t2=mea(nb, na)]=1;
        if(a[1] && a[0]) {
            if(t1==1) A.push_back(na), unc.erase(unc.begin()+x);
            else A.push_back(nb), unc.erase(unc.begin()+y);
        }
        else if(a[1] && a[2]) {
            if(t1==1) A.push_back(na), B.push_back(nb);
            else A.push_back(nb), B.push_back(na);
            unc.erase(unc.begin()+y), unc.erase(unc.begin()+x);
        }
        else if(a[2] && a[0]) {
            if(t1==2) B.push_back(na), unc.erase(unc.begin()+x);
            else B.push_back(nb), unc.erase(unc.begin()+y);
        }
    }
    int ham=-1;
    if(unc.size()==2) {
        na=unc[0], nb=unc[1];
        for(int x:A) {
            a[0]=a[1]=a[2]=0;
            a[mea(na, x)]=a[mea(x, na)]=1;
            if(a[0] && !a[1] && !a[2]) { ham=na, A.push_back(nb); break; } 
        }
        if(ham==-1) ham=nb, A.push_back(na);
    }
    else ham=unc[0];
    int sec=-1, thr=-1;
    for(int x:A) {
        a[0]=a[1]=a[2]=0;
        a[mea(ham, x)]=a[mea(x, ham)]=1;
        if(a[0] && !a[1] && !a[2]) {
            if(sec==-1) sec=x;
            else thr=x;
        }
    }
    if(mea(sec, thr)!=1) swap(sec, thr);
    B=insert_sort(B);
    A=insert_sort(A, sec, thr);
    // stable_sort(B.begin(), B.end(), cmp);
    // stable_sort(A.begin(), A.end(), cmp);
    int tot=3+B.size();
    for(int j=B.size()-1;j>=0;j--) rk[B[j]]=tot--;
    rk[thr]=tot--, rk[sec]=tot--, rk[ham]=tot--;
    for(int j=A.size()-1;j>=0;j--) if(A[j]!=thr && A[j]!=sec) rk[A[j]]=tot--;
    for(int i=0; i<n; i++) ans.push_back(rk[i]);
    return ans;
}

T3 Circuit

这题一开始让我想起了上次那道 bzoj 的那个焊画框的题目...

神仙构造...

就不赘述了题解讲得挺好的，都讲到位了...

本文链接：https://pst.iorinn.moe/archives/jzsim-3-2.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

Powered by Typecho
Theme - Material