Codeforces Round #149 (Div. 2)_html/css_WEB-ITnose

这个round真的太简单了。。
A，B就不说了


C  题目说了合法的点不会超过10^5个
那么直接离散化，完了跑bfs就行了

离散化用map就行

#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cstdlib>#include <ctime>#include <set>#include <vector>#include <map>#define MAXN 111#define MAXM 55555#define INF 1000000007using namespace std;int xa, ya, xb, yb;int n;struct node {    int r, x, y;}p[111111];struct P {    int x, y;}f[111111];bool cmp(node x, node y) {    if(x.r != y.r) return x.r  mp;long long getnum(long long x, long long y) {    return x * (long long)INF + y;}int xx[] = {0, 0, 1, -1, 1, 1, -1, -1};int yy[] = {1, -1, 0, 0, -1, 1, -1, 1};int vis[111111];int q[111111];int ans[111111];bool ok(int mv) {    if(!mv) return false;    if(vis[mv]) return false;    return true;}void bfs() {    int h = 0, t = 0;    vis[1] = 1;    q[t++] = 1;    while(h   <br>  <br>  <p></p>  <p>D .  注意题目中  按钮按下会导致的是 直接相邻的点变化，不是间接的</p>  <p>那么有种想法就是。</p>  <p>对于一个状态，如果其中有的点的值是跟a数组相应的值相同。</p>  <p>那么就去按这些点， 按过之后这些点肯定不会再出现跟a中相应的值相同了</p>  <p>用一个队列去搞，每次把需要按的点放到队列里，然后假如按完出现了新的需要按的点，就加入队列尾部</p>  <p>最后如果按完所有的点还是会出现与a中相应值相同的情况</p>  <p>就要输出-1了</p>  <p>为啥这么搞能对， 想一下就知道</p>  <p>对于一个状态，按非法点会导致其变成合法，如果周围有被按过的，那么这些被按过的一定是合法的，再变化也是合法的，</p>  <p>如果周围有的变化成了非法的，那么这些非法的一定还能按，那要是这么想的话，-1的情况实际是不存在的（看数据里好像也没有-1）</p>  <p>按的时候直接邻接表模拟就行了，因为每个点只能被按一次，所以每条边最多访问两次</p>  <p><br> </p>  <p></p>  <pre name="code" class="sycode">#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cstdlib>#include <ctime>#include <set>#include <vector>#include <map>#define MAXN 111#define MAXM 55555#define INF 1000000007using namespace std;vector<int>g[111111], ans;int n, m;int a[111111], q[111111], vis[111111], tmp[111111];int h = 0, t = 0;void gao() {    for(int i = 0; i   <br>  <br>  <p></p>  <p><br> </p>  <p><br> </p>  <p>E  非常老的题， USACO某个题的变种</p>  <p>按位建线段树就是此题了</p>  <p><br> </p>  <p>  </p>  <pre name="code" class="sycode">#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cstdlib>#include <ctime>#include <set>#include <vector>#include <map>#define lch(x) x> 1;    build(b, lson);    build(b, rson);    up(b, rt);}void down(int b, int rt, int l, int r) {    if(cover[b][rt]) {        cover[b][lch(rt)] ^= 1;        cover[b][rch(rt)] ^= 1;        int m = (l + r) >> 1;        sum[b][lch(rt)] = m - l + 1 - sum[b][lch(rt)];        sum[b][rch(rt)] = r - m - sum[b][rch(rt)];        cover[b][rt] = 0;    }}void update(int b, int L, int R, int l, int r, int rt) {    if(L = r) {        cover[b][rt] ^= 1;        sum[b][rt] = r - l + 1 - sum[b][rt];        return;    }    down(b, rt, l, r);    int m = (l + r) >> 1;    if(L  m) update(b, L, R, rson);    up(b, rt);}int query(int b, int L, int R, int l, int r, int rt) {    if(L = r) return sum[b][rt];    down(b, rt, l, r);    int m = (l + r) >> 1;    int ret = 0;    if(L  m) ret += query(b, L, R, rson);    return ret;}int main(){    int op, x, y, z;    scanf("%d", &n);    for(int i = 1; i   <br>  <p></p>  <p><br> </p>  <p> </p> </map></vector></set></ctime></cstdlib></algorithm></cstdio></cstring></iostream>