首页 > 试题广场 >

Tokitsukaze and Colorful Chess

[编程题]Tokitsukaze and Colorful Chess

热度指数：1556 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

Tokitsukaze 要在一个 $n \times n$ 的棋盘上摆放棋子。她有 $a$ 个红色的棋子和 $b$ 个蓝色的棋子，要求任意两个相同颜色的棋子上下左右四个方向不相邻，允许棋盘上留有不放棋子的空格子。

Tokitsukaze 想知道棋盘的边长 $n$ 至少多大，才能摆放下 $a$ 个红色的棋子和 $b$ 个蓝色的棋子。

输入描述:

第一行包含一个整数  () --- 测试数据的组数。

对于每组测试数据：

第一行包含两个整数 ,  (, ) --- 两种颜色的棋子数。

输出描述:

对于每组测试数据，输出一行，每行包含一个整数表示答案。

示例1

输入

2
4 5
0 6

输出

3
4

说明

第一组测试数据，我们只能这样摆：

第二组测试数据，我们可以这样摆：

算法知识视频讲解

Java

牛客203596504号

这道题很简单，首先观察题面的两个示例不难发现：

把棋盘填满，如果格子是偶数，两者各占一半，如果格子是奇数，两者相差一个。

所以：设a和b中较大的为max，那么n²>=max*2(偶数时)或者n²>=max*2-1(奇数时)
考虑到任何相邻平方数之差一定大于1，我们只需对max*2-1开平方后向上取整(棋盘必须是整数)
注意唯一的例外：当n是奇数，且max*2-1恰好等于n²，如果a=b，会有一枚棋子摆不下

代码两行：

int n = (int)Math.ceil(Math.sqrt(Math.max(a, b) * 2 - 1));
if (a + b > n * n) n++;

如果只想要AC，到此就可以结束了，但是……如果想要快呢？
开方是很耗时的操作，这里有10万条数据就要10万次开方，不划算。
考虑到数据范围是1e9，平方根最大44721，乘法比开方快很多！
我们完全可以打个平方表，然后用二分查找来求解。
具体代码就不贴了，如果不会打平方表，或者不会二分法的，就不用看这段了。

发表于 2026-03-11 01:53:56 回复(0)

ylh123_

#include <bits/stdc++.h>
using namespace std;
#define int long long
using PII = pair<int, int>;

void solve() {
    int a, b;
    cin >> a >> b;
    if (a < b) swap(a, b);
    int l = 1, r = 1e5;
    while (l < r) {
        int mid = (l + r) >> 1;
        int all = mid * mid;
        int t1 = all / 2, t2 = all / 2 + (all & 1);
        if (t2 >= a && t1 >= b) r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

1.最简单的二分想法，复杂度TlogA
2.其实可以TlogT离线，预处理1e5以内的答案然后双指针
3.也可以T,注意到只需要大的放下就行，算一下sqrt(2a)然后O(1)调一下就行

发表于 2026-03-11 22:06:05 回复(0)

pandaC222

注意到，本题用二分解决：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define debug(x) cerr << #x << ": " << x << '\n';
const int INF = 0x3f3f3f3f3f3f3f3f;
//倒序不要忘记是--不是++
const int N=505050;
int fac[N];
void solve(){
    int a,b;cin>>a>>b;
    int mx=max(a,b);
    auto it=lower_bound(fac,fac+N,mx)-fac;
    if((it&1)&&(a==b)&&mx==fac[it]){
        cout<<it+1<<"\n";
    }
    else cout<<it<<"\n";
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    cin>>t;
    for(int i=1;i<=N-1;i++) fac[i]=(i*i+1)/2;
    while(t--){
        solve();
    }return 0;
}

发表于 2026-03-11 13:08:52 回复(0)

提交观点

问题信息

难度：

3条回答 2收藏 14浏览

Tokitsukaze and Colorful Chess

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题