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 小果子 閱讀(157) |
評論 (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 小果子 閱讀(760) |
評論 (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 小果子 閱讀(273) |
評論 (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 小果子 閱讀(333) |
評論 (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 小果子 閱讀(333) |
評論 (0) |
編輯 收藏