跳至正文

明明的随机数 解题报告

  • OI路程

这题不难,不过我看到大部分的人都是使用的先用快排再去重,有些人是先去重再用快排,我这里就用的是哈希排序,能够以线性时间(O(n))对所有数据实现排序和去重。
没什么好解释的,1~1000,把对应的数字放到相应的数组中就可以了。

#include <stdio.h>
char bucket[1001];

int main(void)
{
 int i, t;
 int n, ans = 0;
 scanf(%d, &n);
 for(i = 0; i < n; i++){
 scanf(%[......]

继续阅读

NOIP_2002.PJ1:级数求和 解题报告

  • OI路程

这题网上没找到较好的算法(数学方法),只好自己写暴力版本的了。。。这题真的不好做什么报告,提交就是。

#include <stdio.h>

int main(void)
{
 double n;
 int i;
 double ans = 0;
 scanf(%lf, &n);
 for(i = 1; ans <= n; i++){
 ans += (double)1.0 / i;
 }
 printf(%d\\n, i - 1);
 return 0;
}

[……]

继续阅读

NOIP_2001.PJ2:最大公约数与最小公倍数问题 解题报告

  • OI路程

看到这个题目,不知道怎么做,到网上搜了下最小公倍数和最大公约数之间的公式,就找到了思路,p q = x0 y0..那么我就枚举所有的p,然后求出q,再判断之间的最大公约数是不是x0,就Ok了。

#include <stdio.h>

int gcd(int x, int y)
{
 int t;
 while(y > 0){
 t = x % y;
 x = y;
 y = t;
 }
 return x;
}

int main(void)
{
 int i, ans = 0; //忘记初始[......]

继续阅读

NOIP_2001.PJ4:装箱问题 解题报告

  • OI路程

什么都不说了,简单的DP,直接上代码。
唯一注意的一点,我不是用的剩余做DP值,而是和普通的DP一样,最后再用总质量剪掉这个DP值。

C语言:

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))

int f[20001];

int main(void)
{
 int i, j, t;
 int v, m;
 scanf(%d%d, &v, &m);
 for(i = 0; i < m; i++){
 scanf(%[......]

继续阅读

NOIP_2001.PJ3:求先序排列 解题报告

  • OI路程

在车上想了好久,终于找到了突破口,后序遍历不就是说最后一个节点就是当前书的根节点吗?那不就好说了,先把后序中的最后一个节点在中序中找到下标i,那小于i的便是左子树了,大于的的便是右子树了,而题目要的是先序,那就先把第i个(即后序的最后一个)输出来,然后再分别对左子树和右子树进行递归,然后后序从0~i-1都是左子树,后序i~len – i – 1(len是树的长度)是右子树。
现在解释一下,0~i-1是后序的长度的原因是无论是先序还是后序还是中序都是同一棵树,长度必然相同,现在把一棵树分成了两棵树,长度一定还是相同的[……]

继续阅读

NOIP_2001.PJ1:数的计数 解题报告

  • OI路程

刚看到题目被吓到了,下面有一个Hit(提示),说用高精度,高精度我以前写过一次,几乎忘干净了……后来琢磨了好久,发现能够使用动态规划,注意观察一下样例,输入是6,共有:
6
16
26
126
36
136
设f[i]是以自然数i在最左边的个数,那么很容易发现方程f[i] = f[1] + f[2] + f[3] + …. + f[i/2] + 1;于是就产生了下面的代码:

C语言:


#include <stdio.h>
unsigned f[1001];

int main(void)
{[......]

继续阅读

NOIP 2000 普及组4 单词接龙 解题报告

  • OI路程

哈,这题拿到手时刚开始不知道怎么开始,后来找到了突破点,用f[i][j]记录第i个字符串和第j个字符串重复的字符数,就是说把第i个字符串和第j个字符串之间接起来重合的字符数目。
把这个处理好了就好下手了,不过这里我忽略了两点,导致提交了几次NOIP。第一点f[i][j]中的i,j可以重复!也就是说自己可以接在自己后面,再一个就是记录f[i][j]的时候要注意,从字符串的后面开始搜索,这两点弄了我半个小时到一个小时的时间,具体代码如下。

C语言:

#include <stdio.h>
#include <[......]

继续阅读

乘积最大 解题报告

  • OI路程

拿到题目就想到是一个深搜的题目(可能有其他更快的算法,比如什么用数学解的啊,那种。),便开始下手,对所有的情况进行枚举,算出乘值,与ans变量进行比较,比ans大就覆盖ans,否则继续枚举下一种情况,直至全部枚举完。结果忘记考虑会分成0的情况,导致被除数为0!(所以还是提交了两次,乘积最大

等下我还到网上搜搜看有没有什么高效率的算法,我的代码如下:

C语言:

#include <stdio.h>
int n, k;
char str[41];
int tmp = 1, ans = 0;

void srch[......]

继续阅读

计算器的改良 解题报告

  • OI路程

这个题目确实简单(我还是犯了一些比较低级的错误,提交了几次才AC),本来是想用一个链表来保存的,后来发现不需要专门去实现,因为毕竟题目里只有两种情况,即未知数的幂为0或1,用一个数组就可以了,int a[2][2]; 其中a[0]是保存左边的式子,a[1]保存右边的式子,a[x][0] 用来保存式子中的常数之和,a[x][1]保存未知数的系数之和。
比如:5a+1-3+5=-2a-3+4+a,那么a[0][0] = 1 – 3 + 5,(左边式子常数和)a[0][1] = 5,a[1][0] = -3 + 4,a[[……]

继续阅读

税收与补贴问题

  • OI路程

我一直以为普及组的题目都非常简单,几天看到这题我错了。读了两天题目,硬是不知道题目讲的是什么,悲哀。。
到网上找到一份不错的结题报告,想自己写,估计没那个水平。直接转上来吧,至于代码,等下我会把C的代码写上(自己写)。

我先来说说题目的意思。就从样例开始分析。
输入是:
31
28 130
30 120
31 110
-1 -1
15

意思就是政府预期价是31元。成本28元,按成本销售的时候可以买130件产品。
每个卖30元的时候可以卖120个,
每个卖31元(输入的最高价位)的时候可以卖110个,
每个卖32元的[……]

继续阅读