list

uva,127

前面见过几次类似的模型了。似乎输入输出差不多形式。

考虑vector或list里面放stack。因为这道题目只涉及到随机访问，所以vector相对要快一点。

因为每次其左边的第一个或第三个与其与其匹配时，就把它放在左一或左三上。有木有压栈的感觉～～

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <stack>
 6 
 7 using namespace std;
 8 
 9 struct Node
10 {
11     char value;
12     char suit;  //char value[2];
13 };
14 
15 int match(Node x,Node y)
16 {
17     if(x.value==y.value || x.suit==y.suit)
18         return 1;
19     return 0;
20 }
21 
22 
23 
24 int main()
25 {
26     vector<stack<Node> > vr;
27     char v,s;       //Node s;
28     while(cin>>v && v!='#')  //cin>>s.value && strcmp(s.value,"#");
29     {
30         cin>>s;
31         stack<Node> sk;
32         sk.push((Node){v,s}); //sk.push(s);
33         vr.push_back(sk);
34         int i;
35         if(vr.size()==52)
36         {  while(true)
37             {
38                 for(i=0;i!=vr.size();i++)
39             {
40                 if(i>=3 && match(vr[i].top(),vr[i-3].top()))
41                 {
42                     vr[i-3].push(vr[i].top());
43                     vr[i].pop();
44                     break;
45                 }
46                 
47                 if(i>=1 && match(vr[i].top(),vr[i-1].top()))
48                    {
49                        vr[i-1].push(vr[i].top());
50                        vr[i].pop();
51                        break;
52                    }
53             }
54             if(i==vr.size()) break;
55             else if(vr[i].empty())
56                 vr.erase(vr.begin()+i);
57             }
58             cout<<vr.size()<<(vr.size()==1?" pile remaining:":" piles remaining:");
59             for(i=0;i<vr.size();i++)
60                 cout<<' '<<vr[i].size();
61             cout<<endl;
62             vr.clear();
63           }
64         
65     }
66     return 0;
67 }

View Code

Poj,2766

具体意思：抽象化；一个二维数组，从其边界发出一光束，遇到障碍物就向右转90读，直到射出此数组输出射出的坐标。或者一直停留在此数组里面输出(0,0) 测试了一下好像无论怎样都能射出。。。。所以条件给的有点水就过了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int dx[]={0,1,0,-1},dy[]={1,0,-1,0}; //跳转方向。
 7 //dx[]={-1,0,1,0},dy[]={0,-1,0,1}往左。
 8 
 9 
10 
11 int main()
12 {
13     int t;
14     int n,r,dir;
15     scanf("%d",&t);
16     int arr[52][52];   
17     while(t--)
18     {
19         scanf("%d %d",&n,&r);
20 //用vector<vector<int> > arr(n+2,vector<int>(n+2,0))更快。
21         memset(arr,0,sizeof(arr));
22         int i;
23         int x,y;
24         for(i=0;i<r;i++)
25         {
26             scanf("%d %d",&x,&y);
27             arr[x][y]=1;
28         }
29         for(i=0;i<=n+1;i++)
30             arr[i][0]=arr[i][n+1]=arr[0][i]=arr[n+1][i]=-1;
31         
32         scanf("%d %d",&x,&y);
33         
34         if(y==0) dir=0;
35         else if(x==0) dir=1;
36         else if(y==n+1) dir=2; //r和n搞错了wa了几次，晕
37         else dir=3;
38         
39         x+=dx[dir];
40         y+=dy[dir];
41         while(x>0 && x<n+1 && y>0 && y<n+1)
42         {
43             if(arr[x][y]) dir=(dir+1)%4;
44             x+=dx[dir];
45             y+=dy[dir];
46         }
47         printf("%d %d
",x,y);
48     }
49     return 0;
50 }

View Code

Hdu,4022

一开始不懂什么离散化，现在也不太懂。。

我一开始用数组走了一遍，RE了n次。 100000*50越界了。。

后来用嵌套vector走了一次，还是re

之后去看了别人的博客。感觉思想一样。

用map嵌套一个multiset 一个虚拟的二维数组。stl还是挺好挺强大的。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <map>
 4 #include <set>
 5 
 6 using namespace std;
 7 
 8 typedef map<int,multiset<int> > dep;
 9 
10 void pop(dep& a,dep& b,int k)
11 {
12     printf("%d
",a[k].size());
13     for(multiset<int>::iterator it=a[k].begin();it!=a[k].end();it++)
14         b[*it].erase(k);
15     a[k].clear();
16     return;
17 }
18 
19 
20 int main()
21 {
22     int m,n;
23     dep h,l;
24     while(scanf("%d %d",&n,&m) && m+n)
25     {
26         int i;
27         int x,y;
28         
29         for(i=0;i<n;i++)
30         {
31             scanf("%d %d",&x,&y);
32             h[x].insert(y);
33             l[y].insert(x);
34         }
35         
36         for(i=0;i<m;i++)
37         {
38             scanf("%d %d",&x,&y);
39             
40             if(!x)
41                 pop(h,l,y);
42             else
43                 pop(l,h,y);
44         }
45         printf("
");
46     }
47     return 0;
48 }

View Code

uva,141

把坐标离散化用两个一位数组保存，然后按照一定规律对其进行转置。90 180 270英文180不管向左向右转都一样所以只写一次。

感觉

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <map>
 6 
 7 using namespace std;
 8 
 9 map<string,int> h;
10 int num[2][51];
11 
12 int N,n;
13 char str[101];
14 
15 bool check()
16 {
17     int nn,t;
18     int i,j;
19     for(i=j=nn=0;i<N;i++)
20     {
21         str[i]=num[nn][j++]+1;
22         if(j>=n){j=0;nn++;}
23     }
24     if(h[str]) return 0;
25     
26     for(j=i=0,t=nn=1;i<N;i++)
27     {
28         str[i]=num[nn][j]+1;
29         j+=t;
30         if(j>=n){j=n-1;t=-1;nn--;}
31     }
32     if(h[str]) return 0;
33     
34     for(i=nn=0,j=n-1;i<N;i++)
35     {
36         str[i]=num[nn][j--]+1;
37         if(j<0){j=n-1;nn++;}
38     }
39     if(h[str]) return 0;
40     
41     for(i=0,j=n-1,t=-1,nn=1;i<N;i++)
42     {
43         str[i]=num[nn][j]+1;
44         j+=t;
45         if(j<0){j=0;nn--;t=1;}
46     }
47     if(h[str]) return 0;
48     else
49         h[str]=1;
50     return 1;
51 }
52 
53 int main()
54 {
55     while(~scanf("%d",&n) && n)
56     {
57         h.clear();
58         N=n<<1;
59         memset(num,0,sizeof(num));
60         int a,b;
61         int i;
62         char c;
63         int t;
64         bool flag=0;
65         for(i=0;i<N;i++)
66         {
67             scanf("%d %d %c",&a,&b,&c);
68             if(flag) continue;
69             if(c=='-') t=-1;
70             else t=1;
71         
72             num[0][a-1]+=t;
73             num[1][b-1]+=t;
74         
75         
76             if(!check())
77             {
78                 printf("Player %d wins on move %d
",(i+1)%2+1,i+1);
79                 flag=1;
80             }
81         }
82         if(!flag)
83             printf("Draw
");
84     }
85     return 0;
86 }

View Code

uva,11988

'['右边的内容全部往在队头输出，]''代表beiju结束，当然也可以不结束。

开始是想做标记然后把'['后面到截止的内容压栈再输出，其余的顺序输出。发现中间的细节很繁琐。

后面看了别人的博客。

递归之强大～～～

对deque有了更深的了解。

递归法：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <cstdlib>
 7 #define maxn 1000005
 8 using namespace std;
 9 
10 
11 char ch[maxn];
12 
13 
14 void dfs(int l,int r)
15 {
16     int s=r;
17     while(s>=l && ch[s]!='[' && ch[s]!=']') s--;
18     if(ch[s]==']') dfs(l,s-1);
19     for(int j=s+1;j<=r;++j)
20         printf("%c",ch[j]);
21     if(ch[s]=='[') dfs(l,s-1);
22 }
23 
24 int main()
25 {
26     while(gets(ch))
27     {
28         dfs(0,strlen(ch)-1);
29         printf("
");
30     }
31     return 0;
32 }

View Code

双端队列。感觉list也可以。差不多。

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <deque>
 7 using namespace std;
 8 typedef long long LL;
 9 #define EPS 10e-9
10 #define INF 0x3f3f3f3f
11 #define REP(i,n) for(int i=0; i<(n); i++)
12 char str[100010];
13 int main(){
14 
15     while(scanf("%s",str)!=EOF){
16         deque<int > q;
17         int i=0;
18         while(str[i]=='['||str[i]==']')  i++;
19         q.push_front(i);
20         while(str[i]){
21             if(str[i]=='['){
22                  q.push_front(i+1);
23                  str[i]='';
24             }
25             else if(str[i]==']'){
26                  q.push_back(i+1);
27                  str[i]='';
28             }
29             i++;
30         }
31         while(!q.empty()){
32             printf("%s",str+q.front());
33             q.pop_front();
34         }
35         printf("
");
36 
37     }
38     return 0;
39 }

View Code

活在现实，做在梦里。