2020.3.20
题目一
有一叠扑克牌，每张牌介于1和10之间
有四种出牌方法：
单出1张
出2张对子
出五张顺子，如12345
出三连对子，如112233
给10个数，表示1-10每种牌有几张，问最少要多少次能出完

#include <iostream>
#include <vector>
using namespace std;int Getmintimes(vector<int> cardnums,int k){if(cardnums.size()<10||k>=cardnums.size()) return 0;if(cardnums[k]==0) return Getmintimes(cardnums, k+1);int mintimes=INT_MAX;if(k<=cardnums.size()-3&&cardnums[k]>=2&&cardnums[k+1]>=2&&cardnums[k+2]>=2){cardnums[k]-=2;cardnums[k+1]-=2;cardnums[k+2]-=2;mintimes=min(1+Getmintimes(cardnums,k),mintimes);cardnums[k]+=2;cardnums[k+1]+=2;cardnums[k+2]+=2;}if(k<=cardnums.size()-5&&cardnums[k]>=1&&cardnums[k+1]>=1&&cardnums[k+2]>=1&&cardnums[k+3]>=1&&cardnums[k+4]>=1){cardnums[k]-=1;cardnums[k+1]-=1;cardnums[k+2]-=1;cardnums[k+3]-=1;cardnums[k+4]-=1;mintimes=min(1+Getmintimes(cardnums,k),mintimes);cardnums[k]+=1;cardnums[k+1]+=1;cardnums[k+2]+=1;cardnums[k+3]+=1;cardnums[k+4]+=1;}if(cardnums[k]>=2){cardnums[k]-=2;mintimes=min(1+Getmintimes(cardnums,k),mintimes);cardnums[k]+=2;}if(cardnums[k]>=1){cardnums[k]-=1;mintimes=min(1+Getmintimes(cardnums,k),mintimes);cardnums[k]+=1;}return mintimes;
}int main(){vector<int> cardnums(10,0);//cout<<cardnums.size();cardnums[0]=2;cardnums[1]=2;//cardnums[2]=;cardnums[3]=3;cardnums[4]=2;cardnums[5]=5;cardnums[6]=2;cardnums[7]=1;//cardnums[8]=;cardnums[9]=3;int result=Getmintimes(cardnums,0);cout<<result<<endl;return 0;
}

题目二
定义上升字符串，s[i]≥s[i−1],比如aaa，abc是，acb不是；
给n个上升字符串，选择任意个拼起来，问能拼出来的最长上升字符串长度；

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int Getmaxlen(vector<string> str){if(str.size()==0) return 0;sort(str.begin(),str.end());vector<int> f(str.size(),0);int maxlen=0;for(int i=0;i<str.size();i++){int submaxlen=0;for(int j=0;j<i;j++){if(str[j][str[j].size()-1]<=str[i][0]&&f[j]>submaxlen) submaxlen=f[j];}f[i]=submaxlen+str[i].size();if(f[i]>maxlen) maxlen=f[i];}return maxlen;
}int main(){string s;vector<string> str;s="aaa";str.push_back(s);s="bcd";str.push_back(s);s="bbccdd";str.push_back(s);s="abc";str.push_back(s);s="cde";str.push_back(s);s="fhj";str.push_back(s);int maxlen=Getmaxlen(str);cout<<maxlen<<endl;return 0;
}

2020.3.23
题目一
从n个人中选择任意数量的人员组成一支队伍，然后从一支队伍中选出一位队长，不同的队长算不同的组合，问这样的组合的数量对10^9+7取模 。
数据范围：1 <= n <= 1000000000;
输入：n = 2
输出：4
解释,(1),(2)(1,2),(2,1)四种，括号第一个为队长

#include <iostream>
#include <vector>
using namespace std;int pow(int n, int mod){if(n==0) return 1;if(n==1) return 2;int result=pow(n/2, mod);if(n%2==1) return (result*result*2)%mod;else return (result*result)%mod;
}int Getnums(int n, int mod){int nums;return (pow(n-1,mod)*n)%mod;
}int main(){int mod=1000000007;int nums=Getnums(10,mod);cout<<nums<<endl;return 0;
}

题目二
一个地图n*m，包含1个起点，1个终点，其他点包括可达点和不可达点。 每一次可以：上下左右移动，或使用1点能量从（i,j)瞬间移动到（n-1-i, m-1-j)，最多可以使用5点能量。
数据范围：2 <= n,m <= 500;

输入：
4 4
#S…
E#…
…
…
输出：4
解释:S(0,1)先瞬移到(3, 2)，然后往上一步，往右一步，瞬移到E，一共4步

//待调试（有问题）
#include <iostream>
#include <vector>
#include <string>
using namespace std;int Getsteps(vector<string> str, int curow, int cucol, int k){if(str[curow][cucol]=='E') return 0;int rows=str.size();int cols=str[0].size();int minsteps=1000000000;str[curow][cucol]='#';if(cucol>0&&str[curow][cucol-1]!='#'){int custeps=Getsteps(str,curow,cucol-1,k);minsteps=min(minsteps, custeps+1);}if(cucol<cols-1&&str[curow][cucol+1]!='#'){int custeps=Getsteps(str,curow,cucol+1,k);minsteps=min(minsteps, custeps+1);}if(curow>0&&str[curow-1][cucol]!='#'){int custeps=Getsteps(str,curow-1,cucol,k);minsteps=min(minsteps, custeps+1);}if(curow<rows-1&&str[curow+1][cucol]!='#'){int custeps=Getsteps(str,curow+1,cucol,k);minsteps=min(minsteps, custeps+1);}if(k>0&&str[rows-1-curow][cols-1-cucol]!='#'){int custeps=Getsteps(str,rows-1-curow,cols-1-cucol,k-1);minsteps=min(minsteps, custeps+1);}return minsteps;
}int main(){//string s[10];vector<string> str;string s;s='#S..';str.push_back(s);s='E#..';str.push_back(s);s='....';str.push_back(s);s='....';str.push_back(s);int result=Getsteps(str,0,1,5);cout<<result<<endl;return 0;}

2020.3.25
题目一
3 * n的数组，每行列选出一个数字，输出他们的差值的绝对值的最小值。

如：
5 9 5 4 4
4 7 4 10 3
2 10 9 2 3
最小值为5。 【5，7，5，4，4】 ，差值为2 + 2 + 1 = 5.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;int Getmin(vector<int> a,vector<int> b,vector<int> c){int n=a.size();if(n==0) return 0;if(n==1) return min(a[0],min(b[0],c[0]));vector<vector<int> > f(3,vector<int>(n,0));int min0,min1,min2;for(int i=1;i<n;i++){min0=abs(a[i-1]-a[i]);min1=abs(b[i-1]-a[i]);min2=abs(c[i-1]-a[i]);f[0][i]=min(f[0][i-1]+min0,min(f[1][i-1]+min1,f[2][i-1]+min2));min0=abs(a[i-1]-b[i]);min1=abs(b[i-1]-b[i]);min2=abs(c[i-1]-b[i]);f[1][i]=min(f[0][i-1]+min0,min(f[1][i-1]+min1,f[2][i-1]+min2));min0=abs(a[i-1]-c[i]);min1=abs(b[i-1]-c[i]);min2=abs(c[i-1]-c[i]);f[2][i]=min(f[0][i-1]+min0,min(f[1][i-1]+min1,f[2][i-1]+min2));}return min(f[0][n-1],min(f[1][n-1],f[2][n-1]));
}int main(){int n;cin>>n;int i;vector<int> a(n,0);vector<int> b(n,0);vector<int> c(n,0);for(i=0;i<n;i++)cin>>a[i];for(i=0;i<n;i++)cin>>b[i];for(i=0;i<n;i++)cin>>c[i];int result=Getmin(a,b,c);cout<<result<<endl;return 0;
}

题目二
输入n * m的数组，以及q次查询。
例如 如下数组， 为0代表未知。
数组的行和列都可以构成等差数列
输入：
1 0 3
0 0 0

q次查询为输入的数组，分别输入x,y，代表x行y列。例如当q = 4时。
1 1
1 2
2 1
2 3

输出：
q次查询的结果，有值输出值，值不确定输出Unknow

#include <iostream>
#include <vector>using namespace std;int Recover_row(vector<vector<int> > &matrix, int n,int m){int updatenums=0;for(int i=0;i<n;i++){int nums=0;int firstdata,seconddata;int first;int para;for(int j=0;j<m;j++){if(matrix[i][j]==0) continue;else if(matrix[i][j]!=0) nums++;if(nums==1){firstdata=matrix[i][j];first=j;}if(nums==2){seconddata=matrix[i][j];para=(seconddata-firstdata)/(j-first);break;}}if(nums>=2){for(int k=0;k<m;k++){if(matrix[i][k]==0){matrix[i][k]=firstdata+(k-first)*para;updatenums++;}}}}return updatenums;}int Recover_col(vector<vector<int> > &matrix, int n,int m){int updatenums=0;for(int i=0;i<m;i++){int nums=0;int firstdata,seconddata;int first;int para;for(int j=0;j<n;j++){if(matrix[j][i]==0) continue;else if(matrix[j][i]!=0) nums++;if(nums==1){firstdata=matrix[j][i];first=j;}if(nums==2){seconddata=matrix[j][i];para=(seconddata-firstdata)/(j-first);break;}}if(nums>=2){for(int k=0;k<n;k++){if(matrix[k][i]==0){matrix[k][i]=firstdata+(k-first)*para;updatenums++;}}}}return updatenums;
}void Fillmatrix(vector<vector<int> > matrix, vector<vector<int> > qindex, int n,int m, int q){int updaterownums=Recover_row(matrix,n,m);int updatecolnums=Recover_col(matrix,n,m);while(1){if(updatecolnums>0) updaterownums=Recover_row(matrix,n,m);else break;if(updaterownums>0) updatecolnums=Recover_col(matrix,n,m);else break;}for(int i=0;i<q;i++){if(matrix[qindex[i][0]][qindex[i][1]]==0) cout<<"Unknown";else cout<<matrix[qindex[i][0]][qindex[i][1]]<<endl;}/*for(int i=0;i<n;i++){for(int j=0;j<m;j++)cout<<matrix[i][j]<<" ";cout<<endl;}*/
}int main(){int n,m,q;cin>>n;cin>>m;cin>>q;vector<vector<int> > matrix(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>matrix[i][j];}}vector<vector<int> > qindex(q,vector<int>(2,0));for(int i=0;i<q;i++){cin>>qindex[i][0];cin>>qindex[i][1];}Fillmatrix(matrix,qindex,n,m,q);return 0;
}

2020.3.27
题目一
给两个等长字符串，长度范围1e5，你可以选择第一个字符串的一个字符移动到字符串尾部，目的是让两个字符串相等，求最小的移动次数。能则转换输出最小次数，不能则输出-1，

输入：
akbd
kdba
输出：2

#include <iostream>
#include <string>
#include <vector>
using namespace std;int Gettimes(string s, string t){if(s.size()!=t.size()) return -1;int letters[256]={0};int lettert[256]={0};for(int i=0;i<s.size();i++){letters[s[i]]++;lettert[t[i]]++;}for(int i=0;i<256;i++)if(letters[i]!=lettert[i]) return -1;vector<int> f(s.size(),0);int j=0;int i=0;if(s[i]==s[j]){f[0]=1;j++;i++;}for(;i<s.size();i++){if(s[i]==t[j]){f[i]=f[i-1]+1;j++;}else f[i]=f[i-1];}return s.size()-f[s.size()-1];
}int main(){string s;string t;cin>>s;cin>>t;int result = Gettimes(s,t);cout<<result<<endl;return 0;
}

题目二
第一行输入n个数
第二行输入l1……ln
第三行输入r1……rn
抽n个数，第i个的抽取空间（ln……rn），问抽取的最小期望值是多少，输出保留6位小数。

示例：
输入：2
1 2
3 3
输出：1.833333

思路：

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;double Getexpection(int n,vector<int> l,vector<int> r){double expection;int allnums=1;for(int i=0;i<n;i++)allnums*=(r[i]-l[i])+1;for(int i=0;i<n;i++){for(int j=l[i];j<=r[i];j++){int nums=1;for(int k=0;k<i;k++){if(r[k]>j) nums*=min(r[k]-j,r[k]-l[k]);else if(r[k]<=j){ nums=0; break;}}if(nums!=0){for(int k=i+1;k<n;k++){if(r[k]>=j) nums*=min(r[k]-j,r[k]-l[k])+1;else if(r[k<j]){ nums=0; break;}}}expection += double(j*nums) / allnums;}}return expection;
}int main(){int n;cin>>n;vector<int> l(n,0);vector<int> r(n,0);for(int i=0;i<n;i++)cin>>l[i];for(int i=0;i<n;i++)cin>>r[i];double result=Getexpection(n,l,r);cout<<fixed<<setprecision(6)<<result<<endl;return 0;
}

2020.3.30
题目一
小强有n个养鸡场，弟i个养鸡场初始有a[i]只小鸡。与其他养鸡场不同的是，他的养鸡场每天增加k只小鸡，小强每天结束都会在数量最多的养鸡场里卖掉一半的小鸡，假如一个养鸡场有x只鸡，则卖出后只剩下x/2(向下取整)只鸡。问m天后小强的n个养鸡场一共多少只小鸡？

输入：
第一行输入三个int类型n,m,k（1 <= n,m,k <= 10^6）
第二行输入n个正整数，表示n个养鸡场初始鸡的个数
输出：
输出一个整数表示鸡的总数

示例：
输入：
3 3 100
100 200 400
输出：
925

#include <iostream>
#include <vector>using namespace std;int Getfinalchickens(int n,int m,int k,vector<int> chickens){int maxindex=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){chickens[j]+=k;if(chickens[j]>chickens[maxindex]) maxindex=j;}chickens[maxindex] /=2;}int result=0;for(int i=0;i<n;i++){result+=chickens[i];}return result;
}int main(){int n,m,k;cin>>n>>m>>k;vector<int> chickens(n,0);for(int i=0;i<n;i++)cin>>chickens[i];int result=Getfinalchickens(n,m,k,chickens);cout<<result<<endl;return 0;
}

题目二：
小强得到了长度为n的序列，但他只对非常大的数字感兴趣，因此随机选择这个序列的一个连续子序列，并求这个序列的最大值，请告诉他这个最大值的期望是多少?
输入：
第一行n表示序列长度接下来一行n个数描述这个序列，n大于等于1小于等于1000000，数字保证是正整数且不超过100000
第二行n个数字表示序列的值
输出：保留6位小数

输入：
3
1 2 3
输出：
2.333333
解释：
{1},{2},{3},{1,2},{2,3},{1,2,3}为所有子序列，1最大的概率1/6，2最大的概率为2/6，3最大概率3/6，期望14/6

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;double Getexpection(int n, vector<int> arraylist){vector<int> f(n,1);int allnums=n*(n+1)/2;double expection=0.0;for(int i=0;i<n;i++){int a=0;int b=0;for(int j=i-1;j>=0;j--){if(arraylist[j]>=arraylist[i]) break;a++;}for(int k=i+1;k<n;k++){if(arraylist[k]>arraylist[i]) break;b++;}f[i]+=a+b+(a*b);expection+= double(arraylist[i]*f[i])/double(allnums);cout<<f[i]<<endl;}return expection;
}int main(){int n;cin>>n;vector<int> arraylist(n,0);for(int i=0;i<n;i++){cin>>arraylist[i];}double result=Getexpection(n,arraylist);cout<<fixed<<setprecision(6)<<result<<endl;return 0;
}