Python 和 C++ 中的 ABC269

0 简介 0-1 关于文章

这是 AtCoder Beginner Contest 269 的解释。该实现是用 Python 和 C++ 编写的。C++ 中的实现在本文末尾。请注意,可能与官方解释存在差异。如果您发现任何错误,请在评论部分告诉我。

1 ABC269 评论 1-1 个人印象

我认为这次的悬崖更陡峭。Diff是A和B早灰,C中灰和棕,D晚棕,E晚绿,F(未解决)是蓝色的前半部分。我在大约 40 分钟内赢得了五冠,Perf 大约为 1450,Rating 为 1162 → 1194 (+32)。我想下水...

1-2 问题 A 无论如何高桥 问题

你得到整数 $A,B,C,D$。请按照以下说明进行操作。

第一行输出$(A+B)×(C-D)$,第二行输出Takahashi。

约束

・$ -100 \leq A,B,C,D \leq 100$・$A,B,C,D$ 是整数

评论

自从我遇到“只是做它”的问题以来已经有很长时间了。如果您了解输出/输入和四种算术运算,您就可以解决它。特别是如果你小心错别字。

执行
A,B,C,D=map(int,input().split())
print((A+B)*(C-D))
print("Takahashi")
1-3 问题 B 矩形检测 问题

通过以下方法生成 $10$ 字符串 $S_1,S_2,...S_{10}$。

・首先,生成$S_i(1 \leq i \leq 10)=.........$。・接下来,生成满足以下所有条件的整数$A、B、C和D$。

$1 \leq A \leq B \leq 10 , 1 \leq C \leq D \leq 10$

然后将 $S_i$ 的第 $j$ 个字符转换为 # 以获得满足以下所有条件的整数集 $(i,j)$。

$A \leq i \leq B , C \leq j \leq D$

给定这样生成的$10$个字符串$S_1,S_2,...S_{10}$,输出生成的整数$A,B,C,D$。

约束

・$|S_i|=10$・$S_i$可以通过上述方法生成

评论

它说“将$S_i$ 的第$j$ 个字符转换为$(i,j)$ 的#”,所以你可以看到它是#。$A,B,C,D$可以通过求所有点的$x$轴和$y$轴(?)的最大值和最小值得到。重点是计算矩形顶点的坐标。

执行
S=[list(input()) for _ in range(10)]

xmx,xmn,ymx,ymn=0,10000,0,10000
for i in range(10):
  for j in range(10):
    if S[i][j]=="#":
      xmx=max(xmx,i)
      xmn=min(xmn,i)
      ymx=max(ymx,j)
      ymn=min(ymn,j)
print(xmn+1,xmx+1)
print(ymn+1,ymx+1)
注意每个值的输出顺序,并使其成为 1-indexed。 1-4 问题 C 子掩码 问题

给定非负整数$N$,按升序输入满足以下条件的所有非负整数$x$。

对于所有非负整数$k$,满足以下条件。

当$N$和$x$都用二进制表示时,如果$x$的$k$位是$1$,那么$N$的$k$位也是$1$。

约束

・$N$ 为整数,满足 $0 \leq N < 2^{60}$・当$N$用二进制数表示时变成$1$的位数为$15$或更少。

评论

例如当$N=10_{(10)}=1010_{(2)}$时,枚举所有$x$

$0000_{(2)}=0_{(10)}$$0010_{(2)}=2_{(10)}$$1000_{(2)}=8_{(10)}$$1010_{(2)}=10_{(10)}$

变成。当 $N$ 用二进制表示时,$1$ 有 $2$ 个数字,所以有 $2^2=4$ 个数字。这意味着有点详尽的搜索。约束还指出“当 $N$ 以二进制表示时,组成 $1$ 的位数为 $15 或更少。”作为 n$,我们得到 $O(2^n)$。

当 $N$ 以二进制表示法表示时,找到 $1$ 的数字,并针对该数字执行 $0$ 或 $1$ 的完整搜索。

执行
N=int(input())

one=[]
for i in range(60):
  if N>>i&1:
    one.append(i)
l=len(one)

for i in range(1<<l):
  now=0
  for j in range(l):
    if i>>j&1:
      now+=(1<<one[j])
  print(now)

可以用作$x$ 的数字总是以升序排列,因此无需将它们存储在数组中并对其进行排序。

位穷举搜索是一种相对频繁的算法。如果您不熟悉它,请以此为契机来习惯位操作。中很详细。

1-5 问题 D 使用六边形网格 问题

我们有一个无限宽的六边形网格。一开始都是白色的。将 $N$ 个正方形 $(X_1,Y_1),(X_2,Y_2),...(X_N,Y_N)$ 涂成黑色。涂黑后,求黑色方块的连通部分有多少。此外,正方形 $(i,j)$ 与下一个正方形相邻。

$(i-1,j-1)$$(i-1,j)$$(i,j-1)$$(i,j+1)$$(i+1,j)$$(i+1,j+1)$

约束

・所有输入都是整数・$1 \leq N \leq 1000$・$|X_i|,|Y_i| \leq 1000$・$(X_i,Y_i)$ 不同

评论

问题是找到连接部分的数量。您可以使用 UnionFind 解决它。当然用DFS也可以解决,但是我觉得UnionFind比较好做,所以推荐UnionFind。这里我们用 UnionFind 来实现它。

遍历一对 2 美元的方块并检查它们是否相邻。如果它们是相邻的,它们应该在UnionFind上连接起来,最后应该输出连接部分的数量。

实施(UnionFind 除外)
N=int(input())
P=[tuple(map(int,input().split())) for _ in range(N)]

U=UnionFind()
for i in range(N):
  U.add(i)

OK={(-1,-1),(-1,0),(0,-1),(0,1),(1,0),(1,1)}
for i in range(N):
  ax,ay=P[i]
  for j in range(i+1,N):
    bx,by=P[j]
    if (ax-bx,ay-by) in OK:
      U.union(i,j)

for i in range(N):
  U.find(P[i])

seen=set()
ans=0
for i in range(N):
  par=U.parent[P[i]]
  if par in seen:
    continue
  seen.add(par)
  ans+=1

print(ans)
可悲的事实不幸的是,Python 中没有 UnionFind 库,所以你必须自己准备 UnionFind。 暂时附上我正在使用的UnionFind的代码。 供你参考。
import sys
sys.setrecursionlimit(10**9)

class UnionFind:
  def __init__(self):
    self.parent={}; self.size={}
  
  def find(self,x): #一番上の親
    if self.parent[x]==x: return x
    else: self.parent[x]=self.find(self.parent[x]); return self.parent[x]
  
  def add(self,x): #頂点の登録
    self.parent.setdefault(x,x); self.size.setdefault(x,1)
  
  def issame(self,x,y): #2頂点が連結しているか
    return self.find(x)==self.find(y)
  
  def union(self,x,y): #頂点の連結
    a,b=self.find(x),self.find(y)
    if a==b: return False
    if self.size[a]>self.size[b]: a,b=b,a
    self.parent[b]=a
    self.size[a]+=self.size[b]
    return True
  
  def size(self,x): #部分木の大きさ
    return self.size[x]
 
 def prt(self,x): #親
    return self.parent[x]
  
  def prtsize(self,x): #頂点の属するグループの要素数
    return self.size[self.find(x)] 

使用 UnionFind 的问题不仅限于图形问题。如果你还没有实现过UnionFind,可以参考我这里的文章来实现。你也可以参考这篇文章。UnionFind的简单解释

1-6 E 问题 Last Rook 问题

这是一个互动问题。有一个棋盘,上面有 $N$ 个方格和 $N$ 个车子。(左起$i$行,上起$j$列表示为$(i,j)$)目前棋盘上有$N-1$个车子,满足以下条件:

・$1$ 垂直列中的车不超过 $2$。・一排$1$的车不超过$2$。

请通过询问以下问题输出 $1$ 的方块,您可以在其中放置一个车。

・选择满足$1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N$的$A,B,C,D$。・求由满足 $A \leq i \leq B, C \leq j \leq D$ 的正方形 $(i,j)$ 组成的矩形区域内的车的数量。

此外,请使用您选择的数字为 $A,B,C,D$ 提出类似? A B C D 的问题。你只能问 20 美元的问题。

约束

・$N$ 为整数,$2 \leq N \leq 10^3$

评论前

这是一个“交互式问题”,程序和裁判程序通过输入和输出进行交互。AtCoder 中的问题由来已久,最近也很少出现。但我被问到了。

评论

问题可以重述如下。

通过提问,您可以了解在指定的矩形范围内存在多少个车。根据$20$次以下的问题,输出没有车的行和列。

如果没有问题的数量限制,即使你问 $N$ 个问题来识别每一行和列,也很容易回答,但考虑到问题数量的限制,这似乎是不可能的。

考虑一个边为 4 美元的棋盘,车的位置如下:此时,左起$1$列有$1$车,左起$2$列有$2$车,左起$3$列有$3-1=2$车,$4$来自左边栏有$4-1=3$。$1、2 和 4$ 列中各有 $1$ 车,但 $3$ 列中有 $0$,因此 i 和 左からi列までに存在するルークの数 在 $3$ 时不相等。

所以这转化为以下问题:

找到i 和左からi列までに存在するルークの数 不相等的边界。

这可以使用二分搜索来解决。我举了一个没有车的列的例子,但是在询问没有车的行时也是如此。左端是0,右端是N,从题中可以解决决策问题“i = 左からi列までに存在するルークの数”。使决策问题false 的最小值i 是要寻求的值。

$1 \leq N \leq 10^3$ 所以我们可以在 $10$ 次内识别列和行。 ($10^3 \leq 2^{10}$) 所以你可以在总共 $20$ 个问题中识别它。这样你就不会遇到数量限制。如果将左端设置为1,当在最左列或顶行有要查找的单元格时,会得到错误的答案,所以要小心。

执行
N=int(input())

x,y=0,0

left,right=0,N
while left+1<right:
  mid=(left+right)//2
  print("?",1,mid,1,N)
  T=int(input())
  if T==mid:
    left=mid
  else:
    right=mid
x=right

left,right=0,N
while left+1<right:
  mid=(left+right)//2
  print("?",1,N,1,mid)
  T=int(input())
  if T==mid:
    left=mid
  else:
    right=mid
y=right

print("!",x,y)
exit()

Diff是1050,比较高,但是你做的和猜年龄的游戏一样(用对数的题数猜你的年龄)。

2 最后

感谢您阅读到最后。这一次,主要关注的是算法和编程中的基本问题。看推特,也有评论说需要整体考虑的问题很少,很无聊。我很高兴这篇文章很容易编辑就这样。感谢您的阅读。有一个良好的职业竞争生活!谢谢你的喜欢...(绝望)

-1 奖金 (woi) 在 C++ 中的实现

我觉得用 C++ 实现的需求很高,所以我也用 C++ 编写了它。将来,我想为 C++Users 做更多的事情。这次对不起。

问题A
#include <bits/stdc++.h>
using namespace std;

int main(){
  int A,B,C,D; cin>>A>>B>>C>>D;
  cout<<(A+B)*(C-D)<<endl;
  cout<<"Takahashi"<<endl;
}
问题 B
#include <bits/stdc++.h>
using namespace std;

#define rep(i,N,M) for(int i=N; i<M; i++)

int main(){
  vector<string> S(10);
  rep(i,0,10){
    cin>>S[i];
  }
  
  int xmn=1000,xmx=0,ymn=1000,ymx=0;
  rep(i,0,10){
    rep(j,0,10)}
      if(S[i][j]=='#'){
        xmn=min(xmn,i+1);
        xmx=max(xmx,i+1);
        ymn=min(ymn,j+1);
        ymx=max(ymx,j+1);
      }
    }
  }
  
  cout<<xmn<<" "<<xmx<<endl;
  cout<<ymn<<" "<<ymx<<endl;
}
问题 C
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,N,M) for(int i=N; i<M; i++)

int main(){
  ll N; cin>>N;
  
  vector<int> one;
  rep(i,0,60){
    if(N>>i&1){
      one.push_back(i);
    }
  }
  
  int l=one.size();
  
  rep(i,0,1<<l){
    ll now=0;
    rep(j,0,l){
      if(i>>j&1){
        now+=1LL<<one[j];
      }
    }
    cout<<now<<endl;
  }
}
问题 D
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

int main(){
  int N; cin>>N;
  vector<vector<int>> P(N,vector<int>(2));
  rep(i,0,N){
    int a,b; cin>>a>>b; a--; b--;
    P[i][0]=a; P[i][1]=b;
  }
  
  dsu U(N);
  rep(i,0,N){
    int ax=P[i][0],ay=P[i][1];
    rep(j,i+1,N){
      int bx=P[j][0],by=P[j][1];
      int n=ax-bx,m=ay-by;
      bool flag=false;
      if(n==-1){
        if(m==-1 or m==0){
          flag=true;
        }
      }else if(n==0){
        if(m==-1 or m==1){
          flag=true;
        }
      }else if(n==1){
        if(m==0 or m==1){
          flag=true;
        }
      }
      if(flag){
        U.merge(i,j);
      }
    }
  }
  
  cout<<U.groups().size()<<endl;
}

ACL 很方便...

电子问题
#include <bits/stdc++.h>
using namespace std;

int main(){
  int N; cin>>N;
  int x,y;
  
  int left=0,right=N;
  while(left+1<right){
    int mid=(left+right)/2;
    cout<<"? "<<1<<" "<<mid<<" "<<1<<" "<<N<<endl;
    int T;
    cin>>T;
    if(T==mid){
      left=mid;
    }else{
      right=mid;
    }
  }
  x=right;
  
  left=0; right=N;
  while(left+1<right){
    int mid=(left+right)/2;
    cout<<"? "<<1<<" "<<N<<" "<<1<<" "<<mid<<endl;
    int T;
    cin>>T;
    if(T==mid){
      left=mid;
    }else{
      right=mid;
    }
  }
  y=right;
  
  cout<<"! "<<x<<" "<<y<<endl;
  return 0;
}

我不太擅长 C++,所以请原谅我。我正在检查是否暂时进行交流,但可能会有无用的行为。

原创声明:本文系作者授权爱码网发表,未经许可,不得转载;

原文地址:https://www.likecs.com/show-308626193.html

102人参与, 0条评论 登录后显示评论回复

你需要登录后才能评论 登录/ 注册