2023牛客第八場補題報告A H J K

A-Alive Fossils_2023牛客暑期多校訓練營8 (nowcoder.com)

思路

統計字符串，取出現次數為t的。

代碼

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define sc secondusing namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int, int> PII;
int n;
int a[N];map<string, int> mp;
void solve() {cin >> n;while (n--) {string s;cin >> s;mp[s]++;}
}signed main() {IOS;int t = 1;cin >> t;for (int i = 1; i <= t; i++) {solve();}set<string> res;for (auto [i, j] : mp) {if (j == t) res.insert(i);}cout << res.size() << "\n";for (auto i : res) cout << i << "\n";
}

H-Insert 1, Insert 2, Insert 3, …_2023牛客暑期多校訓練營8 (nowcoder.com)

思路

注意到其實確定了最左邊和最右邊，其間的區間都可以作為右端點，所以就是需要找到每次最遠的右端點，用棧一層層維護。

代碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve();
signed main(){cin.sync_with_stdio(0);cin.tie(0);int T = 1;//cin >> T;while(T--){solve();}return 0;
}#define N 1001000
vector<int> q, stk[N];
int ban[N], a[N];
void solve(){int n;cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];}q.push_back(n + 1);int ans = 0;for(int i = n;i >= 1;i--){if(stk[a[i] + 1].size()){ban[stk[a[i] + 1].back()] = 1;stk[a[i] + 1].pop_back();}if(a[i] > 1){q.push_back(i);stk[a[i]].push_back(i);}while(ban[q.back()] == 1)q.pop_back();ans += q.back() - i;}cout << ans << "\n";
}

J-Permutation and Primes_2023牛客暑期多校訓練營8 (nowcoder.com)

思路

直接考慮枚舉，我的想法是考慮3的等差數列，然后考慮三個等差數列中間怎樣銜接，最終枚舉得出答案。

代碼

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define sc secondusing namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int, int> PII;
int n;
int a[N];bool check(int m) {for (int i = 2; i * i <= m; i++) {if (m % i == 0) return 0;}return 1;
}void solve() {cin >> n;vector<int> res;if (n % 3 == 2) {// 5 2單獨考慮if (n == 5) {cout << "5 2 1 4 3\n";return;}if (n == 2) {cout << "1 2\n";return;}res.push_back(n - 2);res.push_back(n - 5);for (int i = n; i > 0; i -= 3) res.push_back(i);for (int i = 1; i <= n; i += 3) res.push_back(i);for (int i = n - 8; i > 0; i -= 3) res.push_back(i);for (auto i : res) cout << i << " ";cout << "\n";} else if (n % 3 == 1) {// n - 1 n - 4??(2 1 0)//(n - 2)%3 == 2if (n == 1) {cout << 1 << "\n";return;}if (n == 4) {cout << "4 1 2 3\n";return;}if (n == 7) {cout << "1 2 3 4 7 6 5\n";return;}if (n == 10) {cout << "1 2 3 4 7 6 5 8 9 10\n";return;}res.push_back(n - 2);res.push_back(n - 5);res.push_back(n - 8);res.push_back(n - 1);res.push_back(n - 4);res.push_back(n - 11);for (int i = n - 14; i > 0; i -= 3) res.push_back(i);for (int i = 1; i <= n; i += 3) res.push_back(i);for (int i = n - 7; i > 0; i -= 3) res.push_back(i);for (auto i : res) cout << i << " ";cout << "\n";} else {// n-1%3==2// n n-3 n-6// 3 6if (n == 3) {cout << "1 2 3\n";return;}if (n == 6) {cout << "6 5 2 1 4 3\n";return;}res.push_back(n);res.push_back(n - 3);res.push_back(n - 6);for (int i = n - 1; i > 0; i -= 3) res.push_back(i);for (int i = 1; i <= n; i += 3) res.push_back(i);for (int i = n - 9; i > 0; i -= 3) res.push_back(i);for (auto i : res) cout << i << " ";cout << "\n";}
}signed main() {IOS;int t = 1;cin >> t;for (int i = 1; i <= t; i++) {solve();}
}

K-Scheming Furry_2023牛客暑期多校訓練營8 (nowcoder.com)

思路

很容易發現其實在n，m都不等于2時答案只可能是fox和平局，然后再分別討論n，m分別為2和同時為2的時候答案即可。

代碼

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define sc secondusing namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int, int> PII;
int n, m;
int a[N];int mp[500][500];
int tmp[500][500];
void solve() {cin >> n >> m;bool ok = 0;for (int i = 1; i <= n; i++) {int l = INF, r = -INF;for (int j = 1; j <= m; j++) {cin >> mp[i][j];l = min(mp[i][j], l);r = max(mp[i][j], r);}if (r - l + 1 != m) ok = 1;}if (!ok) {if (n == 2 || m == 2) {if (n == 2 && m == 2) {// cout << "***";for (int i = 1; i <= n; i++) {int l = INF;for (int j = 1; j <= m; j++) {l = min(l, mp[i][j]);}for (int j = 1; j <= m; j++) {tmp[i][j] = mp[i][j] - l;}}for (int i = 1; i <= m; i++) {for (int j = 2; j <= n; j++) {if (tmp[j][i] != tmp[1][i]) {cout << "NSFW\n";return;}}}// 2 1// 4 3if (mp[1][1] == 2 && mp[1][2] == 1 && mp[2][1] == 4 && mp[2][2] == 3) {cout << "FOX\n";return;}// 3 4// 1 2if (mp[1][1] == 3 && mp[1][2] == 4 && mp[2][1] == 1 && mp[2][2] == 2) {cout << "FOX\n";return;}// 4 3// 2 1if (mp[1][1] == 4 && mp[1][2] == 3 && mp[2][1] == 2 && mp[2][2] == 1) {cout << "CAT\n";return;}} else {if (n == 2) {for (int i = 1; i <= n; i++) {int l = INF;for (int j = 1; j <= m; j++) {l = min(l, mp[i][j]);}for (int j = 1; j <= m; j++) {tmp[i][j] = mp[i][j] - l;}}for (int i = 1; i <= m; i++) {for (int j = 2; j <= n; j++) {if (tmp[j][i] != tmp[1][i]) {cout << "NSFW\n";return;}}}if(is_sorted(tmp[1]+1,tmp[1]+m+1)) {cout<<"FOX\n";return;}int cnt = 0;for (int j = 1; j <= m; j++) {for (int k = j + 1; k <= m; k++) {if (mp[1][j] > mp[1][k]) cnt++;}}if (mp[1][1] > mp[2][1]) cnt++;//cout<<cnt<<"\n";if (cnt % 2 == 0)cout << "CAT\n";elsecout << "NSFW\n";return;} else if (m == 2) {for (int i = 1; i <= n; i++) {int l = INF;for (int j = 1; j <= m; j++) {l = min(l, mp[i][j]);}for (int j = 1; j <= m; j++) {tmp[i][j] = mp[i][j] - l;}}for (int i = 1; i <= m; i++) {for (int j = 2; j <= n; j++) {if (tmp[j][i] != tmp[1][i]) {cout << "NSFW\n";return;}}}int cnt = 0;for (int j = 1; j <= n; j++) {for (int k = j + 1; k <= n; k++) {if (mp[j][1] > mp[k][1]) cnt++;}}if (mp[1][1] > mp[1][2]) cnt++;if (cnt % 2 == 1)cout << "FOX\n";elsecout << "NSFW\n";return;}}} else {for (int i = 1; i <= n; i++) {int l = INF;for (int j = 1; j <= m; j++) {l = min(l, mp[i][j]);}for (int j = 1; j <= m; j++) {tmp[i][j] = mp[i][j] - l;}}for (int i = 1; i <= m; i++) {for (int j = 2; j <= n; j++) {if (tmp[j][i] != tmp[1][i]) {cout << "NSFW\n";return;}}}int cnt = 0;if(is_sorted(mp[1]+1,mp[1]+m+1)) {for (int i = 1; i <= n; i++) {if (mp[i][1] != 1 + (i - 1)*m) cnt++;}if (cnt == 2) {cout << "FOX\n";return;} else {cout << "NSFW\n";return;}} else {cout << "NSFW\n";return;}}} else {cout << "NSFW\n";return;}
}signed main() {IOS;int t = 1;cin >> t;for (int i = 1; i <= t; i++) {solve();}
}