Codeforces Round 860 (Div. 2) 题解集

题解集"/>

Codeforces Round 860 (Div. 2) 题解集

目录

• CF1798B Three Sevens
• • _Description_
  • _Solution_
  • _Code_
• CF1798C Candy Store
• • _Description_
  • _Solution_
  • _Code_

比赛链接

CF1798B Three Sevens

题目链接

Description

一场彩票活动将持续 m m m 天，每天有 n n n 个编号分别为 a i , 1 , a i , 2 … a i , n a_{i,1},a_{i,2}\dots a_{i,n} ai,1​,ai,2​…ai,n​ 的人在该天的参与名单里，你需要在这 m m m 天的参与名单，每天的名单选出一个人，使得他不在后续任何一天的名单里。如果无法选出，输出 -1，否则输出每天被选出的人的编号。

Solution

设编号为 i i i 的人最后一次出现在名单里是第 l a s t i last_i lasti​ 天。

对于第 j j j 天，若 l a s t i ( 1 ≤ i ≤ n ) ≠ j last_i(1\leq i\leq n)\ne j lasti​(1≤i≤n)=j，则无法选出一个人，因为这天都不是他们最后一次出现在名单上，否则就任选一个 l a s t = j last=j last=j 的人。

可以在输入时就更新当天每个人的 l a s t last last 值。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int last[50050],ans[50050];
vector<int> a[500500]; //数组存不下，用vector储存
ll read(){ll x=0,f=1;char ch;ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
void init(int m){ //记得初始化for(int i=1;i<=m;i++){a[i].clear();}
}
void solve(){memset(last,-1,sizeof(last));memset(ans,0,sizeof(ans));int m=read(),mm=m;init(m);for(int i=1;i<=m;i++){int n=read();for(int j=1;j<=n;j++){int x=read();a[i].emplace_back(x);last[x]=max(last[x],i); //更新last}}for(int i=1;i<=m;i++){bool f=0;for(int j=0;j<a[i].size();j++){if(last[a[i][j]]==i){ //是最后一次出现在名单上f=1;ans[i]=a[i][j]; //因为无法确定后面能否选出人，所以要先存着break;}}if(f==0){cout<<-1<<endl;return;}}for(int i=1;i<=m;i++){cout<<ans[i]<<" ";}cout<<endl;}
int main(){t=read();while(t--){solve();}return 0;
}

CF1798C Candy Store

题目链接

Description

商店里有 n n n 种糖果，每种糖果有 a i a_i ai​ 颗，价格为 b i b_i bi​ 每颗。

现在需要将每种糖果分成若干包，每包的数量 d i d_i di​ 要一样。第 i i i 种糖果最终标价为 c i = d i × b i c_i=d_i\times b_i ci​=di​×bi​，一个价格标签可以概括 l l l 到 r r r 种糖果当且仅当 c l = c l + 1 = ⋯ = c r c_l=c_{l+1}=\dots=c_r cl​=cl+1​=⋯=cr​，问最少需要多少个标签。

注意，问的是标签数量，不是价格有多少种。

假设价格依次为 c 1 = 4 , c 2 = 4 , c 3 = 2 , c 4 = 4 , c 5 = 4 c_1=4,c_2=4,c_3=2,c_4=4,c_5=4 c1​=4,c2​=4,c3​=2,c4​=4,c5​=4，则可以用三个标签 4 , 2 , 4 4,2,4 4,2,4 来概括，数量为 3 3 3，而不是 2 2 2。

Solution

假设 一个标签 t a g tag tag 概括了 l l l 到 r r r 种糖果的标签，则 t a g = c l ∼ r tag=c_{l\sim r} tag=cl∼r​。

∵ c i = d i × b i \because c_i=d_i\times b_i ∵ci​=di​×bi​，

∴ t a g \therefore tag ∴tag 能被 b l ∼ r b_{l\sim r} bl∼r​ 整除

∴ lcm ⁡ ( b l , b l + 1 … b r ) ∣ t a g \therefore \operatorname{lcm}(b_l,b_{l+1}\dots b_r)\mid tag ∴lcm(bl​,bl+1​…br​)∣tag

∵ d i ∣ a i \because d_i\mid a_i ∵di​∣ai​

∴ c i ∣ a i × b i \therefore c_i\mid a_i\times b_i ∴ci​∣ai​×bi​

∴ t a g ∣ gcd ⁡ ( a i × b i , a i + 1 × b i + 1 … a r × b r ) \therefore tag\mid \gcd(a_i\times b_i,a_{i+1}\times b_{i+1}\dots a_r\times b_r) ∴tag∣gcd(ai​×bi​,ai+1​×bi+1​…ar​×br​)

∴ lcm ⁡ ( b l , b l + 1 … b r ) ∣ gcd ⁡ ( a i × b i , a i + 1 × b i + 1 … a r × b r ) \therefore \operatorname{lcm}(b_l,b_{l+1}\dots b_r)\mid \gcd(a_i\times b_i,a_{i+1}\times b_{i+1}\dots a_r\times b_r) ∴lcm(bl​,bl+1​…br​)∣gcd(ai​×bi​,ai+1​×bi+1​…ar​×br​)

所以只要判断当前 gcd ⁡ ( … ) \gcd(\dots) gcd(…) 是否能被 lcm ⁡ ( … ) \operatorname{lcm}(\dots) lcm(…) 整除即可，如果不能，就相当于进入了下一个标签，将 gcd ⁡ ( … ) \gcd(\dots) gcd(…) 更新成 a i × b i a_i\times b_i ai​×bi​， lcm ⁡ ( … ) \operatorname{lcm}(\dots) lcm(…) 更新成 b i b_i bi​。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long //记得开long long
int t;
int a[200200],b[200200];
int gcd(int x,int y){if(y==0) return x;return gcd(y,x%y);
}
int lcm(int x,int y){return x*y/gcd(x,y);
}
void solve(){int n,ansg=0,ansl=1,cnt=1; //注意gcd和lcm的初始化，以及标签至少有一个cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];}for(int i=1;i<=n;i++){ansg=gcd(ansg,a[i]*b[i]);ansl=lcm(ansl,b[i]);if((ansg%ansl)!=0){ //下一个标签，更新gcd和lcmansg=a[i]*b[i];ansl=b[i];cnt++;}}cout<<cnt<<endl;
}
signed main(){cin>>t;while(t--){solve();}
}

持续更新中…