BFS,用位压缩..值得纪念的一题...
1 #include <iostream>
2 #include <string>
3 #include <algorithm>
4 #include <queue>
5 #include <vector>
6
7 using namespace std;
8 struct Node
9 {
10 int bplus;
11 int bminus;
12 int time;
13
14 int eplus;
15 int eminus;
16 Node(int bs=0,int bm=0,int t=0,int es=0,int em=0):bplus(bs),bminus(bm),time(t),eplus(es),eminus(es){};
17 bool operator<(const Node& c)const{
18 return time<c.time;
19 }
20 };
21 int hash[1050000];
22 struct ExNode
23 {
24 int num;
25 int time;
26 bool operator<(const ExNode& x)const{
27 return time>x.time;
28 }
29 ExNode(int n=0,int t=0):num(n),time(t){};
30 };
31 vector<Node> vec;
32 int n,m;
33 inline void Input()
34 {
35 memset(hash,-1,sizeof(hash));
36 int t;
37 string s1,s2;
38 vec.clear();
39 for(int i=0;i<m;i++){
40 cin>>t>>s1>>s2;
41 Node tmp;
42 tmp.time=t;
43 for(int j=0;j<s1.size();j++){
44 if(s1[j]=='+')tmp.bplus|=1<<(n-j-1);
45 else if(s1[j]=='-')tmp.bminus|=1<<(n-j-1);
46 }
47 for(int j=0;j<s2.size();j++){
48 if(s2[j]=='+')tmp.eplus|=1<<(n-j-1);
49 else if(s2[j]=='-')tmp.eminus|=1<<(n-j-1);
50 }
51 vec.push_back(tmp);
52 }
53 sort(vec.begin(),vec.end());
54 }
55 bool BFS()
56 {
57 priority_queue<ExNode> que;
58 ExNode start;
59 for(int i=0;i<n;i++)
60 start.num|=1<<i;
61 que.push(start);
62 while(!que.empty()){
63 ExNode f=que.top();
64 que.pop();
65 if(f.num==0){
66 printf("Fastest sequence takes %d seconds.\n\n",f.time);
67 return true;
68 }
69 ExNode d=f;
70 for(int i=0;i<m;i++){
71 d=f;
72 if(!((~d.num&vec[i].bplus)||(d.num&vec[i].bminus))){
73 d.num|=vec[i].eplus;
74 d.num&=(~vec[i].eminus);
75 d.time=f.time+vec[i].time;
76 if(hash[d.num]==-1||hash[d.num]>d.time){
77 hash[d.num]=d.time;
78 que.push(d);
79 }
80 }
81 }
82 }
83 return false;
84 }
85 int main()
86 {
87 int p=1;
88 while(scanf("%d%d",&n,&m),n+m){
89 Input();
90 printf("Product %d\n",p++);
91 if(BFS()==false){
92 printf("Bugs cannot be fixed.\n\n");
93 continue;
94 };
95 }
96 return 0;
97 }
posted @
2008-09-09 14:25 小果子 阅读(152) |
评论 (0) |
编辑 收藏二、仿射变换(转)
仿射变换是空间直角坐标变换的一种，它是一种二维坐标到二维坐标之间的线性变换，保持二维图形的“平直线”和“平行性”，其可以通过一系列的原子变换的复合来实现，包括平移(Translation)、缩放（Scale）、翻转（Flip）、旋转（Rotation）和剪切(Shear)。
此类变换可以用一个3×3的矩阵来表示，其最后一行为(0, 0, 1)。该变换矩阵将原坐标(x, y)变换为新坐标(x', y')，这里原坐标和新坐标皆视为最末一行为(1)的三维列向量，原列向量左乘变换矩阵得到新的列向量：
[x'] [m00 m01 m02] [x] [m00*x+m01*y+m02]
[y'] = [m10 m11 m12] [y] = [m10*x+m11*y+m12]
[1 ] [ 0 0 1 ] [1] [ 1 ]
用代数式表示如下：
x’ = m00*x+m01*y+m02；
y’ = m10*x+m11*y+m12；
如果将它写成按旋转、缩放、平移三个分量的复合形式，则其代数式如下：
其示意图如下：
几种典型的仿射变换：
1.public static AffineTransform getTranslateInstance(double tx, double ty)
平移变换，将每一点移动到(x+tx, y+ty)，变换矩阵为：
[ 1 0 tx ]
[ 0 1 ty ]
[ 0 0 1 ]
（译注：平移变换是一种“刚体变换”，rigid-body transformation，中学学过的物理，都知道啥叫“刚体”吧，就是不会产生形变的理想物体，平移当然不会改变二维图形的形状。同理，下面的“旋转变换”也是刚体变换，而“缩放”、“错切”都是会改变图形形状的。）
2.public static AffineTransform getScaleInstance(double sx, double sy)
缩放变换，将每一点的横坐标放大（缩小）至sx倍，纵坐标放大（缩小）至sy倍，变换矩阵为：
[ sx 0 0 ]
[ 0 sy 0 ]
[ 0 0 1 ]
3.public static AffineTransform getShearInstance(double shx, double shy)
剪切变换，变换矩阵为：
[ 1 shx 0 ]
[ shy 1 0 ]
[ 0 0 1 ]
相当于一个横向剪切与一个纵向剪切的复合
[ 1 0 0 ][ 1 shx 0 ]
[ shy 1 0 ][ 0 1 0 ]
[ 0 0 1 ][ 0 0 1 ]
（译注：“剪切变换”又称“错切变换”，指的是类似于四边形不稳定性那种性质，街边小商店那种铁拉门都见过吧？想象一下上面铁条构成的菱形拉动的过程，那就是“错切”的过程。）
4.public static AffineTransform getRotateInstance(double theta)
旋转变换，目标图形围绕原点顺时针旋转theta弧度，变换矩阵为：
[ cos(theta) -sin(theta) 0 ]
[ sin(theta) cos(theta) 0 ]
[ 0 0 1 ]
5.public static AffineTransform getRotateInstance(double theta, double x, double y)
旋转变换，目标图形以(x, y)为轴心顺时针旋转theta弧度，变换矩阵为：
[ cos(theta) -sin(theta) x-x*cos+y*sin]
[ sin(theta) cos(theta) y-x*sin-y*cos ]
[ 0 0 1 ]
相当于两次平移变换与一次原点旋转变换的复合：
[1 0 -x][cos(theta) -sin(theta) 0][1 0 x]
[0 1 -y][sin(theta) cos(theta) 0][0 1 y]
[0 0 1 ][ 0 0 1 ][0 0 1]
posted @
2008-09-07 16:35 小果子 阅读(744) |
评论 (0) |
编辑 收藏
1.创建DirectDraw对象的方法,创建主DirectDraw对象并使用QueryInterface()得到一个IDirectDraw7接口.
或者直接用DirectDrawCreateEx()创建一个DirectDraw7的接口.
HRESULT WINAPI DirectDrawCreate(GUID FAR *lpGUID,//guid of object
LPDIRECTDRAW FAR *lplpDD,//receives interface
IUnknown FAR *pUnkOuter);//com stuff
LpGUID--NULL,(视频卡驱动的Globally Unique Identifier)
lplpDD--返回一个DirectDraw的接口而不是DirectDraw7的接口.
pUnkOuter--NULL(always set to zero)
自行发送消息:
1.SendMessage()---send a message which is processed immediately to a window.In fact,
it calls WinProc().
LRESULT SendMessage(HWND hWnd,UINT,WPARAM,LPARAM);
2.PostMessage()---send a message to the messagequeue.just that.if it's succeed,it return a value(!0).
BOOL PostMessage(HWND hWnd,UINT Msg,WPARAM wParam,LPARAM lParam);
1.SetBkMode(hdc,TRANSPARENT);
2.FillRect(hdc,&r,(HBRUSH)GetStockObject(WHITE_BRUSH));
3.CreateSolidBrush(RGB(255,0,0));
4.wchar_t tmp[20];
GetDlgItemText(hDlg,IDC_EDIT1,tmp,20);
::wstringstream is;
is<<tmp;
is>>size;
5.InvalidateRect(hWnd,0,1);
6.DialogBox(hInst, MAKEINTRESOURCE(IDD_DIALOG1), hWnd, inputsize);
7.WM_CLOSE is sent before WM_DESTYOY.
//创建全屏(空白)模式窗口:
if(!(hWnd = CreateWindowEx(NULL,//extend style
WINDOW_CLASS_NAME,//class
"BX",//title
WS_POP|WS_VISIBLE,
0,0,//initial x,y
GetSystemMetrics(SM_CXSCREEN),//Initial width
GetSystemMetrics(SM_CYSCREEN),//Initial height
NULL,//handle to parent
NULL,//handle to menu
hinstance,//instance of this application
NULL)))//extra creation parms
return (0);
posted @
2008-08-25 16:05 小果子 阅读(248) |
评论 (1) |
编辑 收藏
今天做了一题仿自Google Code Jam Round 1 C. Numbers的题目...
大意是求高斯函数y=[(2^(0.5)+3^(0.5))^(2n)]%1024的值
以下是我的解题思路:
//高斯函数y=[pow(2,0.5)+pow(3,0.5)]^(2n)]
//y=[(5+2*pow(6,0.5))^n]
//添加项(5-2*pow(6,0.5))^n
//构造Y=(5+2*pow(6,0.5))^n+(5-2*pow(6,0.5))^n;
//由二项展开得Y是整数...
//因为0<(5-2*pow(6,0.5))<1,所以y=[pow(2,0.5)+pow(3,0.5)]^(2n)]=(5+2*pow(6,0.5))^n + (5-2*pow(6,0.5))^n - 1
//将y展开得y=2*(C0n*5^n+C2n*5^(n-2)(2*pow(6,0.5))^2+Cn4*5^(n-4)*(2*pow(6,0.5))^4+....)%1024
//分析得y=2*(C0n*5^n+C2n*5^(n-2)(2*pow(6,0.5))^2+Cn4*5^(n-4)*(2*pow(6,0.5))^4)%1024
//直接计算可得...
posted @
2008-08-25 01:19 小果子 阅读(323) |
评论 (0) |
编辑 收藏今天写了下http://acm.pku.edu.cn/JudgeOnline/problem?id=1451
两份代码在vc下ac,用g++交RE...
如下:
1 #include <iostream>
2 #include <algorithm>
3 #include <string>
4 #include <vector>
5
6 using namespace std;
7
8 int const NUM=26;
9 vector< vector<char> >vec;
10 struct Node
11 {
12 string ss;
13 int pro;
14 bool operator<(const Node& c)const{
15 if(pro!=c.pro)return pro>c.pro;
16 return ss<c.ss;
17 };
18 Node(string m="",int p=0):ss(m),pro(p){};
19 };
20 class _Trie
21 {
22 public:
23 _Trie():val(0){
24 for(int i=0;i<NUM;i++)next[i]=NULL;
25 }
26 ~_Trie(){
27 for(int i=0;i<NUM;i++)delete next[i];
28 }
29 _Trie* next[NUM];
30 int val;
31 };
32 Node ans[505];
33 string ss;
34 void dfs(_Trie* now,int level,string sm)
35 {
36 if(ss[level]=='1')return;
37 string mm=sm;
38 for(int i=0;i<vec[ss[level]-48].size();i++){
39 _Trie* p=now->next[vec[ss[level]-48][i]-'A'];
40 if(p!=NULL){
41 mm+=(vec[ss[level]-48][i]+32);
42 if(p->val>ans[level+1].pro&&level+1<505){
43 ans[level+1].pro=p->val;
44 ans[level+1].ss=mm;
45 }
46 else if(p->val==ans[level+1].pro){
47 if(ans[level+1].ss>mm){
48 ans[level+1].ss=mm;
49 }
50 }
51 dfs(p,level+1,mm);
52 mm=sm;
53 }
54 }
55 return;
56 }
57 int main()
58 {
59 vec.resize(29);
60 vec[2].push_back('A'),vec[2].push_back('B'),vec[2].push_back('C');
61 vec[3].push_back('D'),vec[3].push_back('E'),vec[3].push_back('F');
62 vec[4].push_back('G'),vec[4].push_back('H'),vec[4].push_back('I');
63 vec[5].push_back('J'),vec[5].push_back('K'),vec[5].push_back('L');
64 vec[6].push_back('M'),vec[6].push_back('N'),vec[6].push_back('O');
65 vec[7].push_back('P'),vec[7].push_back('Q'),vec[7].push_back('R'),vec[7].push_back('S');
66 vec[8].push_back('T'),vec[8].push_back('U'),vec[8].push_back('V');
67 vec[9].push_back('W'),vec[9].push_back('X'),vec[9].push_back('Y'),vec[9].push_back('Z');
68 int T;
69 cin>>T;
70 for(int r=1;r<=T;r++){
71 _Trie root;
72 int n;
73 cin>>n;
74 string str;
75 int pro;
76 while(n--){
77 _Trie* point=&root;
78 cin>>str>>pro;
79 for(int i=0;i<str.size();++i){
80 if(!point->next[str[i]-'a'])
81 point->next[str[i]-'a']=new _Trie;
82 point=point->next[str[i]-'a'];
83 point->val+=pro;
84 }
85 }
86 cout<<"Scenario #"<<r<<":\n";
87 cin>>n;
88 while(n--){
89 memset(ans,0,sizeof(ans));
90 cin>>ss;
91 int cnt=0;
92 for(int i=0;i<ss.size();i++){
93 if(ss[i]=='1')break;
94 else cnt++;
95 }
96 _Trie* now=&root;
97 dfs(now,0,"");
98 sort(ans+1,ans+cnt+1);
99 for(int i=0;i<cnt;++i){
100 if(ans[i+1].pro!=0)cout<<ans[i+1].ss<<endl;
101 else cout<<"MANUALLY"<<endl;
102 }
103 cout<<endl;
104 }
105 cout<<endl;
106 }
107 return 0;
108 }
109
经过两个多小时周折，终于在G++下也ac......聪明的你...能否改改...同样也能在G++下ac...
ps:绝对是一个挑战...至少忍耐力会上一个台阶...(我几乎已崩溃,没找出错误,我在G++下
1 if(p->val>ans[level+1].pro&&level+1<505){
2 ans[level+1].pro=p->val;
3 ans[level+1].ss=mm;
4 }
5 else if(p->val==ans[level+1].pro){
6 if(ans[level+1].ss>mm){
7 ans[level+1].ss=mm;
8 }
9 }
ans[level+1].ss=mm，跳出"程序访问违例(段异常)",
改完ac的acmers留个言...^_^,值得挑战...
原因分析:是memset时出了问题...不能对本身有构造函数的类或类成员中有构造函数的类成员memset..本例就是
string出了问题...
posted @
2008-08-15 16:33 小果子 阅读(318) |
评论 (0) |
编辑 收藏