NWERC 2019

题目链接:2019-2020 ICPC Northwestern European Regional Programming Contest

NWERC 2019

A - Average Rank

n个人参加比赛,每个人有初始分数0,比赛共进行w轮,每一轮会公布哪些人会加一分。每个人在每一轮都有一个排名,相同分数的人排名相同,如3个人的分数分别为2,2,1,则它们的排名分别为1,1,3 ,求每个人这w轮比赛的排名平均值。

  • 这道题利用几何意义来进行解决。
    平均排名等于w周的排名和除以w,考虑如果求每个人的排名和,一开始假设每个人的分数始终都不变,和为w。考虑如果某个人分数在第t周从p变到p+1,如何维护这个和,或者说有什么影响。
  • 如果某一轮x的分数为p,+1后,原来与x排名相同的人的排名在本轮都会+1,他自己的排名会减少num[p+1],其中num[p+1]为本轮分数为p+1的人数(你细品)。那么在维护每个人的排名和时,原来与它排名相同的每个人排名和的增加(m-t+1),x的排名和减少了num[p+1]*(m-t+1),其他人没有变化。
  • 注意,因为数据量较大,在t时刻更新某个人时不能立刻去更新其他与它分数相同的人,而是用f[p]来维护分数为p的人需要累加的排名和,等下一次访问到那个人时才去更新。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int n,m; cin>>n>>m;
vector<double> ans(n,m);
vector<long long>f(m+1,0),g(n,0),point(n,0),num(m+1,0); //这里用g[]辅助f[]
num[0]=n;
for(int i=1;i<=m;i++){
int t;
cin>>t;
for(int j=1;j<=t;j++){
int x;
cin>>x;
x--;
ans[x]+=f[point[x]]-g[x]; //之前已经加了g[x],现在只需要再加f[point[x]]-g[x]即可
f[point[x]]+=(m-i+1);
num[point[x]]--;
point[x]++;
ans[x]-=num[point[x]]*(m-i+1);
g[x]=f[point[x]]; //当前x已经累加过的总值
num[point[x]]++;
}
}
for(int i=0;i<n;i++) ans[i]+=f[point[i]]-g[i];
for(int i=0;i<n;i++) printf("%.10lf\n",ans[i]/(1.0*m));


C - Canvas Line

你的朋友Charmion让你为她把一些画布挂在一条直的晾衣绳上晾干。画布没有重叠,但边缘可以接触。为了稳定,每个画布必须用两个钉子固定,因为画布非常坚硬,所以可以在任何地方固定。
每幅画布的宽度是以厘米为单位(至少10厘米)的整数。每个桩的宽度略小于1厘米。画布和钉子都放置在整数位置。
将每个画布都应该用两个钉子固定,不能多也不能少。有的钉子已经存在,请布置尽可能少的额外的钉子来固定所有画布。

  • 如果某个区域有两个以上的钉子,则impossible,否则贪心得按最少的钉子加:如果相邻两块画布边界接触,则边界处钉一颗钉子即可,否则就在画布的其他位置添加钉子,保证每块画布有两颗钉子即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
int n,m;
vector<int> g[N];
int x[10005],y[10005];
int p[10005];
int num[10005];
map<int,int> mp;
vector<int> ans;
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d",&p[i]),mp[p[i]]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)
if(p[i]>=x[j]&&p[i]<=y[j]) num[j]++;
}
int flag=1;
for(int i=1;i<=n;i++){
if(num[i]==2) continue;
if(num[i]>2){
flag=0;
break;
}
if(num[i]==1){
if(num[i+1]<2&&y[i]==x[i+1]&&mp[y[i]]==0){
mp[y[i]]=1;
ans.push_back(y[i]);
num[i]++,num[i+1]++;
}else{
if(!mp[y[i]-1]){
mp[y[i]-1]=1;
ans.push_back(y[i]-1);
num[i]++;
}else {
mp[y[i]-1]=1;
ans.push_back(y[i]-2);
num[i]++;
}
}
}
if(num[i]==0){
if(num[i+1]<2&&y[i]==x[i+1]&&mp[x[i+1]]==0){
mp[x[i+1]]=1;
ans.push_back(x[i+1]);
num[i]++,num[i+1]++;
}
if(num[i]<2){
mp[y[i]-1]=1;
ans.push_back(y[i]-1);
num[i]++;
}
if(num[i]<2){
mp[y[i]-2]=1;
ans.push_back(y[i]-2);
num[i]++;
}
}
}
if(!flag) puts("impossible");
else{
printf("%d\n",ans.size());
for(auto it:ans){
printf("%d ",it);
}
puts("");
}
}

E - Expeditious Cubing

克莱尔正在参加最受欢迎的比赛:快速解决3×3×3的魔方。每个参赛者需要解魔方五次,每次随机打乱顺序。在所有的解决完成后,最好的和最差的时间被丢弃,最后的分数是剩下三次的平均值。最后得分最低的选手获胜。
到目前为止,克莱尔在比赛中表现很好,是赢得总冠军的竞争者之一。所有的参赛者都已经完成了他们的五个解,但是克莱尔还剩下一个解。通过观察其他选手的最终得分,她推断出了自己的目标最终得分。只要她的最终分数低于或等于这个目标分数,她将被宣布为总冠军。她有可能赢得比赛吗?如果有,她在最后一次破洞时最糟糕的时间是什么时候?

  • 如果有浮点型可能会损失精度,这里说了给出的都是两位小数,所以我们直接把所有小数整体向右移动把他们变成整形,然后推式子的时候先从两个边界推,然后再推一般情况会好写一些。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int a[5];
int main()
{
for(int i=0;i<4;i++){
int x,y;
scanf("%d.%d",&x,&y);
x*=100;
a[i]=x+y;
}
sort(a,a+4);
int x,y; scanf("%d.%d",&x,&y);
int k=x*100+y;
if(k*3>=a[1]+a[2]+a[3]) puts("infinite");
else if(k*3<a[0]+a[1]+a[2]) puts("impossible");
else{
int tmp=k*3-a[1]-a[2];
printf("%d.",tmp/100);
tmp=tmp%100;
if(tmp<10) printf("0%d",tmp);
else printf("%d\n",tmp);
}
}

F - Firetrucks Are Red

给定n个人,每个人手中有一些数字,如果两个人手上有相同的数字,则这两个人可以建立一个关系对,找到n-1个关系对,使得n个人被完全包含。

  • 将第i个人与前面含有相同数字的人连边,i只需要连前面一个人即可,最后会形成一颗树,将树上每条边输出即可。
  • 因为懒得判i连了几个人,所有索性对每个数字,i都与前面的人连一遍,然后找了颗生成树。
  • 如果树的边小于n-1,则impossible。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

struct edge{
int x,y,w;
}e[M];
unordered_map<int,vector<int>> st;
int n,m,tot=0,tem,f[N],a[N],b[N],c[N];
int get(int n){return n==f[n]?n:f[n]=get(f[n]);}
int main(){
rd(n);
rep(i,1,n){
rd(m);
rep(j,1,m){
rd(tem);
if(st.count(tem))
e[++tot] = {st[tem][0],i,tem};
st[tem].push_back(i);
}
}
rep(i,1,n) f[i]=i;
int num=0;
rep(i,1,tot){
int fa=get(e[i].x), fb=get(e[i].y);
if(fa!=fb) {
a[++num]=e[i].x,b[num]=e[i].y,c[num]=e[i].w;
f[fa]=fb;
}
if(num==n-1) break;
}
if(num<n-1) puts("impossible");
else {
rep(i,1,num) cout<<a[i]<<" "<<b[i]<<" "<<c[i]<<endl;
}
return 0;
}

G - Gnoll Hypothesis

  • 题意晦涩难懂,简单来说就是有n个位置,要从中随机等概率选k个出来,再在这k个位置中按照指定概率p(初始时会给定n个概率pi)选择1个出来成为最终目标。在n选k没有选中第i个时,p[i]将会累加到在i后面的第一个被选中的位置(最后一个没有的话就加到第一个中)的概率中,以保证从选出来的k个位置再选择一个的概率和为100%,如下图:
  • 如上所示,当从5个中选3个并且选到1 2 4后,1号位置被选中为最终目标的概率为24%。求每个位置被选中为最终目标的概率的期望。
  • 样例:
    • input:
      5 3
      1 25 39 12 23
    • output:
      8.7 17.6 31 21.4 21.3
  • 求第一个位置时,选中有1的方案及相应的概率:
    1-36% 2-25% 3-39%
    1-24% 2-25% 4-51%
    1-1% 2-25% 5-74%
    1-24% 3-64% 4-12%
    1-1% 3-64% 5-35%
    1-1% 4-76% 5-23%
    1号位置的概率期望为(36+24+1+24+1+1)/C(5,3) = 8.7
  • 对于每一个位置i,f[i][j]表示第i个位置被选中,且其上面恰好有j个相邻的位置没有被选中时,i在k个位置中被选中的概率。f[i][j] = f[i-1][j-1]+a[i]。
  • 当i上有j个位置未被选中时,第i、i-j-1位置已被固定,所以这样的情况一共有C(n-j-2,k-2)种。
  • 对于每个i枚举每个j,答案累加C(n-j-2,k-2)*f[i][j]/C(n,k)。
  • k=1时要特殊处理。每个位置答案均为1/n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

int n,k;
double a[N],c[N][N],f[N][N];
void init(){
c[0][0]=1.0;
rep(i,1,505){
c[i][0]=c[i][i]=1.0;
rep(j,1,i-1)
c[i][j]=c[i-1][j-1]+c[i-1][j];
}
rep(i,1,n-1)
f[1][i] = f[1][i-1]+a[n-i+1];
rep(i,2,n){
rep(j,1,n-1)
f[i][j] = f[i-1][j-1]+a[i];
}
}
int main(){
cin>>n>>k;
rep(i,1,n) {
cin>>a[i];
f[i][0] = a[i];
}
if(k==1){
rep(i,1,n){
if(i!=1) printf(" ");
printf("%.10f",100.0/(1.0*n));
}
puts("");
return 0;
}
init();
rep(i,1,n){
double ans = 0.0;
rep(p,0,n-k){
ans += c[n-p-2][k-2]*f[i][p];
}
if(i!=1) printf(" ");
printf("%.10f",ans/c[n][k]);
}
puts("");
return 0;
}

I - Inverted Deck

给定一个长为n的序列,问是否能找到一个子串,将其翻转后使得整个序列为不下降序列(即i < j && a[i]<=a[j])。

  • 思路:找到第一个非严格下降子序列,将其翻转即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n,a[N];
int main(){
rd(n);
rep(i,1,n) rd(a[i]);
int x=2;
while(x<=n && a[x]>=a[x-1]) x++;
x--;
if(x==n) {puts("1 1"); return 0;}
while(x>0 && a[x]==a[x-1]) x--;
int y = x+1;
while(y<=n && a[y]<=a[y-1]) y++;
y--;
reverse(a+x,a+y+1);
rep(i,2,n){
if(a[i]<a[i-1]) {puts("impossible"); return 0;}
}
printf("%d %d\n",x,y);
return 0;
}

Donate comment here