前言
今天一大早就欣欣然睁开了眼，而且还是被呼噜声给吵醒的，唉，是我上面的五年级的蒟蒻（巨佬）······
今天做了四道题
比赛时才拿了10分，唉，其他题都是WA的WA，TLE的TLE，但之后又改了，爽，瞬间拿了160分
第一题
题目大意
对一个给定的自然数M，求出所有的连续的自然数段，这些连续的自然数段中的全部数之和为M
输入样例
10000
输出样例
18 142
297 328
388 412
1998 2002
解题思路
这道题一开始是用暴力来做的，后来发现时间超限，就把它优化了一下，交上去就AC了
程序如下
第一次做的60分代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define r register
using namespace std;
int m,a[1000000],b[1000000],t;
int main()
{
freopen("combo.in","r",stdin);
freopen("combo.out","w",stdout);
scanf("%d",&m);
for(r int i=1;i<=m/2;i++)
{
a[i]=a[i-1]+i;//前缀和
if(a[i]>=m)//判断是否大于，如果大于就不用了
{
t=1;
for(r int j=t;j<=i;j++)
{
if(a[i]-a[j]==m)//如果减去是等于M的，就证明是大于的
{
b[j+1]=i;
t=j+1;
break;
}
else if(a[i]-a[j]<m)
{
t=j;
break;
}
}
}
}
for(r int i=1;i<=m-1;i++)
{
if(b[i]!=0)
printf("%d %d\n",i,b[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}
第二次AC的代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int m,a[100000],b[1000000];
int main()
{
freopen("combo.in","r",stdin);
freopen("combo.out","w",stdout);
scanf("%d",&m);
for(int i=1;i<=m-1;i++)
{
int t=0;
for(int j=i;j<=m;j++)
{
t=t+j;
if(t==m)
{
printf("%d %d\n",i,j);
}
else
{
if(t>m)
{
break;
}
}
}
}
/* for(int i=1;i<=m-1;i++)
{
for(int j=i;j<=m;j++)
printf("%d %d\n",a[i],b[j]);
}*/
fclose(stdin);
fclose(stdout);
return 0;
}
第二题
题目大意
若给出1~n的一个排列A，则将A1、A2相加，A2、A3相加……An-1、An相加，则得到一组n-1个元素的数列B；再将B1、B2相加，B2、B3相加，Bn-2、Bn-1相加，则得到一组n-2个元素的数列……如此往复…输入一行两个整数n，t即最后求出来的数。两个0表示输入结束。
输出n个整数
输入样例
4 16
3 9
0 0
输出样例
3 1 2 4
1 3 2
解题思路
这道题是有关于杨辉三角的关系连接起来，再不断的推出公式即可
第三题
题目大意
给你一个数N,每张票有2N位,同时给你这2N位上的和S,如果这张票的前N位的和等于后N位的和,那我们称这张票是吉祥的,每一位可以取0-9
你的任务是计算吉祥票的总数
输入样例
2 2
输出样例
4
解题思路
这道题其实是用DP来做的
第四题
题目大意
现有n本书，编号1,2,…,n。每本Pi页。全部分给m个抄写员。每人分到顺序连续的若干本，每本只分给一人。求一种方案，使每人分到的页数和的最大值为最小。输出这个值
输入样例
9 3
100 200 300 400 500 600 700 800 900
输出样例
1700
解题思路
这道题我是用DP来做的，但是只对了60分，最后两个点TLE了，讲题时，巨佬说要用二分来做···我只打了DP
程序如下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define r register
using namespace std;
long long n,m,f[5000][5000],t,a[5000];
int main()
{
freopen("book.in","r",stdin);
freopen("book.out","w",stdout);
memset(f,127/3,sizeof(f));
scanf("%lld%lld",&n,&m);
for(r int i=1;i<=n;i++)
{
scanf("%lld",&t);
a[i]=t+a[i-1];//前缀和
f[i][1]=a[i];
}
for(r int i=2;i<=m;i++)
{
for(r int j=1;j<=n-m+i;j++)
{
for(r int k=1;k<j;k++)
{
f[j][i]=min(max(f[k][i-1],a[j]-a[k]),f[j][i]);
}
}
}
printf("%lld",f[n][m]);
fclose(stdin);
fclose(stdout);
return 0;
}