首页 > 代码库 > Codeforces Round #149 (Div. 2)
Codeforces Round #149 (Div. 2)
这个round真的太简单了。。
A，B就不说了
C 题目说了合法的点不会超过10^5个
那么直接离散化，完了跑bfs就行了
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 1000000007
using 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 < y.r;
if(x.x != y.x) return x.x < y.x;
return x.y < y.y;
}
map<long long, int> 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 < t) {
int u = q[h++];
for(int i = 0; i < 8; i++) {
int tx = f[u].x + xx[i];
int ty = f[u].y + yy[i];
int mv = mp[getnum(tx, ty)];
if(ok(mv)) {
ans[mv] = ans[u] + 1;
q[t++] = mv;
vis[mv] = 1;
}
}
}
if(!ans[2]) printf("-1\n");
else printf("%d\n", ans[2]);
}
int main()
{
scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
int idx = 2;
mp[getnum(xa, ya)] = 1;
mp[getnum(xb, yb)] = 2;
f[1].x = xa;
f[1].y = ya;
f[2].x = xb;
f[2].y = yb;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d%d%d", &p[i].r, &p[i].x, &p[i].y);
}
sort(p, p + n, cmp);
for(int i = 0; i < n; i++) {
for(int j = p[i].x; j <= p[i].y; j++) {
long long tmp = getnum(p[i].r, j);
if(!mp[tmp]) {
mp[tmp] = ++idx;
f[idx].x = p[i].r;
f[idx].y = j;
}
}
}
if(xa == xb && ya == yb) {
printf("0\n");
return 0;
}
bfs();
return 0;
}D . 注意题目中 按钮按下会导致的是 直接相邻的点变化，不是间接的
那么有种想法就是。
对于一个状态，如果其中有的点的值是跟a数组相应的值相同。
那么就去按这些点， 按过之后这些点肯定不会再出现跟a中相应的值相同了
用一个队列去搞，每次把需要按的点放到队列里，然后假如按完出现了新的需要按的点，就加入队列尾部
最后如果按完所有的点还是会出现与a中相应值相同的情况
就要输出-1了
为啥这么搞能对， 想一下就知道
对于一个状态，按非法点会导致其变成合法，如果周围有被按过的，那么这些被按过的一定是合法的，再变化也是合法的，
如果周围有的变化成了非法的，那么这些非法的一定还能按，那要是这么想的话，-1的情况实际是不存在的（看数据里好像也没有-1）
按的时候直接邻接表模拟就行了，因为每个点只能被按一次，所以每条边最多访问两次
#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 1000000007
using 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 < t; i++) vis[q[i]] = 1;
while(h < t) {
int u = q[h++];
if(tmp[u] != a[u]) continue;
ans.push_back(u);
tmp[u]++;
for(int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
tmp[v]++;
if(a[v] == tmp[v]) {
if(!vis[v]) {
q[t++] = v;
vis[v] = 1;
}
}
}
}
for(int i = 1; i <= n; i++) {
if(a[i] == tmp[i]) {
printf("-1\n");
return ;
}
}
printf("%d\n", ans.size());
for(int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
}
int main()
{
int u, v;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if(a[i] == 0) {
q[t++] = i;
}
}
if(t == 0) {
printf("0\n");
} else gao();
return 0;
}E 非常老的题， USACO某个题的变种
按位建线段树就是此题了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <set>
#include <vector>
#include <map>
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define MAXN 111111
#define MAXM 55555
#define INF 1000000007
using namespace std;
int n, m;
int cover[20][4 * MAXN];
int sum[20][4 * MAXN], a[20][MAXN];
void up(int b, int rt) {
sum[b][rt] = sum[b][lch(rt)] + sum[b][rch(rt)];
}
void build(int b, int l, int r, int rt) {
if(l == r) {
sum[b][rt] = a[b][l];
return;
}
int m = (l + r) >> 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 <= l && R >= 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, lson);
if(R > 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 <= l && R >= 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, lson);
if(R > m) ret += query(b, L, R, rson);
return ret;
}
int main()
{
int op, x, y, z;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &x);
for(int j = 0; j < 20; j++) {
if(x & (1 << j)) {
a[j][i] = 1;
}
}
}
for(int i = 0; i < 20; i++) build(i, 1, n, 1);
scanf("%d", &m);
for(int i = 0; i < m; i++) {
scanf("%d", &op);
if(op == 1) {
scanf("%d%d", &x, &y);
long long sum = 0;
for(int j = 0; j < 20; j++) {
sum += (long long)(1<<j) * (long long)(query(j, x, y, 1, n, 1));
}
printf("%I64d\n", sum);
} else {
scanf("%d%d%d", &x, &y, &z);
for(int j = 0; j < 20; j++) {
if(z & (1 << j)) {
update(j, x, y, 1, n, 1);
}
}
}
}
return 0;
}
Codeforces Round #149 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。