A - Max Sum
思路：DP(动态规划)
如果不考虑数据，直接暴力去做。
双层循环，O（n*n)复杂度，超时必然。
代码语言：javascript复制for(int i = 1; i <= n; i ){
int sum = 0;
for(int j = i; j <= n; j ) {
sum = a[j];
ans = max(ans,sum);
}我们要解决的无非是是否把下一个元素加入，是否开始维护一个新的子段。我们开一个数组b[] , 记录bi，表示以ai结尾的全部子段中 最大的那个的 和。 这样我们就可以根据它bi 的正负，去考虑是否把下一个元素加入到当前的子段。 如果bi 是负数，那么我们为什不从ai 1新维护一个子段呢？ 如果bi 是正数，那么显然可以继续把ai 1 加入到当前的子段。最后我们只需要找出所有最大子段中，最大的那个。
代码语言：javascript复制#include<bits/stdc .h>
#define maxn 100014
int a[maxn];
int b[maxn];
using namespace std;
int main(){
int t;
int k=1;
cin>>t;
while(t--){
int sum=0;
int n,begin,end;
int max0=-1001;//最小的数
cin>>n;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=1;i<=n;i ){
cin>>a[i];
b[i]=max(b[i-1] a[i],a[i]);//递归方程
if(max0<b[i])//找到最大的子段的结束位置。
{
max0=b[i];
end=i;
}
}
for(int i=end;i>=1;i--){//最大值以及开始位置
sum =a[i];
if(sum==max0) begin=i;
}
cout<<"Case "<<k <<":"<<endl;//格式控制
cout<<max0<<" "<<begin<<" "<<end<<endl;
if(t)
cout<<endl;
}
return 0;
}B - Elevator
上一层楼6秒，下一层四秒，到一层停留5秒。
读懂题就能AC了。
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int main(){
int n,m,sum,k;
while(~scanf("%d",&n)&&n){//一共按了n层楼
cin>>m;//当前所在楼层
sum = n*5 m*6;//一共要去几层楼和到第一个要到的楼的时间
for(int i=1;i<n;i ){//从第二个数开始判断下一个要到的楼层是上还是下。
cin>>k;
sum = (m-k)>0 ? (m-k)*4:(k-m)*6;
m = k;//更新当前楼层
}
cout<<sum<<endl;
}
return 0;
} C - Keep on Truckin’
My IQ was crushed by the examiners（J S）；
代码语言：javascript复制#include<stdio.h>
int main(){
int a,b,c;
while(~scanf("%d%d%d",&a,&b,&c)){
if(a>168&&b>168&&c>168){
printf("NO CRASHn");
continue;
}
if(a<=168)
printf("CRASH %dn",a);
else if(b<=168)
printf("CRASH %dn",b);
else if(c<=168)
printf("CRASH %dn",c);
}
return 0;D - 二等队形
思路：DP , 求得最长调递减序列~~，然后拿总数n减去这个序列长度就行了！
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int maxn=1005;
int a[maxn];
int dp[maxn];
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=0;i<n;i )
cin>>a[i];
memset(dp,0,sizeof(dp));
dp[0]=1;
int Max = 1;
for(int i=1;i<n;i )
{
int flag=0;
int ans;
for(int j=0;j<i;j ){
if(a[j]>a[i]){
if(flag < dp[j])
flag = dp[j];
}
}
dp[i] = flag 1;
Max = max(dp[i],Max);
}
cout<<n-Max<<endl;
}
return 0;
}E - 产生冠军
思路：如果有一个人一次都没被打败过，则有“YSE”。
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int n,ans;
string str1,str2;
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
ans = 0;
map<string,int> name;
for(int i =0;i<n;i )
{
cin>>str1>>str2;
if(name[str1]==0)
name[str1]=1;
name[str2] = 2;
}
map<string ,int>::iterator it;
for(it=name.begin();it!=name.end();it )
{
if(it->second==1)
ans ;
}
if(ans!=1)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
}F - 最大公约数
水~
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int gcd(int a,int b){
return b ? gcd(b,a%b): a ;
}
int main(){
int a,b;
while(~scanf("%d%d",&a,&b))
{
cout<<gcd(a,b)<<endl;
}
return 0;
}G - A B Problem II
思路：大数问题，字符串处理
代码语言：javascript复制#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
for(int h=1; h<=n; h )
{
char a[10000],b[10000];
int c[10000],d[10000];
int e[10000];
int k,l;
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
scanf(" %s %s",a,b);
k=strlen(a);
l=strlen(b);
for(int i=0; i<k; i )
c[i]=a[k-i-1]-'0';//倒叙输入~
for(int i=0; i<l; i )
d[i]=b[l-i-1]-'0';//倒叙输入~~
int op=0;
for(int i=0; i<1000; i )//然后逆序将数字相加
{
e[i]=(c[i]) (d[i]) op;
if(e[i]>=10)
{
e[i]=e[i];
op=1;
}
else op=0;
}
printf("Case %d:n",h);//格式控制
printf("%s %s = ",a,b);
int i;
for( i=999; i>=0; i--)//因为是倒叙的，所以当不遇到0的时候，就确定了数的位置。
if(e[i]!=0)break;
for(int j=i; j>=0; j--)//输出数字
printf("%d",e[j]);
printf("n");
if(h!=n)//注意格式，多一个空格！
printf("n");
memset(a,0,sizeof(a));//重新给数组归零~~
memset(b,0,sizeof(b));
}
return 0;
}H - Digital Roots
自己推理一下，详细
水过~
代码语言：javascript复制#include<stdio.h>
int main(){
int s;
char c;
while(1){
s=0;
while(scanf("%c",&c)&&c!='n')
s =c-'0';
if(!s) return 0;
else printf("%dn",(s-1)%9 1);
}
return 0;
}I - N!
思路：大数乘法
代码语言：javascript复制#include<stdio.h>
#include<string.h>
const int maxn = 50000;
int f[maxn];
int main()
{
int i,j,n;
while(~scanf("%d",&n))
{
memset(f,0,sizeof(f));
f[0]=1; //小于2的阶乘都为1
for(i=2;i<=n;i )
{
int c=0; //进位
for(j=0;j<maxn;j )
{
int s=f[j]*i c;
f[j]=s;
c=s/10;
}
}
for(i=maxn-1;i>=0;i--) if(f[i]) break;
for(j=i;j>=0;j--) printf("%d",f[j]);
printf("n");
}
return 0;
}J - 母牛的故事
思路：找规律
代码语言：javascript复制#include <stdio.h>
int c(int n)
{
if(n<=4) return n;
else return c(n-1) c(n-3);
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
printf("%dn",c(n));
return 0;
}K - 多项式求和
思路：判断最后一个是偶还是奇数
代码语言：javascript复制#include <stdio.h>
int main(){
double sum;
int z, n, i;
scanf("%d", &z);
while ( z-- ){
scanf("%d", &n);
sum = 0;
if ( n&1 ){
sum = 1;
for ( i=2; i<n; i =2 ){
sum = -1.0/i 1.0/(i 1);
}
}
else {
for ( i=1; i<n; i =2 ){
sum = 1.0/i-1.0/(i 1);
}
}
printf("%.2lfn", sum);
}
return 0;
}L - 小明A B
水题：卡半天，int过不去，改成unsigned就过了，玄学，不懂~
代码语言：javascript复制#include<stdio.h>
int main()
{
unsigned add,a,b;
int t;
scanf("%d",&t);
while(t--){
add=0;
scanf("%d %d",&a,&b);
add=(a b)0;
printf("%dn",add);
}
return 0;
}M - 奇偶位互换
水题
代码语言：javascript复制#include<bits/stdc .h>
#define maxn 55
char a[maxn];
using namespace std;
int main(){
int t;
int s;
cin>>t;
while(t--){
cin>>a;
for(int i=0;i<strlen(a);i =2)
{
s = a[i];
a[i]=a[i 1];
a[i 1]=s;
}
cout<<a<<endl;
}
}N - 统计硬币
水题
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m;
int flag=0;
cin>>n>>m;
for(int i=0;i<=n;i )
for(int j=0;j<=n;j )
for(int k=0;k<=n;k )
if(i j k==n&&i 2*j 5*k==m) flag ;
cout<<flag<<endl;
}
return 0;
}O - 我是菜鸟，我怕谁
水题
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int main(){
int t;
int sum;
cin>>t;
while(t--){
int n;
cin>>n;
sum = (n*n)000;
cout<<sum<<endl;
}
}P - Family planning
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int main ()
{
long long int t,n,m,i,j,k,l;
cin>>t;
while(t--&&cin>>m>>n)
{
for(i=l=0,j=10000;i<n;i )
{
cin>>k;
if(i<m&&k==1)
m=0;
else if(i>=m){
l =j;
j*=2;
}
}
cout<<l<<" RMB"<<endl;
}
return 0;
}Q - Boys and girls
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int t,n,a,b,x,y,tmp;
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
bool flag=1;
a=b=-1; //表示男女生看到的女生人数
x=y=0; //累加器，表示男女生人数
for(int i=0; i<n; i ) {
scanf("%d",&tmp);
if(x==0 || tmp==a) {
a=tmp;
x ;
} else if(y==0 && tmp!=a) {
b=tmp;
y ;
} else if(tmp==b)
y ;
else if(x && y && tmp!=a && tmp!=b) {
printf("Impossible!n"); //出现第三种说法，表示有人说谎
flag=0;
break;
}
}
if(!flag)
continue;
if(a != -1 && b == -1) {
if(a == 0 && n == 1) { //只有一个人无法判断
printf("Impossible!n");
continue;
}
if(a == 0 && n > 1 && x == n) { //当n>1 ,并且 所有人都没看到女生，说明全是男生，则女生人数是0
printf("0n");
continue;
}
if(a == n - 1 && x == n) { //当n>1,且每个人看到的女生数都是n-1，说明全都是女生，即女生数为 n
printf("%dn", n);
continue;
}
printf("Impossible!n");
continue;
}
int da,xiao,fm;
if(a>b) {
da=a;
xiao=b;
fm=y;
} else {
da=b;
xiao=a;
fm=x;
}
//printf("%d %d^^^%dn",da,xiao,fm);
if(da-xiao ==1 && x y == n && fm==da) {
printf("%dn",da);
} else puts("Impossible!");
}
return 0;
}R - 不可摸数
打个表~
代码语言：javascript复制#include <stdio.h>
int main()
{
int n,i,m;
int a[1001]={0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1};
scanf("%d",&m);
for(i=0;i<m;i )
{
scanf("%d",&n);
if(a[n]==0)
printf("yesn");
else
printf("non");
}
return 0;
}S - 七夕节
水题，小心超时
代码语言：javascript复制#include<stdio.h>
int main(){
int t,n,i,s;
scanf("%d",&t);
while(t--){
s=1;
scanf("%d",&n);
for(i=2;i*i<=n;i ){
if(n%i==0){
if(i*i==n) s =i;
else s =i n/i;
}
}
printf("%dn",s);
}
}T - 蟠桃记
水题，找规律
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int a(int n){
int j=1;
if(n==1) return 1;
else
return 2*(a(n-1) 1);
}
int main(){
int n;
int sum;
while(~scanf("%d",&n)){
cout<<a(n)<<endl;
}
return 0;
}U - 月之数
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int a(int n){
if(n==1) return 1;
if(n==2) return 3;
else
return (a(n-1)-a(n-2))*4;
}
int main(){
int t;
cin>>t;
int n;
while(t--){
cin>>n;
cout<<a(n)<<endl;
}
return 0;
} W - 龟兔赛跑
代码语言：javascript复制#include<bits/stdc .h>
const int MAX=150;
const double INF=0xfffff;//0x代表十六进制
double DP[MAX];//DP[i]表示到第i个加电站的最小耗费时间
int s[MAX];//s[i]表示到第i个加电站距离起点的距离
using namespace std;
double Min(double x,double y)//判断大小
{
return x>y?y:x;
}
int main()
{
double L;
int n,i,j;
double electricity_l,electricity_t;
double vt_rabbit,vt_ele,vt_none;
double len,sum,Time;
while(cin>>L)//输入跑道长度
{
cin>>n>>electricity_l>>electricity_t;//输入加电站的个数、电动车最大行驶距离、电动车的充电时间
cin>>vt_rabbit>>vt_ele>>vt_none;//输入兔子、电动车、乌龟用脚踏的各个速度
for(i=1;i<=n;i )//输入各个加电站距离起点的位置
cin>>s[i];
s[n 1]=L;//把第n 1个加电站设为终点，长度为L
s[0]=0;//把第0个加电站设为起点，长度为0
DP[0]=0;//起点到起点最小耗费时间为0
for(i=1;i<=n 1;i )
{
DP[i]=INF;//因为到第i个加电站最小耗费时间未知所以赋值无穷大
for(j=0;j<i;j )
{
len=s[i]-s[j];//从第j个加电站到第i个加电站的距离
if(len>electricity_l)//如果该距离大于电动车能行驶的最大距离
Time=electricity_l/vt_ele (len-electricity_l)/vt_none;//把电动车行驶的时间加上乌龟用脚踏的时间
else//如果小于
Time=len/vt_ele;//直接加上这段距离除于电动车的速度所得的时间
Time =DP[j];//之后加上到第j个加电站的最优时间
if(j>0)//这里判断j>0是因为如果j==0的话,即表明从起点出发，因为起点已经充满电了所以不需要加上电动车的充电时间
{
Time =electricity_t;//如果j>0加上电动车的充电时间
}
DP[i]=Min(DP[i],Time);//每次挑出到第i个加电站的最优时间
}
}
if(DP[n 1]<(L/vt_rabbit))//如果乌龟从起点到终点最小时间小于兔子的跑到终点的时间
cout<<"What a pity rabbit!"<<endl;
else
cout<<"Good job,rabbit!"<<endl;
}
return 0;
}X - Ignatius and the Princess III
代码语言：javascript复制#include<iostream>
using namespace std;
int main()
{
int n,a[121]={0};
a[0]=1;
for(int i=1;i<=120;i )
for(int j=0;j<121;j )
if(a[j]!=0&&i j<121)
a[i j] =a[j];
while(scanf("%d",&n)!=EOF)
cout<<a[n]<<endl;
return 0;
}
