生活随笔
收集整理的這篇文章主要介紹了
Codeforces Beta Round #6 (Div. 2)【未完结】
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
2022.3.4
題單地址:https://codeforces.com/contest/6
目錄
- A. Triangle【枚舉】
- B. President's Office【枚舉】
- C. Alice, Bob and Chocolate【前綴和】
- D. Lizards and Basements 2【未完成 DP】
- E. Exposition【st表 / 單調隊列】
A. Triangle【枚舉】
#include<bits/stdc++.h>
using namespace std
;
int a
[10];
int main(void)
{for(int i
=0;i
<4;i
++) cin
>>a
[i
];sort(a
,a
+4);int flag
=0;for(int i
=0;i
<4;i
++){for(int j
=i
+1;j
<4;j
++){for(int k
=j
+1;k
<4;k
++){if(a
[i
]+a
[j
]>a
[k
]) flag
=max(flag
,2);if(a
[i
]+a
[j
]==a
[k
]) flag
=max(flag
,1);}}}if(flag
==2) puts("TRIANGLE");else if(flag
==1) puts("SEGMENT");else puts("IMPOSSIBLE");return 0;
}
B. President’s Office【枚舉】
這種同一個字符的是一個桌子。故用map來去重，求挨著的不同字符的種類即可
#include<bits/stdc++.h>
using namespace std
;
int n
,m
;
string s
[205];
char c
;
map
<char,int>mp
;
void solve(int x
,int y
)
{int dx
[4]={-1,0,0,1},dy
[4]={0,-1,1,0};for(int i
=0;i
<4;i
++){int tempx
=x
+dx
[i
],tempy
=y
+dy
[i
];if(tempx
<0||tempx
>=n
||tempy
<0||tempy
>=m
) continue;if(s
[tempx
][tempy
]=='.') continue;if(s
[tempx
][tempy
]==c
) continue;mp
[s
[tempx
][tempy
]]++;}
}
int main(void)
{cin
>>n
>>m
>>c
;for(int i
=0;i
<n
;i
++) cin
>>s
[i
];for(int i
=0;i
<n
;i
++){for(int j
=0;j
<m
;j
++) if(s
[i
][j
]==c
) solve(i
,j
);}cout
<<mp
.size();return 0;
}
C. Alice, Bob and Chocolate【前綴和】
用前綴和，再枚舉一個將其分割成兩份。看剩余的相等不相等。
如果相等說明最后一次，他們吃的是同一塊，按照題目給第一個加1即可。
否則的話，我們就輸出分成兩份差最小的位置。
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+10;
int a
[N
],s
[N
],n
;
int main(void)
{cin
>>n
;for(int i
=1;i
<=n
;i
++) cin
>>a
[i
],s
[i
]=s
[i
-1]+a
[i
];int temp
=1e9;for(int i
=1;i
<=n
;i
++){if(s
[i
-1]==s
[n
]-s
[i
]){cout
<<i
<<" "<<n
-i
;return 0;}temp
=min(temp
,abs(s
[n
]-2*s
[i
]));}for(int i
=1;i
<=n
;i
++){if(temp
==abs(s
[n
]-2*s
[i
])){cout
<<i
<<" "<<n
-i
;return 0;}}return 0;
}
D. Lizards and Basements 2【未完成 DP】
E. Exposition【st表 / 單調隊列】
就是求最長的區間，區間內的最大值減去最小值的差小于等于k,且輸出所有滿足最長區間的左右端點。
單調隊列可做，st表也可做。
這里是用二分+st表做的，二分一下區間。
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+1;
int n
,k
,mx
[N
][20],mn
[N
][20],a
[N
];
int getmx(int l
,int r
){int tmp
=log2(r
-l
+1);return max(mx
[l
][tmp
],mx
[r
-(1<<tmp
)+1][tmp
]);
}
int getmn(int l
,int r
){int tmp
=log2(r
-l
+1);return min(mn
[l
][tmp
],mn
[r
-(1<<tmp
)+1][tmp
]);
}
void init()
{for(int i
=1;i
<=n
;i
++) mx
[i
][0]=mn
[i
][0]=a
[i
];for(int j
=1;j
<20;j
++){for(int i
=1;i
+(1<<j
)-1<=n
;i
++){mx
[i
][j
]=max(mx
[i
][j
-1],mx
[i
+(1<<j
-1)][j
-1]);mn
[i
][j
]=min(mn
[i
][j
-1],mn
[i
+(1<<j
-1)][j
-1]);}}
}
vector
<pair
<int,int>>ve
;
bool check(int mid
)
{ve
.clear();for(int i
=1;i
+mid
-1<=n
;i
++){int l
=i
,r
=i
+mid
-1;if( (getmx(l
,r
)-getmn(l
,r
)) <=k
) ve
.push_back({l
,r
});}if(ve
.size()) return true;return false;
}
int main(){cin
>>n
>>k
;for(int i
=1;i
<=n
;i
++) cin
>>a
[i
];init();int l
=1,r
=n
;while(l
<r
){int mid
=l
+r
+1>>1;if(check(mid
)) l
=mid
;else r
=mid
-1;}if(check(l
)) cout
<<l
<<" "<<ve
.size()<<endl
;for(int i
=0;i
<ve
.size();i
++) cout
<<ve
[i
].first
<<" "<<ve
[i
].second
<<endl
;
}
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀
總結
以上是生活随笔為你收集整理的Codeforces Beta Round #6 (Div. 2)【未完结】的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
