杂

ACM

计算几何

注意

• 求反正切的函数atan(double x)与atan2(double y,double x) ，返回的值是弧度
  前者接受的是一个正切值（直线的斜率）得到夹角，atan的值域是从-90~90
  atan2(double y,double x) 其中y代表已知点的Y坐标，同理x，它的值域相应的是-180~180

两圆相交面积

#include <bits/stdc++.h>
using namespace std;
#define PI acos(-1.0)
double dis(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double cos_angle(double a, double b, double c)
{
    return 0.5 * (a * a + c * c - b * b) / (a * c);
}
double get_area(double x1, double y1, double r1, double x2, double y2, double r2)
{
    double d, s, s1_, s2_, s1_tri, s2_tri, an1, an2;
    d = dis(x1, y1, x2, y2);
    if (d >= r1 + r2 || !r1 || !r2) //相切、相离、考虑等于0
        return 0;
    if (d + r1 <= r2) //包含
        return PI * r1 * r1;
    if (d + r2 <= r1) //包含
        return PI * r2 * r2;
    an1 = acos(cos_angle(r1, r2, d));
    an2 = acos(cos_angle(r2, r1, d));
    s1_tri = 0.5 * r1 * r1 * sin(an1 * 2);
    s2_tri = 0.5 * r2 * r2 * sin(an2 * 2);
    s1_ = r1 * r1 * an1;
    s2_ = r2 * r2 * an2;
    s = (s1_ - s1_tri) + (s2_ - s2_tri);
    return s;
}

三角形中整点个数

int area()
{
    return abs((a * d + c * f + b * e - a * f - b * c - d * e) / 2);
}
int gcd(int x, int y)
{
    if (y == 0)return x;
    else
        return gcd(y, x % y);
}
int main ()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
        int s = area();
        int l1 = gcd(abs(a - c), abs(b - d));
        int l2 = gcd(abs(a - e), abs(b - f));
        int l3 = gcd(abs(c - e), abs(d - f));
        printf("%d\n", s - (l1 + l2 + l3) / 2 + 1);
    }
    return 0;
}

三角形面积

$A:（a,b）B:（c,d）C:（e,f）$
$S_{ABC}=(a*d+b*e+c*f-a*f-b*c-d*e)/2$

M*N方格中矩形正方形数量

矩形：$(n+1)*(m+1)*n*m/4$
正方形：$n*(n+1)*(2n+1)/6$

锥形

给出锥形的表面积（包括底部）S，当$4*πR^2=S$的时候，体积最大。

优先队列

• 默认大者优先
  priority_queue<int, vector<int>, greater<int> >a;（小者优先）

struct cmp1  
{  
     bool operator ()(int x, int y)  
    {  
        return x > y;//小的优先级高  
    }  
}; 
struct node  
{  
    int x, y;  
    friend bool operator < (node a, node b)  
    {  
        return a.x > b.x;//结构体中，x小的优先级高  
    }  
};  
priority_queue<int, vector<int>, cmp1>q2;   
priority_queue<node>q4;  

多重背包的二进制优化

//几种不同类型有固定数量的物品拆分成01背包
//这个姿势貌似更好
for (i = 1; i <= m; i++)
{
    scanf("%d%d%d", &p, &h, &c); //价值，重量，个数
    for (j = 1; j <= c; j *= 2)
    {
        v[cnt] = j * p; //分堆后每堆的价值
        w[cnt++] = j * h; //每堆的重量
        c -= j;
    }
    if (c > 0)
    {
        v[cnt] = c * p;
        w[cnt++] = c * h;
    }
}

数学

第一类Stirling数

第一类斯特林数是有正负的，其绝对值是包含n个元素的集合分作k个环排列的方法数目。
递推公式为：$S(n,0) = 0, S(1,1) = 1$ 　　$S(n+1,k) = S(n,k-1) + nS(n,k)$。
边界条件： $S(0 , 0) = 1， S(p , 0) = 0 ( p>=1) ，S(p , p) =1 (p>=0)$
一些性质: $S(p ,1) = 1 (p>=1)， S(p, 2) = 2^{(p-1)}-1， p>=2$　

第二类Stirling数

第二类斯特林数是把包含n个元素的集合划分为正好k个非空子集的方法的数目。 　　
递推公式为： $S(n,k)=0,(n<k||k=0)$ 　　$S(n,n) = S(n,1) = 1$, 　　
$S(n,k) = S(n-1,k-1) + kS(n-1,k)$
考虑第p个物品，p可以单独构成一个非空集合，此时前p-1个物品构成k-1个非空的
不可辨别的集合，方法数为S(p-1,k-1)；
也可以前p-1种物品构成k个非空的不可辨别的集合，
第p个物品放入任意一个中，这样有k*S(p-1,k)种方法。

sdut 2883

n场比赛，m张牌（n>=m）每场比赛用一张牌，
每张牌至少用一次，问有几种方案数。
分析：n场比赛划分成m个集合，每个集合里的比赛只用同一张牌，
没有空的集合。也就是说把包含n个元素的集合划分为正好m个非空子集的方法的数目，
再乘m的全排列。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll sum[110][110];
ll jiec[102];
int main()
{
    jiec[0] = 1;
    jiec[1] = 1;
    jiec[2] = 2;
    for (ll i = 3; i < 102; i++)
        jiec[i] = (jiec[i - 1] * i) % mod;
    for (ll i = 0; i <= 102; i++)
    {
        for (ll j = 0; j <= 102; j++)
        {
            if ( j == 0 || j > i )sum[i][j] = 0;
            else if ( i == j || j == 1 )sum[i][j] = 1;
            else sum[i][j] = ( sum[i - 1][j - 1] + j * sum[i - 1][j] ) % mod;
        }
    }
    int n, m;
    while ( scanf("%d %d", &n, &m) != EOF )
    {
        printf("%lld\n", (jiec[m]*sum[n][m] ) % mod );
    }
    return 0;
}

sdut 3144

现在给你一个数集S的大小n，请输出将它划分为集合的方法总数ans是多少？

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 5002;
ll sum[2][maxn];
ll ans[maxn];
void  cal()
{
    for (ll i = 0; i < maxn; i++)
    {
        ans[i] = 0;
        for (ll j = 0; j < maxn; j++)
        {
            if ( j == 0 || j > i )sum[i % 2][j] = 0;
            else if ( i == j || j == 1 )sum[i % 2][j] = 1;
            else sum[i % 2][j] = ( sum[ (i - 1) % 2 ][j - 1] + j * sum[ (i - 1) % 2 ][j] ) % mod;
            ans[i] = (ans[i] + sum[i % 2][j]) % mod;
        }
    }
}
int main()
{
    cal();
    int n, cas = 1;
    while ( scanf("%d", &n) != EOF )
    {
        printf("Case #%d: %lld\n", cas++, ans[n] % mod );
    }
    return 0;
}

快速幂取余

LL quick(LL x,LL m,LL n)//x^m%mod
{
    LL ans=1;
    while(m>0)
    {
        if(m%2==1)
            ans=ans*x%mod;
        x=x*x%mod;
        m=m/2;
    }
    return ans;
}

矩阵

struct Matrix
{
    int m[10][10];
}M;
Matrix Mult(Matrix a,Matrix b)  //矩阵乘法
{
    Matrix ans;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            ans.m[i][j]=0;
            for(int k=0;k<n;k++)
            {
                ans.m[i][j]+=a.m[i][k]*b.m[k][j];
                ans.m[i][j]%=mod;
            }
        }
    }
    return ans;
}
Matrix quickpow(Matrix a,int b)     //矩阵a的b次方-快速幂
{
    Matrix ans;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==j)
                ans.m[i][j]=1;
            else
                ans.m[i][j]=0;
        }
    }
    while(b)
    {
        if(b&1)
            ans=Mult(ans,a);
        a=Mult(a,a);
        b/=2;
    }
    return ans;
}

Euler_phi函数

• phi(n)为不超过n且与n互质的正整数个数

int phi(int n)
{
    int m = (int)sqrt(n + 0.5);
    int ans = n;
    for (int i = 2; i <= m; i++)
        if (n % i == 0)
        {
            ans = ans / i * (i - 1);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}

$O(nlogn)$：埃式筛法

bool isprime[N];
void primeform(int maxn) //0到maxn内的素数
{
    memset(isprime, true, sizeof(isprime));
    int m = (int)sqrt(maxn + 0.5) + 1;
    for (int i = 2; i < m; i++)
    {
        if (isprime[i])
            for (int j = i * 2; j <= maxn; j += i)
                isprime[j] = false;
    }
}

$O(n)$：快速线性筛法

bool isprime[maxn]; //是否素数
int prime[maxn]; //素数表
void primeform(int maxn) //0-maxn素数
{
    int cnt = 0;
    memset(isprime, true, sizeof(isprime));
    for (int i = 2; i <= maxn; i++)
    {
        if (isprime[i])
            prime[cnt++] = i; //打表
        for (int j = 0; (j < cnt && i * prime[j] <= maxn); j++)
        {
            isprime[i * prime[j]] = false;
            if (i % prime[j] == 0)
                break;
        }
    }
}

高效求n以内素数个数

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL f[340000], g[340000], n;
void init()
{
    LL i, j, m;
    for (m = 1; m * m <= n; ++m)
        f[m] = n / m - 1;
    for (i = 1; i <= m; ++i)
        g[i] = i - 1;
    for (i = 2; i <= m; ++i)
    {
        if (g[i] == g[i - 1])
            continue;
        for (j = 1; j <= min(m - 1, n / i / i); ++j)
        {
            if (i * j < m)
                f[j] -= f[i * j] - g[i - 1];
            else
                f[j] -= g[n / i / j] - g[i - 1];
        }
        for (j = m; j >= i * i; --j)
            g[j] -= g[j / i] - g[i - 1];
    }
}
int main()
{
    while (scanf("%lld", &n) != EOF)
    {
        init();
        printf("%lld\n", f[1]);
    }
    return 0;
}

阶乘最后非0位

//求阶乘最后非零位,复杂度O(nlogn)
//返回该位,n以字符串方式传入
#define MAXN 10000
int lastdigit(char* buf)
{
    const int mod[20] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2};
    int len = strlen(buf), a[MAXN], i, c, ret = 1;
    if (len == 1)
        return mod[buf[0] - '0'];
    for (i = 0; i < len; i++)
        a[i] = buf[len - 1 - i] - '0';
    for (; len; len -= !a[len - 1])
    {
        ret = ret * mod[a[1] % 2 * 10 + a[0]] % 5;
        for (c = 0, i = len - 1; i >= 0; i--)
            c = c * 10 + a[i], a[i] = c / 5, c %= 5;
    }
    return ret + ret % 2 * 5;
}

求$10^n$素数个数的位数

int ans = double(n - log10(n) - log10(log(10)));
printf("%d\n", ans + 1);

拓展欧几里得

求$a/b$ mod $p$的值，且a很大，无法直接求得a/b的值时，我们就要用到乘法逆元。
通过求b关于p的乘法逆元k，将a乘上k再模p，即$(a×k)$ mod $p$。其结果与$a/b$ mod $p$等价

//ax+by=gcd(a,b),所求的x即为a mod b的逆元（a^(-1))，y为b mod a的逆元
void ex_gcd(LL a,LL b) 
{
    if(b==0)
    {
        x=1;
        y=0;
        return ;
    }
    ex_gcd(b,a%b);
    int t=x;
    x=y;
    y=t-a/b*y;
}

A，B互质，组合为其他数

不能表示的数的个数：（A-1）*（B-1）/2
最大不能表示的数：A*B-A-B

组合数奇偶性的判断

对于C(n,k)，若n&k == k ，则c(n,k)为奇数，否则为偶数

青蛙跳台阶问题

• 一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
  $f[1]=1，f[2]=2，f[n]=f[n-2]+f[n-1]$
• 一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？
  $f[0]=1，f[1]=2，f[n]=2*f[n-1]$

卡特兰数

$令h(0)=1,h(1)=1$
$h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)$

另类递推式：
$h(n)=h(n-1)*(4*n-2)/(n+1);$
递推关系的解为：
$h(n)=C(2n,n)/(n+1) (n=0,1,2,...)$
递推关系的另类解为：
$h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)$

    a[0]=1,a[1]=1;
    for(i=2;i<=n;i++)
        a[i]=a[i-1]*(4*i-2)/(i+1);

    a[0]=1,a[1]=1;
    for(i=2;i<=n;i++)
        for(j=0;j<i;j++)
        a[i]=a[i]+a[j]*a[i-j-1];

汉诺塔

递推式：$T(n)=2*T(n-1)+1$
$T(n)=2^n-1$

树状数组

int lowbit(int x)
{
    return x & (-x);
}
void change(int x, int y) //在x点加上值y
{
    for (int i = x; i <= n; i += lowbit(i))
        a[i] += y;
}
int sum(int x) //1到x的和
{
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        sum += a[i];
    return sum;
}

高精度

N!

#include<stdio.h>
#include<string.h>
#define N 3000
int f[N];
int main()
{
    int i, j, n;
    scanf("%d", &n);
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (i = 2; i <= n; i++)
    {
        int c = 0;
        for (j = 0; j < N; j++)
        {
            int s = f[j] * i + c;
            f[j] = s % 10;
            c = s / 10;
        }
    }
    for (j = N - 1; j >= 0; j--)
    {
        if (f[j])
            break;
    }
    for (i = j; i >= 0; i--)
    {
        printf("%d", f[i]);
    }
    printf("\n");
    return 0;
}

A/B

#include<stdio.h>
#include<string.h>
char sa[1111], sb[1111];
int s[1111], la, lb, i, flag, k, j;
void jianfa()
{
    for (i = lb - 1; i > 0; i--)
    {
        if (sa[i] < sb[i])
        {
            sa[i] += 10;
            sa[i - 1]--;
        }
    }
    for (i = lb - 1; i >= 0; i--)
        sa[i] = sa[i] - sb[i] + '0';
}
int main()
{
    while (scanf("%s%s", sa, sb) != EOF)
    {
        memset(s, 0, sizeof(s));
        k = 0;
        flag = 1;
        la = strlen(sa);
        lb = strlen(sb);
        if (la < lb || (la == lb && strcmp(sa, sb) < 0))
            printf("0\n");
        else
        {
            while (flag)
            {
                while (strcmp(sa, sb) >= 0)
                {
                    jianfa();
                    s[k]++;
                }
                k++;
                if (la == lb)
                    flag = 0;
                for (i = lb; i >= 1; i--)
                    sb[i] = sb[i - 1];
                sb[0] = '0';
                lb++;
                sb[lb] = '\0';
            }
        }
        for (i = 0; i < k; i++)
            if (s[i] != 0)
                break;
        for (j = i; j < k; j++)
            printf("%d", s[j]);
        printf("\n");
    }
    return 0;
}

A+B

#include<stdio.h>
#include<string.h>
int a[555], b[555], s[555], la, lb, i, l;
void jiafa()
{
    memset(s, 0, sizeof(s));
    for (i = 0; i < l; i++)
        s[i] = a[i] + b[i];
    for (i = 0; i <= l; i++)
    {
        s[i + 1] += s[i] / 10;
        s[i] %= 10;
    }
    for (i = l; i > 0; i--)
        if (s[i] == 0)
            l--;
        else break;
    for (i = l; i >= 0; i--)
        printf("%d", s[i]);
    printf("\n");
}
int main()
{
    char sa[555], sb[555];
    while (scanf("%s%s", sa, sb) != EOF)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        la = strlen(sa);
        lb = strlen(sb);
        for (i = 0; i < la; i++)
            a[la - i - 1] = sa[i] - '0';
        for (i = 0; i < lb; i++)
            b[lb - i - 1] = sb[i] - '0';
        l = la > lb ? la : lb;
        jiafa();
    }
    return 0;
}

A-B

#include<stdio.h>
#include<string.h>
void jianfa(int *a, int *b, int l)
{
    int i, j, s[111], flag = 0;
    memset(s, 0, sizeof(s));
    for (i = 0; i < l - 1; i++)
    {
        if (a[i] < b[i])
        {
            a[i] += 10;
            a[i + 1]--;
        }
        s[i] = a[i] - b[i];
    }
    s[l - 1] = a[l - 1] - b[l - 1];
    for (i = l - 1; i >= 0; i--)
    {
        if (s[i] != 0)
        {
            flag = 1;
            break;
        }
    }
    if (flag == 0)
        printf("0\n");
    else
        for (j = i; j >= 0; j--)
            printf("%d", s[j]);
    printf("\n");
}
int f(int *a, int *b, int la, int lb)
{
    int i;
    for (i = la - 1; i >= 0; i--)
    {
        if (a[i] > b[i])
        {
            return 1;
            break;
        }
        if (a[i] < b[i])
        {
            return 0;
            break;
        }
    }
    return -1;
}
int main()
{
    char sa[111], sb[111];
    int a[111], b[111], ta, tb, i, j, flag, la, lb;
    while (scanf("%s%s", sa, sb) != EOF)
    {
        ta = 0, tb = 0;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        la = strlen(sa);
        lb = strlen(sb);
        for (i = 0, j = la - 1; j >= 0; i++, j--)
            a[i] = sa[j] - '0';
        for (i = 0, j = lb - 1; j >= 0; i++, j--)
            b[i] = sb[j] - '0';
        for (i = la - 1; i >= 0; i--)
        {
            if (a[i] != 0)
            {
                ta = 1;
                la = i + 1;
                break;
            }
        }
        for (i = lb - 1; i >= 0; i--)
        {
            if (b[i] != 0)
            {
                tb = 1;
                lb = i + 1;
                break;
            }
        }
        if (ta + tb == 0)
            printf("0\n");
        else
        {
            if (la < lb)
            {
                printf("-");
                jianfa(b, a, lb);
            }
            else if (la > lb)
                jianfa(a, b, la);
            else
            {
                if (f(a, b, la, lb) == 1)
                    jianfa(a, b, la);
                else if (f(a, b, la, lb) == 0)
                {
                    printf("-");
                    jianfa(b, a, lb);
                }
                else
                    printf("0\n");
            }
        }
    }
    return 0;
}

A*B

#include<stdio.h>
#include<string.h>
int main()
{
    char sa[44], sb[44];
    int a[44], b[44], la, lb, i, j, sum[88], k, x;
    while (scanf("%s%s", sa, sb) != EOF)
    {
        k = 0;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(sum, 0, sizeof(sum));
        la = strlen(sa);
        lb = strlen(sb);
        for (i = 0, j = la - 1; j >= 0; j--, i++)
            a[i] = sa[j] - '0';
        for (i = 0, j = lb - 1; j >= 0; j--, i++)
            b[i] = sb[j] - '0';
        for (i = 0; i < la; i++)
        {
            for (j = 0, k = i; j < lb; j++)
            {
                sum[k] += a[i] * b[j];
                k++;
            }
        }
        for (i = 0; i < k - 1; i++)
        {
            sum[i + 1] += sum[i] / 10;
            sum[i] %= 10;
        }
        if (sum[k - 1] >= 10)
        {
            sum[k] = sum[k - 1] / 10;
            sum[k - 1] %= 10;
            x = k;
        }
        else
            x = k - 1;
        for (i = x; i >= 0; i--)
            printf("%d", sum[i]);
        printf("\n");
    }
}

RMQ

一维

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[50005], dpmin[50005][16], dpmax[50005][16];
int main()
{
    int i, n, q, st, en, j, d;
    while (scanf("%d%d", &n, &q) != EOF)
    {
        for (i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (i = 1; i <= n; i++)
        {
            dpmin[i][0] = a[i];
            dpmax[i][0] = a[i];
        }
        for (i = 1; (1 << i) <= n; i++) //区间长度
            for (j = 1; j + (1 << i) - 1 <= n; j++) //起点
            {
                dpmax[j][i] = max(dpmax[j][i - 1], dpmax[j + (1 << i - 1)][i - 1]);
                dpmin[j][i] = min(dpmin[j][i - 1], dpmin[j + (1 << i - 1)][i - 1]);
            }
        while (q--)
        {
            scanf("%d%d", &st, &en);
            d = 0;
            while ((1 << d + 1) <= en - st + 1)  d++;
            printf("%d\n", (max(dpmax[st][d], dpmax[en - (1 << d) + 1][d]) - min(dpmin[st][d], dpmin[en - (1 << d) + 1][d])));
        }
    }
    return 0;
}

二维

• 求某个矩阵内的最大值和最小值

#include<stdio.h>
#include<algorithm>
using namespace std;
int mp[255][255];
int dpmin[255][255][8][8]; //若起点为(0,0),2^8=256
int dpmax[255][255][8][8];
//二维RMQ，dp[x][y][i][j]
//表示从(x,y)点到右下角为(x+2^i-1,y+2^j-1)矩形内最小值
void RMQ(int n, int m) //n*m的矩阵
{
    for (int i = 0; (1 << i) <= n; i++)
    {
        for (int j = 0; (1 << j) <= m; j++)
        {
            if (!i && !j)  continue;
            for (int r = 1; r + (1 << i) - 1 <= n; r++)
                for (int c = 1; c + (1 << j) - 1 <= m; c++)
                {
                    if (!j)
                    {
                        dpmax[r][c][i][j] = max(dpmax[r][c][i - 1][j], dpmax[r + (1 << (i - 1))][c][i - 1][j]);
                        dpmin[r][c][i][j] = min(dpmin[r][c][i - 1][j], dpmin[r + (1 << (i - 1))][c][i - 1][j]);
                    }
                    else
                    {
                        dpmax[r][c][i][j] = max(dpmax[r][c][i][j - 1], dpmax[r][c + (1 << (j - 1))][i][j - 1]);
                        dpmin[r][c][i][j] = min(dpmin[r][c][i][j - 1], dpmin[r][c + (1 << (j - 1))][i][j - 1]);
                    }
                }
        }
    }
}
int querymax(int lx, int ly, int rx, int ry)
{
    int kx = 0, ky = 0;
    while (lx + (1 << (1 + kx)) - 1 <= rx) kx++;
    while (ly + (1 << (1 + ky)) - 1 <= ry) ky++;
    int m1 = dpmax[lx][ly][kx][ky];
    int m2 = dpmax[rx - (1 << kx) + 1][ly][kx][ky];
    int m3 = dpmax[lx][ry - (1 << ky) + 1][kx][ky];
    int m4 = dpmax[rx - (1 << kx) + 1][ry - (1 << ky) + 1][kx][ky];
    return max(max(m1, m2), max(m3, m4));
}
int querymin(int lx, int ly, int rx, int ry)
{
    int kx = 0, ky = 0;
    while (lx + (1 << (1 + kx)) - 1 <= rx) kx++;
    while (ly + (1 << (1 + ky)) - 1 <= ry) ky++;
    int m1 = dpmin[lx][ly][kx][ky];
    int m2 = dpmin[rx - (1 << kx) + 1][ly][kx][ky];
    int m3 = dpmin[lx][ry - (1 << ky) + 1][kx][ky];
    int m4 = dpmin[rx - (1 << kx) + 1][ry - (1 << ky) + 1][kx][ky];
    return min(min(m1, m2), min(m3, m4));
}
int main()
{
    int n, b, q;
    scanf("%d%d%d", &n, &b, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &mp[i][j]);
            dpmax[i][j][0][0] = mp[i][j];
            dpmin[i][j][0][0] = mp[i][j];
        }
    RMQ(n, n);
    while (q--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", querymax(x, y, x + b - 1, y + b - 1) - querymin(x, y, x + b - 1, y + b - 1));
    }
    return 0;
}