(6/6) Codeforces Round #694 (Div. 2)

A. Strange Partition

題意：

給一個數組，數組中的所有元素可以任意合并，求數組的每個元素除以x上去整的和，求結果的最大值和最小值。

思路：

瞎猜。最小值肯定是都合并在一起，最大值是分開。

代碼：

#include <bits/stdc++.h> #define int long long using namespace std; int a[100010];void work() {int n, x;cin >> n >> x;int s1 = 0, s2 = 0;for (int i = 1; i <= n; i++) {cin >> a[i];s1 += a[i];s2 += (a[i] + x - 1) / x;}cout << (s1 + x - 1) / x << " " << s2 << endl; }int32_t main() {ios::sync_with_stdio(false);cin.tie(0);int cas;cin >> cas;while (cas--) work();return 0; }

B. Strange List

題意：

給你一數組，一個x，從前往后遍歷數組（也會遍歷后面加進來的元素），如果當前元素a可以被x除盡，則在數組末尾加上x個a/x。如果不能被除盡則停止，問數組的元素之和。

思路：

可以很顯然看出一個性質如果a/x也能被x除盡，那么結果增加a，因為一共有x個a/x。
模擬，如果能除盡，則結果加上當前元素，不能除盡則跳出。

代碼：

#include <bits/stdc++.h> #define int long long using namespace std; int a[100010]; int b[100010];void work() {int n, x, s = 0;cin >> n >> x;for (int i = 0; i < n; i++) {cin >> a[i];b[i] = a[i];s += a[i];}for (int i = 0; i < n; i = (i + 1) % n) {if (b[i] % x == 0) s += a[i], b[i] = b[i] / x;else break;}cout << s << endl; }int32_t main() {ios::sync_with_stdio(false);cin.tie(0);int cas;cin >> cas;while (cas--) work();return 0; }

C. Strange Birthday Party

題意：

商品按價錢從小到大排序，每個商品只能拿1次。
n個客人，每個客人有一個權值，只能拿下標比權值小的商品或者給客人下標為權值的商品對應的現金。

思路：

排序貪心，權值大的先拿前面的，序號小的后拿，如果不存在了，就拿現金。

代碼：

#include <bits/stdc++.h> #define int long long using namespace std; #define int long long constexpr int N = 300010; int k[N],c[N],vis[N];void work() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>k[i];for(int i=1;i<=m;i++) vis[i] = 0;for(int i=1;i<=m;i++) cin>>c[i];sort(k+1,k+1+n);int ans = 0;int j = 1;for(int i=n;i>=1;i--){if(c[k[i]]>c[j] && !vis[j] && j<=m){ans+=c[j];vis[j] = 1;j++;}else{ans+=c[k[i]];}}cout<<ans<<endl; }int32_t main() {ios::sync_with_stdio(false);cin.tie(0);int T;cin>>T;while(T--) work();return 0; }

D. Strange Definition

題意：

如果$lcm(x,y)/gcd(x,y)$為一個完全平方數，那么x和y相鄰。給你一個數組，從0秒開始，每秒鐘每個元素都會被其和與其互為完全平方數的乘積替換，設$d_i$為數組中第i個元素共有幾個互為完全平方數的數（包含本身）。
q個詢問，每個詢問詢問第i秒時d的最大值。

思路：

有一個明顯的推理：x*y如果是完全平方數，那么x和y相鄰。
那么我們把所有元素的偶數質因子都篩掉，設為core數組，那么如果core[x]=core[y]，那么x和y相鄰。
當詢問為0，我們只需要輸出出現次數最多的core。
當詢問不為0，比如為1，那么core出現為偶數次的下次都會為1，如果出現奇數次下次不變，特例當core為1時無論奇偶都不變。所以重新統計。
當詢問大于1，我們可以推一下，結果與1相同。

代碼：

#include <bits/stdc++.h> using namespace std; #define int long long int primes[1001000];void work() {unordered_map<int, int> haxh;int n;cin >> n;haxh[1] = 0;for (int i = 1; i <= n; i++) {int h = 1, x;cin >> x;while (primes[x] != 1) {int t = 0;int j = primes[x];while (x % j == 0) {x /= j;t++;}if (t % 2) h *= j;}haxh[h]++;}int cnt1 = 0, cnt2 = 0;for (auto i : haxh) cnt1 = max(cnt1, i.second);for (auto &i : haxh) if (i.first != 1 && i.second % 2 == 0) {haxh[1] += i.second;i.second = 0;}for (auto i : haxh) cnt2 = max(cnt2, i.second);int q;cin >> q;while (q--) {int x;cin >> x;if (x == 0) cout << cnt1 << endl;else cout << cnt2 << endl;} }int32_t main() {ios::sync_with_stdio(false);cin.tie(nullptr);primes[1] = 1;for (int i = 2; i <= 1000100; i++) {if (!primes[i]) {primes[i] = i;for (int j = i * 2; j <= 1000100; j += i) if (!primes[j]) primes[j] = i;}}int cas;cin >> cas;while (cas--) work(); }

E. Strange Shuffle

題意：

交互題，一組人圍成一圈，每個人都會把當前元素/2下取整給左側的人，當前元素/2上取整給右側的人。
每秒所有人同時執行該操作一次。
有一個偽裝者，他會把所有的元素都給右側，要求在1000秒內找出偽裝者，每秒可以進行一次詢問，詢問q位置的人的當前元素。

思路：

打表看規律。n為15，p為5，下標從1開始，k為50，第一行為初始狀態。

每多一秒，會多出現一個大于k的數，$sqrt(100000)=330$，我們先用sqrt次，讓其出現sqrt個大于k的數，我們可以發現，答案位置永遠為k，答案右側大于k，答案左側小于k。
所以我們找到一個大于k或者小于k的數，然后左移或者右移到第一個等于k的數，即為所求。

代碼：

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; #define x first #define y second #define bg begin() #define ed end() #define pb push_back #define mp make_pair #define sz(a) int((a).size()) #define R(i,n) for(int i(0);i<(n);++i) #define L(i,n) for(int i((n)-1);i>=0;--i) const int iinf=0x3f3f3f3f; const ll linf=0x3f3f3f3f3f3f3f3f;const int N=3e5; int n,m,a[N],b[N];int ask(int i){cout<<"? "<<i+1<<endl;int x; cin>>x; return x; }int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;const int B=sqrt(n)-1;R(i,B+1) ask(i);int p=0,x=ask(p);while(x==m) (p+=B)%=n,x=ask(p);if(x>m){ while(ask((p+n-B)%n)>m) (p+=n-B)%=n;while(ask((p+n-1)%n)>m) (p+=n-1)%=n;(p+=n-1)%=n;} else { while(ask((p+B)%n)<m) (p+=B)%=n;while(ask((p+1)%n)<m) (p+=1)%=n;++p%=n;}cout<<"! "<<p+1<<endl;return 0; }

F. Strange Housing

題意：

給你節點和邊，染色，染色的住老師，未染色的住學生。
要求：相鄰的節點不能同時染色，只有染色的節點和不染色的節點相鄰的邊才成立，要求圖聯通。

思路：

暴力貪心即可。如果與當前節點相鄰的所有節點沒老師，那當前節點就放老師，否則不放。
如果有節點未遍歷到，則輸出NO。
證明：老師一定不相鄰，一定聯通，放學生時周圍一定有老師。

代碼：

#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 300010; vector<int> g[maxn]; int cnt; int st[maxn];void dfs(int u) {int sum1 = 0, sum2 = 0;for (int i = 0; i < g[u].size(); i++) if (st[g[u][i]]) {if (st[g[u][i]] == 1) sum1++;else sum2++;// cout << st[g[u][i]] << endl;// cout << "---" << endl;}// cout << sum1 << endl;if (sum1 == 0) st[u] = 1;else st[u] = 2;for (int i = 0; i < g[u].size(); i++) if (!st[g[u][i]]) dfs(g[u][i]); }void work() {cnt = 0;int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) st[i] = 0, g[i].clear();while (m--) {int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);}dfs(1);int cnt = 0, flag = 0;for (int i = 1; i <= n; i++) {if (st[i] == 1) cnt++;if (!st[i]) flag = 1;}if (flag) cout << "NO" << endl;else {cout << "YES" << endl;cout << cnt << endl;for (int i = 1; i <= n; i++)if (st[i] == 1) cout << i << " ";cout << endl;} }int32_t main() {int cas;cin >> cas;while (cas--) work(); }

總結

以上是生活随笔為你收集整理的(6/6) Codeforces Round #694 (Div. 2)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。