Climber.pI的OI之路

Through the darkest dark，may we see the light.

#

NOIP 2004 合唱队型

双向最长上升子序列，枚举k(0<=k<=n)，f[i] = max{f[j]}+1;
在tyvj提交一直RTE，原因未知.
 1#include<stdio.h>
 2#include<iostream>
 3using namespace std;
 4
 5int main()
 6{
 7    FILE *fin, *fout;
 8    fin = fopen("chorus.in", "r");
 9    fout = fopen("chorus.out", "w");
10    int i, j, k, n, T[120] = {0}, f[120] = {0}, ans = 0, final = 0;
11    fscanf(fin, "%d", &n);
12    for (i = 1; i <= n; i++) fscanf(fin, "%d", &T[i]);
13    for (k = 1; k <= n; k++)
14    {
15        for (i = 1; i <= n; i++) f[i] = 1;
16        for (i = 1; i <= k; i++)
17            for (j = 1; j < i; j++)
18                if (T[j] < T[i] && f[j]+1 > f[i]) f[i] = f[j]+1;
19        ans = f[k]-1;
20        for (i = 1; i <= n; i++) f[i] = 1;
21        for (i = n; i >= k; i--)
22            for (j = n; j > i; j--)
23                if (T[j] < T[i] && f[j]+1 > f[i]) f[i] = f[j]+1;
24        ans += f[k];
25        if (ans > final) final = ans;
26    }
27    fprintf(fout, "%d\n", n-final);
28}
29

posted @ 2010-09-20 21:35 Climber.pI 阅读(358) | 评论 (0) | 编辑 收藏

NOIP 2001 一元三次方程求解

可以利用二分法或者枚举法求解，需要注意的是浮点误差，以及系数不一定为整数.
 1#include<stdio.h>
 2double a, b, c, d;
 3double abs (double n) {return (n > 0) ? n : - n;}
 4double f(double x) {return (((a*x)+b)*x+c)*x+d;}
 5int main()
 6{
 7    int k = 0;
 8    scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
 9    for (double i = -10000; i < 10001; i++)
10    {
11        if (abs(f(i/100)) < 1e-8)
12        {
13            k++; printf("%.2lf", double(i/100));
14            if (k < 3) printf(" ");
15                else printf("\n");
16            i += 10;
17        }
18    }
19}
20

posted @ 2010-09-11 22:18 Climber.pI 阅读(430) | 评论 (0) | 编辑 收藏

NOIP 2001 最大公约数和最小公倍数问题

很有趣的一个数学问题，这一周看完《背包九讲》后，就开始看CCF出的NOIP2001-2003的题解.之前认为很水的题目的最优算法相当精妙，这进一步认证了仅仅AC是不够的，还需要进一步研究算法.

题意略.需要注意的是，题目仅仅需要求出符合条件的数对的个数，而非答案.
因而，我们可以利用一些数学分析得到一个非常简洁的结论：
以x0,y0分别为最大公约数和最大公倍数的数对个数为2^n，n是y0/x0的不同质因子个数.

 

 1#include<stdio.h>
 2int main()
 3{
 4  int x0, y0, x, i = 2, k = 0;
 5  scanf(“%d%d”, &x0, &y0);
 6  if (y0 % x0 != 0) {printf(“0\n”); return 0;}
 7  x = y0 / x0;
 8  while (x != 1)
 9  {
10    while (x % i != 0) i++; k++;
11    while (x % i == 0) x /= i;
12  }
13  printf(“%d\n”, 1<<(k));
14}

posted @ 2010-09-11 22:10 Climber.pI 阅读(1739) | 评论 (1) | 编辑 收藏

Tyvj 1049 最长不下降子序列

经典的最长不下降子序列问题，O(n^2)【还存在基于二分查找的O(nlogn)算法】

方程：if(a[j]<=a[i]) f[i] = max{f[j]} (0<j<i, 1<i<=n)

可能是今天状态不好，一直在纠缠细节.需要注意的是，子序列长度的最大值不一定在f[n]中.

 1#include<iostream>
 2using namespace std;
 3int a[5001], b[5001];
 4int max(int x, int y) {return (x > y) ? x : y;}
 5int main()
 6{
 7    int i, j, n, ans;
 8    cin >> n;
 9    for (i = 1; i <= n; i++) {cin >> a[i]; b[i] = 1;}
10    for (i = 2; i <= n; i++)
11    {
12        for (j = 1; j < i; j++)
13            if (a[j] <= a[i] && b[j]+1 > b[i])
14                b[i] = b[j]+1;
15    }
16    for (i = 1; i <= n; i++) 
17        if (ans < b[i]) ans = b[i];
18    cout << ans << endl;
19}
20


马上要走了，高中还是麻烦很多，进度让人纠结.

posted @ 2010-09-11 21:11 Climber.pI 阅读(332) | 评论 (0) | 编辑 收藏

Prepare NOIP 2010 I

报名的问题已经顺利解决，特别感谢新班主任xm老师在12h内联系好了本部的教练，以及教练dh老师.

上机时间初步定在16:30之后，等待教练通知.

——————————-古事·故事——————————-

NOIP 2009高级出了一等，当年普及两一等的lj神牛，第一年三等，第二年一等.

很神奇的挂靠中山纪念参赛.

不知如何联系.

很多事情总是莫名奇妙的，比如OI，听来的故事可以写成长篇.

比如lccz，两位令人尊敬的学长，lwq和jec，一个复赛二等，一个初赛全市第三.

  • 一个在龙高，一个在深中.
  • 前者高二二等，高三三等；后者高一一等.

再比如，lj 和dy，同样是两位令人尊敬的学长.

  • 前者是初中深圳市实力最强的，来自深中初中部，初二一等300+，初三一等290.之后莫名其妙的去了高级，代表纪中参赛，高一三等210，高二一等210.
  • 后者初三没进复赛，去了深中，高一二等250，高二一等265，今年又拿了NOI铜牌，是深圳历史上第一个NOI奖牌得主.

环境虽然不是决定性的，但对人的限制仍然不可忽视.

保证基本环境，剩下的，事在人为.

—————————–进度——————————-

  • 《背包九讲》看了一半，dd_engi的语言果然不易理解，加深了对01背包、完全背包、多重背包的认识.需要学习某些特殊的情况.需要做题.
  • 刷了1998和1999原题，明天打程序，1999最后一题不会.(DP+搜索)
  • 重新用了龙初的vijos，重建一个提高题库，这应该能节约一些时间，毕竟每天可能的上机时间也就1-1.5h.
  • 现在效率太低了.

posted @ 2010-09-11 21:07 Climber.pI 阅读(303) | 评论 (0) | 编辑 收藏

仅列出标题
共8页: 1 2 3 4 5 6 7 8