本文主要是介绍题解：CF1929B（Sasha and the Drawing），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题解：CF1929B（Sasha and the Drawing）
一、 理解题意
CF链接
洛谷链接
简化题意如下：
给定一个 n × n n\times n n×n 的正方形，现要将其中几个点染色，使得该正方形中至少有 k k k 个对角线被染色。（ n × n n\times n n×n 的正方形共有 4 n − 2 4n-2 4n−2 个对角线）
二、 分析代价
本题 n n n 和 k k k 的范围较大，只能通过 O ( 1 ) O(1) O(1) 的算法做出。
三、 设计算法
考虑正方形的以下 2 n − 2 2n-2 2n−2 个点：
( 1 , 1 ) ( 1 , 2 ) ( 1 , 3 ) . . . . . . ( 1 , n ) (1,1) (1,2) (1,3) ...... (1,n) (1,1)(1,2)(1,3)......(1,n)
( n , 2 ) ( n , 3 ) ( n , 4 ) . . . . . . ( n , n − 1 ) (n,2) (n,3) (n,4) ...... (n,n-1) (n,2)(n,3)(n,4)......(n,n−1)
我们会发现，在这些点中任选 x x x 个进行染色，就会有 2 x 2x 2x 个对角线上有点被染色。
于是，对于 1 ≤ k ≤ 4 n − 2 1\leq k\leq 4n-2 1≤k≤4n−2，都有答案为 ⌈ k 2 ⌉ \lceil \dfrac{k}{2}\rceil ⌈2k⌉。
对于其他情况， k k k 无非就是 4 n − 3 4n-3 4n−3 或者 4 n − 2 4n-2 4n−2，不难看出其答案分别是 2 n − 1 2n-1 2n−1 和 2 n 2n 2n
四、 实现代码
#include<bits/stdc++.h>
using namespace std;
int k=0,n=0,t=0;
int main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);if(k<=n*4-4){printf("%d\n",k-k/2);}else{if(k==n*4-3){printf("%d\n",n*2-1);}else{printf("%d\n",n*2);}}}return 0;
}
这篇关于题解：CF1929B（Sasha and the Drawing）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
