C++博客-Gotta Write A Code

DX笔记

bennycen — Thu, 03 May 2012 13:38:00 GMT

1. 凹凸纹理映射

凹凸纹理存放在一个纹理图片中，其(R,G,B)分别对应(u,v,w)的normalize向量，由于(R,G,B)的归一化后的范围是(0-1)，故要通过(x - 0.5)*2转换成(-1,1)的范围。

另外，由于凹凸纹理记录的是针对一个垂直于视线的平面的向量，如果将其贴到其他物体上，如环体，球体，就必须计算纹理坐标空间，就是将不垂直于视线的变换为垂直于视线的。可以构造渲染object的(法线，切线)，并且得垂直于法线切线的向量，构成坐标系，然后计算光线方向lightDir和视线方向viewDir时，要将其变换到纹理空间坐标系去。

最后在pixel shader中根据lightDir、viewDir和texcoord，像一般光照计算那样计算，只不过其“法向量”由凹凸纹理提供。

2. 立方体环境映射

先构造立方体纹理，CubeMap，像个纸盒打开6个面那样。然后逐顶点计算反射向量，计算如下：R = I - 2*N*dot(I,N)，然后在pixel shader中texCUBE。

3.折射反射

在2中再添加一个折射向量，然后pixel shader中两次texCUBE后混合一下。

bennycen 2012-05-03 21:38 发表评论

hdu 2087 hud 1686

bennycen — Thu, 29 Mar 2012 12:13:00 GMT

摘要: 这两题是单模式串匹配hdu2087 数据量较小，可以采用标准库strstr轻松完成 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include 2#include &... 阅读全文

bennycen 2012-03-29 20:13 发表评论

hdu 2896 多模式串匹配2

bennycen — Thu, 29 Mar 2012 10:18:00 GMT

摘要: 也是一道AC自动机解决多模式串匹配的问题，注意的是用一个visited记录id的出现，以及病毒的数组需要排序，当病毒数超过3时可以结束匹配。代码如下： Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include&nbs... 阅读全文

bennycen 2012-03-29 18:18 发表评论

hdu 2222 多模式串匹配

bennycen — Thu, 29 Mar 2012 10:15:00 GMT

摘要: AC自动机用于多模式串匹配 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include 2#include &n... 阅读全文

bennycen 2012-03-29 18:15 发表评论

水题两道

bennycen — Mon, 26 Mar 2012 12:19:00 GMT

Poj 2081

http://poj.org/problem?id=2081
求数列第i项 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9
解法：按照题目要求递推即可

#include <stdio.h>
#include <string.h>

bool visited[4000005];
int nums[4000005];

void pre()
{
    memset(visited,0,sizeof(visited));
    memset(nums,0,sizeof(nums));
    visited[0] = true;
    for (int i = 1; i <= 500000; ++i)
    {
        int k = nums[i-1] - i;
        if (k <=0 || visited[k])
        {
            nums[i] = nums[i-1] + i;
            visited[nums[i]] = true;
        }
        else
        {
            nums[i] = nums[i-1] - i;
            visited[nums[i]] = true;
        }
    }
}

int main()
{
    pre();
    int n;
    while(scanf("%d",&n) != EOF)
    {
        if (n == -1)
        {
            break;
        }
        printf("%d\n",nums[n]);
    }
    return 0;
}

2250

http://poj.org/problem?id=2250

最长公共串

1 #include <iostream>
  2 #include <string.h>
  3 #include <string>
  4 #include <vector>
  5 using namespace std;
  6
  7 string strs1[128];
  8 int len1;
  9 string strs2[128];
10 int len2;
11 int dp[128][128];
12 int flags[128][128];//1 上 2 左 3 对角
13
14 void Test()
15 {
16     memset(dp,0,sizeof(dp));
17     memset(flags,0,sizeof(flags));
18     for (int i = 1; i <= len1; ++i)
19     {
20         for (int j = 1; j <= len2; ++j)
21         {
22             if (strs1[i] == strs2[j])
23             {
24                 dp[i][j] = dp[i-1][j-1] + 1;
25                 flags[i][j] = 3;
26             }
27             else
28             {
29                 int m1 = dp[i-1][j];
30                 int m2 = dp[i][j-1];
31                 if (m1 < m2)
32                 {
33                     dp[i][j] = m2;
34                     flags[i][j] = 2;
35                 }
36                 else
37                 {
38                     dp[i][j] = m1;
39                     flags[i][j] = 1;
40                 }
41             }
42         }
43     }
44     int pos1 = len1;
45     int pos2 = len2;
46     vector<string> vec;
47     while(true)
48     {
49         if (flags[pos1][pos2] == 3)
50         {
51             vec.push_back(strs1[pos1]);
52             --pos1;
53             --pos2;
54         }
55         else if (flags[pos1][pos2] == 2)
56         {
57             --pos2;
58         }
59         else if (flags[pos1][pos2] == 1)
60         {
61             --pos1;
62         }
63         else
64             break;
65     }
66     for (int i =  vec.size()-1; i >=0 ; --i)
67     {
68         cout << vec[i];
69         if (i == 0)
70         {
71             cout << endl;
72         }
73         else
74         {
75             cout << " ";
76         }
77     }
78 }
79
80 int main()
81 {
82     //freopen("data.txt","r",stdin);
83     string input;
84     int k = 0;
85     len1 = len2 = 0;
86     while(cin >> input)
87     {
88         if (input == "#")
89         {
90             if (k == 1)
91             {
92                 Test();
93                 k = 0;
94                 len1 = len2 = 0;
95                 continue;
96             }
97             else
98             {
99                 k = 1;
100             }
101         }
102         if (k == 0)
103         {
104             strs1[++len1] = input;
105         }
106         else
107         {
108             strs2[++len2] = input;
109         }
110     }
111     return 0;
112 }

bennycen 2012-03-26 20:19 发表评论

zoj 3542

bennycen — Mon, 26 Mar 2012 02:42:00 GMT

摘要: 模拟题，不说了 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include 2#include 3 4char&n... 阅读全文

bennycen 2012-03-26 10:42 发表评论

AnyC:添加类型限制

bennycen — Thu, 22 Mar 2012 14:14:00 GMT

为AnyC添加了函数调用时的参数类型限制功能，可以限制改函数的某个参数的具体类型！
截图如下：

1 function check(<int> k,j)
2 {
3     print(j + k + "\n");
4 }
5
6 //check("world","hello");
7
8 function add(<int> a)
9 {
10     return function ( b)
11     {
12         return a+b;
13     }
14 }
15
16 class Test
17 {
18 public:
19     function add(<int> a, b)
20     {
21         return a+b;
22     }
23 }
24
25 var k = Test();
26 print(k.add(1,2) + "\n");
27
28 function ppp(<array> arrs,<int> _index)
29 {
30     return arrs[_index];
31 }
32
33 var ks = [1,2,3,4,5];
34 ppp(ks,1);
35
36 function testValue(<value> _v)
37 {
38     print(_v+"\n");
39 }
40 testValue(1);
41 testValue(1.2);
42 testValue("sss");
43 testValue(false);
44
45 function testFunc(<function> _f,_v)
46 {
47     return _f(_v);
48 }
49
50 var f1 = add(40);
51 print(testFunc(f1,2) + "\n");

bennycen 2012-03-22 22:14 发表评论

poj 3074

bennycen — Mon, 12 Mar 2012 11:37:00 GMT

摘要: 数独问题采用跳舞链方法会得到比较快的速度用跳舞链解决的方法主要是将问题的模型转换成01覆盖模型，然后模板之首先要了解它的限制条件：(1) 每一格只能填一个数字 (2) 每一列的数字是不同的(3) 每一行的数字是不同的(4) 每一个九宫格的数字是不同的那么我们可以构造出一组状态：行状态(i,j,k)：表示第i行第j列填第k个数列状态(i,j,k)：表示第k个限制的子状态为(i,j)，子状态根据限制而... 阅读全文

bennycen 2012-03-12 19:37 发表评论

作品：动态语言AnyC 1.0

bennycen — Thu, 08 Mar 2012 03:05:00 GMT

摘要: 一、缘起一直很想做一个自己的动态语言了，记得三年前学习Compiler的时候做了不成器的Tiny++和语法全部按足《编译原理实践》的C--，其中C--还做得非常不好(基本只能看看用不了)，然后上次看了《游戏脚本高级编程》，里面介绍的XScript虽然非常简单，但已经有语言的影子。然后又看了《python源码剖析》，看了python的源码，学习了很多python的内部机理，感觉python虽强大巧妙... 阅读全文

bennycen 2012-03-08 11:05 发表评论

旧作品：本地程序评测器

bennycen — Fri, 02 Mar 2012 12:30:00 GMT

前做了一个简单实用的本地程序评测机，用作学校某比赛的评测(该比赛不是在线比赛，而是做完后自己发代码然后我们自己手动萍。。囧)，该程序是一个本地评测系统，用户输入单文件代码或可执行程序，和输入数据和正确的输出数据，系统根据这些数据对代码或程序进行评测。
评测结果有：
Accept   //通过
Compile Error  //编译错误
Worng Answer  //答案错误
Time Limit Exceeded //超时
Memory Limit Exceeded //超内存
Presentation Error //输出格式错误
System Error  //系统错误
下面简单聊聊实现的过程：

一、实现细节
1.1 编译功能
类:CompilerHelper
函数:static int compile(const std::string& sSourceFile, //源文件路径
const std::string& sOutputFile);//执行代码路径
流程如下:
生成编译器输入参数(编译器路径、文件路径、包含路径、库路径)在config.txt定义
-> 重定向in和out -> 创建进程编译->等待完毕后返回执行结果

1.2 评测功能
需要获得执行代码路径、输入文件、期待输出的答案文件、本次执行程序的实际输出文件、
时间、内存、是不是SPJ

监视器线程: 监视进程的执行时间、使用内存的信息
流程:
输入信息-> 根据输入文件产生输入参数->创建进程->监视器开启->等待直到结束
->返回!=0?"System Error" : 记录本次执行所需要的时间和内存->是否SPJ?启动spj比较器
:启动文件比较器

启动文件比较器: 比较实际的和答案的差异,完全相同的AC,只存在空格的差异为PE,其他情况的WA
spj比较器: 使用自己编写的spj程序对两个文件评测

1.3 测试套件
实现多个测试用例(多个输入文件和输出文件)
可以通过配置文件进行配置
配置文件如下:
[TestSuite]
TestCaseCount=19 //用例个数
IsSpecialJudge=0 //是否SPJ
CodeFile=main.cpp //源文件,可设为NULL
SPJExe=lowSPJ.exe //SPJ路径
ExecuteFile=NULL //如设置了就不启用编译功能
[TestCase_n] //第n个用例
TimeLimit=1000 //时间限制
MemoryLimit=65535 //内存限制(KB)
StdInputFile=data1.txt //输入文件
AnswerFile=output1.txt //答案
每个用例将new一个judgerunner实例

二、依赖库
个人开发的mtLibrary中的Common、Thread、Process库模块

三、运行效果
配置文件示例
[TestSuite]
TestCaseCount=19
IsSpecialJudge=0
CodeFile=main.cpp
SPJExe=NULL
[TestCase_1]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data1.txt
AnswerFile=output1.txt
[TestCase_2]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data2.txt
AnswerFile=output2.txt
[TestCase_3]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data3.txt
AnswerFile=output3.txt
[TestCase_4]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data4.txt
AnswerFile=output4.txt
[TestCase_5]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data5.txt
AnswerFile=output5.txt
[TestCase_6]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data6.txt
AnswerFile=output6.txt
[TestCase_7]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data7.txt
AnswerFile=output7.txt
[TestCase_8]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data8.txt
AnswerFile=output8.txt
[TestCase_9]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data9.txt
AnswerFile=output9.txt
[TestCase_10]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data10.txt
AnswerFile=output10.txt
[TestCase_11]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data11.txt
AnswerFile=output11.txt
[TestCase_12]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data12.txt
AnswerFile=output12.txt
[TestCase_13]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data13.txt
AnswerFile=output13.txt
[TestCase_14]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data14.txt
AnswerFile=output14.txt
[TestCase_15]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data15.txt
AnswerFile=output15.txt
[TestCase_16]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data16.txt
AnswerFile=output16.txt
[TestCase_17]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data17.txt
AnswerFile=output17.txt
[TestCase_18]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data18.txt
AnswerFile=output18.txt
[TestCase_19]
TimeLimit=1000
MemoryLimit=65535
StdInputFile=data19.txt
AnswerFile=output19.txt

这是运行的效果，运行后结果将保存带JudgeResult.txt中

bennycen 2012-03-02 20:30 发表评论