最後編輯時間: 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
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 l;
while(n--){
int s=0;
string a;
cin >> a;
unordered_set 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
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> w;
cout << ww(p-2,w) << " ";
}
}
例題 P-2-9. 子集合乘積(折半枚舉) (@@)
#include
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> a[i];
}
for(int i=0;i> b[i];
}
aa(1,0,false);bb(1,0,false);
unordered_map v;
for(int i=0;i
例題 Q-2-10. 子集合的和 (折半枚舉)
#include
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> aa[i];
for(int i=0;i> 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;im) m=a[i]+b[t];}
else {if(a[i]+b[t-1]>m) m=a[i]+b[t-1];}
}
}
cout << m <
例題 P-2-11. 最接近的區間和 (*)
#include
using namespace std;
int main()
{
int n,k,p=0,m=0;cin >> n >> k;
set a({0});
for(int i=0;i> w;
p+=w;
auto it=a.lower_bound(p-k);
if(it!=a.end()) m = max(m,p-*it);
a.insert(p);
}
cout << m <
例題 P-3-2. 括弧配對
#include
using namespace std;
int main()
{
string a;char r[200];
r[']']='[';r['}']='{';r[')']='(';
while(cin >> a){
stack 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
using namespace std;
int main() {
string a;cin >> a;
stack 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 <
例題 P-3-4. 最接近的高人
#include
using namespace std;
int main() {
int n;cin >> n;
stack> 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
using namespace std;
int main(){
int n;cin >> n;
long long s = 0;
vector h(n),p(n),c;
for(int i=0;i> h[i];
for(int i=0;i> p[i];
for(int i=0;i