诣天诣练02

诣天诣练02"/>

诣天诣练02

A - The Doors CodeForces - 1143A

手速水题，题意关闭完同类型的门，则逃脱，问总共关多少个。

统计个数--即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200100;int n, a[maxn], x, y;
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d", &a[i]);if(a[i]) x++;else y++;}for(int i = 1; i <= n; i++){if(a[i]) x--;else y--;if(!x || !y){printf("%d\n", i);break;}}return 0;
}

B - Nirvana CodeForces - 1143B

有点东西的递归题。

这是第二次做了，第一次做的时候，卡住了一点，处理的时候没有考虑到，只要前面一位-1了后面的都可以是9，然鹅问题就变成了哪一位减一或者减不减一的问题。暴力递归找情况。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 20;long long n, a[maxn], tot;
long long ans;
void dfs(int n, long long x, int flag)
{if(n == 0){ans = max(ans, x);return ;}if(flag) dfs(n - 1, x * 9, 1);else{if(a[n] - 1 != 0)dfs(n - 1, x * (a[n] - 1), 1);else dfs(n - 1, x, 1);dfs(n - 1, x * a[n], 0);}
}
int main()
{scanf("%lld", &n);int b = n;tot = 0;while(b){a[++tot] = b % 10;b /= 10;}dfs(tot, 1, 0);printf("%lld\n", ans);return 0;
}

C. Queen

题意：给你每一行为他的父节点和他的属性。要你删点，下面为1，和隔一个为1的可以删点。

分析简单化  我们就可以对每一个父节点，和它所有的子节点与过后，如果还为1则可以删掉。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;int n, a[maxn], b[maxn], c[maxn], flag;
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d%d", &a[i], &b[i]);c[i] = b[i];}for(int i = 1; i <= n; i++) if(a[i] > 0) c[a[i]] &= b[i];for(int i = 1; i <= n; i++) if(c[i]) printf("%d ", i), flag = 1;if(!flag) printf("-1");printf("\n");return 0;
}

D - The Beatles CodeForces - 1143D 

题意：环形区域上，离起点最近的一个餐馆距离a，离第一次行动后的距离L的距离为b.每次行动L距离停一下，给你餐馆的数量和两个餐馆之间的距离，还有a, b,让你求回到起始点，转的圈数的最小值和最大值。

因为 L的长度有以下4种情况：

L = m * k + a - b

L = m * k - a - b

L = m * k + a + b

L = m * k - a + b

走过的圈数为(n * k) / gcd(n * k, l1);

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, k, a, b, l1, l2, l3, l4, maxx, minn;
ll gcd(ll x, ll y)
{if(y == 0) return x;else return gcd(y, x % y);
}
int main()
{scanf("%lld%lld%lld%lld", &n, &k, &a, &b);maxx = -1; minn = 1e18;for(int i = 1; i <= n; i++){l1 = i * k + a - b; l2 = i * k + a + b;l3 = i * k - a - b; l4 = i * k - a + b;if(l1 > 0){ll r = (n * k) / gcd(n * k, l1);maxx = max(maxx, r); minn = min(minn, r);}if(l2 > 0){ll r = (n * k) / gcd(n * k, l2);maxx = max(maxx, r); minn = min(minn, r);}if(l3 > 0){ll r = (n * k) / gcd(n * k, l3);maxx = max(maxx, r); minn = min(minn, r);}if(l4 > 0){ll r = (n * k) / gcd(n * k, l4);maxx = max(maxx, r); minn = min(minn, r);}}printf("%lld %lld\n", minn, maxx);return 0;
}

E. Lynyrd Skynyrd（倍增）

对于A中的每一个Ai，求出 (Ai在P中的前一个数字)在A中的小于i的最大位置b[i]。比如P是(3,2,1),A是(3,1,2,3)，那对于A中的2来说，求出来的b就是1，对于A中第二个3来说，求出来的b就是2,得到的b为(0,0,1,2)。可以通过记录每一个数字最后出现的位置来求每一个Ai的b[i]。
那对于一个A[i],我们算b[b[b[b[…b[i]]…],套n-1次就可以得到[L,i]这个区间存在以A[i]为结尾的循环右移排列需要的最大的L。直接套的话每一个数字都要算N-1次，是O(n²)的算法，所以我们用倍增的思想，f[i][j]代表第i个数字要得到以它为结尾的长度为2^j的排列所需要的最大的区间左端点L，那么显然f[i][0] = b[i],转移方程为f[i][j+1] = f[ f[i][j] ] [ j ],
然后用g[i]表示最大的L使得[L，i]这个区间存在P的循环右移，然后利用f[i][j]算一下第i个要到前n-1需要的最大的L，转移方程是g[i] = max(g[i-1],L)。
对于每个查询[L,R]，只要判断L是不是比R大就可以知道[L,R]存不存在P的循环右移了。
 

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;int n, m, q, p[maxn], pos[maxn], g[maxn], pre[maxn], a[maxn], f[maxn][30], re[maxn];
int slove(int x, int num)
{for(int i = 20; i >= 0; i--){if((1 << i) & num) x = f[x][i];}return x;
}int main()
{scanf("%d%d%d", &n, &m, &q);for(int i = 1; i <= n; i++) scanf("%d", &p[i]), pre[p[i]] = p[i - 1];pre[p[1]] = p[n];for(int i = 1; i <= m; i++){scanf("%d", &a[i]);pos[a[i]] = i;f[i][0] = pos[pre[a[i]]];for(int j = 0; j <= 20; j++)f[i][j + 1] = f[f[i][j]][j];g[i] = max(g[i - 1], slove(i, n - 1));}int tot = 0;while(q--){int x, y;scanf("%d%d", &x, &y);if(x <= g[y]) re[++tot] = 1;else re[++tot] = 0;}for(int i = 1; i <= tot; i++) printf("%d", re[i]);printf("\n");return 0;
}