Codeforces Round #469 (Div. 2)
D. A Leapfrog in the Array
题意：n 个数，一开始按图1 放置，每次操作可以把最后的一个数移到最后的一个空格里。有 q 个询问，每次询问有 xi，问最后不能移动时，第 xi 个位置是什么数。
tags：从 xi 位置往后面推，每次移到奇数位置或偶数位置。
// 469 D #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 200005; ll solve(ll flag, ll xi, ll len, ll sum) { if(flag) { if(!(xi&1)) return sum + xi/2; else return solve(!(len&1), (xi+1)/2, (len+1)/2, sum+len/2); } else { if(xi&1) return sum + (xi+1)/2; else return solve(len&1, (xi+1)/2, len/2, sum+(len+1)/2); } } int main() { ll n; int q; scanf("%lld%d", &n, &q); ll xi; while(q--) { scanf("%lld", &xi); printf("%lld ", solve(0, xi, n, 0)); } return 0; }
E. Data Center Maintenance
蛇皮题。。。读了20 分钟题都没读懂。。。
题意：
某公司有 n 个数据中心，有 m 个客户，每个客户的信息都存在两个不同的中心里。 一天有 h 个小时，第 i 个数据中心要在第 i 小时进行维护，期间客户不能从这个中心获取信息。 假设第 i 个客户的信息存在 c1、c2里，题目保证 c1、c2 不会在同一时间维护。
这个公司要做个实验，要选出至少一个中心，把这些中心的维护时间往后推一个小时。 问你最少要选出多少个中心，使得不管在哪个小时，任何客户都可以获取到他们自己的信息。
tasg：强连通缩点
一开始是想把 m 个客户当 m 条边建图，发现做不了。。。
其实我们只要在 m 条边里选择需要的边建图，即 c1和 c2， 如果 (U[c1]+1)%h == U[c2] ，就表明 c1 推后一个小时会和 c2 重合，连边 c1->c2 。
然后就是缩点，最后在缩点后图中找出度为 0 的点，保证 size 最小即可。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 200005; struct SCC { struct Edge { int from, to, next; } e[N]; int dfn[N], low[N]; int head[N], tot, Belong[N], tot1, cnt; vector< int > ans[N]; stack< int > Stack; bool instack[N]; void Addedge(int u, int v) { e[tot] = (Edge){ u, v, head[u] }; head[u]=tot++; } void Init() { mes(head, -1); } void Tarjan(int u) { dfn[u] = low[u] = ++tot1; Stack.push(u); instack[u]=true; for(int i=head[u]; i!=-1; i=e[i].next) { int to = e[i].to; if(dfn[to]==0) { Tarjan(to); low[u] = min(low[u], low[to]); } else if(instack[to]) { low[u] = min(low[u], dfn[to]); } } if(dfn[u] == low[u]) { ++cnt; while(!Stack.empty()) { int End=Stack.top(); Stack.pop(); instack[End] = false; ans[cnt].PB(End); Belong[End] = cnt; if(End == u) break; } } } } scc; int U[N], out[N]; vector< int > ans; int main() { scc.Init(); int n, m, h; scanf("%d%d%d", &n, &m, &h); rep(i,1,n) scanf("%d", &U[i]); int c1, c2; rep(i,1,m) { scanf("%d%d", &c1, &c2); if((U[c1]+1)%h == U[c2]) scc.Addedge(c1, c2); if(U[c1] == (U[c2]+1)%h) scc.Addedge(c2, c1); } rep(i,1,n) if(scc.dfn[i]==0) scc.Tarjan(i); int u, v; rep(i,0,scc.tot-1) { u=scc.e[i].from, v=scc.e[i].to; if(scc.Belong[u] != scc.Belong[v]) { ++out[scc.Belong[u]]; } } int ans1=0; rep(i,1,scc.cnt) { if(out[i]==0) { if(ans1==0) ans1=i; else if(scc.ans[i].size()<scc.ans[ans1].size()) ans1=i; } } printf("%d ", scc.ans[ans1].size()); for(int i : scc.ans[ans1]) printf("%d ", i); return 0; }