最後編輯時間: 2025/05/20
2025/05/20刷題心得整理
▌TF::OJ刷的題目
▌覺得有趣或值得紀錄的題目以及心得感想
- 習題 Q-2-7. 互補團隊
這題上一次解不出來，整體邏輯沒什麼太大的問題，不知道是原本設定的值有問題還是怎樣，會出錯，後面把陣列改成二進制，讓每個字母有單獨的值，確保字母相加不會相同，並使用map來存值，邊測邊+，最後就可以輸出正確答案了，我還使用set確保每次計算字母只計算一次。 - 習題 Q-2-8. 模逆元 (*)
這題題目不難，就是沒看懂公式，其實就是把公式套進去而已 - 例題 P-2-9. 子集合乘積(折半枚舉) (@@)
這題利用了將陣列分兩半，讓左相乘，右相乘，最後逆模抓出能兩邊相乘%p等於1的值，最後+一起就好了 - 例題 Q-2-10. 子集合的和 (折半枚舉)
這題跟上一題類似，就是把左邊算出來，右邊算出來，最後把左邊所有可能去查詢右邊是否有對應值，有就+ - 例題 P-3-2. 括弧配對
這題超級經典推疊提，總之就是把括號存著，只要後面括號沒辦法匹配到，這一個括號就是錯誤 - 習題 Q-3-3. 加減乘除
這題也是堆疊，如果是+或-直接壓入堆疊，如果是*或/就把上一個壓進去的值進行計算算完後壓回去 - 例題 P-3-4. 最接近的高人
這題利用單調堆疊，總之就是因為一直往後，如果後面的數值比前面的大，那對於更後面的值最高的高人就會是它，所以可以把前面比那個高人小的刪除，總之就這樣，我講得蠻抽象的
▌程式
習題 Q-2-7. 互補團隊
#include <bits/stdc++.h>
using namespace std;
int main(){
int g[26]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,75536,151172,302344,604688,1209376,2418752,4837504,9675008,19350016,38700032};
int m,n,ss=0,w=0;
cin >> m >> n;
for(int i=0;i<m;i++) w+=g[i];
unordered_map<int,int> l;
while(n--){
int s=0;
string a;
cin >> a;
unordered_set<char> b;
for(char c:a){
if(!b.count(c)){
s += g[c-'A'];
b.insert(c);
}
}
l[s]++;
ss += l[w-s];
}
cout << ss << endl;
}
習題 Q-2-8. 模逆元 (*)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL p;
LL ww(LL k,LL w){
if(k==0) return 1;
if(k%2==1) return (ww(k-1,w)*w)%p;
LL q = ww(k/2,w);
return (q * q)%p;
}
int main(){
int n;cin >> n >> p;
for(int i=0;i<n;i++){
LL w;cin >> w;
cout << ww(p-2,w) << " ";
}
}
例題 P-2-9. 子集合乘積(折半枚舉) (@@)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,a[30],b[30],sa[300000]={},sb[300000]={},s=0,ss=0,n;
void aa(long long k, int e, bool selected) {
if (e == n / 2) {
if (selected) sa[s++] = k % p;
return;
}
aa(k, e + 1, selected);
aa(k * a[e] % p, e + 1, true);
}
void bb(ll k,int e,bool selected){
if(e==n-n/2){
if(selected) sb[ss++] = k%p;
return;
}
bb(k%p,e+1,selected);
bb(k*b[e]%p,e+1,true);
return;
}
ll c(ll k,ll nn){
if(nn==0) return 1;
if(nn%2==1) return k * c(k,nn-1) % p;
ll r = c(k,nn/2);
return r * r % p;
}
int main(){
cin >> n >> p;
for(int i=0;i<n/2;i++){
cin >> a[i];
}
for(int i=0;i<n-(n/2);i++){
cin >> b[i];
}
aa(1,0,false);bb(1,0,false);
unordered_map<int,int> v;
for(int i=0;i<ss;i++){
v[sb[i]]++;
}
ll w = 0;
for(int i=0;i<s;i++){
if(sa[i]==1) w++;
w+=v[c(sa[i],p-2)];
}
cout << v[1]+w << endl;
}
例題 Q-2-10. 子集合的和 (折半枚舉)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll aa[38],bb[38],a[524288],b[524288],n,s=0,ss=0;
void aw(ll k,ll e){
if(e==n/2){
if(k!=0) a[s++] = k;
return;
}
aw(k,e+1);aw(k+aa[e],e+1);
return;
}
void bw(ll k,ll e){
if(e==n-n/2){
if(k!=0) b[ss++] = k;
return;
}
bw(k,e+1);bw(k+bb[e],e+1);
return;
}
int main(){
ll m=0;
ll p;cin >> n >> p;
for(int i=0;i<n/2;i++) cin >> aa[i];
for(int i=0;i<n-n/2;i++) cin >> bb[i];
aw(0,0);bw(0,0);
sort(a,a+s);sort(b,b+ss);
ll da = upper_bound(a,a+s,p)-a;
ll db = upper_bound(b,b+s,p)-b;
if(a[da]<=p) {if(a[da]>m) m=a[da];}
else {if(a[da-1]>m) m=a[da-1];}
if(a[da]<=p) {if(b[db]>m) m=b[db];}
else {if(b[db+1]>m) m=b[db+1];}
for(int i=0;i<s;i++){
if(a[i]<=p){
ll w = p - a[i];
ll t = upper_bound(b,b+ss,w)-b;
if(b[t]<=w) {if(a[i]+b[t]>m) m=a[i]+b[t];}
else {if(a[i]+b[t-1]>m) m=a[i]+b[t-1];}
}
}
cout << m <<endl;
}
例題 P-2-11. 最接近的區間和 (*)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k,p=0,m=0;cin >> n >> k;
set<int> a({0});
for(int i=0;i<n;i++){
int w;cin >> w;
p+=w;
auto it=a.lower_bound(p-k);
if(it!=a.end()) m = max(m,p-*it);
a.insert(p);
}
cout << m <<endl;
return 0;
}
例題 P-3-2. 括弧配對
#include <bits/stdc++.h>
using namespace std;
int main()
{
string a;char r[200];
r[']']='[';r['}']='{';r[')']='(';
while(cin >> a){
stack<char> b;
bool w = true;
for(char c:a){
if(c=='}'||c==')'||c==']'){
char s = (!b.empty())?b.top():'0';
if(r[(unsigned char)c]==s) b.pop();
else w=false;
}else b.push(c);
}
if(w&&b.size()==0) cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}
習題 Q-3-3. 加減乘除
#include <bits/stdc++.h>
using namespace std;
int main() {
string a;cin >> a;
stack<int> b;b.push(a[0]-'0');
for(int i=2;i<(int)a.size();i+=2){
int t = b.top();
int y = a[i]-'0';
if(a[i-1]=='/'){
b.pop();
b.push(t/y);
}else if(a[i-1]=='*'){
b.pop();
b.push(t*y);
}else{
if(a[i-1]=='-') b.push(0-y);
else b.push(y);
}
}
int s=0;
while(!b.empty()){
s+=b.top();
b.pop();
}
cout << s <<endl;
return 0;
}
例題 P-3-4. 最接近的高人
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;cin >> n;
stack<pair<int, int>> a;
long long s = 0;
for (int i = 1; i <= n; i++) {
int w;cin >> w;
while (!a.empty() && a.top().first <= w) a.pop();
if (!a.empty()) s += i - a.top().second;
else s += i;
a.push({w, i});
}
cout << s << endl;
return 0;
}
習題 Q-3-5. 帶著板凳排雞排的高人
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;cin >> n;
long long s = 0;
vector<int> h(n),p(n),c;
for(int i=0;i<n;i++) cin >> h[i];
for(int i=0;i<n;i++) cin >> p[i];
for(int i=0;i<n;i++){
int ans = -1,left = 0,right = c.size()-1;
int t = h[i] + p[i];
while(left<=right){
int ni = (right + left) / 2;
if(h[c[ni]]>t){
ans = ni;
left = ni + 1;
}else right = ni - 1;
}
if(ans == -1) s+= i;
else s+= i - c[ans] - 1;
while(!c.empty()&&h[c.back()]<=h[i]) c.pop_back();
c.push_back(i);
}
cout << s << endl;
}