1.输入一个无符号整数x，输出x的二进制表示中1的个数.
输入：
76584
输出：
7
水题：数据应该也不大，long long 也能过
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<cmath>
typedef long long ll;
using namespace std;
int main()
{
unsigned long long n;
cin>>n;
int s=0;
while(n)
{
if(n%2==1)
{
s++;
}
n/=2;
}
cout<<s<<endl;
return 0;
} 2.猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第十天早上想在吃时就只剩下一个桃子了。求第一天共摘了多少桃子。
（下面的不是正确答案）
输出：
8
逆向递推
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<cmath>
typedef long long ll;
using namespace std;
long long a[15];
int main()
{
a[10]=1;
for(int t=9;t>=1;t--)
{
a[t]=(a[t+1]+1)*2;
}
cout<<a[1]<<endl;
return 0;
} 3. 计算一个无符号整数的阿尔法乘积。对于一个无符号整数x来说，它的阿尔法乘积是这样来计算的：如果x是一个个位数，那么它的阿尔法乘积就是它本身；否则的话，x的阿尔法乘积就等于它的各位非0的数字相乘所得到的那个整数的阿尔法乘积。例如，4018224312的阿尔法乘积等于8，它是经过以下的几个步骤计算出来的：
4018224312à4*1*8*2*2*4*3*1*2à3072
3072à3*7*2à42
42à4*2à8
输入：
4018224312
输出：
8
水
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<cmath>
typedef long long ll;
using namespace std;
int main()
{
unsigned long long n;
cin>>n;
while(n/10)
{
unsigned long long k=n;
n=1;
while(k)
{
if(k%10)
{
n*=(k%10);
}
k/=10;
}
}
cout<<n<<endl;
return 0;
} 下一题没写，看着有点麻烦，应该不是很难
5. 数组A中共有n个元素，初始全为0。你可以对数组进行两种操作：1、将数组中的一个元素加1；2、将数组中所有元素乘2。求将数组A从初始状态变为目标状态B所需要的最少操作数。
输入格式
第一行一个正整数n表示数组中元素的个数
第二行n个正整数表示目标状态B中的元素
输出格式
输出一行表示最少操作数
样例输入
2
7 8
样例输出
7
数据规模和约定
n<=50，B[i]<=1000
逆向思维
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<cmath>
typedef long long ll;
using namespace std;
int a[55];
int main()
{
int n;
cin>>n;
for(int t=0;t<n;t++)
{
scanf("%d",&a[t]);
}
int flag=0;
ll s=0;
while(flag==0)
{
int flag1=0;
for(int t=0;t<n;t++)
{
if(a[t]%2==1)
{
a[t]--;
s++;
flag1=1;
}
}
if(flag1==0)
{
for(int t=0;t<n;t++)
{
a[t]/=2;
}
s++;
}
int cnt=0;
for(int t=0;t<n;t++)
{
if(a[t]==0)
{
cnt++;
}
}
if(cnt==n)
{
flag=1;
}
}
cout<<s<<endl;
return 0;
} 6.Anagrams指的是具有如下特性的两个单词：在这两个单词当中，每一个英文字母（不区分大小写）所出现的次数都是相同的。例如，Unclear和Nuclear、Rimon和MinOR都是Anagrams。编写一个程序，输入两个单词（只包含英文字母），然后判断一下，这两个单词是否是Anagrams。每一个单词的长度不会超过80个字符，而且是大小写无关的。
Input:长度不超过80个字符的两个单词，用空格隔开，不考虑字母大小写 （大小写无关）
Output: yes或者no
输入:
Rimon MinOR
输出:
yes
一眼题不解释
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<cmath>
typedef long long ll;
using namespace std;
char str1[85],str2[85];
int vis1[100];
int vis2[100];
int main()
{
scanf("%s",str1);
scanf("%s",str2);
int len1=strlen(str1);
int len2=strlen(str2);
for(int t=0;t<len1;t++)
{
if(str1[t]>='A'&&str1[t]<='Z')
{
str1[t]=tolower(str1[t]);
}
}
for(int t=0;t<len2;t++)
{
if(str2[t]>='A'&&str2[t]<='Z')
{
str2[t]=tolower(str2[t]);
}
}
for(int t=0;t<len1;t++)
{
vis1[str1[t]-'a']++;
}
for(int t=0;t<len2;t++)
{
vis2[str2[t]-'a']++;
}
int flag=1;
for(int t=0;t<26;t++)
{
if(vis1[t]!=vis2[t])
{
flag=0;
}
}
if(flag)
{
cout<<"yes"<<endl;
}
else
{
cout<<"no"<<endl;
}
return 0;
} 7.输入一个正整数n，输出n!的值。
其中n!=1*2*3*…*n。
算法描述
n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。
输入格式
输入包含一个正整数n，n<=1000。
输出格式
输出n!的准确值。
样例输入
10
样例输出
3628800
高精度
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
/*
* 完全大数模板
* 输出cin>>a
* 输出a.print();
* 注意这个输入不能自动去掉前导0的，可以先读入到char数组，去掉前导0，再用构造函数。
*/
#define MAXN 9999
#define MAXSIZE 1010
#define DLEN 4
class BigNum
{
private:
int a[5000]; //可以控制大数的位数
int len;
public:
BigNum() {
len=1; //构造函数
memset(a,0,sizeof(a));
}
BigNum(const int); //将一个int类型的变量转化成大数
BigNum(const char*); //将一个字符串类型的变量转化为大数
BigNum(const BigNum &); //拷贝构造函数
BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算
friend istream& operator>>(istream&,BigNum&); //重载输入运算符
friend ostream& operator<<(ostream&,BigNum&); //重载输出运算符
BigNum operator+(const BigNum &)const; //重载加法运算符，两个大数之间的相加运算
BigNum operator-(const BigNum &)const; //重载减法运算符，两个大数之间的相减运算
BigNum operator*(const BigNum &)const; //重载乘法运算符，两个大数之间的相乘运算
BigNum operator/(const int &)const; //重载除法运算符，大数对一个整数进行相除运算
BigNum operator^(const int &)const; //大数的n次方运算
int operator%(const int &)const; //大数对一个int类型的变量进行取模运算
bool operator>(const BigNum &T)const; //大数和另一个大数的大小比较
bool operator>(const int &t)const; //大数和一个int类型的变量的大小比较
void print(); //输出大数
};
BigNum::BigNum(const int b) //将一个int类型的变量转化为大数
{
int c,d=b;
len=0;
memset(a,0,sizeof(a));
while(d>MAXN) {
c=d-(d/(MAXN+1))*(MAXN+1);
d=d/(MAXN+1);
a[len++]=c;
}
a[len++]=d;
}
BigNum::BigNum(const char *s) //将一个字符串类型的变量转化为大数
{
int t,k,index,L,i;
memset(a,0,sizeof(a));
L=strlen(s);
len=L/DLEN;
if(L%DLEN)len++;
index=0;
for(i=L-1; i>=0; i-=DLEN) {
t=0;
k=i-DLEN+1;
if(k<0)k=0;
for(int j=k; j<=i; j++)
t=t*10+s[j]-'0';
a[index++]=t;
}
}
BigNum::BigNum(const BigNum &T):len(T.len) //拷贝构造函数
{
int i;
memset(a,0,sizeof(a));
for(i=0; i<len; i++)
a[i]=T.a[i];
}
BigNum & BigNum::operator=(const BigNum &n) //重载赋值运算符，大数之间赋值运算
{
int i;
len=n.len;
memset(a,0,sizeof(a));
for(i=0; i<len; i++)
a[i]=n.a[i];
return *this;
}
istream& operator>>(istream &in,BigNum &b)
{
char ch[MAXSIZE*4];
int i=-1;
in>>ch;
int L=strlen(ch);
int count=0,sum=0;
for(i=L-1; i>=0;) {
sum=0;
int t=1;
for(int j=0; j<4&&i>=0; j++,i--,t*=10) {
sum+=(ch[i]-'0')*t;
}
b.a[count]=sum;
count++;
}
b.len=count++;
return in;
}
ostream& operator<<(ostream& out,BigNum& b) //重载输出运算符
{
int i;
cout<<b.a[b.len-1];
for(i=b.len-2; i>=0; i--) {
printf("%04d",b.a[i]);
}
return out;
}
BigNum BigNum::operator+(const BigNum &T)const //两个大数之间的相加运算
{
BigNum t(*this);
int i,big;
big=T.len>len?T.len:len;
for(i=0; i<big; i++) {
t.a[i]+=T.a[i];
if(t.a[i]>MAXN) {
t.a[i+1]++;
t.a[i]-=MAXN+1;
}
}
if(t.a[big]!=0)
t.len=big+1;
else t.len=big;
return t;
}
BigNum BigNum::operator-(const BigNum &T)const //两个大数之间的相减运算
{
int i,j,big;
bool flag;
BigNum t1,t2;
if(*this>T) {
t1=*this;
t2=T;
flag=0;
} else {
t1=T;
t2=*this;
flag=1;
}
big=t1.len;
for(i=0; i<big; i++) {
if(t1.a[i]<t2.a[i]) {
j=i+1;
while(t1.a[j]==0)
j++;
t1.a[j--]--;
while(j>i)
t1.a[j--]+=MAXN;
t1.a[i]+=MAXN+1-t2.a[i];
} else t1.a[i]-=t2.a[i];
}
t1.len=big;
while(t1.a[t1.len-1]==0 && t1.len>1) {
t1.len--;
big--;
}
if(flag)
t1.a[big-1]=0-t1.a[big-1];
return t1;
}
BigNum BigNum::operator*(const BigNum &T)const //两个大数之间的相乘
{
BigNum ret;
int i,j,up;
int temp,temp1;
for(i=0; i<len; i++) {
up=0;
for(j=0; j<T.len; j++) {
temp=a[i]*T.a[j]+ret.a[i+j]+up;
if(temp>MAXN) {
temp1=temp-temp/(MAXN+1)*(MAXN+1);
up=temp/(MAXN+1);
ret.a[i+j]=temp1;
} else {
up=0;
ret.a[i+j]=temp;
}
}
if(up!=0)
ret.a[i+j]=up;
}
ret.len=i+j;
while(ret.a[ret.len-1]==0 && ret.len>1)ret.len--;
return ret;
}
BigNum BigNum::operator/(const int &b)const //大数对一个整数进行相除运算
{
BigNum ret;
int i,down=0;
for(i=len-1; i>=0; i--) {
ret.a[i]=(a[i]+down*(MAXN+1))/b;
down=a[i]+down*(MAXN+1)-ret.a[i]*b;
}
ret.len=len;
while(ret.a[ret.len-1]==0 && ret.len>1)
ret.len--;
return ret;
}
int BigNum::operator%(const int &b)const //大数对一个 int类型的变量进行取模
{
int i,d=0;
for(i=len-1; i>=0; i--)
d=((d*(MAXN+1))%b+a[i])%b;
return d;
}
BigNum BigNum::operator^(const int &n)const //大数的n次方运算
{
BigNum t,ret(1);
int i;
if(n<0)exit(-1);
if(n==0)return 1;
if(n==1)return *this;
int m=n;
while(m>1) {
t=*this;
for(i=1; (i<<1)<=m; i<<=1)
t=t*t;
m-=i;
ret=ret*t;
if(m==1)ret=ret*(*this);
}
return ret;
}
bool BigNum::operator>(const BigNum &T)const //大数和另一个大数的大小比较
{
int ln;
if(len>T.len)return true;
else if(len==T.len) {
ln=len-1;
while(a[ln]==T.a[ln]&&ln>=0)
ln--;
if(ln>=0 && a[ln]>T.a[ln])
return true;
else
return false;
} else
return false;
}
bool BigNum::operator>(const int &t)const //大数和一个int类型的变量的大小比较
{
BigNum b(t);
return *this>b;
}
void BigNum::print() //输出大数
{
int i;
printf("%d",a[len-1]);
for(i=len-2; i>=0; i--)
printf("%04d",a[i]);
// printf("
");
}
int main()
{
BigNum a;
int n;
cin>>n;
a="1";
int t;
for(t=1;t<=n;t++)
{
BigNum s=t;
a=a*s;
}
a.print();
return 0;
}8.如果有人认为吃东西只需要嘴巴，那就错了。
都知道舌头有这么一个特性，“由简入奢易，由奢如简难”（据好事者考究，此规律也适合许多其他情况）。具体而言，如果是甜食，当你吃的食物不如前面刚吃过的东西甜，就很不爽了。
大宝是一个聪明的美食家，当然深谙此道。一次他来到某小吃一条街，准备从街的一头吃到另一头。为了吃得爽，他大费周章，得到了各种食物的“美味度”。他拒绝不爽的经历，不走回头路而且还要爽歪歪（爽的次数尽量多）。
输入格式
两行数据。
第一行为一个整数n，表示小吃街上小吃的数量
第二行为n个整数，分别表示n种食物的“美味度”
输出格式
一个整数，表示吃得爽的次数
样例输入
10
3 18 7 14 10 12 23 41 16 24
样例输出
6
数据规模和约定
美味度为0到100的整数
n<1000
最长上升子序列的稍微不同，不必严格大于，可以等于
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<cmath>
typedef long long ll;
using namespace std;
int a[1005],dp[1005];
int n,ans=-999;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(a[j]<=a[i])
dp[i]=max(dp[i],dp[j]+1);
for(int i=1;i<=n;i++)
ans=max(ans,dp[i]);
printf("%d
",ans);
return 0;
}