Codeforces Round #149 (Div. 2)

C题：给出一些线段，起点和终点，只能在线段上走，线段范围上限为1e9，但是线段的总长不超过1e5.

做法：bfs+map

View Code

 1 /*
 2 Author:Zhaofa Fang
 3 Lang:C++
 4 */
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <sstream>
 8 #include <iostream>
 9 #include <cmath>
10 #include <cstring>
11 #include <algorithm>
12 #include <string>
13 #include <utility>
14 #include <vector>
15 #include <queue>
16 #include <stack>
17 #include <map>
18 #include <set>
19 using namespace std;
20 
21 typedef long long ll;
22 #define DEBUG(x) cout<< #x << ':' << x << endl
23 #define REP(i,n) for(int i=0;i < (n);i++)
24 #define FOR(i,s,t) for(int i = (s);i <= (t);i++)
25 #define PII pair<int,int>
26 #define PB push_back
27 #define MP make_pair
28 #define ft first
29 #define sd second
30 #define lowbit(x) (x&(-x))
31 #define INF (1<<30)
32 
33 PII point;
34 map<PII,int> S,S1;
35 int X0,Y0,X1,Y1;
36 int bfs(void)
37 {
38     S1.clear();
39     queue<PII> Q;
40     Q.push(MP(X0,Y0));
41     S[MP(X0,Y0)] = 0;
42     while(!Q.empty())
43     {
44         int xx = Q.front().ft;
45         int yy = Q.front().sd;
46         Q.pop();
47         FOR(i,-1,1)FOR(j,-1,1)
48         {
49             if(!i && !j)continue;
50             PII next = MP(xx + i,yy + j);
51             if(!S.count(next) || S1.count(next))continue;
52             Q.push(next);
53             S1[next] = S1[MP(xx,yy)] + 1;
54             if(next.ft == X1 && next.sd == Y1)return S1[next];
55         }
56     }
57     return -1;
58 }
59 int main()
60 {
61     //freopen("in","r",stdin);
62     while(cin>>X0>>Y0>>X1>>Y1)
63     {
64         int n;
65         cin>>n;
66         int r,a,b;
67         S.clear();
68         REP(i,n)
69         {
70             cin>>r>>a>>b;
71             FOR(i,a,b)
72             {
73                 S[MP(r,i)]++;
74             }
75         }
76         printf("%d\n",bfs());
77     }
78     return 0;
79 }

D题：每一个节点press一次就会+1，其相邻节点也会+1，每一个节点只能press一次，初始每个节点bi都为0，问press哪些节点

使得最后bi != ai。

做法：如果bi == ai就press，可以用bfs直到所有bi != ai。因为bi只会增加，所以一定有解，复杂度为O(n)。

View Code

 1 /*
 2 Author:Zhaofa Fang
 3 Lang:C++
 4 */
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <sstream>
 8 #include <iostream>
 9 #include <cmath>
10 #include <cstring>
11 #include <algorithm>
12 #include <string>
13 #include <utility>
14 #include <vector>
15 #include <queue>
16 #include <stack>
17 #include <map>
18 #include <set>
19 using namespace std;
20 
21 typedef long long ll;
22 #define DEBUG(x) cout<< #x << ':' << x << endl
23 #define REP(i,n) for(int i=0;i < (n);i++)
24 #define FOR(i,s,t) for(int i = (s);i <= (t);i++)
25 #define PII pair<int,int>
26 #define PB push_back
27 #define MP make_pair
28 #define FI first
29 #define SE second
30 #define lowbit(x) (x&(-x))
31 #define INF (1<<30)
32 
33 vector<int> vec[100005];
34 int X[100005];
35 int a[100005],b[100005];
36 int main()
37 {
38     //freopen("in","r",stdin);
39     int n,m;
40     while(cin>>n>>m)
41     {
42         queue<int> Q;
43         int k = 0;
44         memset(b,0,sizeof(b));
45         while(m --)
46         {
47             int u,v;
48             cin>>u>>v;
49             vec[u].PB(v);
50             vec[v].PB(u);
51         }
52         FOR(i,1,n)
53         {
54             cin>>a[i];
55             if(a[i] == 0)
56             {
57                 Q.push(i);b[i]++;X[k++]=i;
58                 REP(j,vec[i].size())b[vec[i][j]] ++;
59             }
60         }
61         while(!Q.empty())
62         {
63             int x = Q.front();Q.pop();
64             REP(i,vec[x].size())
65             {
66                 int v = vec[x][i];
67                 //DEBUG(v);
68                 //DEBUG(a[v]);DEBUG(b[v]);
69                 if(b[v] == a[v])
70                 {
71                     Q.push(v);
72                     b[v] ++;
73                     X[k++] = v;
74                     REP(j,vec[v].size())b[vec[v][j]]++;
75                 }
76             }
77         }
78         printf("%d\n",k);
79         REP(i,k)printf("%d ",X[i]);
80         puts("");
81     }
82     return 0;
83 }

E题不错

1）区间求和。

2）区间更新，每个数异或X。

做法：把每个数按二进制拆位，故可以建20棵线段树。

View Code

  1 /*
  2 Author:Zhaofa Fang
  3 Lang:C++
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <sstream>
  8 #include <iostream>
  9 #include <cmath>
 10 #include <cstring>
 11 #include <algorithm>
 12 #include <string>
 13 #include <utility>
 14 #include <vector>
 15 #include <queue>
 16 #include <stack>
 17 #include <map>
 18 #include <set>
 19 using namespace std;
 20 
 21 typedef long long ll;
 22 #define DEBUG(x) cout<< #x << ':' << x << endl
 23 #define REP(i,n) for(int i=0;i < (n);i++)
 24 #define FOR(i,s,t) for(int i = (s);i <= (t);i++)
 25 #define PII pair<int,int>
 26 #define PB push_back
 27 #define MP make_pair
 28 #define FI first
 29 #define SE second
 30 #define lowbit(x) (x&(-x))
 31 #define INF (1<<30)
 32 
 33 #define lson l , m , rt<<1
 34 #define rson m + 1 , r , rt<<1|1
 35 
 36 const int maxn = 100111;
 37 int col[maxn<<2];
 38 ll sum[maxn<<2][22];
 39 
 40 void PushUp(int rt)
 41 {
 42     REP(i,21)
 43     sum[rt][i] = sum[rt<<1][i] + sum[rt<<1|1][i];
 44 }
 45 void PushDown(int rt,int m)
 46 {
 47     if(col[rt])
 48     {
 49         col[rt<<1] ^= col[rt];
 50         col[rt<<1|1] ^= col[rt];
 51         REP(i,21)
 52         {
 53             if(col[rt]&1)
 54             {
 55                 sum[rt<<1][i] = m - (m>>1) - sum[rt<<1][i];
 56                 sum[rt<<1|1][i] = (m>>1) - sum[rt<<1|1][i];
 57             }
 58             col[rt] >>= 1;
 59         }
 60     }
 61 }
 62 void build(int l,int r,int rt)
 63 {
 64     REP(i,21)sum[rt][i] = 0;
 65     col[rt] = 0;
 66     if(l == r)
 67     {
 68         int A;
 69         scanf("%I64d",&A);
 70         REP(i,21)
 71         {
 72             sum[rt][i] = (A&1);
 73             A >>= 1;
 74         }
 75         return ;
 76     }
 77     int m = (l + r) >> 1;
 78     build(lson);
 79     build(rson);
 80     PushUp(rt);
 81 }
 82 void updata(int L,int R,int X,int l,int r,int rt)
 83 {
 84     if(L <= l && r <= R)
 85     {
 86         col[rt] ^= X;
 87         REP(i,21)
 88         {
 89             if(X&1)sum[rt][i] = r - l + 1 - sum[rt][i];//0变1,1变0
 90             X>>=1;
 91         }
 92         return ;
 93     }
 94     PushDown(rt,r-l+1);
 95     int m = (l + r) >> 1;
 96     if(L <= m)updata(L,R,X,lson);
 97     if(m < R)updata(L,R,X,rson);
 98     PushUp(rt);
 99 }
100 ll query(int L,int R,int l,int r,int rt)
101 {
102     if(L <= l && r <= R)
103     {
104         ll tmp = 0;
105         REP(i,21)
106         {
107             tmp += sum[rt][i]*(1LL<<i);
108         }
109         return tmp;
110     }
111     PushDown(rt,r-l+1);
112     int m = (l + r) >> 1;
113     ll ret = 0;
114     if(L <= m)ret += query(L,R,lson);
115     if(m < R)ret += query(L,R,rson);
116     return ret;
117 }
118 int main()
119 {
120     //freopen("in","r",stdin);
121     int n;
122     while(~scanf("%d",&n))
123     {
124         build(1,n,1);
125         int m;
126         scanf("%d",&m);
127         int op,l,r,x;
128         while(m--)
129         {
130             scanf("%d",&op);
131             if(op == 1)
132             {
133                 scanf("%d%d",&l,&r);
134                 printf("%I64d\n",query(l,r,1,n,1));
135             }
136             else
137             {
138                 scanf("%d%d%d",&l,&r,&x);
139                 updata(l,r,x,1,n,1);
140             }
141         }
142     }
143     return 0;
144 }