算法竞赛必会题型：约会天数、格子圆交集等4大问题详解

算法竞赛必会题型：约会天数、格子圆交集等4大问题详解

本文整理了几个算法竞赛中的经典问题及其解法，包括格子与圆交集问题、约会天数计算、斐波那契数列余数规律以及合并石头代价问题。每个问题都给出了详细的解题思路和C++代码实现，适合编程爱好者和算法学习者参考。

一. 约会

这道题目涉及n*n的格子和一个直径为2n-1的圆。如果逐个格子判断是否与圆环有交集，时间复杂度会很高。注意到圆恰好仅与一个方格有两个交线（一进一出），再加上首尾相连，可以得出：

格子数等于所有交线数 = （2*n-1）4 = 8n-4

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
    int n;
    while (scanf("%d",&n)==1&&n)
    {
        cout<<8*n-4<<endl;
    }
    return 0;
}

二. 约会（II）

能约会的那天即是三的倍数，[1,a]天能约会的天数=a/3;则[a,b]能约会的天数=b/3-(a-1)/3;

注：

1. 第a天也要考虑在内
2. 不能写为（b-(a-1))/3 可以通过sample判断这种写法的错误性
3. 九位数用long才装得下

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
    long a,b;
    while(scanf("%ld%ld",&a,&b)==2&&a)
    {
       printf("%ld\n",b/3-(a-1)/3);
    }
    return 0;
}

三. 斐波那契数列

如果我们先算出数列的值，还是求f(n) (mod3) 时间复杂度都是o(n) 。前者数据过大会爆，10的10次方 o(n)也可能TLE
故尝试寻找o(1)

我们寻找余数的规律

1
2 0 2 2 1 0 1 1
2 0 2 2 ...

我们不难发现是八个为一组循环（下标为2,6输出yes）

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
    long n;
    while(scanf("%ld",&n)==1)
    {
        n%=8;
        if(n==2||n==6)
        cout<<"yes"<<endl;
        else
        cout<<"no"<<endl;
    }
    return 0;
}

四. 合并石头

不妨以a,b,c三块石头为例
sum=ab+(a+b)*c=ab+ac+bc即无论怎么合并大小都是不变的
归纳可得：代价就是两堆石头的乘积的求和

注：

1. 用到了__int128_t的输出
2. vector的使用

#include <iostream>
#include<vector>
using namespace std;
inline void Print(__int128_t sum)
{
    if(sum>9)
    Print(sum/10);
    putchar('0'+sum%10);
    return;
}
int main()
{
    unsigned int n,i,j;
    scanf("%u",&n);
    vector  <long long> vec(n);
    for(i=0;i<n;i++)
    {
        scanf("%lld",&vec[i]);
    }
    __int128_t sum=0;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            sum+=vec[i]*vec[j];
        }
    }
    Print(sum);
  
    // 请在此输入您的代码
    return 0;
}