[原创]Codeforces Round #420 (Div. 2)
[原创]Codeforces Round #420 (Div. 2)
2017-06-27 19:07:39 Tabris_ 阅读数:203
博客爬取于2020-06-14 22:39:55
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/73822126
A Okabe and Future Gadget Laboratory
——————————————————————————————————————————
简单SB题,
问你矩阵中所有大于的数能否用所在行的一个数加上所在列的一个数表示 ,如果都能就YES,否则NO
1 | int n; |
B Okabe and Banana Trees
——————————————————————————————————————————
还是SB题,暴力找都不会超时
但是显然答案一定在线下方第一个点,
而直到每个点后的答案是能O(1)计算的
所以维护的最小值即可
1 | int main(){ |
C Okabe and Boxes
——————————————————————————————————————————
让你维护一个栈,你可以将栈里面的元素重新排列,现在问你至少重新排列多少回 能让出栈的顺序为升序
就是在维护这个栈的操作,
进栈的时候一样
出站的时候看栈顶是不是预期的那个数,是的话就重新排列下即可
而这里的重新排列 可以用清空栈来代替
1 | char s[22]; |
D Okabe and City
——————————————————————————————————————————
N*M的二维矩阵,有K个位置时初始就是亮着的,一个人要走在当时亮着的格子从(1,1)到(n,m)
站在最初是亮着位置可以花费1来让某一行或某一列全变量,
问你最小花费
同时只能点亮某一行或某一列,那么一定是在最初两者的位置临近的两个行/两个列和本身所在的行/列,
再加上格子相邻的地方
按照这两种规则进行建图计算最短路就行了,
1 | struct node { |
E Okabe and El Psy Kongroo
——————————————————————————————————————————
有n条线段,线段平行于x坐标, 每次只能走在线段下方,从(x,y)能走到(x+1,y+1)(x+1,y)(x+1,y-1)这三个位置,问你最后到(k,0)的方案数,
简单的矩阵快速幂
只与必须在线段下方的限制,我们可以再计算之前将不合格的点清0即可
注意I64 要不然会GG
1 | # include <bits/stdc++.h> |