都匀市建设局网站,如何将网站地图提交给百度,泸州网站公司,沛县网站建设企业T 1 T_1 T1给出一个长度为 n n n的序列#xff0c;你可以进行若干次操作#xff0c;每次花费 c j c_j cj元将 a i a_i ai变为 ⌊ a i j ⌋ \lfloor \frac{a_i}{j} \rfloor ⌊jai⌋#xff0c;你一共有 k k k元。问最终序列的中位数最小是多少。
其中 1 ≤ n , m … T 1 T_1 T1给出一个长度为 n n n的序列你可以进行若干次操作每次花费 c j c_j cj元将 a i a_i ai变为 ⌊ a i j ⌋ \lfloor \frac{a_i}{j} \rfloor ⌊jai⌋你一共有 k k k元。问最终序列的中位数最小是多少。
其中 1 ≤ n , m ≤ 5 ∗ 1 0 5 , 1 ≤ a i ≤ m , 1 ≤ c i , k ≤ 1 0 9 1 \leq n,m \leq 5*10^5,1 \leq a_i \leq m,1\leq c_i,k \leq 10^9 1≤n,m≤5∗105,1≤ai≤m,1≤ci,k≤109。
赛时我并没有想到二分 d p dp dp以为是 d p dp dp结果没有想出来大概想了 30 30 30分钟就放了。 T 2 T_2 T2给出一个无向图进行 q q q次询问每次给出一个点 x x x对于这个图的所有边如果 c i ⊕ x k c_i \oplus x k ci⊕xk则这条边有效否则这条边不存在。求互相联通的点对个数。 1 ≤ n , m ≤ 1 0 5 , 0 ≤ c i , x , k 2 30 1 \leq n,m \leq 10^5,0 \leq c_i,x,k2^{30} 1≤n,m≤105,0≤ci,x,k230。
一开始我先打了 O ( ( n m ) q ) \mathcal O((nm)q) O((nm)q)的暴力。
然后观察了一下后面两组数据点发现虽然 1 ≤ n , m ≤ 1 0 5 1 \leq n,m \leq 10^5 1≤n,m≤105但是 c i , x , k 2 10 c_i,x,k2^{10} ci,x,k210理论上记忆化就可以拿下 80 80 80分。
但是赛后发现第二组数据 T T T了只有 50 50 50分可能是我实现常数太大了。 T 3 T_3 T3需要你进行若干次操作要么将 s i s_i si拼接到当前字符串要么删除结尾的 k k k个字符不足 k k k个时则全部删完。输出最少的操作次数如果不行则输出 − 1 -1 −1。
赛时不会打暴力就去看 T 4 T_4 T4。 T 4 T_4 T4给出一颗树每个节点都可以给他的祖先节点投票问对于每个点 i i i他的票数是否可以严格大于其他人的票数。 1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^6 1≤n≤106。
赛时直接打了个贪心跑路。
总结:这次考试没有看出 T 1 T_1 T1的二分很吃亏平时还是要多注意对题目的总结和归纳。
