ZOJ Monthly, March 2018 A B C J H

本文主要是介绍ZOJ Monthly, March 2018 A B C J H，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A Easy Number Game

贪心 很容易想到，将数列排序 将前2n个数 掐头去尾的相乘求和

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int T;
int n,m;
int s[100100];
int main()
{cin>>T;while(T--){cin>>n>>m;for(int i=0;i<n;i++)cin>>s[i];sort(s,s+n);long long int res=0;for(int i=0;i<m;i++){res+=s[i]*s[2*m-i-1];}cout<<res<<endl;}return 0;
}

B Lucky Man

卡在了第五题上，规律发现了 但是当时做不到快速的得到1000位长度的大整数的平方根而超时，现在已经解决，就是运用模拟笔算的方式得到，1880ms过了题，限制是2000ms

同时也知道了可以用Python直接输入大整数进行牛顿迭代的方法得到。

#include <stdio.h> 
#include <string.h> 
#include <iostream>
using namespace std;
int l; 
char an[1111];
int js=0;
int work(int o,char *O,int I) 
{ 
char c, *D=O ; 
if(o>0) 
{ 
for(l=0;D[l];D[l++]-=10) 
{ 
D[l++]-=120; 
D[l]-=110; 
while(!work(0,O,l)) 
D[l]+=20; 
an[js++]=(D[l]+1032)/20;
} 
} 
else 
{ 
c=o+(D[I]+82)%10-(I>l/2)*(D[I-l+I]+72)/10-9; 
D[I]+=I<0 ? 0 : !(o=work(c/10,O,I-1))*((c+999)%10-(D[I]+92)%10); 
} 
return o; 
} int main() 
{ 
int t;
cin>>t;
while(t--)
{
char s[1200]={};s[0]='0'; 
scanf("%s",s+1); 
js=0;
if(strlen(s)%2 == 1) 
work(2,s+1,0); 
else 
work(2,s,0); 
if((an[js-1]-'0')%2==1)cout<<"1"<<endl;
else cout<<"0"<<endl; 
}
return 0; 
}

C Travel along the Line

概率题，在无现长数轴上，给定起点和终点的距离，给出时间，每一秒有0.25的概率前进，0.25的概率后退，0.5的概率不懂，问在时间用完的时候恰好在终点的概率。 当时列了个式子，想着用lucas算法去解大组合数，结果超时，后来把式子化简一下，打了个阶乘表，就过了，以后碰到10e5以内的组合数 优先考虑打表。

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
LL p = 1e9+7;
LL quick_mod(LL a, LL b)
{LL ans = 1;a %= p;while(b){if(b & 1){ans = ans * a % p;b--;}b >>= 1;a = a * a % p;}return ans;
}long long  jc[100005];LL inv(LL a)
{if(a==1)return 1;return inv(p%a)*(p-p/a)%p;
}
int main(){long long int n,m;jc[0]=1;for(int i=1;i<=100000;i++){jc[i]=i*jc[i-1]%p;}int t;cin>>t;while(t--){cin>>n>>m;m=abs(m);long long int ans=0;for(int i=n-m;i>=0;i-=2){long long in=quick_mod(2,2*n-i);long long a1=jc[(n-i-m)/2]*jc[(n-i+m)/2]%p;a1=a1*jc[i]%p;ans=(ans+jc[n]%p*inv(in*a1%p)%p)%p;}cout<<ans<<endl;}return 0;
}

H Happy Sequence

dp题，从1到n 求长度为m的good数列的个数，即数列中前一个数可以整除后面一个数，主要思路就是将长度为k的某个数列的最后一个数能整除的数放到后面 使该数列的长度变为k+1，从而可以写出状态转移方程。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int mod=1000000007;
int T;
int n,m;
int dp[2002][2002];
vector<int> fac[2002];
int main()
{for(int i=1;i<=2000;i++){for(int j=1;j<=sqrt(i*1.0);j++){if(i%j==0){fac[i].push_back(j);if(j!=i/j)fac[i].push_back(i/j);}}}memset(dp,0,sizeof(dp));for(int i=0;i<=2000;i++)dp[i][1]=1;for(int i=2;i<=2000;i++){for(int j=1;j<=2000;j++){for(int k=0;k<fac[j].size();k++){(dp[j][i]+=dp[fac[j].at(k)][i-1])%=mod;}}}for(int i=1;i<=2000;i++){for(int j=2;j<=2000;j++){(dp[j][i]+=dp[j-1][i])%=mod;}}cin>>T;while(T--){cin>>n>>m;cout<<dp[n][m]<<endl;}return 0;
}

J Super Brain

快速找出2个数列中出现2次的数，数据范围很小，所以很简单。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int T,x;
int n,m;
bool s[1000100];
int main()
{cin>>T;while(T--){cin>>n;memset(s,0,sizeof(s));for(int i=0;i<n;i++){cin>>x;s[x]=1;}for(int i=0;i<n;i++){cin>>x;if(s[x])cout<<x<<endl;}}return 0;
}

这篇关于ZOJ Monthly, March 2018 A B C J H的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---