【题目记录】——2021百度之星程序设计大赛-复赛

小灰灰 2022-09-14 13:28 113阅读 0赞

### 文章目录 ###

*  1001 Palindrome
 *  1002 Add or Multiply 1

题目集原地址 [2021百度之星程序设计大赛-复赛][2021_-]  
题目集地址 [2021百度之星程序设计大赛-复赛][2021_- 1]

# 1001 Palindrome #

题目地址[Palindrome][]  
思路：只需要分类即可，

> 当n等于k的时候，只要n>2就可以满足条件同时是回文串  
> n为1的时候不可能满足条件  
> 否则k为奇数就可以满足条件，k为偶数就无法满足条件

AC代码：

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int t;
        scanf("%d",&t);
        while(t--)
        { 
            int n, k;
            scanf("%d%d",&n,&k);
            if(n == k&&n > 2)
            { 
                printf("Yes!\n");
                continue;
            }
            if(n==1)
            { 
                printf("No!\n");
            }
            else if(k&1)
            { 
                printf("Yes!\n");
            }
            else
            { 
                printf("No!\n");
            }
        }
        return 0;
    }

# 1002 Add or Multiply 1 #

题目地址[Add or Multiply 1][]  
思路：是关于斯特林数的内容，数论这块我不是很清楚  
参考题解[Add or Multiply 1][Add or Multiply 1 1]  
参考题解[Add or Multiply 1 CSDN][]  
AC代码：

#include<iostream>
    using namespace std;
    typedef long long ll;
    ll F[3050][3050]={ 0};
    long long A[3030];
    const long long mod = 1e9+7;
    long long S(ll n,ll m){ 
    	if(F[n][m]) return F[n][m];
    	if(n==0||m==0) return 0;
        if(m==1 || m==n)
            F[n][m] = 1;
        else{ 
        	F[n][m] = S(n-1,m-1)%mod + ((S(n-1,m)%mod)*m)%mod;
    	}
        return F[n][m]%mod;
    }
     
    void init(){ 
        ll n;
        n = 3010;
        for(int i=1; i<=n; i++){ 
        	for(int j=1;j<=i;j++){ 
        		F[i][j] = S(i,j);
    		}
    	}
    	A[0] = 1;
    	for(int i=1;i<n;i++){ 
    		A[i] = (A[i-1]*i)%mod;	
    	}
    }
    long long mul(ll a,ll b,ll c,ll d){ 
    	ll ans = 1;
    	ans = a*b%mod;
    	ans = ans*c%mod;
    	ans = ans*d%mod;
    	return ans;
    }
    int main(){ 
    	int t;
    	cin >> t;
    	init();
    	while(t--){ 
    		long long n,m;
    		scanf("%lld%lld",&n,&m);
    		if(n>m) swap(n,m);
    		ll ans = 0;
    		for(int i=1;i<n;i++){ 
    			ans += mul(F[n][i],A[i],F[m][i-1],A[i-1]);
    			ans += 2*mul(F[n][i],A[i],F[m][i],A[i]);
    			ans += mul(F[n][i],A[i],F[m][i+1],A[i+1]);
    			ans %= mod;
    		}
    		if(n == m){ 
    			ans = ans + (2*A[n]*A[n])%mod + mul(F[n][n],A[n],F[m][n-1],A[n-1]);
    			ans %= mod;
    		}
    		else{ 
    			ans += mul(F[n][n],A[n],F[m][n-1],A[n-1]);
    			ans += 2*mul(F[n][n],A[n],F[m][n],A[n]);
    			ans += mul(F[n][n],A[n],F[m][n+1],A[n+1]);
    			ans %= mod;			
    		}
    		printf("%lld\n",ans);
    	}
    	return 0;
    }

[2021_-]: http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=1032
[2021_- 1]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021+%C4%EA%B0%D9%B6%C8%D6%AE%D0%C7%A1%A4%B3%CC%D0%F2%C9%E8%BC%C6%B4%F3%C8%FC+-+%B8%B4%C8%FC&source=1&searchmode=source
[Palindrome]: https://acm.hdu.edu.cn/showproblem.php?pid=7094
[Add or Multiply 1]: https://acm.hdu.edu.cn/showproblem.php?pid=7095
[Add or Multiply 1 1]: https://www.cnblogs.com/do-while-true/p/15171396.html
[Add or Multiply 1 CSDN]: https://blog.csdn.net/yingtingqi/article/details/119848541