D. Co-growing Sequence
input:
5 4 1 3 7 15 4 1 2 4 8 5 1 2 3 4 5 4 11 13 15 1 1 0
output:
0 0 0 0 0 1 3 7 0 1 0 3 2 0 2 0 14 0
code:
int a[maxn<<1],b[maxn<<1]; int main() { int _ = read; while(_ --){ int n = read; for(int i=1;i<=n;i++){ a[i] = read; if(i >= 2){ int temp = (a[i] | a[i-1]); b[i] = a[i] ^ temp; a[i] = temp; } } for(int i = 1;i <= n;i++){ printf("%d ",b[i]); }puts(""); } return 0; }
E. Air Conditioners
input:
5 6 2 2 5 14 16 10 1 7 30 5 5 3 1 4 2 5 3 1 4 2 5 7 1 1 1000000000 6 3 6 1 3 5 5 5
output:
15 14 15 16 16 17 36 35 34 33 32 31 30 31 32 33 1 2 3 4 5 1000000000 1000000001 1000000002 1000000003 1000000004 1000000005 1000000006 5 6 5 6 6 5
int a[maxn << 1], b[maxn << 1]; typedef pair<int, int> PII; vector<PII> vet; int main() { int _ = read; while(_ --) { memset(b,0x3f3f3f3f,sizeof b); int n = read, m = read; for(int i = 1; i <= m; i++) a[i] = read; for(int i = 1; i <= m; i++) { b[a[i]] = read; } for(int i = 1; i <= n; i++) b[i] = min(b[i], b[i - 1] + 1); for(int i = n - 1; i >= 1; i--) b[i] = min(b[i], b[i + 1] + 1); for(itn i = 1; i <= n; i++) { printf("%d ", b[i]); } puts(""); } return 0; }
另一种做法：
int n, m; struct node{ int u,v,w,nex; }e[maxn]; int head[maxn << 1],cnt,dis[maxn << 1],a[maxn << 1]; bool vis[maxn << 1]; void init(int x){ cnt = 0; for(int i=1;i<=x;i++) head[i] = -1,vis[i] = 0,dis[i] = INF; } void add(int u,int v,int w){ e[cnt].u = u; e[cnt].v = v; e[cnt].w = w; e[cnt].nex = head[u]; head[u] = cnt++; } typedef pair<int,int> PII; void dijkstra(int x){ priority_queue<PII,vector<PII>, greater<PII> > que; dis[x] = 0; vis[x] = 1; que.push({0,x}); while(que.size()){ PII t = que.top();que.pop(); int u = t.second; int w = t.first; vis[u] = 0; for(int i=head[u];~i;i=e[i].nex){ int to = e[i].v; int w = e[i].w; if(dis[to] > dis[u] + w){ dis[to] = dis[u] + w; if(!vis[to]){ que.push({dis[to],to}); } } } } } int main() { int _ = read; while(_ --){ int n = read,k = read; init(n + 1000); int pt = n + 1; for(int i=1;i<=k;i++) a[i] = read; for(int i=1;i<=k;i++){ int w = read; add(pt,a[i],w); } for(int i=1;i<=n;i++){ if(i != 1) add(i,i-1,1); if(i != n) add(i,i+1,1); } dijkstra(pt); for(int i=1;i<=n;i++) printf("%d ",dis[i]); puts(""); } return 0; }
F. Array Stabilization (GCD version)
input:
5 4 16 24 10 5 4 42 42 42 42 3 4 6 4 5 1 2 3 4 5 6 9 9 27 9 9 63
output:
3 0 2 1 1
code:
首先是一个错误的代码，但是可以ac的
int n; int st[maxn][21]; int a[maxn << 1],b[maxn << 1]; int get(int i,int j){ int t = log2(j-i+1); return gcd(st[i][t], st[j-(1<<t)+1][t]); } int main() { int _ = read; while(_ --){ n = read; for(int i=1;i<=n;i++) st[i][0] = st[i+n][0] = a[i+n] = a[i] = read,b[i] = 0; int ans = 0,flag = 0; for(int i=1;i<=n;i++){ if(a[i] != a[1]) flag = 1; } if(!flag) { cout << 0 <<endl; continue; } int gd = a[1]; for(int i=2;i<=n;i++) gd = gcd(gd,a[i]); ///cout << gd <<endl; int lim = 2 * n; for(int j=1;(1<<j) <= lim;j ++){ for(int i=1;i + (1 << j) - 1 <= lim;i ++){ st[i][j] = gcd(st[i][j-1],st[i+(1<<j-1)][j-1]);//错误！！！！！！ } } for(int i=1;i<=n;i++){ int l = i, r = n + i - 1;/// n + i - 1 - i + 1 == n while(l < r){ int mid = l + r >> 1; if(get(i,mid) != gd) l = mid + 1; else r = mid; } ans = max(ans,l-i); } cout << ans <<endl; } return 0; }
正确代码：
int n; int st[maxn][21]; int a[maxn << 1],b[maxn << 1]; int get(int i,int j){ int t = log2(j-i+1); return gcd(st[i][t], st[j-(1<<t)+1][t]); } int main() { int _ = read; while(_ --){ n = read; for(int i=1;i<=n;i++) st[i][0] = st[i+n][0] = a[i+n] = a[i] = read,b[i] = 0; int ans = 0,flag = 0; for(int i=1;i<=n;i++){ if(a[i] != a[1]) flag = 1; } if(!flag) { cout << 0 <<endl; continue; } int gd = a[1]; for(int i=2;i<=n;i++) gd = gcd(gd,a[i]); ///cout << gd <<endl; int lim = 2 * n; for(int j=1;(1<<j) <= lim;j ++){ for(int i=1;i + (1 << j) - 1 <= lim;i ++){ st[i][j] = gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);/// 1 << (j-1) 2 ^j-1^ } } for(int i=1;i<=n;i++){ int l = i, r = n + i - 1;/// n + i - 1 - i + 1 == n while(l < r){ int mid = l + r >> 1; if(get(i,mid) != gd) l = mid + 1; else r = mid; } ans = max(ans,l-i); } cout << ans <<endl; } return 0; }
G. How Many Paths?
input:
5 6 7 1 4 1 3 3 4 4 5 2 1 5 5 5 6 1 0 3 3 1 2 2 3 3 1 5 0 4 4 1 2 2 3 1 4 4 3
output:
1 0 1 2 -1 -1 1 -1 -1 -1 1 0 0 0 0 1 1 2 1
ac_code:
typedef int itn; int n,m,cnt,head[maxn]; int col[maxn],col2[2][maxn]; set<int> s[2]; struct node{ int u,v,nex; }e[maxn]; void init(int x){ cnt = 0; for(int i=0;i<=x + 1;i++) head[i] = -1,col[i] = 0,col2[0][i] = col2[1][i] = 0; } void add(int u,int v){ e[cnt].u = u; e[cnt].v = v; e[cnt].nex = head[u]; head[u] = cnt ++; } void dfs1(int u){ /** value = 0 -> not used value = 1 -> using value = 2 -> used **/ col[u] = 1;/// using for(int i = head[u];~i; i = e[i].nex){ int to = e[i].v; if(col[to] == 0) dfs1(to); else{ int t = col[to]; s[t-1].insert(to); } } col[u] = 2;/// used } void dfs2(int u,int lev){ /** the same like dfs1 value = 0 -> not used value = 1 -> using value = 2 -> used **/ col2[lev][u] = 1; for(int i=head[u];~i;i=e[i].nex){ int to = e[i].v; if(col2[lev][to] == 0) dfs2(to,lev); } col2[lev][u] = 2; } int main() { int _ = read; while(_ --){ n = read, m = read; init(n); s[0] = s[1] = set<int>(); for(int i=1;i<=m;i++){ int u = read,v = read; u--,v--; add(u,v); }///build edge dfs1(0);/// use col for(int i=0;i<=1;i++){ for(auto u: s[i]){ dfs2(u,i); } } for(int i=0;i<n;i++){ int t = 0; if(col[i] != 0){ t = 1; if(col2[0][i]) t = -1; else if(col2[1][i]) t = 2; } printf("%d ",t); } puts(""); } return 0; } /** 5 6 7 1 4 1 3 3 4 4 5 2 1 5 5 5 6 1 0 3 3 1 2 2 3 3 1 5 0 4 4 1 2 2 3 1 4 4 3 **/
