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; }找规律 偶数长度 贡献度 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; }我们按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; }