2019 ICPC 南昌现场赛 重现（部分）

A. Attack

poj 3123
板子题 斯坦纳树
板子 如下

const int maxm=2009;
const int maxn=39;
const int inf=0x3f3f3f3f;
 
struct Edge{
    int v,w,next;
}edge[maxm];
 
int head[maxn],top;
 
void init(){
    memset(head,-1,sizeof(head));
    top=0;
}
 
void add(int u,int v,int w){
    edge[top].v=v;
    edge[top].w=w;
    edge[top].next=head[u];
    head[u]=top++;
}
 
queue<int> q;
 
int stns[1<<9][maxn];
bool vis[1<<9][maxn];
 
void spfa(int sta){
    int u,v,w;
    while(!q.empty()){
        u=q.front(); q.pop();
        vis[sta][u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next){
            v=edge[i].v;
            w=edge[i].w;
            if(stns[sta][v]>stns[sta][u]+w){
                stns[sta][v]=stns[sta][u]+w;
                if(!vis[sta][v]){
                    vis[sta][v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int can[maxn];//为1表示这个点是点集中的点;
 
int STNS(int n,int id){//所有点数,斯坦纳点个数;
    int MAX=(1<<id)-1;
    memset(stns,0x3f,sizeof(stns));
    for(int i=1;i<=n;++i)
        if(can[i]) stns[(1<<id)-1][i]=0;
    for(int sta=1;sta<=MAX;++sta){
        for(int i=1;i<=n;++i){
            for(int son=sta&(sta-1);son;son=(son-1)&sta)
                stns[sta][i]=min(stns[sta][i],stns[son][i]+stns[sta-son][i]);
            if(stns[sta][i]!=inf&&vis[sta][i]==0){
                q.push(i);
                vis[sta][i]=1;
            }
        }
        spfa(sta);
    }
    int res=inf;
    for(int i=1;i<=n;++i)
        res=min(res,stns[MAX][i]);
    return res;
}

F. Sequence

找规律 偶数长度 贡献度 0
奇数长度 奇数位贡献 1次

#include <iostream>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int data[maxn];
int tree[maxn << 2][2];

void push_up(int rt) {
	tree[rt][0] = tree[rt << 1][0] ^ tree[rt << 1 | 1][0] ;
	tree[rt][1] = tree[rt << 1][1] ^ tree[rt << 1 | 1][1] ;
}

void buid(int l, int r, int rt) {
	if(l == r) {
		if(l % 2 == 0)
			tree[rt][0] = data[l];
		else
			tree[rt][1] = data[l];
		return;
	}
	int mid = l + r >> 1;
	buid(l, mid, rt << 1);
	buid(mid + 1, r, rt << 1 | 1);
	push_up(rt);
}

void update(int L, int d, int l, int r, int rt, int k) {
	if(l == r) {
		tree[rt][k] = d;
		return;
	}
	int mid = l + r >> 1;
	if(L <= mid)
		update(L, d, l, mid, rt << 1, k);
	else
		update(L, d, mid + 1, r, rt << 1 | 1, k);
	push_up(rt);
}

int find(int L, int R, int l, int r, int rt, int k) {
	if(L <= l && R >= r) {
		return tree[rt][k];
	}
	int mid = (l + r) >> 1;
	ll ans = 0;
	if(L <= mid)
		ans ^= find(L, R, l, mid, rt << 1, k);
	if(R > mid)
		ans ^= find(L, R, mid + 1, r, rt << 1 | 1, k);
	return ans;
}

int main() {
	int t;
	scanf("%d", &t);
	int cas = 1;
	while(t --) {
		int n, m;
		scanf("%d %d", &n, &m);
		for(int i = 1; i <= n; i++) scanf("%d", &data[i]);

		buid(1, n, 1);
		printf("Case #%d:\n", cas++);
		while(m--) {
			int cmd, l, r;
			scanf("%d %d %d", &cmd, &l, &r);
			if(cmd == 0)
				if(l % 2 == 0)
					update(l, r, 1, n, 1, 0);
				else
					update(l, r, 1, n, 1, 1);
			else if((r - l + 1) % 2 == 0) printf("0\n");
			else if(l % 2 == 0) printf("%d\n", find(l, r, 1, n, 1, 0));
			else printf("%d\n", find(l, r, 1, n, 1, 1));
		}
	}
	return 0;
}

G. Winner

我们按3个排序 把最大的标记1 然后权值有小到大 不断 扫 把一之后跟新 为1 直到没有跟新退出

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;

struct node {
    int num;
    int val;
    bool operator < (const node &a) const {
        return val < a.val;
    }
} data[maxn], data2[maxn], data3[maxn];
bool vis[maxn];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int a = 0, b = 0, c = 0;
    for(int i = 1; i <= n; i++) {
        data[i].num = i;
        scanf("%d", &data[i].val);
        if(data[i].val > data[a].val) a = i;
    }
    for(int i = 1; i <= n; i++) {
    	data2[i].num = i;
        scanf("%d", &data2[i].val);
        if(data2[i].val > data2[b].val) b = i;
    }
    for(int i = 1; i <= n; i++) {
    	data3[i].num = i;
        scanf("%d", &data3[i].val);
        if(data3[i].val > data3[c].val) c = i;
    }
    vis[a] = vis[b] = vis[c] = 1;
    sort(data + 1, data + 1 + n);
    sort(data2 + 1, data2 + 1 + n);
    sort(data3 + 1, data3 + 1 + n);

    while(1) {
        bool flag = 0;
        bool tt = 0;
        for(int i = 1; i <= n; i++) {
            if(vis[data[i].num] == 1) flag = 1;
            if(flag == 1 && vis[data[i].num] == 0) {
                tt = 1;
				vis[data[i].num] = 1;
            }
        }

        flag = 0;
        for(int i = 1; i <= n; i++) {
            if(vis[data2[i].num] == 1) flag = 1;
            if(flag == 1 && vis[data2[i].num] == 0) {
                tt = 1;
				vis[data2[i].num] = 1;
            }
        }

        flag = 0;
        for(int i = 1; i <= n; i++) {
            if(vis[data3[i].num] == 1) flag = 1;
            if(flag == 1 && vis[data3[i].num] == 0) {
                tt = 1;
				vis[data3[i].num] = 1;
            }
        }
        if(tt == 0) break;
    }

    while(m--) {
        int p;
        scanf("%d", &p);
        if(vis[p] == 1) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}