新隊伍一起的第一場正式練習，表現還算可以啦。只是很久沒三人共用一台電腦，實在有點卡卡的。
討論熱烈，希望可以維持。
線性掃過去，遇到三的倍數就累加。
1#include <bits/stdc++.h>
2
3using namespace std;
4
5typedef long long ll;
6
7void solve()
8{
9 int n;
10 scanf("%d", &n);
11
12 ll ans = 0;
13 for(int i = 1; i <= n; i++)
14 if(i % 3 == 0)
15 ans += i;
16 printf("%lld\n", ans);
17}
18
19int main()
20{
21 int ncase;
22 scanf("%d", &ncase);
23 while(ncase--)
24 solve();
25
26 return 0;
27}問問隊友 黃鈺程 陳煒杰
1m = int(input())
2for _ in range(m):
3 data = [0 for _ in range(10001)]
4 n = int(input())
5 for _ in range(n):
6 a, b = map(int, input().split())
7 for i in range(a, b):
8 data[i] = 1
9 print(sum(data))基本上掌握對於 1-based 的 complete binary tree index 的性質即可:
IO有點麻煩，各自實現吧！
1#include <bits/stdc++.h>
2
3using namespace std;
4
5typedef long long ll;
6
7#define lc(i) (i*2)
8#define rc(i) (i*2+1)
9
10void solve()
11{
12 int C;
13 scanf("%d", &C);
14
15 char inp[111];
16 scanf("%s", inp);
17
18 int len = strlen(inp);
19 // printf("%s\n", inp);
20
21 int tree[111], idx = 1;
22 for(int i = 0; i < len; i++) {
23 if(inp[i] == '(') {
24 int num;
25 sscanf(inp + i + 3, "%d", &num);
26 // printf("%s\n", inp + i);
27
28 tree[idx] = num;
29 idx++;
30 }
31 }
32
33 /*
34 for(int i = 1; i < idx; i++)
35 printf("%d %d\n", i, tree[i]);
36 */
37
38 vector<string> ans;
39 for(int i = 1; i < idx; i++) {
40 if(lc(i) < idx && abs(tree[i] - tree[lc(i)]) <= C) {
41 string tmp = "";
42 tmp += 'A' + (i - 1);
43 tmp += 'A' + (lc(i) - 1);
44
45 ans.push_back(tmp);
46 }
47
48 if(rc(i) < idx && abs(tree[i] - tree[rc(i)]) <= C) {
49 string tmp = "";
50 tmp += 'A' + (i - 1);
51 tmp += 'A' + (rc(i) - 1);
52
53 ans.push_back(tmp);
54 }
55
56 }
57
58 sort(ans.begin(), ans.end());
59 for(int i = 0; i < (int)ans.size(); i++) {
60 printf("%s%c", ans[i].c_str(), i == (int)ans.size() - 1 ? '\n' : ' ');
61 }
62}
63
64int main()
65{
66 int ncase;
67 scanf("%d", &ncase);
68 while(ncase--)
69 solve();
70
71 return 0;
72}問問隊友 黃鈺程 陳煒杰
1#include <bits/stdc++.h>
2using namespace std;
3
4#define st first
5#define nd second
6
7typedef pair<int, int> pii; // <d, v>
8struct Edge {
9 int to, w;
10};
11
12const int MAX_V = 1000;
13const int INF = 0x3f3f3f3f;
14
15int V; // V, Source
16vector<Edge> g[MAX_V];
17int d[MAX_V][MAX_V];
18
19void dijkstra(int S) {
20 fill(d[S], d[S] + V, INF);
21 priority_queue< pii, vector<pii>, greater<pii> > pq;
22
23 d[S][S] = 0;
24 pq.push(pii(0, S));
25
26 while (!pq.empty()) {
27 pii top = pq.top(); pq.pop();
28 int u = top.nd;
29
30 if (d[S][u] < top.st) continue;
31
32 // for (const Edge& e : g[u]) {
33 for (size_t i = 0; i < g[u].size(); i++) {
34 const Edge& e = g[u][i];
35 if (d[S][e.to] > d[S][u] + e.w) {
36 d[S][e.to] = d[S][u] + e.w;
37 pq.push(pii(d[S][e.to], e.to));
38 }
39 }
40 }
41}
42
43int main() {
44 int N, M;
45 scanf("%d", &N);
46 scanf("%d", &M);
47 for (int u = 0; u < M; u++) {
48 for (int v = 0; v < M; v++) {
49 int w; scanf("%d", &w);
50 g[u].push_back(Edge{v, w});
51 }
52 }
53 V = M;
54 for (int i = 0; i < N; i++) {
55 int p, q; scanf("%d %d", &p, &q);
56 dijkstra(p);
57 printf("%d\n", d[p][q]);
58 }
59 return 0;
60}比賽時想不出數學解，只好暴力去做，畢竟 $m, n$ 都至多 15而已。
枚舉所有的可能放的數量，且只要枚舉 non-decreasing order 的數列來做排列組合即可。
舉例而言，$m = 4, n = 2$的話，我們枚舉
但是 $3, 1$ 等等不枚舉，因為這個數列不是 non-decreasing order。
有了數列 $a_1, a_2, …, a_n$，之後就…
$C(m, a_1) * C(m - a_1, a_2) * … * C(m - a_1 - a_2 - … - a_{n - 1}, a_n)$
記得，如果有多於一個相同的 $a_i$ 值，要除上 $(相同a_i個數)!$ ，因為我們不管排列方式。
對於全部數列都累加上述算式即可。
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5
6ll dp[16][16];
7ll C(ll a, ll b) {
8 if(dp[a][b] != -1)
9 return dp[a][b];
10 ll ans = 1;
11 for (int i = 1; i <= b; i++) {
12 ans = ans * (a - i + 1);
13 ans = ans / i;
14 }
15 return dp[a][b] = ans;
16}
17
18ll ans = 0;
19
20ll factorial[16];
21
22int sz[16];
23
24int total = 0;
25void dfs(int partition, int depth, int rem)
26{
27 if(rem <= 0)
28 return;
29
30 if(depth == partition - 1) {
31 // get last partition
32 if(depth != 0 && rem < sz[depth - 1])
33 return;
34
35 sz[depth] = rem;
36
37 // for(int i = 0; i < partition; i++)
38 // printf("%d%c", sz[i], i == partition - 1 ? '\n' : ' ');
39 // get ans
40 int sum = total;
41 ll tmp = 1;
42
43 int acc[16] = {0};
44 for(int i = 0; i < partition; i++) {
45 tmp *= C(sum, sz[i]);
46 acc[sz[i]]++;
47 sum -= sz[i];
48 }
49 // printf("tmp = %lld\n", tmp);
50
51 for(int i = 0; i < 16; i++) {
52 if(acc[i] > 1)
53 tmp /= factorial[acc[i]];
54 }
55 // printf("tmp = %lld\n", tmp);
56
57 ans += tmp;
58
59 return;
60 }
61
62 int i;
63 if(depth == 0) {
64 i = 1;
65 } else {
66 i = sz[depth - 1];
67 }
68
69 for(; i <= rem; i++) {
70 if(depth != 0 && i < sz[depth - 1])
71 continue;
72 sz[depth] = i;
73 dfs(partition, depth + 1, rem - i);
74 }
75}
76
77void solve(int num_cnt, int partition)
78{
79 // printf("%d %d\n", num_cnt, partition);
80 ans = 0;
81
82 total = num_cnt;
83 dfs(partition, 0, num_cnt);
84
85 // printf("ans = %lld\n", ans);
86 printf("%lld\n", ans);
87}
88
89int main() {
90 int TC; scanf("%d", &TC);
91 memset(dp, -1, sizeof(dp));
92
93 factorial[1] = 1;
94 for(int i = 2; i <= 15; i++) {
95 factorial[i] = factorial[i - 1] * i;
96 }
97
98 while (TC--) {
99 int m, n;
100 scanf("%d,%d", &m, &n);
101
102 solve(m, n);
103 }
104
105 return 0;
106}問問隊友 _陳煒杰_，聽說範測看完就解了！
1#include <bits/stdc++.h>
2using namespace std;
3
4int main(){
5 int n;
6 scanf(" %d", &n);
7 for (int i = 0; i < n; i++){
8 int x;
9 scanf(" %d", &x);
10 printf("%d\n", x * 6 + (x - 1) * 2);
11 }
12 return 0;
13}y值其實完全沒有意義…..
主要的觀察是，最早結束的區間一定要釘釘子。所以，就 greedy 的找切點啦！
對結尾排序後，線性掃過去，如果下個線段起點比目前的切點小，不處理; 反之，切點向後移且切點總數+1
1#include <bits/stdc++.h>
2using namespace std;
3
4#define sz(x) (int(x.size()))
5
6inline int getint() {
7 int inp; scanf("%d", &inp); return inp;
8}
9
10struct Seg {
11 int s, t;
12 bool operator < (const Seg& k) const {
13 return t < k.t;
14 }
15};
16vector<Seg> segs;
17
18int solve() {
19 // sort(segs.begin(), segs.end(), [&](const Seg& a, const Seg& b) {
20 // if (a.t == b.t) {
21 // return a.s < b.s;
22 // }
23 // return a.t < b.t;
24 // });
25 sort(segs.begin(), segs.end());
26
27 int ans = 1;
28 Seg cur = segs[0];
29 for (int i = 1; i < sz(segs); i++) {
30 // printf("(%d, %d): ", segs[i].s, segs[i].t);
31 if (segs[i].s < cur.t) {
32 // puts("c");
33 continue;
34 }
35 else {
36 ans++;
37 // printf("%d\n", ans);
38 cur = segs[i];
39 }
40 }
41 return ans;
42}
43
44int main() {
45 int TC = getint();
46 while (TC--) {
47 segs.clear();
48
49 int N = getint();
50 for (int i = 0; i < N; i++) {
51 int l = getint();
52 int x = getint();
53 int y = getint();
54
55 segs.push_back(Seg {x, x + l});
56 }
57 printf("%d\n", solve());
58 }
59 return 0;
60}問問隊友 黃鈺程 陳煒杰
1#include <bits/stdc++.h>
2using namespace std;
3
4inline int getint() {
5 int inp; scanf("%d", &inp); return inp;
6}
7
8struct Edge {
9 int to, cap, rev;
10 Edge(int a, int b, int c) {
11 to = a;
12 cap = b;
13 rev = c;
14 }
15};
16
17const int INF = 0x3f3f3f3f;
18const int MAX_V = 400;
19vector<Edge> g[MAX_V];
20int level[MAX_V];
21int iter[MAX_V];
22
23void add_edge(int u, int v, int cap) {
24 g[u].push_back((Edge){v, cap, (int)g[v].size()});
25 g[v].push_back((Edge){u, 0, (int)g[u].size() - 1});
26}
27
28void bfs(int s) {
29 memset(level, -1, sizeof(level));
30 queue<int> q;
31
32 level[s] = 0;
33 q.push(s);
34
35 while (!q.empty()) {
36 int v = q.front(); q.pop();
37 for (int i = 0; i < int(g[v].size()); i++) {
38 const Edge& e = g[v][i];
39 if (e.cap > 0 && level[e.to] < 0) {
40 level[e.to] = level[v] + 1;
41 q.push(e.to);
42 }
43 }
44 }
45}
46
47int dfs(int v, int t, int f) {
48 if (v == t) return f;
49 for (int& i = iter[v]; i < int(g[v].size()); i++) {
50 Edge& e = g[v][i];
51 if (e.cap > 0 && level[v] < level[e.to]) {
52 int d = dfs(e.to, t, min(f, e.cap));
53 if (d > 0) {
54 e.cap -= d;
55 g[e.to][e.rev].cap += d;
56 return d;
57 }
58 }
59 }
60 return 0;
61}
62
63int max_flow(int s, int t) { // dinic
64 int flow = 0;
65 for (;;) {
66 bfs(s);
67 if (level[t] < 0) return flow;
68 memset(iter, 0, sizeof(iter));
69 int f;
70 while ((f = dfs(s, t, INF)) > 0) {
71 flow += f;
72 }
73 }
74}
75
76int cnt[5];
77
78int main() {
79 int TC = getint();
80 while (TC--) {
81 for (int u = 0; u < MAX_V; u++) {
82 g[u].clear();
83 }
84
85 for (int i = 0; i < 5; i++) {
86 cnt[i] = getint();
87 }
88
89 int N = getint();
90 int s_super = N + 10;
91 int t_super = N + 11;
92 for (int i = 0; i < 5; i++) {
93 add_edge(s_super, i, cnt[i]);
94 }
95
96 for (int i = 0; i < N; i++) {
97 char s1[5], s2[5];
98 scanf("%s %s", s1, s2);
99 int c1 = s1[0] - 'A';
100 int c2 = s2[0] - 'A';
101
102 add_edge(c1, i + 5, 1);
103 add_edge(c2, i + 5, 1);
104 add_edge(i + 5, t_super, 1);
105 }
106
107 int f = max_flow(s_super, t_super);
108 if (f == N) {
109 puts("YES");
110 }
111 else {
112 puts("NO");
113 }
114 }
115 return 0;
116}