2024/11/08 選修期中考

Scoreboad

scoreboard

一開始先寫掉了 pD
然後實作大燒雞pA pB pC
最後突然找到BUG
然後就三連破 (看起來超像在藏code www)

題目

各題連結

pA

題意 :
有一長度為

$N$ 的陣列
$A$
今天有一長度為
$N \times K$ 的陣列
$B$
陣列
$B$ 是陣列
$A$ 循環
$K$ 次
求陣列
$B$ 中的 "逆序數對" 有幾個

1 \leq N \leq 2000

1 \leq K \leq 10^{9}

想法 + code

想法 :
乍一看，很像排列組合
但其實蠻單純的一題
看看

$N$ 的大小可以判斷出來應該是
$N^{2}$ 的解

然後再稍微通靈一下解法 :

A n s = \sum_{i = 1}^{n} \sum_{j = 1}^{n} {\begin{cases} 0, & if a [i] < a [j] \\ \frac{k \times (k - 1)}{2} + {\begin{cases} k, & if i < j \\ 0, & if i \geq j \end{cases}, & if a [i] > a [j] \end{cases}

CODE














#include <iostream>
using namespace std;
const int mod = 1e9+7;
int v[2005];
int main() {
    int n, k; cin >> n >> k;
    long long ans = 0;
    for(int i = 0; i < n; i++) cin >> v[i];
    for(int i = 0; i < n; i++) 
        for(int j = 0; j < n; j++) 
            if(v[j] < v[i]) 
                ans = (ans%mod + 1ll*(k-1)*k/2%mod + (i < j)*k)%mod;
    cout << ans << '\n';
}

賽後心得 :
這題有寫過，所以想說放到最後再來寫
結果同樣的思路，範例測資卻錯的很離譜
到最後才發現我沒開long long…

pB

有一字串

$S$

$S$ 初始為
$1$
接著會給你
$Q$ 次操作

操作 1 : 將會輸入一數
$x$ ，將
$x$ 放到
$S$ 的最後面
操作 2 : 將
$S$ 最前面的數字拿走
操作 3 : 輸出以十進制表示
$S$ 的數字除以
$998244353$ 的餘數

$1 \leq Q \leq 6 \times 10^{5}$

$x \in {1, 2, 3, 4, 5, 6, 7, 8, 9}$
操作 2 只會在
$S$ 為二位數以上(含)時拿走數字

想法 + code

就簡單的字串處理
像是維護

$a n s$ 值
當有一數
$X$ 加進來的時候，
$a n s = a n s + x (\mod 998244353)$
當最前面的數字
$Y$ 拔除時，需要知道他後面的位數個數
$Z$ ，將
$a n s$ 維護為
$a n s - Y \times 10^{Z} (\mod 998244353)$
小心負數取模























#include <iostream>
#include <vector>
using namespace std;
const int mod = 998244353;
int main() {
	int q; cin >> q;
	vector<int> v{1}, pre{1};
	// v -> 模擬 queue
	// pre -> 紀錄10^n，且隨著 queue 大小而變動，所以當要拔除最前面的數時，要得10的冪次剛好在最後面那個元素
	int ans = 1, now = 0;
	while(q--) {
		int c; cin >> c;
		if(c == 1) {
			int x; cin >> x;
			v.push_back(x);
			ans = (1ll*ans*10+x)%mod; // 維護元素，記得避免 overflow
			pre.push_back(1ll*pre.back()*10%mod); // 將10^n 變為 10^{n+1}，因為數字長度 + 1
		} else if(c == 2) {
			ans = ((ans-1ll*v[now++]*pre.back())%mod+mod)%mod; // - {最高位} * 10^{那個數字後面的位數個數}
			pre.pop_back(); // 將10^n -> 10^{n-1} 因為數字長度縮短
		} else cout << ans << '\n';
	}
}

賽後心得 :
從開始就卡住的題目
丟了4次 WA
結果到最後才發現是我的快速冪沒取模
:jokerisme:

pC

題意 :
有

$N$ 個人
其中有會一直說真話的人
其他的人有可能會說真話或謊話
每個人會說
$A_{i}$ 句話
每句話的格式是
$X_{i}$
$Y_{i}$
代表
$X_{i}$ 的那個人是
$Y_{i}$ (1是會說真話的, 0相反)

1 \leq N \leq 15

0 \leq A_{i} \leq N - 1

想法 + code

想法 :
因為

$N$ 超級小，所以合理推斷是枚舉的題目
枚舉又有分很多種枚舉方法
位元或者遞迴
我比較偏向位元
雖然位元常數有時候會比較大，但是好寫哈哈

CODE :
大致上的結構

































#include <iostream>
#include <vector>
using namespace std;
int popcount(int i) {
	int re = 0;
	while(i) {
		re += i&1;
		i >>= 1;
	}
	return re;
}
int main() {
	int n; cin >> n;
	vector<vector<pair<int, int> > > v(n);
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		v[i].resize(a);
		for(int j = 0; j < a; j++) cin >> v[i][j].first >> v[i][j].second, v[i][j].first--;
	}
	/* 位元枚舉 */
	int ans = 0;
	for(int i = 0; i < (1 << n); i++) {
		bool ok = true;
		for(int j = 0; j < n; j++) if(i & (1 << j)) {
			for(int k = 0; k < v[j].size(); k++) if(((i & (1<<v[j][k].first)) > 0) != v[j][k].second) {
				/* 矛盾了 */
				ok = false;
			}
		}
		if(ok) ans = max(ans, popcount(i));
	}
	cout << ans << '\n';
}

再運用一些簡單的函式與技巧可以使得code更加簡潔!




















#include <iostream>
#include <vector>
using namespace std;
int main() {
	int n; cin >> n;
	vector<vector<pair<int, int> > > v(n);
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		v[i].resize(a);
		for(auto &[c, d] : v[i]) cin >> c >> d, c--;
	}
	int ans = 0;
	for(int i = 0; i < (1 << n); i++) {
		bool ok = true;
		for(int j = 0; j < n; j++) if(i & (1 << j))
			for(auto &[a, b] : v[j]) ok = ok && (((i & (1<<a)) > 0) == b);
		if(ok) ans = max(ans, __builtin_popcount(i));
	}
	cout << ans << '\n';
}

__builtin_popcount 好用而且很快!

賽後心得 :
更新答案丟錯迴圈根本輸光

pD

題意 :
給你一字串

$S$ 每一個字元代表當次操作內容
且你必須符合以下操作原則 :

當字元為 '(' 時 "do nothing"
當字元是小寫字母時 "do nothing"
當字元為 ')' 時請往前找 '('
且必須保證在第一次碰到 '(' 之前的這整個字串須符合
一種字母只出現一次
不會遇到 ')'
且一定要找到 '('

符合上述規則則

$S$ 被視為"好字串"
假如
$S$ 是好字串輸出 "Yes" 反之則輸出 "No"

1 \leq | S | \leq 3 \times 10^{5}

$S$ 只會有上述所提到的這些字元種類

想法 + code

看到括號匹配問題基本上都要想到stack
然後小寫字母的部分有很多種作法
位元、bukket、(map、set 後面這兩個可以做，但是吃毒)
位元因為很抽象，我愛用

CODE


























#include <iostream>
#include <vector>
using namespace std;
int main() {
	string s; cin >> s;
	bool ok = true;
	int instk = 0;
	vector<char> stk;
	for(char &c : s) {
		if(c == ')') {
			while(stk.back() != '(') {
				instk ^= (1<<stk.back()-'a');
				stk.pop_back();
			}
			stk.pop_back();
		} else {
			stk.push_back(c);
			if(isalpha(c)) {
				ok = ok && instk>>c-'a'&1^1;
				instk |= 1<<c-'a';
			}
		}
	}
	cout << (ok ? "Yes" : "No") << '\n';
}

賽後心得 :
把字母判成數字
:jokerismeagain:

賽後心得

關於題目

整體比賽難度沒有到多難
除了第一題的公式或者是數字間的關係很難想
其他題目就缺點實作而已
但大家好像都沒在刷atcoder
對於題目的梗不太了解XD

關於我自己

這次實作超級爛
每一題都出BUG
然後一直都找不出來
原本可以20分鐘結束的東西
硬生生被搶走了兩個深綠…
真的要找時間再穩固一下實作了

我是小丑

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →