7.29 Test——Math Theory 1

痛定思痛。 2021-10-19 11:10 188阅读 0赞

**T1：**

1 菠萝包

1.1 Description  
萨塔妮亚正在吃菠萝包，可她不知道菠萝包被人涂上了芥末。  
菠萝包表面烤出了一个n \* m 的网格，其中有一些格子涂上了芥末。  
萨塔妮亚会一口咬下其中k \* k 大小的一个正方形网格，这k \* k格中如果有一格有芥末，萨塔妮亚就会呛到无法自拔。  
你想知道有多少种情况她会被呛到。

1.2 Task  
1.2.1 Input  
第一行三个数n, m, k；  
接下来一个nm 的01 矩阵表示菠萝包上的情况，1 表示涂了芥末。

1.2.2 Output  
输出一个整数表示萨塔妮亚会吃到芥末的情况数。

1.3 Sample  
1.3.1 Input  
4 4 2  
1000  
0100  
0000  
0001  
1.3.2 Output  
5

1.4 Constraint  
对于30% 的数据，n，m <= 30；  
对于100% 的数据，n, m <= 1000，k <= min(n, m)。

解析：

签到题， 二维前缀和预处理，计算k\*k的矩阵和是否为0

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1005;
    
    int n, m, k, s[maxn][maxn], ans;
    
    int main()
    {
        freopen("a.in", "r", stdin);
        freopen("a.out", "w", stdout);
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                char c=getchar();
                while(c<'0'||c>'9')     c = getchar();
                s[i][j] = c - '0';
            }
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
                if(i >= k && j >= k)
                {
                    int res = s[i][j] - s[i-k][j] - s[i][j-k] + s[i-k][j-k];
                    if(res)
                        ans ++;
                }
            }
        printf("%d", ans);
        return 0;
    }

**T2:**

2 无聊

2.1 Description  
薇奈把珈百璃的电脑收走了，无聊的珈百璃只好躺在床上数数。  
珈百璃想：一个数有很多很多约数，这些约数又有很多很多约数，那一个数就有很多约数的约数。  
珈百璃想：12 有多少个约数的约数呢？12 的约数有1,  2,  3,  4,  6, 12，这些数分别有1,  2,  2,  3,  4,  6 个约数，那12 有18 个约数的约数。  
珈百璃想：1 ~ n 的数里哪个数的约数的约数个数最多呢？  
没了电脑的珈百璃数不出来（虽然她一有电脑就会打网游），于是她请求你帮忙。

2.2 Task  
2.2.1 Input  
一行一个正整数n。  
2.2.2 Output  
输出共两行。  
第一行一个正整数表示约数的约数个数最多的数，如果有多个输出最  
小的。  
第二行一个正整数表示这个数的约数的约数的个数

2.3 Sample I  
2.3.1 Input  
15  
2.3.2 Output  
12  
18  
  
2.4 Sample II  
2.4.1 Input  
114514  
2.4.2 Output  
110880  
3402

2.5 Constraint  
测试点n

解析：

考试时最后打的表，结果没时间跑样例， 就没发现要加1， 普通打表可以打40pts， 当然高手可以打出70pts， 这我也不知道该怎么打，我太菜了

考虑到一个为 ∏piri的数（其中pi为互不相同的质数）， 它的约数个数为 ∏（ri \+ 1）， 那么由乘法分配律可以得到，约数的约数个数为 ∏（1 + 2 + … + （ri  \+ 1））， 即 ∏（（ri \+ 2）\* （ri \+ 1） /  2）

如何求答案呢，由于答案要求相同情况下输出较小的一个， 考虑答案的质因数分解， 当pi单增时，ri一定不严格单减 ， 那么枚举ri的序列即可，pi的个数也并不多，复杂度可以接受

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    int pri[17] = {
         0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
    ll n, ans1, ans2;
    
    void dfs(int x, ll now, ll res, int pre)
    {
        if(res > ans2)
        {
            ans1 = now;
            ans2 = res;
        }
        else if(res == ans2 && now < ans1)
            ans1 = now;
        if(x == 17)    return ;
        for(int i = 1; i <= pre && now <= n / pri[x] && now * 1LL * pri[x] <= n; ++i)
        {
            now *= 1LL * pri[x];
            dfs(x + 1, now, res * 1LL * (i + 1) * (i + 2) / 2, i);
        }
    }
    
    int main()
    {
        freopen("b.in", "r", stdin);
        freopen("b.out", "w", stdout);
        scanf("%lld", &n);
        dfs(1, 1, 1, 60);
        printf("%lld\n%lld", ans1, ans2);
        return 0;
    }

**T3:**

3 密道

3.1 Description  
珈百璃在打副本时，走到一个奇怪的密道。密道由n+1条横道和n+1条纵道交叉形成，这些横纵道分别编号为0 到n。  
横道和纵道相交的地方都有路口，姑且把第i 条横道和第j 条纵道交错的路口叫做路口(i; j)。  
有的路口有怪物，经过珈百璃一段时间的发掘，珈百璃发现了刷怪的秘密：  
　　所有路口(i, 0) 和路口(0, i) 一定有怪物。  
　　 对于其他路口(i, j)，如果(i - 1, j) 和(i, j - 1) 都有怪物或者都没有怪物，那么这个路口也没有怪物；否则有。  
珈百璃想通过这个副本，自然需要先知道这些密道里有多少怪物了。  
那么，到底有多少路口有怪物呢？

3.2 Task  
3.2.1 Input  
一行一个正整数n。  
3.2.2 Output  
一行一个正整数表示有怪物的路口数量。

3.3 Sample I  
3.3.1 Input  
3  
3.3.2 Output  
9  
  
3.4 Sample II  
3.4.1 Input  
114514  
3.4.2 Output  
119562749

3.5 Constraint  
对于30% 的数据，n <= 3000；  
对于另外30% 的数据，n 是形如2k  - 1 的数；  
对于100% 的数据，n <= 109；

解析：

其实可以打表找规律，然后就发现，有1的地方（有怪物的地方）组成了长相相似三角形，三角形的边长都是2的次幂， 三角形内1的个数都是3的次幂， 三角形的个数取决于当前的边长， 与上一个三角形的边长和个数， 这个不太能说清，可以打个表体会一下

然后来一发正解（From Solution）:

可以发现如果把这个矩阵旋转45 度就是杨辉三角的递推式，也就是说(i, j) 的状态是C(i + j, j) mod 2。  
　　在模2 意义下由Lucas 定理C(i + j, j)只在j 的二进制表示是i+j 的子集时为1，等价于i 和j 的二进制表示没有任何一位同时为1，直接枚举最高位算或者数位dp 解决。

代码（非正解）：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    ll n, ans;
    ll pw3[40];
    
    void dfs(ll rest, ll num, int len)
    {
        if(rest == 0)    return ;
        for(int i = len - 1; i >= 0; --i)
            if(1LL * (1<<i) <= rest)
            {
                ll now = (1<<(len-i)) * num/2;
                ans += 1LL * 2 * now * pw3[i];
                dfs(rest - (1<<i), now, i);
                return ;
            }
    }
    
    int main()
    {
        freopen("c.in", "r", stdin);
        freopen("c.out", "w", stdout);
        scanf("%lld", &n);
        n ++;
        pw3[0] = 1;
        for(int i = 1; i <= 32; ++i)
            pw3[i] = 1LL * pw3[i-1] * 3;
        int len = log(n)/log(2);
        ans = pw3[len];
        dfs(n - (1<<len), 2, len);
        printf("%lld\n", ans);
        return 0;
    }

转载于:https://www.cnblogs.com/Joker-Yza/p/11266485.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211018/100ebf3e49b94c1ba59111b5c732a146.png