# APCS 2020/7 題解
## ==購物車==
### <font color="0E81A6">題目</font>
[購物車](https://zerojudge.tw/ShowProblem?problemid=f579)
### <font color="0E81A6">核心</font>
while
### <font color="0E81A6">思路</font>

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,n;
    scanf("%d%d%d",&a,&b,&n);
    int num,ans=0;
    while(n--)
    {
        int aTrue=0,bTrue=0;
        while(scanf("%d",&num))
        {
            if(num==0) break;
            if(num==a) aTrue++;
            else if(num==-a) aTrue--;
            else if(num==b) bTrue++;
            else if(num==-b) bTrue--;
        }
        if(aTrue&&bTrue) ans++;
    }
    printf("%d\n",ans);
}

## ==骰子==
### <font color="0E81A6">題目</font>
[骰子](https://zerojudge.tw/ShowProblem?problemid=f580)
### <font color="0E81A6">核心</font>
struct
### <font color="0E81A6">思路</font>
用struct模擬。

#include<bits/stdc++.h>
using namespace std;
#define N 25
struct dice
{
    int top=1,down=6,fron=4,bac=3,left=5,right=2;
};
int main()
{
    int n,m;
    dice A[N];
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        dice temp=A[a];
        if(b==-1)
        {
            A[a].top=temp.bac;
            A[a].fron=temp.top;
            A[a].down=temp.fron;
            A[a].bac=temp.down;

        }
        else if(b==-2)
        {
            A[a].top=temp.left;
            A[a].left=temp.down;
            A[a].down=temp.right;
            A[a].right=temp.top;
        }
        else
        {
            A[a]=A[b];
            A[b]=temp;
        }
    }
    for(int i=1; i<=n; i++)
    {
        printf("%d ",A[i].top);
    }
}

## ==圓環出口==
### <font color="0E81A6">題目</font>
[圓環出口](https://zerojudge.tw/ShowProblem?problemid=f581)
### <font color="0E81A6">核心</font>
前綴和、二分搜
### <font color="0E81A6">思路</font>

#include <bits/stdc++.h>
using namespace std;
#define N 500010
int p[N];
int main()
{
    int i, n, m;
    scanf("%d%d",&n, &m);
    for (i=0; i<n; i++) scanf("%d", &p[i]);
    for (i=0; i<n; i++) p[n+i] = p[i];
    for (i=1; i<2*n; i++) p[i] += p[i-1];
    int room=0, q;
    for (i=0; i<m; i++)
    {
        scanf("%d", &q);
        if (room != 0) q += p[room-1];
        room = lower_bound(p+room, p+2*n, q)-p;
        room = (room+1)%n;
    }
    printf("%d\n",room);
    return 0;
}

## ==病毒演化==
### <font color="0E81A6">題目</font>
[病毒演化](https://zerojudge.tw/ShowProblem?problemid=f582)
### <font color="0E81A6">核心</font>
dp、tree
### <font color="0E81A6">思路</font>
罕見的三維dp，

#include <bits/stdc++.h>
#define Max 1000000
using namespace std;
int n, m;
int dp[1003][81][6];
map<char, int> get_index = {{'A',1},{'U',2},{'C',3},{'G',4}};
vector<int> child[1003];

int calculate(int idx, int num, int ch){
    if(dp[idx][num][ch] != -1) return dp[idx][num][ch];
    if(child[idx].empty()) return dp[idx][num][ch] = 0;
    dp[idx][num][ch] = 0;
    for(int i: child[idx]){
        int add = Max;
        for(int k = 1; k<=4; k++)
            add = min(add, (calculate(i, num, k) + (k!=ch)));
        dp[idx][num][ch] += add;
    }
    return dp[idx][num][ch];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int root_idx;
    string tmp;
    for(int i = 0, tmpI, tmpJ; i < n; i++){
        cin >> tmpI >> tmpJ;
        if(tmpI == tmpJ) root_idx = tmpI;
        else child[tmpJ].push_back(tmpI);
        cin >> tmp;
        for(int j = 0; j < m; j++){
            for(int k = 1; k <= 4; k++){
                dp[tmpI][j][k] = -1;
                if(tmp[j] != '@' && k != get_index[tmp[j]])
                    dp[tmpI][j][k] = Max;
            }
        }
    }
    int ans = 0;
    for(int j = 0; j< m; j++){
        int little_ans = Max;
        for(int k = 1; k <= 4; k++)
            little_ans=min(little_ans, calculate(root_idx, j, k));
        ans+=little_ans;
    }
    cout<<ans<<'\n';
}