加训(个人纪录)

目录

2023年5月22日

A. Musical Puzzle

B. Restore the Weather 

C. Vlad Building Beautiful Array

D. Flipper

2023年5月23日

A 猫猫与广告

B 猫猫与密信

C 猫猫与数列

D 猫猫与主人

2023年5月25日 

A. Grasshopper on a Line

B. Comparison String

C. Best Binary String

D. Bracket Coloring

2023年5月28日

A. Twin Permutations​编辑

B. Array merging

2023年5月29日 

小d和答案修改 

小d和图片压缩

小d和超级泡泡堂

小d和孤独的区间

小d的博弈 

2023年6月4日 

A. The Good Array

B. Lamps

C. Insert Zero and Invert Prefix

2023年6月5日

A. Blackboard List 

B. Minimize Permutation Subarrays

C. No Prime Differences

2023年6月6日

A. Cipher Shifer 

B. Binary Cafe 

C. Ski Resort

D. Wooden Toy Festival

---

2023年5月22日

CodeForce Round 874 (div.3)

A. Musical Puzzle

#include <iostream>
#include <set>
using namespace std;
int main()
{int t;cin >> t;while(t -- ){set<string> Q;int n;cin >> n;getchar();string s;cin >> s;for(int i = 0;i < s.size() - 1;i ++ ){string t;t += s[i];t += s[i + 1];Q.insert(t);}cout << Q.size() << endl;}return 0;
}

B. Restore the Weather 

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000000 + 10;
struct node
{int v;int idx;
};
node a[N];
int b[N],ans[N];
int cmp(node a,node b)
{return a.v < b.v;
}
int main()
{int t;cin >> t;while(t -- ){int n,m;cin >> n >> m;for(int i = 1;i <= n;i ++ ){cin >> a[i].v;a[i].idx = i;} sort(a + 1,a + 1 + n,cmp);for(int i = 1;i <= n;i ++ )cin >> b[i];sort(b + 1,b + 1 + n);for(int i = 1;i <= n;i ++ ){ans[a[i].idx] = b[i];}for(int i = 1;i <= n;i ++ )cout << ans[i] << ' ';cout << endl;}return 0;
}

C. Vlad Building Beautiful Array

#include <iostream>
using namespace std;
int main()
{int t;cin >> t;while(t -- ){int n,minji = 0x3f3f3f3f,minou = 0x3f3f3f3f,ji = 0,ou = 0;cin >> n;while(n -- ){int num;cin >> num;if(num & 1){ji ++ ;minji = min(minji,num);}else {ou ++ ;minou = min(minou,num);}}if(!ji||!ou)cout << "YES" << endl;else {if(minji > minou)cout << "NO" << endl;else cout << "YES" << endl;}}return 0;
}
→Judgement Protocol

D. Flipper

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2020;
int a[N],ans[N];
void deal(int l,int r,int n)
{if(l > r)return;vector<int> t;if(r + 1 <= n){for(int i = r + 1;i <= n;i ++ ){t.push_back(a[i]);}}for(int i = r;i >= l;i -- ){t.push_back(a[i]);}if(l - 1 >= 1){for(int i = 1;i <= l - 1;i ++ ){t.push_back(a[i]);}}for(int i = 0;i < int(t.size());i ++ ){int j = i + 1;if(t[i] == ans[j])continue;else if(t[i] > ans[j]){for(int i = 0;i < int(t.size());i ++ )ans[i + 1] = t[i];break;}else break;}
}
int main()
{int t;cin >> t;while(t -- ){memset(a,0,sizeof(a));memset(ans,0,sizeof(ans));int n,idx = 0,t = -1;cin >> n;for(int i = 1;i <= n;i ++ ){cin >> a[i];if(a[i] > t){t = a[i];idx = i;}}if(idx == 1){t = -1;for(int i = 2;i <= n;i ++ ){if(a[i] > t){t = a[i];idx = i;}}}for(int i = 1;i <= idx;i ++ ){deal(i,idx,n);deal(i,idx - 1,n);}for(int i = 1;i <= n;i ++ )cout << ans[i] << ' ';cout << endl;}
}

2023年5月23日

牛客小白月赛71

A 猫猫与广告

 

#include <iostream>
using namespace std;
int main()
{int a,b,c,d;cin >> a >> b >> c >> d;if(a > b)swap(a,b);if(c > d)swap(c,d);if(c >= a && d >= b)cout << "YES" << endl;else cout << "NO" << endl;return 0;
}

B 猫猫与密信

 

#include <iostream>
#include <cstring>
using namespace std;
int main()
{string s;cin >> s;if(s.find("ove") != -1 || s.find("lve") != -1 || s.find("loe") != -1 || s.find("lov") != -1)cout << "YES" << endl;else cout << "NO" << endl;return 0;
}

C 猫猫与数列

#include <iostream>
using namespace std;
typedef long long ll;
int main()
{ll p,q;cin >> p >> q;ll t,ans = 0;for(int i = 3;;i ++ ){int flag = 1;t = 1;for(int j = 1;j <= q;j ++ ){t *= p;if(t > 1e18){flag = 0;ans = i - 1;break;}}if(flag == 0)break;swap(p,q);q = t;}cout << ans << endl;return 0;
}

D 猫猫与主人

#include <iostream>
#include <algorithm>
using namespace std;
struct node
{int a;int b;int id;
};
const int N = 2e5 + 10;
node cat[N];
node peo[N];
int ans[N];
bool cmp0(node t1,node t2)
{return t1.a < t2.a;
} 
bool cmp1(node t1,node t2)
{return t1.b < t2.b;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m;cin >> n >> m;for(int i = 1;i <= n;i ++ )cin >> cat[i].a;for(int i = 1;i <= n;i ++ ){cin >> cat[i].b;cat[i].id = i;}for(int i = 1;i <= m;i ++ )cin >> peo[i].a;for(int i = 1;i <= m;i ++ ){cin >> peo[i].b;peo[i].id = i;}sort(cat + 1,cat + 1 + n,cmp0);sort(peo + 1,peo + 1 + m,cmp1);int j = 1,sum = -1;for(int i = 1;i <= n;i ++ ){while(cat[i].a >= peo[j].b && j <= m){sum = max(sum,peo[j].a);j ++ ;}if(sum < cat[i].b)ans[cat[i].id] = -1;else ans[cat[i].id] = sum;}for(int i = 1;i <= n;i ++ )cout << ans[i] << ' ';cout << endl;return 0;
}

2023年5月25日 

Educational Codeforces Round 149 (Rated for Div. 2)

A. Grasshopper on a Line

#include <iostream>
using namespace std;
typedef long long ll;
int main()
{ll t;cin >> t;while(t -- ){ll x,k;cin >> x >> k;if(x < k || x % k != 0)cout << 1 << endl << x << endl;else{cout << 2 << endl;cout << (x / k - 1) * k + (k - 1) << ' ' << 1 << endl; }}return 0;
}

B. Comparison String

#include <iostream>
using namespace std;
int main()
{int t;cin >> t;getchar();while(t -- ){int n;cin >> n;string s;cin >> s;int l = 0,res = -1e9;char c = s[0];l ++ ;for(int i = 1;i < s.size();i ++ ){if(c == s[i])l ++ ;else {res = max(res,l);c = s[i];l = 1;}}res = max(res,l);cout << res + 1 << endl;}return 0;
}

C. Best Binary String

#include <iostream>
using namespace std;
int main()
{int t;cin >> t;getchar();while(t -- ){int nums = 0,zero = 0;string s;cin >> s;for(int i = 0;i < s.size();i ++ ){if(s[i] == '?')nums ++ ;else if(s[i] == '0')zero ++ ;}if(nums == 0){cout << s << endl;continue;}else {if(nums == int(s.size())){for(int i = 0;i < s.size();i ++ )cout << '0';cout << endl;continue;}else {if(zero == 1){for(int i = s.size() - 1;i >= 0;i -- ){if(s[i] == '0'){for(int j = i + 1;j < s.size();j ++ ){if(s[j] == '?')s[j] = '1';}break;}}}if(s[0] == '?'){int idx = 0;while(s[idx] == '?' && idx < s.size())idx ++ ;for(int i = 0;i < idx;i ++ )s[i] = s[idx];
//					cout << idx << "@1" << endl << s << endl;}if(s[s.size() - 1] == '?'){int idx = s.size() - 1;while(s[idx] == '?' && idx >= 0)idx -- ;for(int i = s.size() - 1;i > idx;i -- )s[i] = s[idx];
//					cout << idx << "@2" << endl << s << endl;;}for(int i = 0;i < s.size();i ++ ){if(s[i] != '?')continue;else{char c1 = s[i - 1];int j = i;while(s[j] == '?' && j < s.size())j ++ ;char c2 = s[j];if(c1 == c2){for(int k = i;k < j;k ++ )s[k] = c1;}else {for(int k = i;k < j;k ++ )s[k] = '0';}i = j - 1;}}}}cout << s << endl;}return 0;
}

D. Bracket Coloring

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
int ans[N];
int main()
{int t;cin >> t;getchar();while(t -- ){int n;cin >> n;string s;cin >> s;int l = int(s.size());if(l & 1)cout << -1 << endl;else {int L = 0,R = 0;for(int i = 0;i < s.size();i ++ ){if(s[i] == '(')L ++ ;else if(s[i] == ')')R ++ ;}if(L != R)cout << -1 << endl;else {memset(ans,0,sizeof(ans));char c = s[0];queue<int> Q;Q.push(0);for(int i = 1;i < s.size();i ++ ){if(c == s[i])Q.push(i);else {if(Q.size()){ans[i] = 1;int idx = Q.front();ans[idx] = 1;Q.pop();}else ans[i] = 2;}}int t = 1;if(Q.size())t = 2;while(Q.size()){int idx = Q.front();ans[idx] = 2;Q.pop();}cout << t << endl;for(int i = 0;i < s.size();i ++ )cout << ans[i] << ' ';cout << endl;}}}return 0;
}

2023年5月28日

Codeforces Round 875 (Div. 2)

A. Twin Permutations

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{int t;cin >> t;while(t -- ){int n;cin >> n;for(int i = 1;i <= n;i ++ ){int num;cin >> num;cout << n - num + 1 << ' ';}cout << endl;}return 0;
} 

B. Array merging

#include <iostream>
#include <map>
using namespace std;
const int N = 2e5 + 10;
int a[N],b[N]; 
int main()
{int t;scanf("%d",&t);while(t -- ){int n,ans = 0;scanf("%d",&n);map<int,int> QA,QB;for(int i = 1;i <= n;i ++ )scanf("%d",&a[i]);for(int i = 1;i <= n;i ++ )scanf("%d",&b[i]);for(int i = 1;i <= n;i ++ ){int j = i + 1,l = 1;while(a[j] == a[i] && j <= n){j ++ ;l ++ ;}i = j - 1;QA[a[i]] = max(QA[a[i]],l);}for(int i = 1;i <= n;i ++ ){int j = i + 1,l = 1;while(b[j] == b[i] && j <= n){j ++ ;l ++ ;}i = j - 1;QB[b[i]] = max(QB[b[i]],l);}for(auto p : QA){ans = max(ans,p.second + QB[p.first]);}for(auto p : QB){ans = max(ans,p.second + QA[p.first]);}printf("%d\n",ans);}return 0;
}

2023年5月29日 

牛客小白月赛70

小d和答案修改 

#include <iostream>
using namespace std;
int main()
{string s;cin >> s;for(int i = 0;i < s.size();i ++ ){if(s[i] >= 'a' && s[i] <= 'z')s[i] -= 32;else if(s[i] >= 'A' && s[i] <= 'Z')s[i] += 32;}cout << s << endl;return 0;
}

小d和图片压缩

 

#include <iostream>
using namespace std;
const int N = 1000 + 10;
int a[N][N];
int main()
{int n,m;cin >> n >> m;for(int i = 1;i <= n;i ++ ){for(int j = 1;j <= m;j ++ ){cin >> a[i][j];}}for(int i = 1;i <= n;i += 2 ){for(int j = 1;j <= m;j += 2 ){cout << (a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1]) / 4 << ' ';}cout << endl;}return 0;
}

小d和超级泡泡堂

#include <iostream>
#include <queue>
using namespace std;
const int N = 1000 + 10;
char g[N][N];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
bool vis[N][N];
int ans = 0;
int n,m,sx,sy;
struct point
{int x;int y;
};
void bfs()
{queue<point> Q;Q.push({sx,sy});vis[sx][sy] = 1;while(Q.size()){point t = Q.front();Q.pop();for(int i = 0;i < 4;i ++ ){int X = t.x + dx[i];int Y = t.y + dy[i];if(X >= 1 && X <= n && Y >= 1 && Y <= m && g[X][Y] != '#' && !vis[X][Y]){vis[X][Y] = true;if(g[X][Y] == '!')ans ++ ;Q.push({X,Y});}}}
}
int main()
{cin >> n >> m;for(int i = 1;i <= n;i ++ ){for(int j = 1;j <= m;j ++ ){cin >> g[i][j];if(g[i][j] == '@'){sx = i;sy = j;}}}bfs();cout << ans << endl;return 0;
}

小d和孤独的区间

#include <iostream>
using namespace std;
const int N = 1000000 + 10;
typedef long long ll;
ll a[N];
int main()
{ll n,ans = 0,num1 = 0,num2 = 0;cin >> n;for(int i = 1;i <= n;i ++ ){cin >> a[i];if(a[i] == 0)num1 ++ ;if(a[i] == 1)num2 ++ ;}for(int i = 1;i <= n;i ++ ){if(a[i] == 0)continue;else if(a[i] == 1){ans ++ ;ll t1 = 0,t2 = 0;ll l = i - 1;ll r = i + 1;while(a[l] == 0 && l >= 1){t1 ++ ;l -- ;}while(a[r] == 0 && r <= n){t2 ++ ;r ++ ;}if(!t1 || !t2)ans = ans + t1 + t2;else {ans = ans + t1 + t2;ans += t1 * t2;}}}cout << ans << endl;return 0;
}

小d的博弈 

#include <iostream>
using namespace std;
typedef long long ll;
int main()
{ll t;cin >> t;while(t -- ){ll n,m;cin >> n >> m; n ++ ;m ++ ;ll cnt = 0,flaga = 0,flagb = 0;while(n){flaga ++ ;n /= 2;}while(m){flagb ++ ;m /= 2;}if(flaga == flagb)cout << "Bob" << endl;else cout << "Alice" << endl;}return 0;
}

2023年6月4日 

Codeforces Round 876 (Div. 2)

A. The Good Array

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 100 + 10;
int a[N];
int main()
{int t;cin >> t;while(t -- ){memset(a,0,sizeof(a));int n,k,ans = 0;cin >> n >> k;for(int i = 1;i <= n;i += k )a[i] = 1;a[n] = 1;for(int i = 1;i <= n;i ++ ){if(a[i] == 1)ans ++ ;}cout << ans << endl;}return 0;
}

B. Lamps

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
int cmp(PII a,PII b)
{if(a.first != b.first)return a.first > b.first;else return a.second > b.second;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while(t -- ){vector<PII> Q;ll n,ans = 0;cin >> n;while(n -- ){ll a,b;cin >> a >> b;Q.push_back({a,b});}sort(Q.begin(),Q.end(),cmp);for(int i = 0;i < Q.size();i ++ ){int j = i + 1;while(Q[j].first == Q[i].first && j < Q.size())j ++ ;int nums = Q[i].first,cnt = 0;for(int k = i;k < j;k ++ ){ans += Q[k].second;cnt ++ ;if(cnt >= nums)break;	}i = j - 1;}cout << ans << endl;}
}

C. Insert Zero and Invert Prefix

#include <iostream>
using namespace std;
const int N = 100000 + 10;
int a[N];
int main()
{int t;cin >> t;while(t -- ){int n;cin >> n;for(int i = 1;i <= n;i ++ )cin >> a[i];if(a[n] == 1)cout << "NO" << endl;else {cout << "YES" << endl;for(int i = n;i >= 1;i -- ){if(a[i] == 0 && a[i - 1] != 1)cout << 0 << ' ';else {int r = i,l = r - 1;while(a[l] == 1 && l >= 1)l -- ;for(int k = l + 1;k <= r;k ++ ){if(a[k] == 1)cout << 0 << ' ';else if(a[k] == 0)cout << r - 1 - l << ' ';}i = l + 1;}}cout << endl;}}return 0;
}

2023年6月5日

Codeforces Round 877 (Div. 2)

A. Blackboard List 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{int t;cin >> t;while(t -- ){int n;cin >> n;vector<int> Q;while(n -- ){int num;cin >> num;Q.push_back(num);}sort(Q.begin(),Q.end());Q.erase(unique(Q.begin(),Q.end()),Q.end());if(Q[0] < 0)cout << Q[0] << endl;else cout << Q[Q.size() - 1] << endl;}return 0;
}

B. Minimize Permutation Subarrays

#include <iostream>
using namespace std;
const int N = 200000 + 10;
int a[N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int t;cin >> t;while(t -- ){int n;cin >> n;int idxl = -1,idxr = -1,idx = -1; for(int i = 1;i <= n;i ++ ){cin >> a[i];if(a[i] == 1)idxl = i;else if(a[i] == 2)idxr = i;else if(a[i] == n)idx = i;}if(idxl > idxr)swap(idxl,idxr);if(idx > idxl && idx < idxr)cout << 1 << ' ' << 1 << endl;else if(idx < idxl)cout << idx << ' ' << idxl << endl;else if(idx > idxr)cout << idx << ' ' << idxr << endl;	}return 0;
}

C. No Prime Differences

#include <iostream>
using namespace std;
const int N = 1000 + 10;
int s[N][N],a[N][N],b[N][N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while(t -- ){int n,m;cin >> n >> m;for(int i = 1;i <= n;i ++ ){for(int j = 1;j <= m;j ++ ){s[i][j] = (i - 1) * m + j;if(i <= n / 2)a[i][j] = s[i][j];else b[i][j] = s[i][j];}}for(int i = n / 2 + 1;i <= n;i ++ ){for(int j = 1;j <= m;j ++ ){s[(i - n / 2) * 2 - 1][j] = b[i][j];}}for(int i = 1;i <= n / 2;i ++ ){for(int j = 1;j <= m;j ++ ){s[i * 2][j] = a[i][j];}}for(int i = 1;i <= n;i ++ ){for(int j = 1;j <= m;j ++ ){cout << s[i][j] << ' ';}cout << endl;}}return 0;
}

2023年6月6日

Codeforces Round 878 (Div. 3)

A. Cipher Shifer 

#include <iostream>
using namespace std;
int main()
{int t;cin >> t;while(t -- ){string ans;int n;cin >> n;string s;cin >> s;for(int i = 0;i < s.size();i ++ ){int j = i + 1;while(s[j] != s[i] && j < s.size())j ++ ;ans += s[i];i = j;}cout << ans << endl;}return 0;
} 

B. Binary Cafe 

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{int t;cin >> t;while(t -- ){ll n,k;cin >> n >> k;ll t = log2(n + 1);ll ans = 1;ll o = min(t,k);while(o -- )ans = ans * 2;if(k > t)ans += n - pow(2,t) + 1;cout << ans << endl;}return 0;
}

C. Ski Resort

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 200000 + 10;
ll a[N];
int main()
{ll t;cin >> t;while(t -- ){ll ans = 0;ll n,k,q;cin >> n >> k >> q;for(ll i = 1;i <= n;i ++ )cin >> a[i];ll len = 0;for(ll i = 1;i <= n;i ++ ){if(a[i] > q){if(len && len >= k){
//					cout << len - k + 1 << endl;for(ll j = 1;j <= len - k + 1;j ++ )ans += j;}len = 0;}else len ++ ;}if(len && len >= k){
//			cout << len - k + 1 << endl;for(ll j = 1;j <= len - k + 1;j ++ )ans += j;}cout << ans << endl;}return 0;
}

D. Wooden Toy Festival

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool check(int mid,vector<int> A)
{int cur = -2e9,cnt = 0;for(int i = 0;i < A.size();i ++ ){if(abs(A[i] - cur) > mid){cur = A[i] + mid;cnt ++ ;}}return cnt <= 3;
} 
void solve()
{vector<int> A;int n;cin >> n;for(int i = 1;i <= n;i ++ ){int num;cin >> num;A.push_back(num);}sort(A.begin(),A.end());A.erase(unique(A.begin(),A.end()),A.end());int l = 0,r = A[A.size() - 1];if(A.size() <= 3)cout << 0 << endl;else {while(l < r){int mid = l + r >> 1;if(check(mid,A))r = mid;else l = mid + 1;}cout << r << endl;}
}
int main()
{int t;cin >> t;while(t -- ){solve();}return 0;
}