2021暑假康复性训练
Codeforces Round #731 (Div. 3)
A Shortest Path with Obstacle
input
7
1 1
3 3
2 2
2 5
2 1
2 3
1000 42
1000 1
1000 1000
1 10
3 10
2 10
3 8
7 8
3 7
2 1
4 1
1 1
1 344
1 10
1 1
output
4
6
41
4
4
2
334
code:
int main()
{
int _ = read;
while(_ --){
int x1 = read,y1 = read;
int x2 = read,y2 = read;
int tx1 = read,ty1 = read;
int ans = abs(x1 - x2) + abs(y1 - y2);
if(x1 == x2 && x2 == tx1 && ty1 >= min(y1,y2) && ty1 <= max(y2,y1)) ans += 2;
if(y1 == y2 && y2 == ty1 && tx1 >= min(x1,x2) && tx1 <= max(x1,x2)) ans += 2;
printf("%d\n",ans);
}
return 0;
}
B. Alphabetical Strings
input
11
a
ba
ab
bac
ihfcbadeg
z
aa
ca
acb
xyz
ddcba
output:
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
Note
The example contains test cases from the main part of the condition.
code:
int main()
{
int _ = read;
while(_ --){
char str[100];
cin >> (str + 1);
int len = strlen(str + 1);
int l = 1,r = len;
int flag = 0;
for(int i = len;i >= 1;i--){
char c = i + 96;
if(c == str[l]) l ++;
else if(c == str[r]) r --;
else flag = 1;
}
if(flag) puts("NO");
else puts("YES");
}
return 0;
}
/**
**/
C. Pair Programming
input:
5
3 2 2
2 0
0 5
4 3 2
2 0 5
0 6
0 2 2
1 0
2 3
5 4 4
6 0 8 0
0 7 0 9
5 4 1
8 7 8 0
0
output:
2 0 0 5
0 2 0 6 5
-1
0 6 0 7 0 8 0 9
-1
int main()
{
int _ = read;
while(_ --){
int k = read,n = read,m = read;
for(int i=1;i<=n;i++) a[i] = read;
for(int i=1;i<=m;i++) b[i] = read;
int p1 = 1,p2 = 1;
vector<int> vet;
int flag = 0;
while(p1 <= n || p2 <= m){
if(p1 <= n && a[p1] <= k){
if(a[p1] == 0) k++;
vet.push_back(a[p1]);
p1 ++;
}
else if(p2 <= m && b[p2] <= k){
if(b[p2] == 0) k ++;
vet.push_back(b[p2]);
p2 ++;
}
else{
flag = 1;
break;
}
}
if(flag) puts("-1");
else{
int siz = n + m;
for(int i=1;i<=siz;i++){
printf("%d ",vet[i-1]);
}puts("");
}
}
return 0;
}
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
**/