1.取余
原题:
解题思路:
这道题30%的数据可以开longlong去存储计算,但100%的数据最多有3000位,无法存储,所以可以运用同余的性质,(a*b)%p=(a%p*b%p)%p
AC代码:
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e3+5,MOD = 1e4+7;; ll a[N],n,ans=1; int main(){ freopen("mod.in","r",stdin); freopen("mod.out","w",stdout); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)ans=((ans%MOD)*(a[i]%MOD))%MOD; cout<<ans; return 0; }
2.加密
原题:
解题思路:
这道题有两种方法,第一种是打表,记录每个字母对应的字符,进行输出,第二种是模拟法,分情况输出,当Si=a或b是,分别输出y和z,其他的是输出前2个字符。
AC代码:
这里用的是打表的方法。
#include<bits/stdc++.h> #define ll long long using namespace std; string p; char a[26]={'y','z','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x'}; char b[26]={'Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X'}; int main(){ freopen("jm.in","r",stdin); freopen("jm.out","w",stdout); cin>>p; for(int i=0;i<p.length();i++){ if(p[i]>='a'&&p[i]<='z')cout<<a[p[i]-'a']; else if(p[i]>='A'&&p[i]<='Z')cout<<char(b[p[i]-'A']); } return 0; }
3.进制转换
原题:
解题思路:
暴力求模数逆序串即可
AC代码:
#include<bits/stdc++.h> #define ll long long using namespace std; ll n; int k; char t[17]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; string change(ll n,int k){ string ans=""; while(n){ ans+=t[n%k]; n/=k; } for(int i=0,j=ans.length()-1;i<j;i++,j--)swap(ans[i],ans[j]); return ans; } int main(){ freopen("change.in","r",stdin); freopen("change.out","w",stdout); cin>>n>>k; cout<<change(n,k); return 0; }
4.上学路线
原题:
解题思路:
这道题与第一题相似,都用到了同余的性质,这道题可以用深搜,也可以用DP,DP的状态转移方程是dpi,j=(dpi-1,j+dpi,j-1)%1000000007
AC代码:
这里用的是DP
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e3+5,MOD = 1e9+7; ll dp[N][N],n,m; int main(){ freopen("roud.in","r",stdin); freopen("roud.out","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++)dp[1][i]=1; for(int i=1;i<=n;i++)dp[i][1]=1; for(int i=2;i<=n;i++){ for(int j=2;j<=m;j++){ dp[i][j]=((dp[i-1][j]%MOD)+(dp[i][j-1]%MOD))%MOD; } } cout<<dp[n][m]; return 0; }
标签:竞赛,int,ll,long,2019,freopen,using,程序设计,include From: https://www.cnblogs.com/zhanghx-blogs/p/17357463.html