Codeforces Round 950 (Div. 3)(A~F2)

G題只會暴力..不會數據結構

A - 問題 Generator?

暴力模擬即可

// Problem: A. Problem Generator
// Contest: Codeforces - Codeforces Round 950 (Div. 3)
// URL: https://codeforces.com/contest/1980/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int a[7];int n , m;cin >> n >> m;for(int i = 0 ; i < 7 ; i ++){a[i] = m;}	string s;cin >> s;for(auto c : s){a[c - 'A']--;}int cnt = 0 ;for(int i = 0 ; i < 7 ;i ++){cnt += max(0 , (a[i]));}cout << cnt << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

B - Choosing Cubes??

??????? 題意:

??????? 還是暴力模擬,記錄一下最喜歡立方體在排序后的左右界,然后搞一搞

// Problem: B. Choosing Cubes
// Contest: Codeforces - Codeforces Round 950 (Div. 3)
// URL: https://codeforces.com/contest/1980/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
bool cmp(int a  , int b){return a > b;
}
void solve() 
{int n , f , k;cin >> n >> f >> k;for(int i = 1 ; i <= n ; i ++)cin >> a[i];int tar = a[f];sort(a.begin() + 1 , a.begin() + 1 + n , cmp);int l = -1 , r;for(int i = 1 ; i <= n ; i ++){if(a[i] == tar){if(l == -1){l = i;}r = i;}}if(l > k){cout <<"No\n";}else if(r <= k){cout <<"Yes\n";}else{cout <<"Maybe\n";}
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

C - Sofia and the Lost Operations??

??????? 題意:

??????? 思路:若最后一個修改數存在于b數組中,那么只需要看這些修改的數能否把a數組中待修改的數全部覆蓋即可,否則一定不存在。

????????

// Problem: C. Sofia and the Lost Operations
// Contest: Codeforces - Codeforces Round 950 (Div. 3)
// URL: https://codeforces.com/contest/1980/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int n;cin >> n;int a[n] , b[n];for(int i = 0 ; i < n ; i ++)cin >> a[i];for(int i = 0 ; i < n ; i ++)cin >> b[i];set<int>st;map<int , int>mp;for(int i = 0 ; i < n ; i ++)st.insert(b[i]);for(int i = 0 ; i < n ; i ++){if(a[i] != b[i]){mp[b[i]]++;}}int m;cin >> m;vector<int>tmp;for(int i = 0 ; i < m ; i ++){int x;cin >> x;tmp.pb(x);}if(st.count(tmp[tmp.size() - 1])){for(auto it : tmp){mp[it]--;}int ok = 1;for(auto it : mp){if(it.second > 0){ok = 0;}}if(ok)cout <<"YES\n";elsecout <<"NO\n";}else{cout <<"NO\n";}
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

D - GCD-sequence??

??????? 題意:

??????? 思路:將刪除前的gcd序列求出來,可以發現若要滿足題意,必然需要找到gcd序列中最后一個遞減的位置,并且刪除與之相關的數(只有三個數與之相關)。然后判斷刪除后的序列能否形成非遞減即可。

????????

// Problem: D. GCD-sequence
// Contest: Codeforces - Codeforces Round 950 (Div. 3)
// URL: https://codeforces.com/contest/1980/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int n;cin >> n;for(int i = 0 ; i < n ; i ++){cin >> a[i];}	vector<int>b;for(int i = 1 ; i < n ; i ++){b.pb(__gcd(a[i] , a[i - 1]));}int f1 = -1, f2 = -1 , f3 = -1;for(int i = b.size() - 1 ; i >= 1 ; i --){if(b[i - 1] > b[i]){f1 = i + 1;f2 = i;f3 = i - 1;break;}}if(f1 == -1){cout << "YES\n";return;}else{vector<int>tmp;vector<int>tmpb;for(int i = 0 ; i < n ; i ++){if(i == f1) continue;tmp.pb(a[i]);}for(int i = 1 ; i < n - 1; i ++){tmpb.pb(__gcd(tmp[i] , tmp[i - 1]));}		int ok = 1;for(int i = 1 ; i < n - 2 ; i ++){if(tmpb[i] >= tmpb[i - 1]) continue;else ok = 0;}if(ok){cout <<"YES\n";return;}tmp.clear();tmpb.clear();for(int i = 0 ; i < n ; i ++){if(i == f2) continue;tmp.pb(a[i]);}for(int i = 1 ; i < n - 1; i ++){tmpb.pb(__gcd(tmp[i] , tmp[i - 1]));}		ok = 1;for(int i = 1 ; i < n - 2 ; i ++){if(tmpb[i] >= tmpb[i - 1]) continue;else ok = 0;}if(ok){cout <<"YES\n";return;}tmp.clear();tmpb.clear();for(int i = 0 ; i < n ; i ++){if(i == f3) continue;tmp.pb(a[i]);}for(int i = 1 ; i < n - 1; i ++){tmpb.pb(__gcd(tmp[i] , tmp[i - 1]));}		ok = 1;for(int i = 1 ; i < n - 2 ; i ++){if(tmpb[i] >= tmpb[i - 1]) continue;else ok = 0;}if(ok){cout <<"YES\n";return;}}cout <<"NO\n";
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

E - Permutation of Rows and Columns??

??????? 題意:給定兩個矩陣,每個格子中有一個唯一的數。求這兩個矩陣能否通過行變換,列變換變成相同的矩陣。

??????? 思路:可以發現無論怎么變換,一行/一列中的數的情況是一樣的,因此只需要看兩個矩陣每一行/每一列中的數是否匹配即可。

????????

// Problem: E. Permutation of Rows and Columns
// Contest: Codeforces - Codeforces Round 950 (Div. 3)
// URL: https://codeforces.com/contest/1980/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int n , m;cin >> n >> m;int a[n][m];for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j < m ; j ++)cin >> a[i][j];}	int b[n][m];for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j < m ; j ++)cin >> b[i][j];}		map< set<int> , int> mp;map< set<int> , int> pm;	for(int i = 0 ; i < n ; i ++){set<int>tmp;for(int j = 0 ; j < m ; j ++){tmp.insert(a[i][j]);}mp[tmp]++;}for(int i = 0 ; i < m ; i ++){set<int>tmp;for(int j = 0 ; j < n ; j ++){tmp.insert(a[j][i]);}pm[tmp]++;}	for(int i = 0 ; i < n ; i ++){set<int>tmp;for(int j = 0 ; j < m ; j ++){tmp.insert(b[i][j]);}if(mp.count(tmp)){continue;}else{cout <<"NO\n";return;}}for(int i = 0 ; i < m ; i ++){set<int>tmp;for(int j = 0 ; j < n ; j ++){tmp.insert(b[j][i]);}if(pm.count(tmp)){continue;}else{cout <<"NO\n";return;}}	cout <<"YES\n";
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

F2 - Field Division (hard version)?

?

思路:(純暴力做法)可以發現:若一個噴泉的左下方存在另一個噴泉,那么Alice就不會劃線到該噴泉旁邊,而是會劃到左下方噴泉中最左邊的那個噴泉的左側。 因此只需要記錄一下每一行左下方最左側噴泉的位置即可,然后再計算每一行劃了多少,由于矩陣很大,所以需要離散化處理。

??????? 另外如何判斷刪除某噴泉后會增加多少,同樣是模擬刪除該噴泉后的,在其上方的噴泉的情況,然后如果跟沒刪除前一樣就不用再模擬下去了。

????????

// Problem: F1. Field Division (easy version)
// Contest: Codeforces - Codeforces Round 950 (Div. 3)
// URL: https://codeforces.com/contest/1980/problem/F1
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
#define int long long
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int n , m , k;cin >> n >> m >> k;pair<int,int>p[k];for(int i = 0 ; i < k ; i ++){cin >> p[i].x >> p[i].y;}	set<int>st;for(int i = 0 ; i < k ; i ++){st.insert(p[i].x);}int idx = 0;map<int,int>mp;map<int,int>pm;for(auto it : st){mp[it] = ++idx;pm[idx] = it;}map<int , set<int> >left;for(int i = 0 ; i < k ; i ++){int idx = mp[p[i].x];left[idx].insert(p[i].y);}vector<int>pre(idx + 5 , m + 1);for(int i = idx; i >= 0 ; i --){if(i != 0)pre[i] = min(pre[i + 1] , *left[i].begin());elsepre[i] = pre[i + 1];}int ans = 0;for(int i = 0 ; i <= idx ; i ++){int l , r;if(i == 0){l = 0;}else{l = pm[i];}if(i == idx){r = n;}else{r = pm[i + 1];}ans += (pre[i + 1] - 1) * (r - l);}cout << ans << endl;for(int i = 0 ; i < k ; i ++){int idx = mp[p[i].x];if(p[i].y > *left[idx].begin()){cout << 0 << " ";}else{if(p[i].y < pre[idx + 1]){auto it = left[idx].begin();it++;int x;if(it == left[idx].end())x = pre[idx + 1];elsex = *it;int out = 0;x = min(x , pre[idx + 1]);out += (x - p[i].y) * (pm[idx] - pm[idx - 1]);for(int i = idx - 1; i >= 0 ; i --){x = min(x , *left[i].begin());if(x == pre[i]) break;out += (x - pre[i]) * (pm[i] - pm[i - 1]);			}cout << out << " ";}else{cout << 0 << " ";}}}cout << endl;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

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

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

相關文章

哈夫曼樹的構造,哈夫曼樹的存在意義--求哈夫曼編碼

一:哈夫曼樹的構造 ①權值,帶權路徑長度。 ②一組確定權值的葉子節點可以構造多個不同的二叉樹,但是帶權路徑長度min的是哈夫曼樹 ③算法基本思想及其實操圖片演示 注:存儲結構和偽代碼 1 初始化: 構造2n-1棵只有一個根節點的二叉樹,parent=rchild=lchild=-1; 其中…

構造一個高效的哈希表:從基本思路到最終實現

哈希表是計算機科學中常用的數據結構之一&#xff0c;它提供了快速的查找、插入和刪除操作。在本篇博客中&#xff0c;我們將探討如何構造一個高效的哈希表&#xff0c;從最基本的思路逐步完善&#xff0c;直至最終實現。 1. 初始思路&#xff1a;使用布爾數組存儲 我們最初的…

AIGC 全面介紹

隨著人工智能技術的不斷進步&#xff0c;生成式人工智能&#xff08;AI Generated Content, AIGC&#xff09;成為了一個日益熱門的話題。AIGC 指利用人工智能技術生成各類內容&#xff0c;包括文本、圖像、音頻、視頻等。與傳統的內容生成方法相比&#xff0c;AIGC 具有速度快…

谷歌創新框架:從非結構化數據,實現多模態學習

看、聽、說的多模態已成為主流大模型的重要功能之一。但在數據爆炸時代&#xff0c;大模型學習文本類的結構化數據相對還好一些&#xff0c;但要去學習視頻、音頻、圖片等非結構化數據非常困難。 目前&#xff0c;從結構化和非結構化數據實現多模態學習&#xff0c;會隨著模態…

RK3588 VOP圖層分配介紹

RK3588 VOP圖層分配介紹 RK3588圖層介紹 RK3588有8個圖層&#xff0c;分別是Custer 0/1/2/3 和Esmart 0/1/2/3&#xff0c;兩種圖層的能力不一樣&#xff0c;具體如下&#xff1a; Custer 分辨率&#xff1a;最大分辨率包括兩種合并集群和單集群&#xff0c;分別為7680x432…

QT_UI設計

mainwindow.h #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow>QT_BEGIN_NAMESPACE //命名空間 namespace Ui { class MainWindow; } //ui_MainWindow文件里定義的類&#xff0c;外部聲明 QT_END_NAMESPACEclass MainWindow : public QMainWindow {Q_O…

AccessibilityEvent的生成和處理

在 Android 框架層&#xff0c;AccessibilityEvent 的生成和處理是通過系統的 UI 框架和輔助功能服務框架密切協作來實現的。這個機制涉及幾個關鍵的部分&#xff1a;UI 組件、輔助功能服務、事件監聽和事件分發。以下是對這些部分和它們如何協同工作的詳細解釋&#xff1a; 1…

httprunner接口自動化測試框架使用說明【保姆級教程】

背景介紹&#xff1a; httprunner是國內開源的一個接口自動化框架&#xff0c;已經有部分公司開始使用這種框架來完成自己公司的接口自動化編寫&#xff0c;本文主要是從簡單的流程上去講解咋使用的&#xff08;PS&#xff1a;開發者本尊的官網教程寫的是真的爛。。。&#xf…

JVM調優實戰

如果老年代能回收掉大部分&#xff0c;說明年輕代太小了&#xff0c;放不下 OOM 1數據量一次性申請的內存過多&#xff0c;比如數據庫查詢返回值大多&#xff0c;所以做個分頁 2.并發過高的情況下&#xff0c;一些連接未釋放 3.堆內存不夠

DP-Kmaens密度峰值聚類算法

我有個問題 關于 [密度值>密度閾值] 的判定這里&#xff0c;新進來的新數據怎么確定他的密度值&#xff1f;密度閾值又是怎樣確定的呢&#xff1f;

正則表達式 0.1v

正則表達式 擴展 --> :% s/\///g //文件里面所有的 / 去掉 * 通配符 \ //轉義&#xff0c;讓字符變成原本的意思 ^ //行首 $ //行尾 [0-9] //數字 [a-z] //小寫字母 [A-Z] //大寫字母 把文件的小寫字母替換為大寫字母&#xff1f; 固定寫法 :% s/[a-…

Vscode git 插件

超好用的git記錄 軟件 安裝之后&#xff0c;鼠標在哪一行就可以看最新一次是誰提交的&#xff0c;真的超好用&#xff01;&#xff01;&#xff01;

43頁 | 2024年企業級BI平臺白皮書(免費下載)

【1】關注本公眾號&#xff0c;轉發當前文章到微信朋友圈 【2】私信發送 2024年企業級BI平臺白皮書 【3】獲取本方案PDF下載鏈接&#xff0c;直接下載即可。 誠摯邀請您微信掃碼加入以下方案驛站知識星球&#xff0c;獲取上萬份PPT/WORD解決方案&#xff01;&#xff01;&…

【NOI】C++程序結構入門之循環結構二-for循環

文章目錄 前言一、for循環1.導入2.語法3.使用場景4.條件控制5.小結 二、例題講解問題&#xff1a;1264 - 4位反序數問題&#xff1a;1085 - 尋找雷劈數問題&#xff1a;1057 - 能被5整除且至少有一位數字是5的所有整數的個數問題&#xff1a;1392 - 回文偶數&#xff1f;問題&a…

Linux命令 netstat -anp | grep 的用法

文章目錄 1、第一種解釋2、第二種解釋3、第三種解釋4、第四種解釋5、第五種解釋6、netstat --help 在Windows中&#xff0c;殺死端口占用的博客鏈接 1、第一種解釋 在Unix和Linux系統中&#xff0c;netstat -anp 命令用于顯示所有的網絡連接&#xff08; -a 表示所有&#xff…

文件md5加密

使用場景&#xff1a;為了避免上傳資源空間的浪費&#xff0c;通過對文件進行md5摘要加密獲取唯一的值&#xff0c;從數據庫中查詢是否已有該md5碼存在&#xff0c;不存在的就上傳&#xff0c;存在的話使用之前已存儲的文件信息。 如何加密 下載插件browser-md5-file 【之前有…

maridb10.4.30數據庫數據遷移

1.新建數據存儲文件夾&#xff0c;例如E:\maridb_data 2.修改原數據所在目錄的my.ini文件&#xff0c;例如D:\Program Files\MariaDB 10.4\data\my.ini 3.剪切除my.ini文件外的其他所有文件到遷移目的地文件(E:\maridb_data) 結果如下&#xff1a; 原數據文件目錄&#xff1a…

聊聊限流的一些事兒

一、背景 最近幾年&#xff0c;隨著微服務的流行&#xff0c;服務與服務之間依賴越來越強&#xff0c;調用也越來越復雜&#xff0c;服務間的穩定性變突顯出來。特別是在遇到突發請求時&#xff0c;常常需要通過緩存、限流、熔斷降級、負載均衡等多種方式保證服務的穩定性。其…

C++命名空間(詳解)

C基礎語法 C基于C語言的改進&#xff1a;c在C語言的基礎上引入并擴充了面向對象的概念 C基礎概念&#xff1a;C是基于C語言而產生的,它即可以進行C語言的過程化程序設計,又可以進行以抽象數據類型為特點的基于對象的程序設計,還可以進行面向對象的程序設計 在1998年 出現C98…

愛普生差分晶振在光模塊中的重要角色

光模塊是現代通信設備中的重要組成部分&#xff0c;主要用于實現光電轉換和信號傳輸&#xff0c;它是一種將光信號轉換為電信號&#xff0c;或者將電信號轉換為光信號的設備。在光纖通信中&#xff0c;光模塊扮演著至關重要的角色。 光模塊的主要組成部分包括光源、光接收器、…