【Codeforces #168 Div1 & Div2】Solutions

　　转载请注明出处：http://www.cnblogs.com/Delostik/archive/2013/02/21/2920087.html

　　上一次失误掉进Div2，这次也很可惜，B题读错了题又差一点。。。

【A.Lights Out】

　　http://www.codeforces.com/contest/275/problem/A

　　题目大意：按开关会导致周围相邻开关状态一起变化，给出操作问结果。

　　简单模拟

View Code

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int dx[5]={0,1,0,-1,0};
 5 const int dy[5]={1,0,-1,0,0};
 6 int res[5][5],x;
 7 
 8 int main(){
 9     for(int i=1;i<=3;i++)
10         for(int j=1;j<=3;j++){
11             cin>>x;
12             for(int k=0;k<5;k++)
13                 res[i+dx[k]][j+dy[k]]+=x;
14         }
15     for(int i=1;i<=3;i++){
16         for(int j=1;j<=3;j++)
17             cout<<(res[i][j]+1)%2;
18         cout<<endl;
19     }
20     return 0;
21 }

【B.Convex Shape】

　　http://www.codeforces.com/contest/275/problem/B

　　题目大意：判断所给图形是不是所谓"Convex Shape"(即任意两个格子互达且只需转向一次)

　　枚举两个格子，沿着路径走就可以了= =竟然读错题了啊囧

View Code

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int n,m,x[3000],y[3000],cnt;
 5 char s[50][50];
 6 
 7 bool check(int x,int a1,int b1,int y,int a2,int b2){
 8     for(int i=min(a1,b1);i<=max(a1,b1);i++)
 9         if(s[x][i]!='B') return 0;
10     for(int i=min(a2,b2);i<=max(a2,b2);i++)
11         if(s[i][y]!='B') return 0;
12     return 1;
13 }
14 
15 int main(){
16     cin>>n>>m;
17     for(int i=0;i<n;i++){
18         cin>>s[i];
19         for(int j=0;j<m;j++)
20             if(s[i][j]=='B') x[++cnt]=i,y[cnt]=j;
21     }
22     for(int i=1;i<cnt;i++)
23         for(int j=i+1;j<=cnt;j++){
24             if(check(x[i],y[i],y[j],y[j],x[i],x[j])) continue;
25             if(check(x[j],y[i],y[j],y[i],x[i],x[j])) continue;
26             cout<<"NO";
27             return 0;
28         }
29     cout<<"YES";
30     return 0;
31 }

【C.k-Multiple Free Set】(A in Div1)

　　http://www.codeforces.com/contest/275/problem/C

　　http://www.codeforces.com/contest/274/problem/A

　　题目大意：从所给数集中找出最大子集，使得子集中不存在x,y，使得y=x*k。求最大子集的大小。

　　我思路大体是这样的。。。

　　首先我把题目抽象成一个图的问题，对于集合中x,x*k，将他们连边，最后图中会形成若干条链，不同的链一定互不干扰，问题转换成在每条链中选取尽量多的点。

　　到这里就可以做了（博主就是这样做的结果时间内存都巨大），但是可以继续想

　　选取尽量多的点的一种方法就是：链头上的点先选，然后隔一个点选一个。这样就有了一种贪心的方法，先将集合中数字排序，然后如果该数可选，就选，不可选就不选。

　　代码1：贪心方法

View Code

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <map>
 4 using namespace std;
 5 
 6 map<long long,bool> m;
 7 int n,ans;
 8 long long k,a[100010];
 9 
10 int main(){
11     cin>>n>>k;
12     for(int i=0;i<n;i++)
13         cin>>a[i];
14     sort(a,a+n);
15     for(int i=0;i<n;i++)
16         if(!m[a[i]]) m[a[i]]=m[a[i]*k]=true;
17     ans=(k==1)?m.size():m.size()/2;
18     cout<<ans;
19     return 0;
20 }

　　代码2：图方法

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <map>
 5 #define mn 100010
 6 #define mm 200020
 7 using namespace std;
 8 typedef long long ll;
 9 
10 map<long long,int> m;
11 int cnt[100010],n,ans,tot;
12 long long k,a[100010];
13 bool vis[100010];
14 
15 struct EDGE{
16     int pnt;
17     EDGE *pre;
18     EDGE(){}
19     EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
20 }Edge[mm],*SP=Edge,*edge[mn];
21 
22 inline void addedge(int a,int b){
23     edge[a]=new(++SP)EDGE(b,edge[a]);
24     edge[b]=new(++SP)EDGE(a,edge[b]);
25 }
26 
27 int dfs(int x){
28     vis[x]=true;
29     for(EDGE *j=edge[x];j;j=j->pre)
30         if(!vis[j->pnt]){
31             cnt[x]+=dfs(j->pnt)    ;
32         }
33     return cnt[x];
34 }    
35 
36 int main(){
37     cin>>n>>k;
38     for(int i=1;i<=n;i++){
39         scanf("%d",&a[i]);
40         cnt[i]=1;
41     }
42     sort(a+1,a+1+n);
43     for(int i=1;i<=n;i++)
44         if(!m[a[i]]) m[a[i]]=++tot;
45     n=tot;
46     for(int i=1;i<=n;i++){
47         int tmp=m[a[i]*k];
48         if(tmp>0) addedge(m[a[i]],tmp);
49     }
50     for(int i=1;i<=n;i++)
51         if(!vis[i]){
52             dfs(i);
53             ans+=(cnt[i]+1)/2;
54         }
55     cout<<ans<<endl;
56     return 0;
57 }

【D.Zero Tree】(B in Div1)

　　http://www.codeforces.com/contest/275/problem/D

　　http://www.codeforces.com/contest/274/problem/B

　　题目大意，给定一棵带权树，每次可以选取包括节点1的一棵子树，使其所有点权±1，问最少操作次数使得所有节点点权为0.

　　显然应该先把叶子节点变成0，然后依次向上做。dfs即可

View Code

 1 #include <iostream>
 2 #define mn 100010
 3 #define mm 200010
 4 using namespace std;
 5 typedef long long ll;
 6 template<class T>inline void gmax(T &a,T b){if(a<b)a=b;}
 7 
 8 struct EDGE{
 9     int pnt;
10     EDGE *pre;
11     EDGE(){}
12     EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
13 }Edge[mm],*SP=Edge,*edge[mn];
14 
15 ll add[mn],sub[mn],w[mn];
16 int n,a,b;
17 
18 inline void addedge(int a,int b){
19     edge[a]=new(++SP)EDGE(b,edge[a]);
20     edge[b]=new(++SP)EDGE(a,edge[b]);
21 }
22 
23 void dfs(int x,int fa){
24     ll t_add=0,t_sub=0;
25     for(EDGE *j=edge[x];j;j=j->pre)
26         if(j->pnt!=fa){
27             dfs(j->pnt,x);
28             gmax(t_add,add[j->pnt]);
29             gmax(t_sub,sub[j->pnt]);
30         }
31     w[x]+=t_add-t_sub;
32     if(w[x]<0) t_add-=w[x];
33     else t_sub+=w[x];
34     add[x]=t_add,sub[x]=t_sub;
35 }
36 
37 int main(){
38     cin>>n;
39     for(int i=1;i<n;i++){
40         cin>>a>>b;
41         addedge(a,b);
42     }
43     for(int i=1;i<=n;i++)
44         cin>>w[i];
45     dfs(1,0);
46     cout<<sub[1]+add[1]<<endl;
47     return 0;
48 }

【E.】The Last Hole!(C in Div 1)

　　http://www.codeforces.com/contest/275/problem/E

　　http://www.codeforces.com/contest/274/problem/C

　　题如其名，最后一题是个坑。。。等会写

【D.Lovely Matrix】(Div 1)

　　http://www.codeforces.com/contest/274/problem/D

　　题目大意：n×m格子，格子有权值，有空格，问是否可以交换某些列的次序，使得每一行上的数字不减。

　　显然是拓扑排序。问题在于数据范围有点大，如果出现权值相同的格子，建图时逐个连边复杂度非常高。我们可以考虑附加点P[x]，使权值为x的点都连向P[x]，然后由P[x]连向比x大的点。

View Code

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <queue>
 4 #define mm 200010
 5 #define mn 400010
 6 using namespace std;
 7 
 8 queue<int> q;
 9 int n,m,ans[mn],deg[mn],cnt,idx;
10 struct REC{int v,p;}a[mn];
11 
12 struct EDGE{
13     int pnt;
14     EDGE *pre;
15     EDGE(){}
16     EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
17 }Edge[mm],*SP=Edge,*edge[mn];
18 
19 inline void addedge(int a,int b){
20     edge[a]=new(++SP)EDGE(b,edge[a]);
21     deg[b]++;
22 }
23 
24 inline bool cmp(REC a,REC b){return a.v<b.v;}
25 
26 int main(){
27     cin>>n>>m;
28     for(int i=0;i<n;i++){
29         for(int j=0;j<m;j++){
30             cin>>a[j].v;
31             a[j].p=j;
32         }
33         sort(a,a+m,cmp);
34         for(int j=0;j<m;j++)
35             if(a[j].v!=-1){
36                 if(!j || a[j].v!=a[j-1].v) cnt++;
37                 addedge(a[j].p,m+cnt+1);
38                 addedge(m+cnt,a[j].p);
39             }
40         cnt++;
41     }
42     for(int i=0;i<m+cnt;i++)
43         if(!deg[i]) q.push(i);
44     while(!q.empty()){
45         int i=q.front();q.pop();
46         if(i<m) ans[++idx]=i;
47         for(EDGE *j=edge[i];j;j=j->pre)
48             if(!--deg[j->pnt]) q.push(j->pnt);
49     }
50     if(idx<m) cout<<-1;
51     else for(int i=1;i<=m;i++) 
52         cout<<ans[i]+1<<" ";
53     return 0;
54 }

【E. Mirror Room】(Div 1)

　　http://www.codeforces.com/contest/274/problem/E

　　题目大意：光线在镜子格里反射，问能经过多少格子。

　　看了liouzhou101大神的代码明白了，其实就是用了一堆map和set然后模拟。。。。

　　好不容易仿照着写出来了，但是今天CF评测机抽风，在第24个点tle，连liouzhou101的代码现在都过不了。。。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <map>
 5 #include <set>
 6 #define x first
 7 #define y second
 8 using namespace std;
 9 typedef pair<int,int> PII;
10 
11 int n,m,k,ans,x,y;
12 set<PII> block,empty_cell;
13 map<PII,set<PII> > vis;
14 PII s,t,dir;
15 char sym[5];
16 
17 int main(){
18     cin>>n>>m>>k;
19     for(int i=0;i<=n+1;i++)
20         block.insert(PII(i,0)),
21         block.insert(PII(i,m+1));
22     for(int i=0;i<=m+1;i++)
23         block.insert(PII(0,i)),
24         block.insert(PII(n+1,i));
25     while(k--){
26         scanf("%d%d",&x,&y);
27         block.insert(PII(x,y));
28     }
29     scanf("%d%d",&s.x,&s.y);
30     scanf("%s",sym);
31     dir=PII(sym[0]=='N'?-1:1,sym[1]=='W'?-1:1);
32     while(true){
33         if(empty_cell.insert(s).y) ans++;
34         t=PII(s.x+dir.x,s.y+dir.y);
35         if(!block.count(t)){
36             s=t;
37             continue;
38         }
39         if(!vis[t].insert(dir).y) break;
40         x=block.count(PII(t.x-dir.x,t.y)),y=block.count(PII(t.x,t.y-dir.y));
41         if (x==y) dir.x=-dir.x,dir.y=-dir.y;
42         else if(x) s.x+=dir.x,dir.y=-dir.y;
43         else s.y+=dir.y,dir.x=-dir.x;
44     }
45     cout<<ans<<endl;
46     return 0;
47 }