2023牛客暑假多校10

K

签到题。

答案即为 $\Big(\dfrac{2}{n}\Big)^m$ 。

注意特判 $n=1$ 时的情况。

代码

#include<bits/stdc++.h>

using namespace std;

long double n,m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    long double ans=1;
    if(n<=2.0) printf("%.15Lf\n",ans);
    else {
        long double t=2.0/n;
        for(int i=1;i<=m;i++) ans*=t;
        printf("%.15Lf\n",ans);
    }  
    return 0;
}

---

L

wjh 想到可以根据大小关系连边建图，之后拓扑排序。

但是 1、2 号节点的值要相同，不太好处理。

想到直接做 256 遍拓扑排序，枚举 1、2 号节点的值，但是还是不太好写。

比赛结束前一小时才想到可以将 1、2 号节点缩成一个点进行拓扑排序，判断拓扑排序的最大值是否大于 255 来判断解是否合法。

代码

#include<bits/stdc++.h>
#define N 1010

using namespace std;

int n;
vector <int> G[N];
int in[N],ans[N],maxn=0;

void toposort() {
    vector<int> l;
    queue<int> q;
    for(int i=1;i<n;i++) if(!in[i]) q.push(i);
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        l.push_back(x);
        for(auto y:G[x]) {
            if(--in[y]==0) {
                q.push(y);
                ans[y]=ans[x]+1;
                maxn=max(maxn,ans[y]);
            }
        }
    }
}
int r[N],g[N],b[N];

bool check(int x,int y) {
    return r[x]>r[y]&&g[x]>g[y]&&b[x]>b[y];
}
void work() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>r[i]>>g[i]>>b[i];
    if(check(1,2)||check(2,1)) {
        cout<<-1<<endl;
        return ;
    }
    for(int i=3;i<=n;i++) {
        if(check(i,1)||check(i,2)) {
            in[i-1]++;
            G[1].push_back(i-1);
        }
        if(check(1,i)||check(2,i)) {
            in[1]++;
            G[i-1].push_back(1);
        }
    }
    for(int i=3;i<=n;i++) {
        for(int j=3;j<=n;j++) {
            if(check(j,i)) {
                in[j-1]++;
                G[i-1].push_back(j-1);
            }
        }
    }
    toposort();
    if(maxn>255) cout<<-1<<endl;
    else {
        cout<<ans[1]<<endl<<ans[1]<<endl;
        for(int i=2;i<n;i++) cout<<ans[i]<<endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    work();
    return 0;
}