Codeforces Round #702 (Div. 3)A-G題解
比賽鏈接:https://codeforces.ml/contest/1490
這場F讀錯題意白給一發，G二分的if(dp[mid]<x)居然寫成了if(dp[l]<x)，做夢都沒想到自己二分有寫錯的一天，瘋狂白給5發，
Div3相對以前變簡單了，罰時手速場，
A題
暴力
題意:
1000組資料
給定一個只包含正整數的長度為n的陣列（n最大50），每個數字均在1到50之間，
你可以在任意位置插入任意的整數（這里其實有bug，你如果插入一個負數那怎么都滿足了，題目要求的應該是正整數），
問最少需要插入多少個數字，使得該陣列每一對相鄰的兩個數字，都滿足大的那個不超過小的那個的2倍，
思路:
數值都非常小，直接暴力檢測每一對相鄰的數字，貪心對小的那個數不斷乘2翻倍直到大于等于大的那個數即可，
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=1e6+7;
const double eps=1e-6;
const int mod=1e9+7;
int main()
{
IOS
int t;cin>>t;
while(t--)
{
int n;cin>>n;
vector<int>num(n);
for(int i=0;i<n;i++) cin>>num[i];
int ans=0;
for(int i=1;i<n;i++)
{
int x=min(num[i],num[i-1]);
int y=max(num[i],num[i-1]);
while(x*2<y)
{
ans++;
x*=2;
}
}
cout<<ans<<endl;
}
}
B題
暴力
題意:
給定一個長度為n的只包含整數的數列，其中n必定能被3整除，
數列中對3取余得到0的數字的個數記為cas0，
數列中對3取余得到1的數字的個數記為cas1，
數列中對3取余得到2的數字的個數記為cas2，
每次操作，你可以將數列中的某個數字的值+1，
問最少經過多少次操作，可以使得cas0=cas1=cas2，
思路:
我們最后的目標是使得cas0=cas1=cas2=n/3，
那么實際上我們就是要把多了的通過+1操作補到少了的cas上去，
如果cas1大于n/3的話，我們可以把多了的部分都+1，讓他們變成cas2的值，
cas0,cas1,cas2的具體情況當然是有很多種，但是不論是哪種，都存在[0->1->2]或者[1->2->0]或者[2->0->1]這樣的轉移順序使得最后三個cas都為n/3，
直接暴力for兩遍0-2的轉移即可，
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=1e6+7;
const double eps=1e-6;
const int mod=1e9+7;
int main()
{
IOS
int t;cin>>t;
while(t--)
{
int n;cin>>n;
vector<int>num(n);
int cas[3]={0};
for(int i=0;i<n;i++)
{
cin>>num[i];
if(num[i]%3==0) cas[0]++;
else if(num[i]%3==1) cas[1]++;
else cas[2]++;
}
int ans=0;
for(int i=0;i<2;i++)//回圈兩遍
for(int j=0;j<3;j++)
if(cas[j]>n/3) {ans+=cas[j]-n/3;cas[(j+1)%3]+=cas[j]-n/3;cas[j]=n/3;}
cout<<ans<<endl;
}
}
C題
預處理，map
題意:
t組資料，最大100組，
每組資料給定一個1e12以內的正整數x，你需要求出滿足a3+b3=x的(a,b)有多少對，
思路:
注意到x最大為1e12，那么a和b的取值最大只有1e4，
我們可以預處理出1到1e4這1e4個整數的三次方為多少，用map記錄其是否出現，
每組資料，我們暴力列舉這1e4個三次方，用map檢測x減去當前的值，剩下的部分是否也為一個立方數即可，
復雜度為100
×
\times
× 1e4
×
\times
× log(1e4)，
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=1e6+7;
const double eps=1e-6;
const int mod=1e9+7;
map<ll,int>M;
vector<ll>num;
int main()
{
IOS
int t;cin>>t;
for(int i=1;i<=10000;i++)
{
ll x=i;
x=x*x*x;
M[x]=1;
num.push_back(x);
}
while(t--)
{
bool flag=0;
ll x;cin>>x;
for(int i=0;i<num.size();i++)
{
if(M.find(x-num[i])!=M.end()) {flag=1;break;}
}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
D題
暴力模擬，dfs
題意:
給定一個長度為n的排列，
你要按照如下的規則將這個排列構造成一棵二叉樹，依次輸出每個位置在這棵樹中的深度是多少，
先把整個排列中最大的數，作為樹根，
在原排列中，在當前這個數左側的所有數都在當前根的左子樹中，并且以其中最大的值為子樹的根，
在原排列中，在當前這個數右側的所有數都在當前根的右子樹中，并且以其中最大的值為子樹的根，
之后左右子樹同上進行構造，
思路:
直接dfs模擬這個程序就可以了，分析復雜度會發現最糟糕也就是n2，再乘以資料組數100組也就1e6的級別，
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=1e6+7;
const double eps=1e-6;
const int mod=1e9+7;
int num[107];
int deep[107];//deep[i]記錄第i個數在樹中所在的深度
void dfs(int l,int r,int now,int d)//l和r記錄當前子樹的值在原排列中的下標區間，now為當前作為根的數是哪一個，d代表深度
{
if(l==r) return;
if(l<now)//處理左區間
{
int tar=now-1;
for(int i=l;i<now-1;i++) if(num[i]>num[tar]) tar=i;
deep[tar]=d+1;
dfs(l,now-1,tar,d+1);
}
if(r>now)//處理右區間
{
int tar=now+1;
for(int i=now+2;i<=r;i++) if(num[i]>num[tar]) tar=i;
deep[tar]=d+1;
dfs(now+1,r,tar,d+1);
}
}
int main()
{
IOS
int t;cin>>t;
while(t--)
{
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>num[i];
memset(deep,0,sizeof(deep));
int tar=1;
for(int i=2;i<=n;i++) if(num[i]>num[tar]) tar=i;
deep[tar]=0;
dfs(1,n,tar,0);
for(int i=1;i<=n;i++) cout<<deep[i]<<' ';
cout<<endl;
}
}
E題
前綴和，貪心
真是絕了，上場讀錯了的題意這次居然真的出了這樣的題
題意:
給定n個玩家，每個玩家一開始都有若干的代幣，
會進行n-1次比拼，每次比拼隨機選出兩個代幣數量不為0的玩家，
如果兩個人代幣數量不相同，代幣多的那個人，拿走兩個人的全部代幣，
如果兩個人代幣數量相同，在這兩個人中隨機選一個人，拿走兩個人的所有代幣，
最后只剩下一個人，
問有哪些人是有可能是最后剩下的那個人，
思路:
既然說是有可能了，那么我們可以理解為我們可以貪心地去操作比賽的結果，平局的時候我們都令自己選的哪個人獲勝，
對于每個人來說，肯定都是先貪心去找其他人當中代幣最少的那個去比，如果出現剩下的人中，代幣最少的那個也比自己的代幣多，那就沒辦法勝利了，
實際上我們注意到，勝利的人會拿走所有的代幣，我們先對著n個人按照代幣數量從小到大排序為num[n]陣列，隨便取一個人，如果他打贏了前i個人的話，那么它當前的代幣數量就是num[i]的前綴和，
如果num[i]<num[i+1]，則代表這個人無法繼續贏下去了，
我們從后往前去找，找到前綴和不足以贏下一個人的位置，就得到了想贏所有人需要的最少代幣，輸出初始代幣數量不少于這個值的人即可，
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=2e5+7;
const double eps=1e-6;
const int mod=1e9+7;
ll num[maxn],chuli[maxn],sum[maxn];
int main()
{
IOS
int t;cin>>t;
while(t--)
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>num[i];
chuli[i]=num[i];
}
sort(chuli+1,chuli+n+1);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+chuli[i];//sum為前綴和陣列
ll bas=chuli[n];//bas記錄有可能獲勝的人的初始代幣最少為多少
for(int i=n-1;i>=1;i--)
{
if(sum[i]<chuli[i+1]) break;//如果當前這個人把不比他大的所有人都贏了，此時他已經是剩下的人當中最少的人了
//但是他如果贏不了其他人當中最小的那個，那他就沒有獲勝的希望
bas=chuli[i];
}
vector<int>out;
for(int i=1;i<=n;i++)
if(num[i]>=bas) out.push_back(i);
cout<<out.size()<<endl;
for(int i=0;i<out.size();i++) cout<<out[i]<<' ';
cout<<endl;
}
}
F題
前綴和，暴力
讀錯題意成既可以洗掉也可以增加可還行，不過還好只需要刪改兩三行就可以了
題意:
給定一個長度為n只包含正整數的陣列，（n最大2e5）
現在你需要洗掉盡可能少的數，使得陣列中的每個數字出現的次數相同，
思路:
直接暴力列舉最后結果的陣列中，每個數字出現了多少次，次數肯定在1到2e5之間，
而每次列舉的計算程序，可以利用前綴和來O(1)實作，具體看代碼和注釋，
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=2e5+7;
const double eps=1e-6;
const int mod=1e9+7;
map<int,int>M;
ll cishu[maxn];//cishu[i]記錄出現了i次的數字有多少種
ll sumcishu[maxn];//sumcishu為cishu陣列的前綴和，記錄出現了不超過i次的數字有多少種
ll num[maxn];//num[i]記錄出現了i次數字，他們總共出現了幾次
ll sumnum[maxn];//sunnum為num陣列的前綴和，記錄出現了不超過i次的數字，他們總共出現了幾次
int main()
{
IOS
int t;cin>>t;
while(t--)
{
int n;cin>>n;
ll ans=llINF;
for(int i=0;i<n;i++)
{
int x;cin>>x;
if(M.find(x)==M.end()) M[x]=1;
else M[x]++;
}
for(auto &x:M)
{
cishu[x.second]++;
num[x.second]+=x.second;
}
for(int i=1;i<=n;i++)
{
sumcishu[i]=sumcishu[i-1]+cishu[i];
sumnum[i]=sumnum[i-1]+num[i];
}
for(int i=1;i<=n;i++)//i為我們最后希望陣列中剩下的數字，每個數字出現多少次
{
ll temp=0;
temp+=n-sumnum[i]-(sumcishu[n]-sumcishu[i])*i;//對于一開始出現次數大于i次的，我們要把他們減少到i次
//sumcishu[n]-sumcishu[i]即為有多少種數字一開始出現次數是大于i次的，他們最后都要變為出現i次，總次數就乘以i
//用n-sumnum[i]即為一開始出現次數大于i次的總共出現了幾次，減去目標的總次數即為需要刪掉的個數
temp+=sumnum[i-1];//出現次數小于i的所有數字都要被刪掉
ans=min(ans,temp);
}
cout<<ans<<endl;
for(int i=1;i<=n;i++) cishu[i]=sumcishu[i]=num[i]=sumnum[i]=0;
M.clear();
}
}
G題
二分，前綴和，dp
二分函式的mid寫成了l是我沒想到的，瘋狂白給5發，二分居然寫錯了，青結
題意:
給定n個數字，每次操作都從第一個數字開始，每過一秒，依次加上下一位置的數字，不斷回圈，
給定m個數字x，問經過多少秒之后，累加的和不小于x，如果永遠不可能達到x，輸出-1，
n和m最大均為2e5，
思路:
首先用sum[i]記錄前i個數字累加起來是多少，mi記錄sum陣列的最大值，
如果給定的x小于等于mi的話，那么在第一輪回圈遍n個數字前便已經結束，我們可以對sum[i]做一個dp，用dp[i]記錄sum[1]到sum[i]中最大的值為多少，由此利用二分可在logn的時間找到累加大于等于x的第一個位置，
如果給定的x大于mi的話，就要看后面多次回圈后能否達到了，x大于mi，那么x的值至少要被減去x-mi才行，
如果sum[n]<=0的話，代表每次回圈結束x的值x與mi的差值并不會減少，因此此時就是無限回圈，輸出-1即可，
當sum[n]>0時，x-mi至少需要(x-mi)/sum[n]向上取整的回圈后才會被減去，再下一輪回圈就能達到值x了，同樣利用二分來logn時間尋找位置，
#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int maxn=2e5+7;
const double eps=1e-6;
const int mod=1e9+7;
ll num[maxn];
ll sum[maxn];//num陣列的前綴和
ll dp[maxn];//dp[i]記錄sum[1]到sum[i]中最大的值為多少
int search(int n,ll x)
{
int l=1,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(dp[mid]<x) l=mid+1;
else r=mid;
}
return l;
}
int main()
{
IOS
int t;cin>>t;
while(t--)
{
int n,m;cin>>n>>m;
ll mi=-1e10;//記錄最大的前綴和為多少，也就是依次回圈程序中可以得到的最大數值
for(int i=1;i<=n;i++)
{
cin>>num[i];
sum[i]=sum[i-1]+num[i];
dp[i]=max(dp[i-1],sum[i]);
mi=max(mi,sum[i]);
}
while(m--)
{
ll x;cin>>x;
if(x>mi)
{
if(sum[n]<=0) cout<<-1<<' ';
else
{
ll cas=(x-mi)/sum[n];
if((x-mi)%sum[n]) cas++;
x-=cas*sum[n];
cout<<cas*n-1+search(n,x)<<' ';
}
}
else cout<<search(n,x)-1<<' ';
}
cout<<endl;
for(int i=1;i<=n;i++) num[i]=sum[i]=dp[i]=0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260675.html
標籤：其他