2014-2015 ACM-ICPC, NEERC, Southern Subregional Contest

acm 2017年7月 codeforces 组队训练

入口：2014-2015 ACM-ICPC, NEERC, Southern Subregional Contest

D. Data Center

• 先按容量a从大到小排个序，那么可以很容易得到个数为k，即前k个
• 然后考虑用不在前k个中的类型为1的物品，去替换前k个中类型为0的物品，替换时用尽可能大的a去替换尽可能小的a
  
  
  

E. Election of a Mayor

• 因为不管怎么合并，能赢的次数是不会变的，因此，每次操作的目的就是，在不改变能赢的次数的前提下减少站点数。
• 那么每次对于相邻的两个站点，只要合并之后能符合上述的情况，就合并，一直做下去即可。
  
  
  

F. Ilya Muromets

• 先处理出一个前缀和与后缀和
• 对于每个$i$，处理出$[1,i]$和$[i,n]$能获得的最大的长度为k的连续和，最后枚举一下$i$即可
  
  
  

G. FacePalm Accounting

• 从左到右扫的话，每次更新尽可能右边的点的值（可能需要更新多个值），记录改变值。
• 因为更新的次数并不会太多，所以可能考虑直接更新。
  
  
  

I. Sale in GameStore

• 模拟，排序，取最大值mx，以及前k个满足前缀和sum[k]<=mx。
  
  
  

K. Treeland

• 首先，你考虑，对于每一个点$u$，离他最远的那个点$v$肯定是一个叶子。假设离$v$最近的点为$r$，那么在$v$和$r$之间连一条边，就可以删掉这个叶子节点$v$
• 不断删除叶子节点，直到最后构出一棵树即可。
  
  
  

M. Variable Shadowing

• 用stack实现。
• 用pair<int,int> pre[r][c]和pair<int, int> cur[c]记录信息。