實作三

邏輯電路

使用：
拓樸

拓樸

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    int p, q, r, m, x, y;
    cin >> p >> q >> r >> m;

    vector<int> type(p + q + r + 1);
    vector<vector<int>> input(p + q + r + 1);
    vector<int> indegree(p + q + r + 1);
    vector<vector<int>> v(p + q + r + 1);
    vector<int> output(p + q + r + 1);
    vector<int> d(p + q + r + 1);
    int maxd = 0;

    for (int i = 1; i <= p; i++) {
        cin >> x;
        input[i].push_back(x);
        output[i] = x;
    }

    for (int i = 1; i <= p; i++) {
        type[i] = -1;  // input gate
    }
    for (int i = p + 1; i <= p + q; i++) {
        cin >> type[i];
    }
    for (int i = p + q + 1; i <= p + q + r; i++) {
        type[i] = 0;  // output gate
    }

    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        indegree[y]++;
    }

    queue<int> que;

    for (int i = 1; i <= p + q + r; i++) {
        if (indegree[i] == 0) {
            que.push(i);
        }
    }

    while (!que.empty()) {
        int f = que.front();
        que.pop();

        if (type[f] == -1 || type[f] == 0) {
            output[f] = input[f][0];
        } else if (type[f] == 1) {
            if (input[f][0] && input[f][1]) {
                output[f] = 1;
            } else {
                output[f] = 0;
            }

        } else if (type[f] == 2) {
            if (input[f][0] || input[f][1]) {
                output[f] = 1;
            } else {
                output[f] = 0;
            }

        } else if (type[f] == 3) {
            if (input[f][0] ^ input[f][1]) {
                output[f] = 1;
            } else {
                output[f] = 0;
            }

        } else if (type[f] == 4) {
            output[f] = !input[f][0];
        }

        for (int i : v[f]) {
            indegree[i]--;
            input[i].push_back(output[f]);

            d[i] = max(d[i], d[f] + 1);
            maxd = max(maxd, d[i]);

            if (!indegree[i]) {
                que.push(i);
            }
        }
    }

    cout << maxd - 1 << "\n";
    for (int i = p + q + 1; i <= p + q + r; i++) {
        cout << output[i] << " ";
    }

    return 0;
}

expandcollapse

搬家

使用：
亂寫-1

亂寫-1

#include<bits/stdc++.h>
using namespace std;
#define N 555
#define nn "\n"
char v[N][N];
vector<int> vv[N];
int g[N][N];
int mag=1;
int n,m;
int sumg[N*N];
bool visit[N*N];
int ma_w[N*N];
int ans;

bool _have(int x,int y){
    if(x<0||x>=n||y<0||y>=m) return false;
    return true;
}

int _outputg(){
    cout<<nn;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<g[i][j];
        }
        cout<<nn;
    }
    cout<<nn;
}

int dfs(int f){
    visit[f]=true;
    ma_w[f]=sumg[f];
    for(int i:vv[f]){
        if(!visit[i]){
            dfs(i);
            ma_w[f]+=ma_w[i];
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>v[i][j];
            g[i][j]=0;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int ma=0;
            if(v[i][j]=='0') continue;
            if(v[i][j]=='X'){
                if(_have(i,j+1)&&(v[i][j+1]=='X'||v[i][j+1]=='H'||v[i][j+1]=='7'||v[i][j+1]=='J')) ma=max(g[i][j+1],ma);
                if(_have(i,j-1)&&(v[i][j-1]=='X'||v[i][j-1]=='H'||v[i][j-1]=='L'||v[i][j-1]=='F')) ma=max(g[i][j-1],ma);
                if(_have(i-1,j)&&(v[i-1][j]=='X'||v[i-1][j]=='I'||v[i-1][j]=='7'||v[i-1][j]=='F')) ma=max(g[i-1][j],ma);
                if(_have(i+1,j)&&(v[i+1][j]=='X'||v[i+1][j]=='I'||v[i+1][j]=='L'||v[i+1][j]=='J')) ma=max(g[i+1][j],ma);
            }
            if(ma==0){
                g[i][j]=mag;
                sumg[mag]++;
                mag++;
            }else{
                g[i][j]=ma;
                sumg[ma]++;
            }
        }
    }
    for(int i=1;i<=mag;i++){
        if(!visit[i]){
            dfs(i);
        }
    }
    for(int i=1;i<=mag;i++){
        ans=max(ans,ma_w[i]);
    }
    cout<<ans;
}

expandcollapse

磁軌移動序列

使用：
遞迴

遞迴

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int idx=0;
string track;

ll seq(int &head, int &tail) {
    ll total = 0, t;
    head = tail = -1;
    while (true) {
        if (idx >= track.length()) return total;
        if (track[idx]=='T') {
            t = stoi(track.substr(idx+1,2));
            idx += 3;
            if (tail < 0) head = t;
            else total += abs(tail-t);
            tail = t;
        } else if (track[idx]=='L') {
            t = stoi(track.substr(idx+1,1));
            idx += 2;
            int h,e;
            ll cost = seq(h,e);
            if (tail < 0) head = h;
            else total += abs(tail-h);
            tail = e;
            total += cost*t+abs(h-e)*(t-1);
        } else {
            idx += 1;
            return total;
        }
    }
}

int main() {
    int xx,i,j;
    cin >>track;
    ll total = seq(i,j);
    total += abs(10-i);
    cout << total <<endl;
    return 0;
}

expandcollapse

先加後乘與函數

使用：
鏈結

鏈結

#include <bits/stdc++.h>
using namespace std;
#define nn "\n"
#define N 555
#define int long long

struct li {
    int L;
    int R;
    char value_char;
    int value_int;
};

struct st {
    int power = 0;
    int index = 0;
};

bool cmp(st a, st b) {
    if (a.power == b.power) {
        return a.index < b.index;
    }
    return a.power > b.power;
}

vector<li> lis;
vector<st> prio;

int del(int x, int y) {
    int pr = lis[x].L;
    int ne = lis[y].R;
    lis[pr].R = ne;
    lis[ne].L = pr;
}

void out() {
    int w = 0;
    while (1) {
        if (lis[w].value_char != 'n') {
            cout << lis[w].value_char << " ";
        } else {
            cout << lis[w].value_int << " ";
        }
        w = lis[w].R;
        if (w == -1) break;
    }
    cout << nn;
}

#undef int
int main() {
#define int long long
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    s = s + 'e';
    int it = 1, t = 0, num = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            t += 3;
            lis.push_back({lis.size() - 1, lis.size() + 1, s[i]});
            it++;
        } else if (s[i] == ')') {
            t -= 3;
            lis.push_back({lis.size() - 1, lis.size() + 1, s[i]});
            it++;
        } else if (s[i] == 'f') {
            lis.push_back({lis.size() - 1, lis.size() + 1, s[i]});
            prio.push_back({t + 3, lis.size() - 1});
            it++;
        } else if (s[i] == '*') {
            lis.push_back({lis.size() - 1, lis.size() + 1, s[i]});
            prio.push_back({t + 1, lis.size() - 1});
            it++;
        } else if (s[i] == '+') {
            lis.push_back({lis.size() - 1, lis.size() + 1, s[i]});
            prio.push_back({t + 2, lis.size() -1});
            it++;
        } else if (s[i] == ',' || s[i] == 'e') {
            lis.push_back({lis.size() - 1, lis.size() + 1, s[i]});
        } else {
            num *= 10;
            num += s[i] - '0';
            if (!isdigit(s[i + 1])) {
                it++;
                lis.push_back({lis.size() - 1, lis.size() + 1, 'n', num});
                num = 0;
            }
        }
    }
    lis[lis.size() - 1].R = -1;
    sort(prio.begin(), prio.end(), cmp);
    for (st i : prio) {
        int it = i.index;
        if (lis[it].value_char == '+') {
            int pr = lis[it].L;
            int ne = lis[it].R;
            lis[pr].value_char = 'n';
            lis[pr].value_int += lis[ne].value_int;
            del(it, ne);
        } else if (lis[it].value_char == '*') {
            int pr = lis[it].L;
            int ne = lis[it].R;
            lis[pr].value_char = 'n';
            lis[pr].value_int *= lis[ne].value_int;
            del(it, ne);
        } else if (lis[it].value_char == 'f') {
            int ma = -1, mi = 201, ne = lis[it].R, on = lis[ne].R;
            while (lis[on].value_char == 'n') {
                ma = max(ma, lis[on].value_int);
                mi = min(mi, lis[on].value_int);
                on = lis[lis[on].R].R;
            }
            int mami = (ma == -1 || mi == 201) ? 0 : ma - mi;
            lis[it].value_char = 'n';
            lis[it].value_int = mami;
            del(ne, lis[on].L);
        }
    }
    cout << lis[0].value_int;
}

expandcollapse

遞迴

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int idx=0;
string track;
// return cost and head and tail
ll seq(int &head, int &tail) {  //回傳頭尾
    ll total = 0, t;  //total回傳長度 、 尾部變數
    head = tail = -1; //頭尾
    while (true) {
        if (idx>=track.length()) return total; //如果超出範圍


        if (track[idx]=='T') {   //如果掃到T
            t = stoi(track.substr(idx+1,2)); //t為後一個數字
            idx += 3;   //往後3個

            if (tail<0) head = t;        //如果還沒有頭尾，就把頭確定好
            else total += abs(tail-t);   //中間長度增加
            tail = t;     //尾巴數字

        } 
        
        else if (track[idx]=='L') {  //如果掃到L
            t = stoi(track.substr(idx+1,1));   //t為後一個數字
            idx += 2;    //往後2個

            int h,e;       //L內的頭尾數字
            ll cost = seq(h,e);  //內部總計

            if (tail<0) head = h;  //如果還沒有頭尾，就把頭確定好
            else total += abs(tail-h); //加總頭尾
            tail = e;     //尾巴數字


            total += cost*t+abs(h-e)*(t-1);  //中間*t次， 頭接尾*(t-1)次


        } else { // E
            idx += 1;
            return total;
        }
    }
}

int main() {
    int xx,i,j;
    cin >>track;    // 輸入文字
    ll total = seq(i,j);   //開始遞迴
    total += abs(10-i);   //因為起點是10，所以加上與起點距離
    cout << total <<endl;
    return 0;
}

expandcollapse

石窟探險

雷射測試

數位占卜

生產線

幸運數字

切割費用

勇者修煉

圓環出口

使用：
取餘數

取餘數

#include <bits/stdc++.h>
using namespace std;
#define nn "\n";
#define int long long
#define N 400004

int n, m, x;
vector<int> v;
vector<int> w;
vector<int> p;

int vv(int x) {
    if (x < 0) return 0;
    return p[x];
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> x;
        v.push_back(x);
    }

    for (int i = 0; i < m; i++) {
        cin >> x;
        w.push_back(x);
    }

    for (int i = 0; i < n; i++) {
        v.push_back(v[i]);
    }

    p.push_back(v[0]);
    for (int i = 1; i < v.size(); i++) {
        p.push_back(p[i - 1] + v[i]);
    }

    int it = 0;
    for (int i : w) {
        x = i;
        it = (distance(p.begin(), lower_bound(p.begin(), p.end(), x + vv(it - 1))));
        it = (it + 1) % n;
    }
    cout << it;
}

expandcollapse

砍樹

使用：
鏈結 AC (35ms, 3.9MB)

鏈結 AC (35ms, 3.9MB)

#include<bits/stdc++.h>
using namespace std;
#define nn  "\n"

struct li{
    int L;
    int R;
    int index;
    int w;
};
int n,m,head,sum=0,ma=0;
vector<li>lis;

void del(int inde){
    int LL=lis[inde].L;
    int RR=lis[inde].R;
    lis[LL].R=RR;
    lis[RR].L=LL;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    head=0;
    lis.push_back({-1,1,0});
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        lis.push_back({i-1,i+1,x});
    }
    lis.push_back({n,-1,m});
    lis[0].w=m+2;
    lis[n+1].w=m+2;
    for(int i=1;i<=n;i++){
        cin>>lis[i].w;
    }
    queue<int>q;
    int it=1;
    while(1){
        int ind_L=lis[it].L;
        int ind_R=lis[it].R;
        if(ind_L!=-1 && lis[ind_L].index <= lis[it].index-lis[it].w){
            del(it);
            sum++;
            ma=max(ma,lis[it].w);
            it=lis[it].L;
        }
        else if(ind_R!=-1 && lis[ind_R].index >= lis[it].index+lis[it].w){
            del(it);
            sum++;
            ma=max(ma,lis[it].w);
            it=lis[it].L;
        }
        else{
            it=lis[it].R;
        }
        if(it==-1){
            break;
        }
    }
    cout<<sum<<nn<<ma;
    return 0;
}

expandcollapse

傳送點/闖關路線

使用：
BFS

BFS

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"

vector<int>v;
vector<int>d;
vector<bool>vis;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,en,l,r;
    cin>>n>>en>>l>>r;
    v.resize(n);
    d.resize(n);
    vis.resize(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    queue<int>q;
    q.push(0);
    vis[0]=true;
    while(!q.empty()){
        int f=q.front();
        q.pop();
        if(f==en){
            cout<<d[f];
            return 0;
        }
        if(f-l>=0 && f-l<n){
            int i=v[f-l];
            if(i>=0 && i<n && !vis[i]){
                vis[i]=true;
                d[i]=d[f]+1;
                q.push(i);
            }
        }
        if(f+r>=0 && f+r<n){
            int i=v[f+r];
            if(i>=0 && i<n && !vis[i]){
                vis[i]=true;
                d[i]=d[f]+1;
                q.push(i);
            }
        }
    }
    cout<<-1;
    return 0;
}

expandcollapse

互補CP

使用：
位元運算

位元運算

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"

int n, m;

int makebit(string s) {
    int re = 0;
    for (int i = 0; i < s.size(); i++) {
        int bit = 1 << (s[i] - 'A');
        re = re | bit;
    }
    return re;
}

int main() {
    set<int> se;
    int ans = 0;
    cin >> n >> m;
    int b = (1 << n) - 1;
    string s;
    for (int i = 0; i < m; i++) {
        cin >> s;
        se.insert(makebit(s));
        if (se.find(b ^ makebit(s)) != se.end()) {
            ans++;
        }
    }
    cout << ans;
}

expandcollapse

函數運算式求值

使用：
ap325解

ap325解

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"

int a() {
    char c[5];
    cin >> c;
    if (c[0] == 'f') {
        return 2 * a() - 3;
    } else if (c[0] == 'g') {
        return 2 * a() + a() - 7;
    } else if (c[0] == 'h') {
        return 3 * a() - 2 * a() + a();
    } else {
        return atoi(c);
    }
}

int main() {
    cout << a();
}

expandcollapse

DF-expression

使用：
遞迴

遞迴

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

long long ans = 0;
long long it = 0;
string s;

long long cut(long long n) {
    if (it == s.size()) return 0;
    for (long long i = 0; i < 4; i++) {
        if (s[it] == '2') {
            it++;
            cut(n / 2);
        } else if (s[it] == '1') {
            ans += n * n;
            it++;
        } else {
            it++;
        }
    }
    return 0;
}

int main() {
    cin >> s;
    long long n;
    cin >> n;
    cut(n);
    cout << ans;
}

expandcollapse

支點切割

樹狀圖分析

使用：
DFS

DFS

#include<bits/stdc++.h>
using namespace std;
#define N 100111

vector<long long> v[N];
bool notroot[N];
long long d[N];

long long dfs(long long f) {
    for (long long i : v[f]) {
        dfs(i);
        d[f] = max(d[f], d[i] + 1);
    }
}

int main() {
    long long n;
    cin >> n;
    for (long long i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        for (long long j = 0; j < x; j++) {
            long long s;
            cin >> s;
            notroot[s] = true;
            v[i].push_back(s);
        }
    }
    for (long long i = 1; i <= n; i++) {
        if (!notroot[i]) {
            cout << i << endl;
            dfs(i);
            break;
        }
    }
    long long ans = 0;
    for (long long i = 1; i <= n; i++) {
        ans += d[i];
    }
    cout << ans;
}

expandcollapse

數字龍捲風

使用：
單純迴圈

程式碼 單純迴圈

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

#define nn "\n"

int v[60][60];
int n, m, t;

int tt() {
    t += 1;
    t %= 4;
}

int main() {
    cin >> n >> m;
    t = m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> v[i][j];
        }
    }

    int toi[4] = {0, -1, 0, 1};
    int toj[4] = {-1, 0, 1, 0};

    int x = n / 2, y = n / 2;
    int d = 1;

    cout << v[x][y];
    while (d < n) {
        int w = 2;
        if (d == n - 1) {
            w = 3;
        }
        for (int i = 0; i < w; i++) {
            for (int go = 0; go < d; go++) {
                x += toi[t];
                y += toj[t];
                cout << v[x][y];
            }
            tt();
        }
        d++;
    }
}

expandcollapse

定時K彈

使用：
約瑟夫問題

約瑟夫問題

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

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ans = 0, n, m, k;
    cin >> n >> m >> k;
    for (int i = n - k + 1; i <= n; i++) ans = (ans + m) % i;
    cout << ans + 1 << '\n';
    return 0;
}

expandcollapse

線段覆蓋長度

使用：
Gready

Gready

#include <bits/stdc++.h>
using namespace std;
#define N 10000
#define nn "\n"

struct st {
    int x, y;
};

bool cmp(st a, st b) {
    return a.x < b.x;
}

int main() {
    int n;
    cin >> n;
    st v[N];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> v[i].x >> v[i].y;
    }

    sort(v, v + n, cmp);

    ans += v[0].y - v[0].x;
    int p_head = v[0].x;
    int p_tail = v[0].y;

    for (int i = 1; i < n; i++) {
        int head = v[i].x;
        int tail = v[i].y;

        if (p_tail < head) {  // No overlap
            ans += tail - head;
            p_head = v[i].x;
            p_tail = v[i].y;
        } else if (p_tail >= head && p_tail < tail) {  // Overlap, update tail
            ans += tail - p_tail;
            p_head = v[i].x;
            p_tail = v[i].y;
        }
    }
    cout << ans;
}

expandcollapse