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;
}