（7题弟弟。B题知道正解，懒得写了）
A：^&^ HDU - 6702
题意：给出A，B。求一个最小的C，使得min=(A^C)&(B^C)最小。
思路：如果存在A和B都有的位，那么全选，就行了，这时结果min为0； 否则，选最小的那个，一个有，一个没有的那一位p，结果min=1<<p；
#include<bits/stdc++.h> #define ll long long using namespace std; int T; unsigned int A,B,C; template<class T> inline void read(T&a){ char c=getchar(); for(a=0;(c<‘0‘||c>‘9‘)&&c!=‘-‘;c=getchar()); bool f=0;if(c==‘-‘)f=1,c=getchar(); for(;c>=‘0‘&&c<=‘9‘;c=getchar())a=a*10+c-‘0‘; if(f)a=-a; } int main(){ for(read(T);T--;){ read(A),read(B);C=0; for(long long i=1;i<=A&&i<=B;i<<=1) if((i&A)&&(i&B))C|=i; if(!C){ for(long long i=1;i<=A||i<=B;i<<=1) if((i&A)||(i&B)){C|=i;break;} } printf("%u\n",C); } return 0; }
B：array HDU - 6703
题意：有两种操作，第一种单点修改。 第二种，给出(R,K)，查询大于等于K的最小数，满足在a[1,R]中没有出现。 强制在线。
思路：记录每个数出现的最小位置，把它们插入线段树。那么就是在[K,N]中找第一个对应值>R的，所以线段树保存的信息的区间最大值。 这个由于线段树自带二分功能，即如果作区间有Mx>R的，那么在左区间找答案，是否在右区间找； set保存相同数的最小位置； 所以整体的复杂度就是O(NlogN);
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=400010; int a[maxn],Mx[maxn],RR; set<int>s[maxn]; set<int>::iterator it; void read(int &x){ x=0; char c=getchar(); while(c>‘9‘||c<‘0‘) c=getchar(); while(c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘,c=getchar(); } void update(int Now,int L,int R,int pos,int val) { if(L==R){ Mx[Now]=val; return ; } int Mid=(L+R)>>1; if(pos<=Mid) update(Now<<1,L,Mid,pos,val); else update(Now<<1|1,Mid+1,R,pos,val); Mx[Now]=max(Mx[Now<<1],Mx[Now<<1|1]); } int query(int Now,int L,int R,int l,int r,int RR) { int Mid=(L+R)>>1,res=0; if(Mx[Now]<=RR) return 0; if(l<=L&&r>=R) { if(L==R&&Mx[Now]>RR) return L; if(Mx[Now<<1]>RR) return query(Now<<1,L,Mid,l,r,RR); if(Mx[Now<<1|1]>RR) return query(Now<<1|1,Mid+1,R,l,r,RR); return 0; } if(l<=Mid) res=max(res,query(Now<<1,L,Mid,l,r,RR)); if(res) return res; if(r>Mid) res=max(res,query(Now<<1|1,Mid+1,R,l,r,RR)); return res; } int main() { int T,N,M,ans,opt,K,pos; scanf("%d",&T); while(T--){ ans=0; scanf("%d%d",&N,&M); rep(i,1,N) s[i].clear(); rep(i,1,N<<2) Mx[i]=0; rep(i,1,N) read(a[i]); rep(i,1,N) s[a[i]].insert(i); rep(i,1,N){ if(s[i].empty()) continue; int t=*s[i].begin(); update(1,1,N,i,t); } rep(i,1,M){ read(opt); if(opt==1){ read(pos); pos^=ans; if(a[pos]<=N) { it=s[a[pos]].lower_bound(pos); if(it==s[a[pos]].begin()){ s[a[pos]].erase(it); int tmp=N+1; if(!s[a[pos]].empty()) tmp=*s[a[pos]].begin(); if(tmp==N+1) update(1,1,N,a[pos],N+1); else update(1,1,N,a[pos],tmp); } else s[a[pos]].erase(it); a[pos]+=10000000; } } else { read(RR); read(K); RR^=ans; K^=ans; ans=query(1,1,N,K,N,RR); if(ans==0) ans=N+1; printf("%d\n",ans); } } } return 0; }
C：K-th occurrenceHDU - 6704
题意：给定字符串S，Q次询问，每次给出(L,R,K)，让你求S中 str[L,R]这个子串第K次出现的位置。
思路：显然SA的题，可以RMQ出一个区间，满足这个区间的min(ht)>=R-L+1；然后在这个区间主席树求第K大。
代码，稍等两天。
D：path HDU - 6705
题意：给定有向图，然后对走路没有限制，包括起点，终点，是否重复走，都是自由的。 求第K长路径。 K<=5e4；（内存比较小）
思路：显然是个比较水的BFS，可以用优先队列来搞，但是内存不够。所以用multiset，这样如果set.size()>K，可以删除尾巴。 看似O(NlogN)的复杂度，却卡了。
是这样的，如果菊花图，边比较多，那么复杂度就接近(KM)了，显然GG，那么我们可以把后续节点按照边权排序，然后每次取前面几个小的即可。
(即是set里面可以删去尾巴，图里面的G[]的尾巴也可以删一部分。不然很容易GG。
#include<bits/stdc++.h> #define f first #define s second #define ll long long #define pii pair<ll,int> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=250010; int Mx,tot,N,fcy[maxn]; ll ans[maxn]; vector<pair<int,int> >G[maxn]; void read(int &x){ x=0; char c=getchar(); while(c>‘9‘||c<‘0‘) c=getchar(); while(c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘,c=getchar(); } void SPFA() { multiset<pii>q; tot=0;ll FCY=0;int SZ=0; multiset<pii>::iterator it; rep(i,1,N) { for(int j=0;j<G[i].size();j++){ q.insert(make_pair(G[i][j].first,G[i][j].second)); SZ++; if(SZ>Mx) q.erase(--q.end()),SZ--; } } while(SZ){ pii now=*q.begin(); int u=now.second; q.erase(q.begin()); SZ--; ans[++tot]=now.first; if(tot>=Mx) return ; for(int i=0;i<G[u].size();i++){ if(SZ&&SZ+tot==Mx&&now.f+G[u][i].f>(*(--q.end())).f) break; int v=G[u][i].second; q.insert(pii{now.first+G[u][i].first,v}); SZ++; while(SZ>Mx-tot) q.erase(--q.end()),SZ--; } } } int main() { int T,M,Q,u,v,w; scanf("%d",&T); while(T--){ scanf("%d%d%d",&N,&M,&Q); rep(i,1,N) G[i].clear(); Mx=0; rep(i,1,M){ read(u); read(v); read(w); G[u].push_back(make_pair(w,v)); } rep(i,1,N) sort(G[i].begin(),G[i].end()); rep(i,1,Q) { read(fcy[i]); Mx=max(Mx,fcy[i]); } SPFA(); rep(i,1,Q) printf("%lld\n",ans[fcy[i]]); } return 0; }
E： huntian oy HDU - 6706
题意：求题意中的互质对数量。
思路：。
#include <bits/stdc++.h> #include<tr1/unordered_map> #define Accepted 0 using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int maxn = 5e6 + 10; bool not_prime[maxn]; int prime[maxn / 10]; ll phi[maxn]; void init() { int n = 5000000; int tot = 0; not_prime[1] = 1; phi[1] = 1; for(int i = 2; i <= n; i++) { if(!not_prime[i])prime[tot++] = i, phi[i] = i - 1; for(int j = 0; j < tot && 1LL * prime[j] * i <= n; j++) { not_prime[prime[j] * i] = 1; if(i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; break; } else { phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } } phi[1] = 1; for(ll i = 2; i <= n; i++) phi[i] = (i * phi[i] % MOD + phi[i - 1]) % MOD; } tr1::unordered_map<ll, ll>sumphi; const ll inv2 = 500000004; const ll inv6 = 166666668; ll Sum(ll x) { if(x <= 5000000)return phi[x]; if(sumphi[x])return sumphi[x]; ll ans = x * (x + 1) % MOD * (2 * x + 1) % MOD * inv6 % MOD; for(ll l = 2; l <= x; l++) { ll r = x / (x / l); ll tmp = (l + r) * (r - l + 1) % MOD * inv2 % MOD * Sum(x / l) % MOD; ans = (ans + MOD - tmp) % MOD; l = r; } return sumphi[x] = ans; } int main() { init(); int T; scanf("%d", &T); while(T--) { ll n, a, b, ans = 0; scanf("%lld%lld%lld", &n, &a, &b); printf("%lld\n", (Sum(n) + MOD - 1) * inv2 % MOD); } return Accepted; }
F：Shuffle Card HDU - 6707
题意：给定N个数的排列，然后M次操作，每次把给定的数放到排列的最前面。求最后的排列。
思路：如果一个数多次放到前面，那么最后一次是有影响的操作。 所以我们倒叙操作，维护一个queue，如果是第一次操作，就处理，放到队尾。然后把没有操作过的数按原来顺序插入即可。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=200010; int Laxt[maxn],Next[maxn],To[maxn],cnt; void add(int u,int v) { Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; } int a[maxn],vis[maxn],p[maxn],ans[maxn],tot; int main() { int T,N,M; scanf("%d%d",&N,&M); rep(i,1,N) scanf("%d",&a[i]); rep(i,1,M) scanf("%d",&p[i]); for(int i=M;i>=1;i--){ if(vis[p[i]]) continue; ans[++tot]=p[i]; vis[p[i]]=1; } rep(i,1,N) if(!vis[a[i]]) ans[++tot]=a[i]; rep(i,1,N) printf("%d ",ans[i]); return 0; }
原文：https://www.cnblogs.com/hua-dong/p/11407399.html
