C++博客-Rest

C#读写

蔗晨 — Tue, 02 Mar 2010 12:56:00 GMT

打开文件流：
FileStream fs = new FileStream(@"d:\2.txt",FileMode.Open,FileAccess.ReadWrite);
StreamWriter sw = new StreamWriter(fs);
定位指针：
sw.BaseStream.Seek(0, SeekOrigin.End);
写缓冲区：
sw.Write(string a);
写入文件：
sw.Flush();
最后关闭文件：sw.Close();

蔗晨 2010-03-02 20:56 发表评论

09暑假集训contest5总结

蔗晨 — Fri, 28 Aug 2009 17:03:00 GMT

看到不熟悉的题，不要以为都是有专门的算法（特别是图论的），今天那道Ranking the Cows其实就是很简单的一道。我还以为是专门的图论的算法，就没去想。注意__int64的最大值可以达到9，000，000，000，000，000，000多。对线段树的理解还是不够深入。处理儿子的下标有2中处理方法，各有所长。插入线段前，把数据先排序，能够避免线段树的递归。复杂度降低。对各种算法的复杂度一定要知道。今天看到那个矩形面积的题，一看坐标的范围那么大，就直接用了矩形切割。但其实N是4000，矩形切割是N的平方。显然超时。对于n特别大的，比如5000，就要想想贪心了，想想策略。

蔗晨 2009-08-29 01:03 发表评论

09暑假集训contest4总结

蔗晨 — Fri, 28 Aug 2009 04:46:00 GMT

一个低级失误导致浪费了很多时间，后面的题没时间做了。一位数字是0到9，我写成了1到9. 在计算几何中，用向量的方法求点的坐标方便，用平面几何的方法会出现平方。

蔗晨 2009-08-28 12:46 发表评论

09暑假培训contest 2总结

蔗晨 — Tue, 25 Aug 2009 10:51:00 GMT

今天我写的很失败。一道简单的暴搜找路径，找不出哪里错了。还好sweet重写马上就过了。还有一道记忆化搜索的题，最优解是很快写出来了。不过回溯路径的时候出了点小问题。后来用来sxj的方法过了。其中犯了一个低级错误。。。调试了半天。还好sxj调试能力强。学到了很多调试的方法。有个很容易出错的地方：向上递归父亲节点的时候， while(res--) { cout<

蔗晨 2009-08-25 18:51 发表评论

09暑假集训contest 1 总结（补上）

蔗晨 — Tue, 25 Aug 2009 10:41:00 GMT

1. 找到了原来二分枚举的模板的一个错误。 2. 对矩阵的坐标搞混了。以后每次这样： A[x][y]指第x行，第y列。注意向右走一格的时候是y+1。因为向右走行数不变，列数变。也可以画一个坐标辅助。坐标向右是y方向。向下是x方向。 A[M][N]是是M行，N列。这次选题有些失误。

蔗晨 2009-08-25 18:41 发表评论

pku1064二分枚举+控制精度

蔗晨 — Sat, 02 May 2009 10:19:00 GMT

#include<iostream>
using namespace std;

const int N=10010;

int a[N];
int n,aim;

bool Check(int x){
    int cnt=0;
    int i;
    for(i=1;i<=n;++i)
    {
        cnt+=a[i]/x;
    }
    if(cnt>=aim)return 1;
    return 0;
}

int solve(int mx){
    int mid,left=1,right=mx;
    while(left<=right)
    {
        mid=(left+right)>>1;
        if(Check(mid))left=mid+1;
        else right=mid-1;
    }
    return right;
}

int main(){
    scanf("%d%d",&n,&aim);
    double tp;
    int i;
    int mx=-1;
    for(i=1;i<=n;++i)
    {
        scanf("%lf",&tp);
        a[i]=(tp+0.001)*100;
        if(mx<a[i])mx=a[i];
    }
    int res=solve(mx);
    if(res==0)printf("0.00\n");
    else printf("%.2lf\n",(double)res/100.00);
    return 0;
}

蔗晨 2009-05-02 18:19 发表评论

标记头方法

蔗晨 — Thu, 12 Mar 2009 12:57:00 GMT

pku2951
1属于S，若X属于S，则2*X+1,3*X+1也属于S。
求S的前10000000个元素（从小到大）。
量太大，只能用O（n）的。
用表记录，最后不可能用排序的，所以要一开始放的时候就是从小到大。
用t2记录 2*X+1 方法增加数的最大的一个的下标。
用t3记录 3*X+1 方法增加数的最大的一个的下标。
只要比较a[t2]*2+1与a[t3]*3+1哪个小，小的一个放入a。t2或t3加1.

这种方法适用于扩展方法有限，且要按序排放的题。用标记头记录各种扩展方法的状态。

蔗晨 2009-03-12 20:57 发表评论

ural 1011

蔗晨 — Mon, 09 Mar 2009 12:17:00 GMT

Conductors
枚举，精度问题。
关于精度的问题可以转成整数做，因为这题的input是2位小数，所以读入后乘以100，化整数，且不失去精度。
有时候读取一个小数就会失去精度(就是0.9999999999)。所以要加一个eps（1e-9).若不是0.999999999这样的，eps会被舍去
中途处理全部用整数

蔗晨 2009-03-09 20:17 发表评论

最少区间覆盖问题

蔗晨 — Wed, 18 Feb 2009 01:31:00 GMT

关于区间的往往可以贪心。
pku2376
用最少的线段覆盖一条大线段。
按左边的坐标排序，找左边符合开始的线段中右边最大的。

sort(a,a+n);
    end=1;
    i=0;
    tp=-1;
    cnt=0;
    while(end<=T)
    {
        if(i>n||cnt>n)
        {
            printf("-1\n");
            return 0;
        }
        if(a[i].l<=end)
        {
            if(tp<=a[i].r)
            {
                tp=a[i].r;
            }
            i++;
            if(tp>=T)
            {
                cnt++;
                break;
            }
        }
        else
        {
            end=tp+1;
            cnt++;
            tp=-1;
        }
    }

蔗晨 2009-02-18 09:31 发表评论

联想图模型

蔗晨 — Fri, 13 Feb 2009 11:08:00 GMT

pku3041 N*N的方格，小方格里有的有点。可以一次消除一列或一行上的点，求最少几次可以把点都消除。
行，列是二维的，可能可以二分图，而且一次消一行，就像二分图的点覆盖，消一个点把相关的边全消了。
因此就是二分图的点覆盖问题。

蔗晨 2009-02-13 19:08 发表评论