2021春季个人赛-13 补题-一一网

【摘要】 C.hivalric Blossom
题意：有 n n n个任务，你需要给每个任务指定一个优先级，之后你会按优先级递增的顺序完成这些任务。如果有两个任务优先级相同，你会先完成编号小的。现在有 m m m对任务必须连续完成，你的目标是在满足这些限制的情况下，让不同优先级的数量尽可能少。分析：显然每个任务之间关系是一条链，每次记录节点的前驱和后继。之后把 n n …

C.hivalric Blossom

题意： 有 $n$ 个任务，你需要给每个任务指定一个优先级，之后你会按优先级递增的顺序完成这些任务。如果有两个任务优先级相同，你会先完成编号小的。现在有 $m$ 对任务必须连续完成，你的目标是在满足这些限制的情况下，让不同优先级的数量尽可能少。
分析： 显然每个任务之间关系是一条链，每次记录节点的前驱和后继。
之后把 $n$ 个颜色放入从大到小栈中（因为只有 $n$ 个任务，所以最多有 $n$ 个颜色），先从编号 $1$ 到 $n$ 依次遍历，如果这个节点是链头，那么取出颜色栈的一个颜色，遇到这个链的中间节点和链尾节点，都附上与链头相同的节点，并且把链尾的颜色节点入栈，表示还可以用这个颜色。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,l[N],r[N],a,b,col[N];
stack<int> s;
int main(){ cin>>n>>m; for(int i=0;i<m;i++){ cin>>a>>b; r[a]=b; l[b]=a; } for(int i=n;i;i--) s.push(i); for(int i=1;i<=n;i++){ if(l[i]){ col[i]=col[l[i]]; if(!r[i]) s.push(col[i]); } else{ col[i]=s.top(); if(r[i]) s.pop(); } } for(int i=1;i<=n;i++) cout<<col[i]<<" ";
}

  
 
  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

E. clipsing Star

题意： $n$ 轮游戏，每轮有 $a_i$ 块钱。在一轮中，先手可以自己拿 $b_i$ 块钱，给后手 $a_i-b_i$ 块钱，然后交换先后手的概率为 $\frac{b_i}{a_i}$ 。问最优策略下先手方与后手方总钱数之差的期望。
分析： 最后一轮的先手必定要拿走 $a_i$ ，这样 $n - 1$ 轮的先手可以不拿，让最后一轮获得先手。要么 $n - 1$ 轮他不是先手，后手拿走了 $a_{n-1}$ ，失去第 $n$ 轮的先手。故而这两轮可以变为价值为 $a_n-a_{n-1}$ 的一轮，所以一直往前归纳即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,a[N];
int main(){ cin>>n; for(int i=0;i<n;i++) scanf("%d",&a[i]); int res=a[n-1]; for(int i=n-2;~i;i--) res=abs(res-a[i]); printf("%d\n",res);
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11