Skip to content

Instantly share code, notes, and snippets.

@ray2060

ray2060/GESP-Lv7-cpp.md Secret

Last active August 27, 2024 14:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ray2060/3476b18baeceb672160b1388f31dcfea to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ray2060/3476b18baeceb672160b1388f31dcfea to your computer and use it in GitHub Desktop.
Download ZIP
GESP Lv. 7 C++ Code (2023.12-2024.06)
Raw
GESP-Lv7-cpp.md

GESP Lv.7 2023.12-2024.06 C++ Code

商品交易 2023.12 A

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int h[N], ne[N], e[N], idx;
bool st[N];
int dist[N];

void add(int x, int y) {
    e[idx] = y;
    ne[idx] = h[x];
    h[x] = idx ++ ;
}

int main() {
    memset(dist, 0x3f, sizeof dist);
    memset(h, -1, sizeof h);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    int va, vb;
    for (int i = 0; i < n; i ++ ) {
        int x;
        cin >> x;
        if (i == a) va = x;
        if (i == b) vb = x;
    }
    for (int i = 0; i < m; i ++ ) {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }
    queue<int> q;
    q.push(a);
    st[a] = 1;
    dist[a] = 0;
    while (!q.empty()) {
        int tmp;
        tmp = q.front(); q.pop();
        if (tmp == b) {
            break;
        }
        for (int i = h[tmp]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[tmp] + 1) {
                dist[j] = dist[tmp] + 1;
                q.push(j);
            }
        }
    }
    if (dist[b] != INF) {
        cout << vb - va + dist[b] << endl;
    } else {
        cout << "No solution";
    }
    return 0;
}

纸牌游戏 2023.12 B

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e3 + 10;

int n;
int a[N], b[N], c[N];
int f[N][3][N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i < n; i ++ ) {
        cin >> b[i];
        b[i] += b[i - 1];
    }
    for (int i = 1; i <= n; i ++ ) cin >> c[i];
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 0; j <= 2; j ++ ) {
            for (int k = 0; k < n; k ++ ) {
                int score = ((c[i] == j) ? a[i] : (2 * ((c[i] + 3 - j) % 3 - 1) * a[i]));
                if (k == 0) {
                    f[i][j][k] = f[i - 1][j][k] + score;
                } else {
                    int t1 = f[i - 1][0][k + ((j == 0) ? 0 : -1)];
                    int t2 = f[i - 1][1][k + ((j == 1) ? 0 : -1)];
                    int t3 = f[i - 1][2][k + ((j == 2) ? 0 : -1)];
                    f[i][j][k] = max(max(t1, t2), t3) + score;
                }
            }
        }
    }
    int ans = 0xc0c0c0c0;
    for (int j = 0; j <= 2; j ++ ) {
        for (int k = 0; k < n; k ++ ) {
            ans = max(ans, f[n][j][k] - b[k]);
        }
    }
    cout << ans << endl;
    return 0;
}

交流问题 2024.03 A

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 10, M = 4e5 + 10;

int n, m, min_stu;
int h[N], e[M], ne[M], idx;
int c[N];

void add(int u, int v) {
    e[idx] = v;
    ne[idx] = h[u];
    h[u] = idx ++ ;
}

void color(int ver) {
    queue<int> q;
    q.push(ver);
    c[ver] = 0;
    int cnt0 = 1, cnt1 = 0;
    while (!q.empty()) {
        int t = q.front(); q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (!~c[j]) {
                c[j] = 1 - c[t];
                if (c[j]) cnt1 ++ ;
                else cnt0 ++ ;
                q.push(j);
            }
        }
    }
    min_stu += min(cnt0, cnt1);
}

int main() {
    memset(h, -1, sizeof h);
    memset(c, -1, sizeof c);
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i ++ ) {
        if (!~c[i]) {
            color(i);
        }
    }
    cout << min_stu << ' ' << (n - min_stu) << endl;
    return 0;
}

俄罗斯方块 2024.03 B

DFS

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

const int N = 510;
const int dx[] = {0, 0, -1, 1},
          dy[] = {-1, 1, 0, 0};

int n, m;
int g[N][N];
bool st[N][N];
set<string> ans;
string s;

void dfs(int x, int y) {
    for (int i = 0; i < 4; i ++ ) {
        int nx = x + dx[i], ny = y + dy[i];
        
        if (nx < 1 || nx > n || ny < 1 || ny > m)
            continue;
        if (st[nx][ny])
            continue;
        if (g[x][y] != g[nx][ny])
            continue;
        s += i + '0';
        st[nx][ny] = true;
        dfs(nx, ny);
    }
    s += ' ';
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ )
            cin >> g[i][j];
    
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ ) 
            if (!st[i][j]) {
                s.clear();
                st[i][j] = true;
                dfs(i, j);
                ans.insert(s);
            }
    
    cout << ans.size() << endl;
    return 0;
}

BFS

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 510;
const int dx[] = {0, 0, -1, 1},
		  dy[] = {-1, 1, 0, 0};

int n, m;
int g[N][N];
bool st[N][N];
set<string> ans;
string s;

void bfs(int x, int y) {
	queue<PII> q;
	q.push({x, y});
	while (!q.empty()) {
		PII t = q.front(); q.pop();
		int tx = t.first, ty = t.second;
		for (int i = 0; i < 4; i ++ ) {
			int nx = tx + dx[i], ny = ty + dy[i];
			
			if (nx < 1 || nx > n || ny < 1 || ny > m)
				continue;
			if (st[nx][ny])
				continue;
			if (g[tx][ty] != g[nx][ny])
				continue;
			s += i + '0';
			st[nx][ny] = true;
			q.push({nx, ny});
		}
		s += ' ';
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) 
		for (int j = 1; j <= m; j ++ )
			cin >> g[i][j];
	
	for (int i = 1; i <= n; i ++ ) 
		for (int j = 1; j <= m; j ++ ) 
			if (!st[i][j]) {
				s.clear();
				st[i][j] = true;
				bfs(i, j);
				ans.insert(s);
			}
	
	cout << ans.size() << endl;
	return 0;
}

黑白翻转 2024.06 A

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 10;
const int M = 2e5 + 10;

int n, ans;
bool c[N];
int h[N], ne[M], e[M], idx;
int d[N];
bool del[N];

void add(int x, int y) {
    d[x] ++ ;
    e[idx] = y;
    ne[idx] = h[x];
    h[x] = idx ++ ;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> c[i];
        if (c[i] == 0) ans ++ ;
    }
    for (int i = 1; i < n; i ++ ) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    queue<int> q;
    for (int i = 1; i <= n; i ++ ) {
        if (d[i] <= 1 && c[i] == 0) {
            q.push(i), del[i] = true, ans -- ;
        }
    }
    while (!q.empty()) {
        int t = q.front(); q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (--d[j] <= 1 && c[j] == 0 && !del[j]) {
                q.push(j), del[j] = true, ans -- ;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

区间乘积 2024.06 B

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int mp[40] = {
    0, 0, 2, 4, 0, 
    8, 6, 16, 2, 0, 
    10, 32, 4, 64, 18, 
    12, 0, 128, 2, 256,
    8, 20, 34, 512, 6,
    0, 66, 4, 16, 1024, 
    14, 0, 2, 36, 130, 24
};

int n;
LL ans;
LL f[N];
int s[N];

int main() {
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i ++ ) {
        int x;
        cin >> x;
        s[i] = mp[x] ^ s[i - 1];
        ans += f[s[i]]; f[s[i]] ++ ;
    }
    cout << ans;
    return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment