首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >快乐AC三道题---第一周

快乐AC三道题---第一周

作者头像
杨鹏伟
发布2020-09-11 14:59:02
3140
发布2020-09-11 14:59:02
举报
文章被收录于专栏:ypwypw

A - Max Sum

思路:DP(动态规划)

如果不考虑数据,直接暴力去做。

双层循环,O(n*n)复杂度,超时必然。

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 加入到当前的子段。最后我们只需要找出所有最大子段中,最大的那个。

#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了。

#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);

#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 CRASH\n");
		continue;
		}
		 if(a<=168)
            printf("CRASH %d\n",a);
        else if(b<=168)
            printf("CRASH %d\n",b);
        else if(c<=168)
            printf("CRASH %d\n",c);
	
	}
	return 0;

D - 二等队形

思路:DP , 求得最长调递减序列~~,然后拿总数n减去这个序列长度就行了!

#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”。

#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 - 最大公约数

水~

#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

思路:大数问题,字符串处理

#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]%10;
                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

自己推理一下,详细

水过~

#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("%d\n",(s-1)%9+1);
    }
    return 0;
}

I - N!

思路:大数乘法

#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%10;
                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 - 母牛的故事

思路:找规律

#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("%d\n",c(n));
    return 0;
}

K - 多项式求和

思路:判断最后一个是偶还是奇数

#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("%.2lf\n", sum);
    }
    return 0;
}

L - 小明A+B

水题:卡半天,int过不去,改成unsigned就过了,玄学,不懂~

#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)%100;
   printf("%d\n",add);
  }
return 0;
}

M - 奇偶位互换

水题

#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 - 统计硬币

水题

#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 - 我是菜鸟,我怕谁

水题

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	int sum;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		sum = (n*n)%10000;
		cout<<sum<<endl;
	}
}

P - Family planning

#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

#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("0\n");
                continue;
            }
            if(a == n - 1 && x == n) {      //当n>1,且每个人看到的女生数都是n-1,说明全都是女生,即女生数为 n
                printf("%d\n", 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^^^%d\n",da,xiao,fm);
        if(da-xiao ==1 && x + y == n  && fm==da) {
            printf("%d\n",da);
        } else puts("Impossible!");
    }
    return 0;
}

R - 不可摸数

打个表~

#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("yes\n"); 
               else 
				   printf("no\n");  
            
       }  
          
      return 0;  
  }

S - 七夕节

水题,小心超时

#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("%d\n",s);
    }
}

T - 蟠桃记

水题,找规律

#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 - 月之数

#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 - 龟兔赛跑

#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

#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;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-12-02 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档