| A | B | C | D | E1 | E2 | F |
|---|---|---|---|---|---|---|
| \(\checkmark\) | \(\checkmark\) | \(O\) | \(O\) | \(O\) | \(O\) | \(\times\) |
\(\checkmark\)：代表比賽時通過，
\(O\)：代表賽后補題通過，
\(\times\)：代表目前還未通過，
A. Array with Odd Sum
題目鏈接
題目大意
給你一個大小為\(n\)的陣列\(a\)，每次操作可以選擇兩個下標\(i,j\)(\(1\le i,j \le n\)，\(i\ne j\))，使得\(a[i]=a[j]\)，問進行有限次數的操作是否能使陣列的和為奇數，
解題思路
分別計數陣列當中奇數和偶數的個數，會有以下幾種情況：
- 只有偶數，那么這種情況下一定是不可以的，
- 只有奇數，如果陣列的大小為偶數，那么和不可能為奇數；反之，則可以，
- 既有奇數，也有偶數，這種情況一定是可以的，
AC代碼1
#include<bits/stdc++.h>
const int mod = 1e9+7;
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int a[maxn];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
bool flag1=false,flag2=false;
for(int i=0;i<n;i++){
if(a[i]%2==1){
flag1=true;
}else if(a[i]%2==0){
flag2=true;
}
}
if(!flag1){
cout<<"NO"<<endl;
}else {
if(flag2){
cout<<"YES"<<endl;
}else{
if(n%2==0){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
}
}
}
}
return 0;
}
AC代碼2
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int sum = 0;
bool odd = false, even = false;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
sum += x;
odd |= x % 2 != 0;
even |= x % 2 == 0;
}
if (sum % 2 != 0 || (odd && even)) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
總結
這道題就是一道思維題，沒有什么可說的，思維角度不一定相同，但一定盡可能的考慮全面，
B. Food Buying
題目鏈接
題目大意
手里總共有\(s\)元，去超市買價格為\(x\)(\(1\le x \le s\))的商品，會優惠\(\lfloor \frac x{10} \rfloor\)元，其中\(\lfloor \frac x {10} \rfloor\)為向下取整，問最多消費多少元，
解題思路
貪心思想，因為優惠是向下取整的，那么個位數會丟掉，所有\(x\)為\(10\)的倍數時，能夠消費最多，
AC1代碼
#include<bits/stdc++.h>
const int mod = 1e9+7;
const int maxn=1e5+10;
typedef long long ll;
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int s;
cin>>s;
ll res=0;
while(s>=10){
res+=s/10*10;
s=s-s/10*10+s/10;
}
cout<<res+s<<endl;
}
return 0
}
AC代碼2
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int s;
cin >> s;
int ans = 0;
int pw = 1000 * 1000 * 1000;
while (s > 0) {
while (s < pw) pw /= 10;
ans += pw;
s -= pw - pw / 10;
}
cout << ans << endl;
}
return 0;
}
總結
簡單的貪心思維題，
C. Yet Another Walking Robot
題目鏈接
題目大意
給你一個只包含“\(L,R,U,D\)”的字串機器指令，其中\(L\)代表向左移動，\(R\)代表向右移動，\(U\)代表向上移動，\(D\)代表向下移動，其中在二維坐標原點\((0,0)\)開始執行機器指令，求字串能洗掉的最短子串的下標以達到機器最終到達的二維坐標點不變，
解題思路
暴力，遍歷一遍，\(pair\)存下每次到達的二維坐標點，\(map\)存下對應二維坐標的陣列下標并擔當查詢是否出現過的功能，
AC代碼1
/*
C題補題
*/
#include<bits/stdc++.h>
#define p pair<int,int>
#define fre(x) freopen(x,"r",stdin)
const int mod = 1e9+7;
const int maxn=1e5+10;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int main()
{
int t;
// fre("data.txt");
cin>>t;
while(t--){
int n;
cin>>n;
string str;
cin>>str;
map<p,int>mp;
//初始化位置
mp[make_pair(0,0)]=0;
int x=0,y=0;
p ans=make_pair(1,1e9);
for(int i=0;i<str.size();i++){
if(str[i]=='L')x--;
else if(str[i]=='R')x++;
else if(str[i]=='U')y++;
else if(str[i]=='D')y--;
if(mp.find(make_pair(x,y))!=mp.end()){
int l=mp[make_pair(x,y)],r=i+1;
if(r-l<ans.second-ans.first){
ans=make_pair(l,r);
}
}
mp[make_pair(x,y)]=i+1;
}
if(ans.second!=1e9){
cout<<ans.first+1<<" "<<ans.second<<endl;
}else cout<<"-1"<<endl;
}
}
AC代碼2
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
int l = -1, r = n;
map<pair<int, int>, int> vis;
pair<int, int> cur = {0, 0};
vis[cur] = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == 'L') --cur.first;
if (s[i] == 'R') ++cur.first;
if (s[i] == 'U') ++cur.second;
if (s[i] == 'D') --cur.second;
if (vis.count(cur)) {
if (i - vis[cur] + 1 < r - l + 1) {
l = vis[cur];
r = i;
}
}
vis[cur] = i + 1;
}
if (l == -1) {
cout << -1 << endl;
} else {
cout << l + 1 << " " << r + 1 << endl;
}
}
return 0;
}
總結
比賽的時候沒能想到這道題的解法，尤其是如何去找已經出現過的點，
D. Fight with Monsters
題目鏈接
題目大意
有\(n\)只怪獸，每個怪獸\(i\)都有一個生命值\(h_i\)，你的攻擊值是\(a\),對手的攻擊值是\(b\)，對于每一只怪獸，自己先發起攻擊，然后對手攻擊，若當前怪獸被自己打死，那么加\(1\)分，移動到下一個怪獸，自己有\(k\)次特權，每次特權都可以讓對手當前的攻擊對怪獸無效，問自己最多可以得多少分，
解題思路
如果當前怪獸的值對兩個攻擊者的攻擊值取余：
- 若余數小于\(a\)且不為\(0\)，那么不用特權都可以得分，移動到下一個怪獸，
- 若余數為\(0\)，則當怪獸剩余生命值為\(b\)時，將其值扔到一個陣列當中，
- 若余數不為\(0\)且大于\(a\)，將余數扔到陣列當中，
對陣列進行排序，貪心策略使用特權\(k\)已達到得分最多，
AC代碼1
#include<bits/stdc++.h>
#define p pair<int,int>
#define fre(x) freopen(x,"r",stdin)
const int mod = 1e9+7;
const int maxn=2e5+10;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll num[maxn];
vector<ll>mid;
int main(){
// fre("data.txt");
ll n,a,b,k;
cin>>n>>a>>b>>k;
for(int i=0;i<n;i++){
cin>>num[i];
}
ll cnt=0;
ll sum=a+b;
for(int i=0;i<n;i++){
if(num[i]%sum!=0&&num[i]%sum<=a){
cnt++;
}else{
mid.push_back(num[i]%sum==0?b:num[i]%sum-a);
}
}
sort(mid.begin(),mid.end());
for(int i=0;i<mid.size();i++){
if(k*a>=mid[i]){
cnt++;
k-=(mid[i]/a+(mid[i]%a==0?0:1));
}else break;
}
cout<<cnt<<endl;
}
AC代碼2
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, a, b, k;
cin >> n >> a >> b >> k;
vector<int> h(n);
for (int i = 0; i < n; ++i) {
cin >> h[i];
h[i] %= a + b;
if (h[i] == 0) h[i] += a + b;
h[i] = ((h[i] + a - 1) / a) - 1;
}
sort(h.begin(), h.end());
int ans = 0;
for (int i = 0; i < n; ++i) {
if (k - h[i] < 0) break;
++ans;
k -= h[i];
}
cout << ans << endl;
return 0;
}
總結
取模+貪心，
E1. String Coloring (easy version)
題目鏈接
題目大意
給你一個只包含小寫字母的字串，給每一個字符圖上黑色或者白色，相鄰字串如果顏色不同則可以交換位置，經過有限次數的交換，問是否有可能使得字串變為有序，
解題思路
題目告訴相鄰顏色不同的字符才能交換，換句話說就是顏色相同的字符順序是不會發生改變的，要達到最后字串為有序且顏色相同字符的順序不改變，那么只有顏色相同的字符本身就是有序的，那么問題就轉變為字串是否能夠轉變為兩個非遞減的子序列，用兩個字符分別標記兩個子序列的最后一個字符，如果大于兩個字符當中的任意一個，則可添加其到相應子序列的尾部，
AC代碼
/*
E1題補題
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
string str;
cin>>str;
char l1='a',l2='a';
string res;
for(int i=0;i<str.size();i++){
if(str[i]>=l1){
res+="0";
l1=str[i];
}else if(str[i]>=l2){
res+="1";
l2=str[i];
}else{
cout<<"NO"<<endl;
return 0;
}
}
cout<<"YES"<<endl;
cout<<res<<endl;
return 0;
}
總結
在理解到題意之后，不要僅局限于題目給的方向，要換角度思考問題，
E2. String Coloring (hard version)
題目鏈接
題目大意
題目意思和\(E1\)類似，給你一個長度為\(n\)的字串，給每個字符涂上一種顏色，相鄰不同顏色的字符可以交換位置，問最少需要多少種顏色使得經過有限次數的交換可以讓字串變得有序，
解題思路
思路和\(E1\)類似，去找覆寫字串所有字符所需要非遞減子序列的最少數量，解決方案有兩種：
- 將字串倒序一下，就是找覆寫所有字符所需要非遞增子序列的個數，把每一個子序列尾部的字符插入到\(set\)中，此時可以用二分查找函式找第一個大于等于\(str[i]\)字符的字符，
- 根據\(Dilworth\)定理可以得知，覆寫整個序列所需的非遞減序列的最小數量等于最長遞減子序列的長度，那么用動態規劃找到達每個字符的最長遞減子序列的長度，其中\(dp[i]\)表示到第\(i\)個字符\(c\)的最長遞減子序列的長度，其等于所有以大于字符\(c\)的字符結尾的最長遞減子序列長度加\(1\)，最后陣列\(dp\)存的就是答案，
AC代碼1
#include<bits/stdc++.h>
using namespace std;
int c[30];
vector<char>G[300];
int main()
{
// freopen("data.txt","r",stdin);
int n;
cin>>n;
string str;
cin>>str;
set<char>se;
int cnt=1;
vector<string>res;
reverse(str.begin(),str.end());
se.insert(str[0]);
c[str[0]-'a']=1;
for(int i=0;i<str.size();i++){
auto it=se.lower_bound(str[i]);
if(it!=se.end()){
res.push_back(to_string(c[(*it)-'a']));
c[str[i]-'a']=c[(*it)-'a'];
se.erase(it);
se.insert(str[i]);
}else {
se.insert(str[i]);
cnt++;
c[str[i]-'a']=cnt;
res.push_back(to_string(cnt));
}
}
reverse(res.begin(),res.end());
set<string>sp;
for(int i=0;i<res.size();i++){
sp.insert(res[i]);
}
cout<<sp.size()<<endl;
for(int i=0;i<res.size();i++){
if(i)cout<<" ";
cout<<res[i];
}
return 0;
}
AC代碼2
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("data.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
string s;
cin >> n >> s;
vector<int> maxdp(26);
vector<int> dp(n, 1);
for (int i = 0; i < n; ++i) {
for (int c = 25; c > s[i] - 'a'; --c) {
dp[i] = max(dp[i], maxdp[c] + 1);
}
maxdp[s[i] - 'a'] = max(maxdp[s[i] - 'a'], dp[i]);
}
cout << *max_element(maxdp.begin(), maxdp.end()) << endl;
for (int i = 0; i < n; ++i) cout << dp[i] << " ";
cout << endl;
return 0;
}
總結
自己的思路和標程還是有很大差距，標程簡便很多，但總算自己能夠用一種寫法寫出來，\(Dilworth\)定理之前沒有了解過，這次算是學習到了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/64973.html
標籤：C++
上一篇：coin change
下一篇：eight（待考究）