# APCS 2019/6 題解
## ==籃球比賽==
### 題目
[籃球比賽](https://zerojudge.tw/ShowProblem?problemid=e286)
### 核心
迴圈
### 思路

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int As1=0,Bs1=0,As2=0,Bs2=0;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            int score;
            scanf("%d",&score);
            if(i<2&&i&1) Bs1+=score;
            else if(i<2) As1+=score;
            else if(i>=2&&i&1) Bs2+=score;
            else As2+=score;
        }
    }
    printf("%d:%d\n%d:%d\n",As1,Bs1,As2,Bs2);
    if(As1>Bs1&&As2>Bs2) printf("Win\n");
    else if(Bs1>As1&&Bs2>As2) printf("Lose\n");
    else printf("Tie\n");
}

## ==機器人的路徑==
### 題目
[機器人的路徑](https://zerojudge.tw/ShowProblem?problemid=e287)
### 核心
二維陣列、模擬
### 思路
邊界設為已探過。

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define oo 1000005
#define int long long
int a[N][N];
bool visit[N][N]={false};
signed main()
{
    int m,n;
    scanf("%lld %lld", &m,&n);
    int imax=oo;
    int si,sj,i,j;
    int di[4]={0,1,0,-1},dj[4]={1,0,-1,0};
    for(j=0; j<=n+1; j++) visit[0][j]=true,visit[m+1][j]=true;
    for(i=0; i<=m+1; i++) visit[i][0]=true,visit[i][n+1]=true;
    for(i=1; i<=m; i++)
    {
        for(j=1; j<=n; j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]<imax)
            {
                imax=a[i][j],si=i,sj=j;
            }
        }
    }
    int total=0;
    while(true)
    {
        total+=a[si][sj];
        visit[si][sj]=true;
        imax=oo;
        for(int dir=0; dir<4; dir++)
        {
            int ni=si+di[dir],nj=sj+dj[dir];
            if(!visit[ni][nj]&&a[ni][nj]<imax)
            {
                i=ni,j=nj,imax=a[ni][nj];
            }
        }
        if(imax==oo) break;
        si=i,sj=j;
    }
    printf("%lld\n",total);
}

## ==互補CP==
### 題目
[互補CP](https://zerojudge.tw/ShowProblem?problemid=e288)
### 核心
map、位元
### 思路
這題後25%真的搞到我了，百思不得其解，後來查了一下才知道要用unorder_map。
還有 all=(((long long)1)<<m)-1，1要先設為long long。
團隊可以邊存邊找，這樣也剛好不會重複計算。

#include<bits/stdc++.h>
using namespace std;
int cvt(char c)
{
    return c<='Z'?c-'A':c-'a'+26;
}
int main()
{
    unordered_map<long long,int> M;
    int n,m;
    scanf("%d%d",&m,&n);
    long long all=(((long long)1)<<m)-1,ans=0;
    for(int i=0;i<n;i++)
    {
        char str[1005];
        scanf("%s",str);
        long long we=0;
        for(int j=0;j<strlen(str);j++) we|=(long long)1<<cvt(str[j]);
        M[we]++;
        ans+=M[we^all];
    }
    printf("%lld\n",ans);
}

## ==美麗的彩帶==
### 題目
[美麗的彩帶](https://zerojudge.tw/ShowProblem?problemid=e289)
### 核心
sliding window、string、map
### 思路
要注意數字大小到10^150^，故用string。

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> M;
int cnt=0,ans=0;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int m,n;
    cin>>m>>n;
    string ribbon[n];
    for(int i=0;i<n;i++) cin>>ribbon[i];
    for(int i=0;i<m;i++)
    {
        if(M[ribbon[i]]==0) cnt++;
        M[ribbon[i]]++;
    }
    if(cnt==m) ans++;
    for(int i=m;i<n;i++)
    {
        if(M[ribbon[i]]==0) cnt++;
        M[ribbon[i]]++;
        if(M[ribbon[i-m]]==1) cnt--;
        M[ribbon[i-m]]--;
        if(cnt==m) ans++;
    }
    cout<<ans<<endl;
}