Codeforces Round 1034 (Div. 3)

比賽鏈接如下:https://codeforces.com/contest/2123?

A. Blackboard Game

Initially, the integers from?00?to n?1?are written on a blackboard.

In one round,

  • Alice chooses an integer?a?on the blackboard and erases it;
  • then Bob chooses an integer?b?on the blackboard such that?a+b≡3(mod4) and erases it.

Rounds take place in succession until a player is unable to make a move — the first player who is unable to make a move loses. Determine who wins with optimal play.

We define that x≡y(mod m)?whenever x?y?is an integer multiple of?mm.

解題思路:

其實根據輸入輸出也能大概猜出來

(a+b-3)%4=0, Alice去拿一個數, 然后Bob去進行配對, 誰先操作不了, 誰就輸了

eg:

n=4, 0 1 2 3

Alice拿0, Bob拿3進行配對

Alice拿1, Bob拿2進行配對

Bob贏

n=5, 0 1 2 3 4

這里Alice先拿0還是4無所謂,

Alice贏

n=8 0 1 2 3 ; 4 5 6 7

Bob贏

n%4==0, Bob贏

n%4!=0, Alice贏

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {ll n;cin >> n;if (n % 4 == 0) {cout << "Bob" << endl;} else {cout << "Alice" << endl;}
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

?B. Tournament

You are given an array of integers a1,a2,…,an. A tournament is held with?nn?players. Player?i?has strength?aiai.

While more than?k?players remain,

  • Two remaining players are chosen at random;
  • Then the chosen player with the lower strength is eliminated. If the chosen players have the same strength, one is eliminated at random.

Given integers?j?and?k?(1≤j,k≤n), determine if there is any way for player?j?to be one of the last?k?remaining players.

解題思路:

當k=1時, aj要想留下來, 只能是數組最大值,?

k>1時, aj肯定是能留下來的

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {int n, j, k;cin >> n >> j >> k;j--;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}if (k == 1) {int mx = *max_element(a.begin(), a.end());if (a[j] == mx) {cout << "YES" << endl;} else {cout << "NO" << endl;}} else {cout << "YES" << endl;}
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

?C. Prefix Min and Suffix Max

You are given an array?aa?of?distinct?integers.

In one operation, you may either:

  • choose a nonempty?prefix?of?aa?and replace it with its minimum value, or
  • choose a nonempty?suffix?of?aa?and replace it with its maximum value.

Note that you may choose the entire array?a.

For each element?ai, determine if there exists some sequence of operations to transform?aa?into?[ai]; that is, make the array?a?consist of only one element, which is?aiai. Output your answer as a binary string of length?nn, where the?ii-th character is?1?if there exists a sequence to transform?aa?into [ai], and?0?otherwise.

A?prefix?of an array is a subarray consisting of the first?kk?elements of the array, for some integer?k.

A?suffix?of an array is a subarray consisting of the last?k?elements of the array, for some integer?k.

給你一個不同整數的數組。
在一個操作中,您可以選擇a的非空前綴*并將其替換為其最小值,或者選擇a的非空前綴*并將其替換為其最大值。
注意,您可以選擇整個數組a。對于每個元素a?,確定是否存在一些操作序列將a轉換為[a′];
也就是說,使數組只包含一個元素,即a。將您的答案輸出為長度為n的二進制字符串,如果存在將a轉換為[ai]的序列,則第i個字符為1,否則為0。
對于整數k,數組的前綴是由數組的前k個元素組成的子數組。數組的后綴是由數組的最后k個元素組成的子數組。?

解題思路:

??????1.前綴最小值:元素 ai?是從數組開頭到 i?位置(a1?到 ai)的最小值。

2.后綴最大值:元素 ai?是從 i?位置到數組結尾(ai?到 an)的最大值。

3.可保留條件:如果 ai?是前綴最小值或后綴最大值,則存在操作序列將數組縮減為 [ai];否則,無法保留。

eg:?數組 [1, 3, 5, 4, 7, 2],輸出?100011

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {int n;cin >> n;vector<int> a(n + 1), pre(n + 1, INT_MAX), suf(n + 2);for (int i = 1; i <= n; i++) {cin >> a[i];pre[i] = min(pre[i - 1], a[i]);}for (int i = n; i >= 1; i--) {suf[i] = max(suf[i + 1], a[i]);}for (int i = 1; i <= n; i++) {cout << (a[i] == pre[i] || a[i] == suf[i] ? 1 : 0);}cout << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

?D. Binary String Battle

Alice and Bob are given a binary string?s?of length?n, and an integer?k?(1≤k<n).

Alice wins if she is able to transform all characters of?ss?into zeroes. If Alice is unable to win in a finite number of moves, then Bob wins.

Alice and Bob take turns, with Alice going first.

  • On Alice's turn, she may choose any?subsequence???of length?k?in?s, then set all characters in that subsequence to zero.
  • On Bob's turn, he may choose any?substring???of length?k?in?ss, then set all characters in that substring to one.

Note that Alice wins if the string consists of all zeros at any point during the game, including in between Alice's and Bob's turns.

Determine who wins with optimal play.

??A?subsequence?of a string?s?is a set of characters in?s. Note that these characters do not have to be adjacent.

??A?substring?of a string?s?is a contiguous group of characters in?s. Note that these characters must be adjacent.

解題思路:

1.Alice必贏的條件:
如果初始 cnt(s 中 1 的數量) ≤ k,Alice 一次就能把所有 1 清掉 —— 贏。
如果 n < 2*k,則 Bob 無法每次維護 cnt > k 的策略(因為沒地方藏一個"額外的 1")—— Alice?
2. Bob必贏的條件:
如果 cnt > k 且 n ≥ 2*k,Bob 總能維護至少一個額外的 1,并總能抵消 Alice 的操作 —— 贏。?

因為你要找兩個不重疊的長度為 k 的子串,至少需要長度 2k

否則他怎么也得和 Alice 的[清除區]發生重疊,Alice 就能全清了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){int n, k, cnt = 0;string s;cin >> n >> k >> s;for(char c : s){if(c == '1'){cnt++;}}cout << (cnt <= k || n < 2*k ? "Alice" : "Bob") << '\n';
}int main(){int t;cin >> t;while(t--) {solve();}return 0;
}

E. MEX Count

Define the?MEX (minimum excluded value) of an array to be the smallest nonnegative integer not present in the array. For example,

  • MEX([2,2,1])=0 because?0?is not in the array.
  • MEX([3,1,0,1])=2 because?0?and?1?are in the array but?2?is not.
  • MEX([0,3,1,2])=4 because?0,?1,?2, and?3?are in the array but?44?is not.

You are given an array?aa?of size?n?of nonnegative integers.

For all?k?(0≤k≤n), count the number of possible values of MEX(a)?after removing exactly?kk?values from?a.

解題思路:MEX是數組a中的最小非負整數

eg:

數組a:?

0 1 2 3 4 5 .. n

出現次數分別為:

1 2 1 3 0 2 .. 5

比如MEX=1, 我們最少需要刪除2個1

最多為n-1 (1之前每個數字次數剩1個,1后面全刪了,最后剩1個數字,刪除n-1個)

就是你刪除任意個[cntx, n-x] 都能得到x

題目是刪除k個數字, mex的可能性

然后差分即可

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {int t;cin >> t;while (t--) {int n;cin >> n;vector<int> a(n), cnt(n + 1, 0);for (int i = 0; i < n; i++) {cin >> a[i];if (a[i] <= n) {cnt[a[i]]++;}}vector<int> ok(n + 1, false);ok[0] = true;for (int m = 1; m <= n; m++) {ok[m] = ok[m - 1] && (cnt[m - 1] > 0);}vector<int> diff(n + 2, 0);for (int m = 0; m <= n; m++) {if (!ok[m])break;int L = cnt[m];int R = n - m;if (L <= R) {diff[L] += 1;diff[R + 1] -= 1;}}vector<int> ans(n + 1);int cur = 0;for (int k = 0; k <= n; k++) {cur += diff[k];ans[k] = cur;}for (int k = 0; k <= n; k++) {cout << ans[k] << (k == n ? '\n' : ' ');}}return 0;
}

?F. Minimize Fixed Points

Call a permutation??p?of length?nn?good?if?gcd(pi,i)>1?for all?2≤i≤n. Find a good permutation with the?minimum?number of?fixed points???across all good permutations of length?n. If there are multiple such permutations, print any of them.

???A permutation of length?nn?is an array that contains every integer from?1?to?n?exactly once, in any order.

gcd(x,y)?denotes the?greatest common divisor (GCD)?of?x?and?y.

??A?fixed point?of a permutation?p?is an index?j?(1≤j≤n) such that?pj=j.

解題思路:

n=6,

1 4 6 2 5 3

1 2 3 4 5 6

gcd:

1 2 3 2 5 3

fixed points = 2

gcd(pi,i)>1, i>1

i=0, a[0]=1

當n=13,

質數2及其倍數為:2? 4? 6? 8 10 12?

數左移一位, 就可以和下標形成 gcd(pi,i)=2

2 4 6 8 10 12

4 6 8 10 12 2

prime = 3

3 6 9 12

素數越大, 在1-n這個序列中, 倍數的出現次數越少??

prime=5

5 10

只能這兩進行輪換, 因此我們從prime比較大 -> prime比較小

prime在比較大的數輪換過后, 后續就不需要進行輪換了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1000005;
vector<bool> isp(MAXN, true); // isp[i] = true 表示是素數
void init(int n) {isp[0] = isp[1] = false;for (int i = 2; i * i <= n; i++) {if (isp[i]) {for (int j = i * i; j <= n; j += i) {isp[j] = false;}}}
}void solve() {int n;cin >> n;init(n);vector<int> a(n + 1, -1);vector<bool> vis(n + 1, false);for (int i = n / 2; i >= 2; i--) {if (!isp[i]) {continue;}vector<int> c;    收集所有 i 的倍數for (int j = i; j <= n; j += i) {if (vis[j]) {continue;}vis[j] = true;c.push_back(j);}// // 構造一個環:c[0]->c[1]->...->c[k-1]->c[0]for (int j = 0; j < c.size(); j++) {a[c[j]] = c[(j + 1) % c.size()];}}for (int i = 1; i <= n; i++) {cout << (a[i] == -1 ? i : a[i]) << " ";}cout << '\n';
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

G. Modular Sorting

?You are given an integer?m?(2≤m≤5?105) and an array?aa?consisting of nonnegative integers smaller than?m.

Answer queries of the following form:

  • 1?i?x: assign ai:=x
  • 2?k: in one operation, you may choose an element?aiai?and assign?ai:=(ai+k)(modm)a — determine if there exists some sequence of (possibly zero) operations to make?a?nondecreasing.

Note that instances of query?2?are independent; that is, no actual operations are taking place. Instances of query?1?are persistent.

a(modm)?is defined as the unique integer?bb?such that 0≤b<m?and a?b?is an integer multiple of?m.

An array?a?of size?n?is called nondecreasing if and only if ai≤ai+1?for all?1≤i<n.

解題思路:

(ai+k)%m?

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1000100;
vector<bool> isp;
vector<int> primes;void init(int top) {isp.assign(top + 1, true);isp[0] = isp[1] = false;for (int i = 2; i <= top; ++i) {if (isp[i])primes.push_back(i);for (int j = 0; j < (int)primes.size(); ++j) {int p = primes[j];if (i * p > top)break;isp[i * p] = false;if (i % p == 0)break;}}
}map<int, int> factorize(int v) {map<int, int> res;for (int i = 0; i < (int)primes.size(); ++i) {int p = primes[i];if (1LL * p * p > v)break;int cnt = 0;while (v % p == 0) {cnt++;v /= p;}if (cnt)res[p] = cnt;}if (v > 1)res[v] = 1;return res;
}vector<int> get_divisors(int v) {map<int, int> f = factorize(v);vector<int> res;res.push_back(1);for (map<int, int>::iterator it = f.begin(); it != f.end(); ++it) {int p = it->first, c = it->second;int sz = res.size();int base = 1;for (int i = 0; i < c; ++i) {base *= p;for (int j = 0; j < sz; ++j) {res.push_back(res[j] * base);}}}return res;
}int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }void solve() {int n, m, qn;cin >> n >> m >> qn;vector<int> a(n);for (int i = 0; i < n; i++)cin >> a[i];vector<array<int, 3>> q(qn);for (int i = 0; i < qn; i++) {cin >> q[i][0];if (q[i][0] == 1) {cin >> q[i][1] >> q[i][2];} else {cin >> q[i][1];}}vector<int> res(qn, -1);vector<int> b(n);vector<int> divisors = get_divisors(m);for (int d_index = 0; d_index < (int)divisors.size(); ++d_index) {int d = divisors[d_index];for (int i = 0; i < n; i++) {b[i] = a[i] % d;}int sum = 0;for (int i = 0; i + 1 < n; i++) {if (b[i] > b[i + 1])sum++;}for (int i = 0; i < qn; i++) {if (q[i][0] == 1) {int w = q[i][1] - 1;int v = q[i][2];if (w - 1 >= 0 && b[w - 1] > b[w])sum--;if (w + 1 < n && b[w] > b[w + 1])sum--;b[w] = v % d;if (w - 1 >= 0 && b[w - 1] > b[w])sum++;if (w + 1 < n && b[w] > b[w + 1])sum++;} else {if (gcd(q[i][1], m) == d) {res[i] = sum < m / d;}}}}for (int i = 0; i < qn; i++) {if (res[i] != -1) {cout << (res[i] ? "YES" : "NO") << '\n';}}
}int main() {init(MAXN);int t;cin >> t;while (t--) {solve();}return 0;
}

感謝大家的點贊和關注,你們的支持是我創作的動力!

?

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/pingmian/87299.shtml
繁體地址,請注明出處:http://hk.pswp.cn/pingmian/87299.shtml
英文地址,請注明出處:http://en.pswp.cn/pingmian/87299.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

微電網系列之微電網的孤島運行

個人主頁&#xff1a;云納星辰懷自在 座右銘&#xff1a;“所謂堅持&#xff0c;就是覺得還有希望&#xff01;” 微電網的孤島運行 微電網具有并網和孤島兩種運行模式&#xff0c;由于孤島運行模式下&#xff0c;分布式電源為微電網內部負荷提供頻率和電壓支撐&#xff0c;由…

JsonCpp的核心類及核心函數使用匯總

文章目錄 JsonCpp的核心類及核心函數使用匯總一、前言二、JsonCpp 核心類介紹三、Value 類函數解析1. 值獲取函數&#xff08;asxxx 系列 &#xff09;2. 值類型判斷函數&#xff08;isxxx 系列 &#xff09;3. 數組操作函數4. 對象操作函數5. 運算符重載6. 迭代器7. JSON 轉化…

Qt寫入excel

1.tableView導出到excel 點擊導出函數按鈕、發送sendMessage信號&#xff08;信號名稱&#xff0c;對象&#xff0c;數據&#xff09; void HydroelectricPowerPluginImpl::exportTableViewSelectedRows(QTableView* tableView, QWidget* parent) {if (!tableView || !tableVie…

OSCP - Proving Grounds - DC - 1

主要知識點 drupal 7 RCEfind SUID提權 具體步驟 nmap起手,80端口比較有意思&#xff0c;安裝了 Drupal 7 Starting Nmap 7.94SVN ( https://nmap.org ) at 2024-12-17 14:23 UTC Nmap scan report for 192.168.57.193 Host is up (0.00087s latency). Not shown: 65531 cl…

仿小紅書交流社區(微服務架構)

文章目錄 framework - 平臺基礎設施starter - jacksoncommonexceptionresponseutil starter - content 全局上下文distributed - id - generate - 分布式 IdSnowflake - 基于雪花算法生成 IdSegment - 基于分段式生成 Id OSS - 對象存儲KV - 短文本存儲筆記評論 user - 用戶服務…

大模型開源技術解析 4.5 的系列開源技術解析:從模型矩陣到產業賦能的全棧突破

提示&#xff1a;本篇文章 1300 字&#xff0c;閱讀時間&#xff1a;5分鐘。 前言 6 月 30 日&#xff0c;百度正式開源文心大模型 4.5 系列&#xff0c;這一動作不僅兌現了 2 月發布會上的技術承諾&#xff0c;更以 10 款全維度模型矩陣刷新了國內開源模型的技術邊界。從學術…

[6-02-01].第05節:配置文件 - YAML配置文件語法

SpringBoot學習大綱 一、YAML語法 1.1.概述&#xff1a; 1.YAML是一種數據序列化格式&#xff1b;2.它是以數據為中心3.容易閱讀&#xff0c;容易與腳本語言交互,如下圖所示&#xff1a; 1.2.基本語法 1.key: value&#xff1a;kv之間有空格2.使用縮進表示層級關系3.縮進時…

FPGA學習

一、module : 定義&#xff1a; 是構建數字系統的基本單元&#xff0c;用于封裝電路的結構和行為。它可以表示從簡單的邏輯門到復雜的處理器等任何硬件組件。 1. module 的基本定義 module 模塊名 (端口列表);// 端口聲明input [位寬] 輸入端口1;output [位寬] 輸出端口1;ino…

26-計組-存儲器與Cache機制

一、存儲器與局部性原理 1. 局部性原理 基礎概念&#xff1a; 時間局部性&#xff1a;一個存儲單元被訪問后&#xff0c;短時間內可能再次被訪問&#xff08;例如循環變量&#xff09;。空間局部性&#xff1a;一個存儲單元被訪問后&#xff0c;其附近單元可能在短時間內被訪…

I/O 線程 7.3

前言 以下&#xff1a; 概述 1.基礎 2.代碼演示 3.練習 4.分析題 1.基礎 一、線程基礎概念 并發執行原理 通過時間片輪轉實現多任務"并行"效果 實際為CPU快速切換執行不同線程 線程 vs 進程 線程共享進程地址空間&#xff0c;切換開銷更小 進程擁有獨立資源&am…

MySQL JSON數據類型完全指南:從版本演進到企業實踐的深度對話

&#x1f4ca; MySQL JSON數據類型完全指南&#xff1a;從版本演進到企業實踐的深度對話 在當今數據驅動的時代&#xff0c;MySQL作為最受歡迎的關系型數據庫之一&#xff0c;不斷演進以滿足現代應用的需求。JSON數據類型的引入&#xff0c;讓MySQL在保持關系型數據庫優勢的同時…

BI × 餐飲行業 | 以數據應用重塑全鏈路業務增長路徑

在競爭激烈的餐飲行業中&#xff0c;數據已成為企業保持競爭力的關鍵資產。通過深入分析顧客數據&#xff0c;餐飲企業能夠洞察消費者的需求和偏好&#xff0c;從而提供更加精準和個性化的服務。此外&#xff0c;利用數據優化業務管理&#xff0c;降低成本&#xff0c;并提高運…

【學習線路】機器學習線路概述與內容關鍵點說明

文章目錄 零、機器學習的企業價值一、基礎概念1. 機器學習定義2. 學習類型3. 學習范式 二、核心算法與技術1. 監督學習2. 無監督學習3. 模型評估與優化 三、深度學習與神經網絡1. 神經網絡基礎2. 深度學習框架3. 應用場景 四、工具與實踐1. 數據處理2. 模型部署3. 機器學習的生…

Linux 命令:cp

Linux cp 命令詳細教程 cp 是 Linux 系統中最常用的命令之一&#xff0c;用于復制文件或目錄。它可以將源文件/目錄復制到指定的目標位置&#xff0c;支持批量復制、強制覆蓋、保留文件屬性等功能。下面詳細介紹其用法。資料已經分類整理好&#xff1a;https://pan.quark.cn/s…

java分頁插件| MyBatis-Plus分頁 vs PageHelper分頁:全面對比與最佳實踐

MyBatis-Plus分頁 vs PageHelper分頁&#xff1a;全面對比與最佳實踐 一、分頁技術概述 在Java持久層框架中&#xff0c;分頁是高頻使用的功能。主流方案有&#xff1a; MyBatis-Plus分頁&#xff1a;MyBatis增強工具的內置分頁方案PageHelper分頁&#xff1a;獨立的MyBatis…

PROFINET轉MODBUS TCP網關在機械臂通信操作中的應用研究

在特定的汽車零部件生產工廠焊接生產線上&#xff0c;機械臂被應用于焊接作業&#xff0c;其控制體系基于Profinet協議。同時&#xff0c;工廠的自動化控制體系以西門子S7-1200PLC為核心&#xff0c;通過ModbusTCP協議實現數據交換。為實現焊接過程的自動化控制以及生產數據的實…

Mac中如何Chrome禁用更新[update chflags macos]

寫在前面 在 macOS 系統中&#xff0c;系統更新提示的小紅點常常讓人不勝其擾。 尤其是當你希望保持現有系統的穩定性&#xff0c;或因兼容性問題暫不想升級時&#xff0c;這個小紅點就像一個頑固的提醒。 - windowsMac版直接刪除更新程序, 有效 cd ~/Library/Google/Googl…

LoRA使用-多個LoRA

LoRA的風格分類 不用去記它有什么很特別的風格&#xff0c;簡單來說基礎模型就像一個全能畫手&#xff0c;什么都能畫&#xff0c;而LoRA是在某個風格中經過特訓的它的一個分身。使得它更精通該風格。 關于LoR風格分類&#xff1a;提示詞撰寫公式 Checkpoint&LoRA對比 訓…

牛客刷題 — 【排序】[NOIP2012] 國王的游戲(高精度結構體排序)

1.題面&#xff1a;傳送門 2. 思路&#xff1a; 相鄰的兩個大臣的先后順序只會互相影響&#xff0c;并不會影響其他人的金幣數。 假設前 i-1 個人左手上的數乘積為 s 。 ① 若 A 大臣排在B 大臣的前面&#xff0c;則&#xff1a; s 此時的金幣數最大值為 。 ② 若B大臣排…

grpc 和限流Sentinel

基于gRPC的微服務通信模塊技術方案書 1. 總體架構設計 #mermaid-svg-TiN9cudEfW5mCWHm {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-TiN9cudEfW5mCWHm .error-icon{fill:#552222;}#mermaid-svg-TiN9cudEfW5mCWHm…