---
title: 'AtCoder Beginner Contest 269'
disqus: hackmd
---

AtCoder Beginner Contest 269
===

[TOC]
:::info
直接做，水題
:::
### [A - Anyway Takahashi ](https://atcoder.jp/contests/abc269/tasks/abc269_a)

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define fast ios::sync_with_stdio(0), cin.tie(0)

int main() {
  fast;cout.tie(0);
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  cout<<(a+b)*(c-d)<<endl;
  cout<<"Takahashi";
  return 0;
}

### [B - Rectangle Detection](https://atcoder.jp/contests/abc269/tasks/abc269_b)
:::info
直接做，水題
:::

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define sz(s) (int)s.size()
#define max(p,q)((p)>(q)?(p):(q))
#define fast ios::sync_with_stdio(0), cin.tie(0)

string s[10];
int main() {
  fast;cout.tie(0);
  ll a=-1,b=-1,c=-1,d=-1;
  for(ll i=0;i<10;i++){
    cin>>s[i];
  }
  for(ll i=0;i<10;i++){
    for(ll j=0;j<10;j++){
      if(a==-1 && s[i][j]=='#'){a=i;b=j;}
      if(i+1<10 && j+1<10 && s[i][j]=='#' && s[i+1][j+1]=='.'){c=i;d=j;}
      if(i+1<10 && j+1==10 && s[i][j]=='#' && s[i+1][j]=='.'){c=i;d=j;}
      if(j+1<10 && i+1==10 && s[i][j]=='#' && s[i][j+1]=='.'){c=i;d=j;}
    }
  }
  if(c==-1){c=9;d=9;}
  cout<<a+1<<" "<<c+1<<endl;
  cout<<b+1<<" "<<d+1;
  return 0;
}

### [C - Submask](https://atcoder.jp/contests/abc269/tasks/abc269_c)
:::info
解題關鍵
1. 要用什麼資料結構存這些數字呢?
因為數字不會重複出現，又可以幫忙排序，當然選他阿
2. 通靈for loop 技巧: i = (i-1)&n
可以直接跳過n用二進位表達法有0的位數，同時i可表達成n有的二進位數字的組合。
:::

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
using namespace std;
signed main(){
	fastio
	int n;
	cin >> n;
	set<int> st;
	for(int i = n;i > 0; i = (i-1)&n){
    cout<<i<<endl;
		st.insert(i);//代表那些數字有
	}
	st.insert(0);
	for(auto x : st){
	    cout << x << "\n";
	}
}

### [D - Do use hexagon grid](https://atcoder.jp/contests/abc269/tasks/abc269_d)
:::info
關鍵:
1. 座標有負數，加上夠大的正數(1010)使其為正。
2. 對黑點 i BFS一圈。如果這一圈有黑點j且沒有被BFS過，那就BFS他。(連通就連續BFS)(不連續BFS，測資三不會過)
3. 怎麼檢查j是否為黑點?簡單，直接O(n)檢查是否在陣列裡面，複雜度O($n^2$)也不會爆開
:::

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pll pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define sz(s) (int)s.size()
#define max(p,q)((p)>(q)?(p):(q))
#define fast ios::sync_with_stdio(0), cin.tie(0)
#define N 2020
ll vis[N][N],nx,ny,n;
ll dx[6]={-1,-1,0,0,1,1};
ll dy[6]={-1,0,1,-1,0,1};
vector<pll> np;
void bfs(ll p, ll q){
  for(ll j=0;j<6;j++){
    nx=p+dx[j];
    ny=q+dy[j];
    //cout<<"nx="<<nx<<"ny="<<ny<<endl;
    if(nx>=0 && ny>=0 && !vis[nx][ny]) {
      vis[nx][ny]=1;
      for(ll k=0;k<n;k++){
        if(nx==np[k].F && ny==np[k].S) bfs(nx,ny);//連通就連續BFS
      }
    }
  }
}
int main() {
  fast;cout.tie(0);
  ll cnt=0;
  ll x,y;
  cin>>n;
  for(ll i=0;i<n;i++){
    cin>>x>>y;
    np.pb(mp(x+1010,y+1010));//info 1.
  }
  for(ll i=0;i<n;i++){
    if(vis[np[i].F][np[i].S]==1) bfs(np[i].F,np[i].S);;
    if(!vis[np[i].F][np[i].S]){//沒有被BFS過就BFS他
      vis[np[i].F][np[i].S]=1;
      cnt+=1;//記錄連通塊
      bfs(np[i].F,np[i].S);
    }
  }
  cout<<cnt;
  return 0;
}