APCS 1061028

試題

c461: apcs 邏輯運算子 (Logic Operators)

基本位元運算題

AC Code

 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031
 
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	a = a > 0 ? 1 : 0;
	b = b > 0 ? 1 : 0;
	c = c > 0 ? 1 : 0;
	
	bool ok = false;
	if((a & b) == c) {
		printf("AND\n");
		ok = true;
	}
	if((a | b) == c) {
		printf("OR\n");
		ok = true;
	}
	if((a ^ b) == c) {
		printf("XOR\n");
		ok = true;
	}

	if(!ok)
		printf("IMPOSSIBLE\n");
	
	return 0;
}

c462: apcs 交錯字串 (Alternating Strings)

可以先對大小寫進行01編碼後，壓縮一下 (run-length encoding)

之後就是找頭尾 $\ge k$ 且中間均 $=k$ 的長子字串即可

AC Code

 1 2 3 4 5 6 7 8 91011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
 
#include <bits/stdc++.h>

using namespace std;

int k;
char inp[111111];

int main()
{
	scanf("%d %s", &k, inp);
	
	int len = strlen(inp);
	int data[len];
	for(int i = 0; i < len; i++) {
		if('a' <= inp[i] && inp[i] <= 'z') {
			data[i] = 0;
		} else {
			data[i] = 1;
		}
	}
	
	int cnt = 1;
	vector<int> compressed;
	for(int i = 1; i < len; i++) {
		if(data[i] == data[i - 1]) {
			cnt++;
		} else {
			compressed.push_back(cnt);
			cnt = 1;
		}
	}
	compressed.push_back(cnt);
	/*
	for(auto i : compressed)
		printf("%d ", i);
	printf("\n");
	*/
	
	bool active = false;
	int ans = 0;
	int tmp = 0;
	// head tail is ok to be >= k, other must be == k
	for(int i = 0; i < (int)compressed.size(); i++) {
		if(active == false) {
			if(compressed[i] >= k) {
				active = true;
				tmp++;
			}
		} else {
			if(compressed[i] == k) {
				tmp++;
			} else {
				if(compressed[i] >= k)
					tmp++;
				tmp *= k;
				ans = max(ans, tmp);
				tmp = 0;
				i--; // current one might be the start for another one

				active = false;
			}
		}
	}

	tmp *= k;
	ans = max(ans, tmp);

	printf("%d\n", ans);

	return 0;
}

c463: apcs 樹狀圖分析 (Tree Analyses)

Bottom up DP

從 leaf 開始拔，並且一路更新 parent 的解即可。

AC Code

 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
	int n;
	scanf("%d", &n);

	if(n == 1) {
		printf("1\n0\n");
		return 0;
	}

	int dp[n];
	int par[n];
	int deg[n];
	memset(par, -1, sizeof(par));
	memset(dp, 0, sizeof(dp));

	queue<int> q;
	for(int p = 0; p < n; p++) {
		int k;
		scanf("%d", &k);
		if(k == 0)
			q.push(p);

		deg[p] = k;

		for(int j = 0; j < k; j++) {
			int child;
			scanf("%d", &child);
			child--;
			par[child] = p;
		}
	}	

	while(q.size() > 0) {
		int cur = q.front();
		q.pop();

		if(par[cur] != -1) {
			dp[par[cur]] = max(dp[par[cur]], dp[cur] + 1);
			deg[par[cur]]--;
			if(deg[par[cur]] == 0)
				q.push(par[cur]);
		}
	}

	ll ans = 0;
	for(int i = 0; i < n; i++) {
		if(par[i] == -1)
			printf("%d\n", i + 1);
		ans += dp[i];
	}
	printf("%lld\n", ans);

	return 0;
}

c471: apcs 物品堆疊 (Stacking)

Hint

Solution

AC Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Data {
	int w, f;
};

bool cmp(const Data& a, const Data &b)
{
	// return a.f * b.w < b.f * a.w;
	return a.w * b.f < b.w * a.f;
}

int main()
{
	int n;
	scanf("%d", &n);

	Data data[n];
	for(int i = 0; i < n; i++) {
		scanf("%d", &data[i].w);
	}

	for(int i = 0; i < n; i++) {
		scanf("%d", &data[i].f);
	}
	sort(data, data + n, cmp);

	ll ans = 0, accum = 0;
	for(int i = 0; i < n - 1; i++) {
		accum += data[i].w;
		ans += accum * data[i + 1].f;
	}

	printf("%lld\n", ans);

	return 0;
}