《2013腾讯编程马拉松初赛(3月21)》我的解答(C语言)

 

21日是初赛的第一天,我自己报的是24号,看了郭子分享的题目。昨晚和今天花了些时间做了下。算是温故之前的算法知识吧。

[xiami id=”2105807″]森林狂想曲 — 群星[/xiami]

我的代码是用C语言写的。

一共
5题,第1235题都没问题,第四题本以为是背包问题,结果代码跑下来发现题目是有些不一样的。

题目连接,猛击下载。

 

为了方便我以后自己阅读,我把题目放下面

第一题:

QQprogramTest1

 

代码:

#include <stdio.h>void readdata();int countTime(int);void printResult();int C,N;int people[100][15];int time;int max;

 

int main(){

 

readdata();  //read data

for (int i=0;i<C;i++)

{

time=0;

max=0;

countTime(i); //count time cost

printResult();

}

 

return 0;

}

 

void readdata(){

scanf(“%d”,&C);

for (int m=0;m<C;m++)

{

scanf(“%d”,&people[m][0]); //how many people

N=people[m][0];

for(int i=1;i<=N;i++)

scanf(“%d”,&people[m][i]);   //which floor

}

}

 

int countTime(int m){

int member=0;

for (int j=1;j<100;j++)

{

int open=0;

N=people[m][0];

for (int k=1;k<=N;k++)

{

if (people[m][k]==j)

{

open=1; // open door

if (j>max) max=j; // the high level

time++; // 1s per people

member++;

//printf(“%s  %d  %d \n”,”第几个人:”,k,member);

}

else{}

}

if (open!=0) time+=5; // 5 s open door

 

if (member==N) // if  i is the high level

{

time=time+max*10;

return time;

}

}

 

}

 

void printResult(){

//printf(“the time cost is: “);

printf(“%d \n”,time);

}

 

 

第二题

 

QQprogramTest2

代码:

#include <stdio.h>int n[100],t[100],k[100],T;int a[100][10000];int M=100000007;void init();void PerChange(int);void printResult(int);

 

int main(){

init(); //init

for (int i=0;i<T;i++)

{

for (int j=0;j<t[i];j++) //调用t[i]次运算

{

PerChange(i);

}

printResult(i);

}

return 0;

}

 

void init()

{

scanf(“%d”,&T);

for (int m=0;m<T;m++)

{

scanf(“%d %d %d”,&n[m],&t[m],&k[m]);

for (int i=0;i<n[m];i++)

{

scanf(“%d”,&a[m][i]);

}

}

}

 

void PerChange(int m) //每改变一次的效果

{

int tem[10000];

for (int i=1;i<n[m];i++) //tem数组为更改后的数组

{

tem[i]=a[m][i-1]*k[m];

tem[i]=tem[i]%M;

}

tem[0]=a[m][(n[m]-1)]*k[m];

for (i=0;i<n[m];i++) //tem数组重新赋值给原a数组

{

a[m][i]=tem[i];

}

 

}

 

void printResult(int m){

for (int i=0;i<n[m];i++)

{

printf(“%d “,a[m][i]);

}

printf(“\n”);

}

 

 

第三题

QQprogramTest3

代码:

#include <stdio.h>int T,L[50],R[50],MyResult[50];void init();void count(int);void printResult(int);int check(int); 

int main()

{

init();

for (int i=0;i<T;i++)

{

count(i);

printResult(i);

}

return 0;

}

 

void init()

{

scanf(“%d”,&T);

for (int m=0;m<T;m++)

scanf(“%d %d”,&L[m],&R[m]);

}

 

void count(int m)

{

MyResult[m]=0;

for (int i=L[m];i<=R[m];i++)

{

if(check(i)!=0)

MyResult[m]=MyResult[m]+(i*i);

}

}

 

int check(int m)

{

int sum=0;

if(m%7==0) //如果能被7整除

{

return 0;

}else

if (m>10)

{

while(m/10)

{

if (m%10==7) //如果有一位数字为7

{

return 0;

}

sum+=m%10;

m=m/10;

}

if (sum%7==0) //如果各个位和能被7整除

{

return 0;

}else{

return 1;

}

}

else //如果都不满足,则返回为真

{

return 1;

}

 

 

}

 

void printResult(int m)

{

//printf(“answer:  “);

printf(“%d \n”,MyResult[m]);

}

 

 

第五题:

QQprogramTest5

代码:

#include <stdio.h>#include <stdlib.h>int T[100000],number=0,time[100];int hour[100][100000],minute[100][100000];//100个测试用例,,100000件事int m_hour[100][100000],m_minute[100][100000];void readdata();

void countTime(int);

void printResult(int);

 

int main(){

readdata();

for (int m=0;m<number;m++)

{

countTime(m);

printResult(m);

}

return 0;

}

 

void readdata(){

printf(“若想结束程序则输入数字0,表示没有事情\n”);

 

scanf(“%d”,&T[number]);

while(T[number]>0) //能读到事件数目

{

 

for (int m=0;m<T[number];m++) //读取事件时间

{

scanf(“%d:%d %d:%d”,&hour[number][m],&minute[number][m],&m_hour[number][m],&m_minute[number][m]);

}

number++;

scanf(“%d”,&T[number]);

}

system(“cls”);

}

 

void countTime(int m){

int startHour=hour[m][0],startMinute=minute[m][0],endHour=m_hour[m][0],endMinute=m_minute[m][0];

for (int index=0;index<T[m];index++)

{

if (startHour>hour[m][index]) //获取开始时间

{

if (startHour!=hour[m][index])

{

startMinute=minute[m][index];

}else

{

if(startMinute>minute[m][index])

startMinute=minute[m][index];

}

startHour=hour[m][index];

}

if (endHour<m_hour[m][index]) //获取结束时间

{

 

if (endHour!=m_hour[m][index])

{

endMinute=m_minute[m][index];

}else

{

if (endMinute<m_minute[m][index])

endMinute=m_minute[m][index];

}

endHour=m_hour[m][index];

}

 

}

// printf(“–start:%d:%d–\n”,startHour,startMinute);

// printf(“–endtime:%d:%d–\n”,endHour,endMinute);

time[m]=(endHour-startHour)*60+endMinute-startMinute;

time[m]=24*60-time[m];

}

 

void printResult(int m){

printf(“%d \n”,time[m]);

}

 

第四题

QQprogramTest4

之所以第四题放最后,是因为这题太恶心了。本来把题目看了一遍,以为是背包问题,只要遍历所有组合,就可以求出最佳组合。

 

背包代码:

 

#include <stdio.h>int n[100],a[100][100],b[100][100],m[100],T;int tem[100],max;void init();void search(int,int);void checkEnergy(int);

void printResult();

 

int main()

{

init();

for (int i=0;i<T;i++)

{

max=0,tem[100]=0;

search(i,0);

printResult();

}

return 0;

}

 

 

void init()

{

int i,j;

T=2;

for (i=0;i<T;i++)

{

scanf(“%d”,&n[i]);

for (j=0;j<n[i];j++)

{

scanf(“%d %d”,&a[i][j],&b[i][j]);

}

scanf(“%d”,&m[i]);

}

 

}

void search(int i,int j)

{

 

if (j>=n[i])

{

checkEnergy(i);

}

else

{

tem[j]=0;

search(i,j+1);

tem[j]=1;

search(i,j+1);

}

}

 

void checkEnergy(int i){

int j,xingfugan=0,kaluli=0;

for (j=0;j<n[i];j++)

{

if (tem[j]==1)

{

xingfugan+=a[i][j];

kaluli+=b[i][j];

}

}

if (kaluli<=m[i])

{

if (xingfugan>max)

max=xingfugan;

}

 

}

 

void printResult(){

 

printf(“%d \n”,max);

}

唉,后来发现,它题目说的是“种”不是“个”,就是一种食品可以多选,坑爹啊~~~。后来想了好久,代码试了好几个,都在复杂度上没把握好,主要是没有一个清晰的思路。若有算法大神看到了,可以指点下。此刻自己是不想再想这东西了。

 

工程项目代码下载

 

 

 

留下评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据