【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（7）

超、凢脫俗 2022-09-04 03:46 110阅读 0赞

### 文章目录 ###

*  1003 Fall with Trees 数学几何
 *  1004 Link with Balls 排列组合+数学
 *  1008 Smzzl with Greedy Snake 模拟
 *  1012 Yiwen with Sqc 统计贡献，差分优化

题目集地址 [2021“MINIEYE杯”中国大学生算法设计超级联赛（7）][2021_MINIEYE_7]  
题目集原地址 [2021“MINIEYE杯”中国大学生算法设计超级联赛（7）][2021_MINIEYE_7 1]  
这次题目集我们做了3道题目,1003,1010,1012

# 1003 Fall with Trees 数学几何 #

题目地址[1003 Fall with Trees][]  
思路：  
这道题基本上就是找规律然后求公式，我们可以设树层与层之间的高为h，根节点为第一层的话，第二层两个结点间的距离的一半为a，则第二层是2a，第三层是3a，第五层是(7/2)a，可以推出每一层的长度的通项公式为：(4-(1/2)k)\*a，其中k=n-2，n为层数。  
这样推公式容易理解，但是需要对只有两层的情况进行特判。其实我们可以发现面积就是三角形加上几个梯形的面积。因此写出梯形面积公式后求和即可，涉及到等比数列求和的部分直接使用求和公式即可。  
AC代码：

#include <iostream>
    #include <bits/stdc++.h>
    
    #define INF 0x3f3f3f3f
    #define pi 3.141592653589793238462643383279
    #define eps 1e-6
    
    using namespace std;
    typedef long long ll;
    double a[10010];
    void init()//初始化a数组，里面存的是2的次幂
    { 
        a[0]=1;
        for(int i=1;i<=10001;i++)
        { 
            a[i]=a[i-1]*0.5;
        }
    }
    void solve()
    { 
        int k,kk;
        scanf("%d",&k);
        double x[10],y[10];
        for(int i=0;i<3;i++)
        { 
            scanf("%lf%lf",&x[i],&y[i]);
        }
        double h=abs(y[1]-y[0]);
        double cha=abs(x[1]-x[0]);
        double res;
        res=2*cha*h;
        if(k==2)
        { 
            res/=2;
            printf("%.3lf\n",res);
            return ;
        }
        kk=k-2;
        double res1=4*(kk-1)+a[kk-1]+a[kk];
        res+=(res1*h*cha);
        printf("%.3lf\n",res);
    }
    
    int main()
    { 
        init();
        int t;
        scanf("%d",&t);
        while(t--)
            solve();
        return 0;
    }

# 1004 Link with Balls 排列组合+数学 #

题目地址[Link with Balls][]  
题意：有n个框，在第2x-1个框中可以取kx个球(k为整数)，在第2x个框中最多可以取x个球。要取m个球，有多少种方案。  
思路：将可以取0~k-1个球的框与只能取k的倍数个球的框合并为一个可以取任意个球的框，就得到了 n个可以取任意个球的框和一个可以取0~n个球的框。枚举0~n个球的框中取出了多少个球，剩下的球的选取方案可以由插板法得到，于是答案为 ∑ i = 0 n C m − i + n − 1 n − 1 \\sum\_\{i=0\}^\{n\}C\_\{m-i+n-1\}^\{n-1\} ∑i=0nCm−i\+n−1n−1，即 C m + n n − C m − 1 n C\_\{m+n\}^\{n\}-C\_\{m-1\}^n Cm\+nn−Cm−1n

公式是由数学推导得来的，不是很懂，但是求组合数的板子还是很好用的。

#include <stdio.h>
    #define MN 2000000
    typedef long long ll;
    const int mod = 1000000007;
    
    int fac[MN+5],inv[MN+5];
    
    ll qpow(ll bsc,ll y){ 
    	ll ret = 1;
    	while(y){ 
    		if(y&1) ret = ret*bsc%mod;
    		bsc = bsc*bsc%mod;
    		y >>= 1; 
    	}
    	return ret;
    }
    
    void init(){ 
    	fac[0] = 1;
    	for(int i=1;i<=MN;i++)
    		fac[i] = (ll)fac[i-1]*i%mod;
    	inv[MN] = qpow(fac[MN],mod-2);
    	for(int i=MN-1;i>=0;i--)
    		inv[i] = (ll)inv[i+1]*(i+1)%mod;
    }
    
    int C(int n,int m){ 
    	if(m>n) return 0;
    	return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
    }
    
    void solve(){ 
    	int n,m;
    	scanf("%d%d",&n,&m);
    	int ans = C(m+n,n)-C(m-1,n);
    	if(ans<0) ans += mod;
    	printf("%d\n",ans);
    }
    
    int main(){ 
    	init();
    	int T;
    	scanf("%d",&T);
    	while(T--) solve();
    }

# 1008 Smzzl with Greedy Snake 模拟 #

题目地址[1008 Smzzl with Greedy Snake][]  
题意：一个贪吃蛇，有初始位置和方向，吃到一个点下一个点才会出现，给定几个点，输出最短的操作序列，操作c顺时针转，操作u逆时针转，操作f前进，不考虑咬到自身的情况。  
思路：这个题是我最后做的，但是当时没做出来，想的太复杂了，其实挺简单的，关键就是决定转向的时候繁琐一点。  
AC代码：

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    using namespace std;
    //0上1右2下3左
    void print(int &x1,int x2)
    { 
        int n;
        if(x1 < x2)
        { 
            n = x2 - x1;
        }
        else
        { 
            n = x1 - x2;
        }
        for(int i = 1;i <= n;i++)
        { 
            printf("f");
        }
        x1 = x2;
    }
    int turnround(int x1,int y1,int a,int x2,int y2)
    { 
        if(y2 > y1)
        { 
            if(x2 > x1) //终点在起点右上
            { 
                if(a == 3)//如果方向朝左顺时针转
                { 
                    cout << 'c' ;
                    return 0;
                }
                else if(a == 2)//下
                { 
                    cout << 'u' ;
                    return 1;
                }
            }
            else if(x2 < x1)//终点在起点左上
            { 
                if(a == 1)//起点方向朝右
                { 
                    cout << 'u';
                    return 0;
                }
                else if(a == 2)//下
                { 
                    cout << 'c';
                    return 3;
                }
            }
            else//正上方
            { 
                if(a == 1)
                { 
                    cout << 'u' ;
                }
                else if(a == 2)
                { 
                    cout << "uu" ;
                }
                else if(a == 3)
                { 
                    cout << 'c';
                }
                return 0;
            }
        }
        else if(y2 < y1)
        { 
            if(x2 > x1)//右下
            { 
                if(a == 3)//起点方向朝左
                { 
                    cout << 'u';
                    return 2;
                }
                else if(a == 0)//上
                { 
                    cout << 'c';
                    return 1;
                }
            }
            else if(x2 < x1)//左下
            { 
                if(a == 0)//上
                { 
                    cout << 'u';
                    return 3;
                }
                else if(a==1)
                { 
                    cout << 'c';
                    return 2;
                }
            }
            else//正下方
            { 
                if(a == 0)
                { 
                    cout << "cc";
                }
                else if(a == 1)
                { 
                    cout << 'c';
                }
                else if(a == 3)
                { 
                    cout << 'u';
                }
                return 2;
            }
        }
        else
        { 
            if(x2 < x1)//正左方
            { 
                if(a == 0)
                { 
                    cout << 'u';
                }
                else if(a == 1)
                { 
                    cout << "cc";
                }
                else if(a == 2)
                { 
                    cout << 'c';
                }
                return 3;
            }
            else if(x2 > x1)
            { 
                if(a == 0)
                { 
                    cout << 'c';
                }
                else if(a == 2)
                { 
                    cout << 'u';
                }
                else if(a == 3)
                { 
                    cout << "cc";
                }
                return 1;
            }
        }
        return a;
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	int t;
    	scanf("%d",&t);
    	while(t--)
        { 
            int x, y, d,x1,y1;
            scanf("%d%d%d",&x,&y,&d);
            int n;
            scanf("%d",&n);
            for(int i = 1;i <= n;i++)
            { 
                scanf("%d%d",&x1 ,&y1);
                for(int i = 1;x!=x1||y!=y1;i++)
                { 
                    d = turnround(x,y,d,x1,y1);
                    if(d%2)
                    { 
                        print(x,x1);
                    }
                    else
                    { 
                        print(y,y1);
                    }
                }
            }
            printf("\n");
        }
        return 0;
    }

# 1012 Yiwen with Sqc 统计贡献，差分优化 #

题目地址[1012 Yiwen with Sqc][]  
题意：给一个字符串，求所有子区间各个字符出现次数之和。  
思路：求后缀，因为每增加一个字母，假设这是第i个字母，那么整个字符串的子串数量就会加i个，这时候只要计算这i个新增字串对答案的贡献即可，这样我们的时间复杂度是O(26n)，我看题解说会卡常，但我们没有卡。。  
AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <cstdlib>
    #include <queue>
    #include <unordered_map>
    #include <map>
    #include <set>
    #include <numeric>
    #include <stack>
    #include <sstream>
    #include <cmath>
    #include <bitset>
    #include <unordered_set>
    #include <functional>
    #include <list>
    #include <vector>
    #include <iterator>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef __int128 Bint;
    const int maxn=1e5+10;
    const int mod=998244353;
    int T;
    ll square[27],sum[27],cnt[27];
    char s[maxn];
    int main() { 
        scanf("%d",&T);
        getchar();
        while(T--) { 
            scanf("%s",s+1);
            int len=strlen(s+1);
            ll ans=0;
            for(int i=1; i<=len; i++) { 
                int t=s[i]-'a';
                if(i==1) { 
                    square[t]++;
                    sum[t]++;
                    cnt[t]++;
                    continue;
                } else { 
                    for(int j=0; j<=26; j++)
                        ans=(ans+square[j])%mod;
                    square[t]=(square[t]+(2*sum[t]%mod)+i)%mod;
                    cnt[t]=i;
                    sum[t]=(sum[t]+i)%mod;
                }
            }
            for(int i=0; i<=26; i++)
                ans=(ans+square[i])%mod;
            printf("%lld\n",ans);
            memset(square,0,sizeof(square));
            memset(sum,0,sizeof(sum));
            memset(cnt,0,sizeof(cnt));
        }
        return 0;
    }

[2021_MINIEYE_7]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A87%A3%A9&source=1&searchmode=source
[2021_MINIEYE_7 1]: https://acm.hdu.edu.cn/contests/contest_show.php?cid=990
[1003 Fall with Trees]: https://acm.hdu.edu.cn/showproblem.php?pid=7046
[Link with Balls]: https://acm.hdu.edu.cn/showproblem.php?pid=7047
[1008 Smzzl with Greedy Snake]: https://acm.hdu.edu.cn/showproblem.php?pid=7051
[1012 Yiwen with Sqc]: https://acm.hdu.edu.cn/showproblem.php?pid=7055