Codeforces Round #774 (Div. 2)

A. Square Counting

个数, 每一个数满足:

给你 ,问有多少个

  • 若有 个,

  • 若有 个,

  • 若有 个,

答案显然易见

1
2
3
4
5
void solve(){
long long n,s;
cin>>n>>s;
cout<<s/n/n<<"\n";
}

B. Quality vs Quantity

在数组 中分别找 个数属于 集合, 个数属于 集合,

问是否存在

集合都选最大的, 集合都选最小的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve(){
int n;
cin>>n;
vector<long long> a(n);
for(auto &i:a)cin>>i;
sort(a.begin(),a.end());
int lim=n/2;
long long sum1=a[0],sum2=0;//sum1是Y sum2是X
for(int i=1;i<=lim;i++){
sum1+=a[i];
sum2+=a[n-i];
if(sum1<sum2){cout<<"YES\n";return;}
}
cout<<"NO\n";
}

C. Factorials and Powers of Two

给你一个数,问它最少由多少个在 集合中的元素构成

广搜,向 递减的方向搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void solve(){
int t;
cin>>t;
vector<long long> a;//储存阶乘和2的次方
int n=14;//14!已经满足范围
long long res=1;
a.push_back(0);
for(int i=1;i<=n;i++){
res*=i;
a.push_back(res);
}
for(int i=1;i<=40;i++)//2^40足矣
a.push_back(1ll<<i);
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());
vector<long long> sum(a);//前缀和
for(int i=1;i<sum.size();i++)
sum[i]+=sum[i-1];
struct dd{
int cnt;//记录步数
long long num;
int pos;//记录上次剪去a[pos]的下标
};
while(t--){
long long x;
cin>>x;
int cnt=0;
queue<dd> q;
q.push({0,x,(int)a.size()-1});
while(q.size()){
auto p=q.front();
q.pop();
if(p.num<0)continue;
if(p.num==0){
cout<<p.cnt<<"\n";
break;
}
int pos=upper_bound(a.begin(),a.end(),p.num)-1-a.begin();
pos=min(pos,p.pos);
for(;pos>=1&&p.num-a[pos]<=sum[pos-1];pos--){
//如果剩下的总和sum[pos-1]<p.num-a[pos]肯定不行
q.push({p.cnt+1,p.num-a[pos],pos-1});
}
}
}
}

D. Weight the Tree

树形dp

有一个显而易见的结论, 如果当前节点是好节点, 那么它的相邻节点一定不是好节点,树大小为2的时候需特判

节点是好节点,以 为根的子树最多好节点的数量

节点不是好节点,以 为根的子树最多好节点的数量

费用计算:不难发现不是好节点的 ,好节点的 为相邻边数时,总和最小

注意:不能在dp的时候直接储存好节点,这样会炸内存的,具体做法就是再进行一遍dfs,找到好节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
#define add(x,y) edge[++tail]={head[x],y};head[x]=tail;
struct Edge
{
int ne,to;
}edge[404040];
int n,head[202020],tail,in[202020],w[202020],tree_sum[202020];
struct Dp{
int cnt,sum;
Dp operator+=(const Dp& b){
cnt+=b.cnt;
sum+=b.sum;
return {cnt,sum};
}
bool operator<(const Dp& b){
if(cnt!=b.cnt)return cnt<b.cnt;
return sum>b.sum;
}
}dp[202020][2];
void dfs1(int t,int fa){
if(t!=1)in[t]++;//表示节点t的度
tree_sum[t]++;//表示子树大小
dp[t][0].cnt=1;
dp[t][0].sum=0;
dp[t][1].cnt=0;
dp[t][1].sum=1;
for(int i=head[t];i;i=edge[i].ne){
int to=edge[i].to;
if(to!=fa){
dfs1(to,t);
in[t]++;
tree_sum[t]+=tree_sum[to];

dp[t][0]+=dp[to][1];

if(dp[to][0]<dp[to][1]) dp[t][1]+=dp[to][1];
else dp[t][1]+=dp[to][0];
}
}
dp[t][0].sum+=in[t];
}
void dfs2(int t,int fa,int best){
w[t]=(best==0)?in[t]:1;
for(int i=head[t];i;i=edge[i].ne){
int to=edge[i].to;
if(to!=fa){
if(best==0)dfs2(to,t,1);
else {
int best2=dp[to][0]<dp[to][1];
dfs2(to,t,best2);
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
if(n==2){
cout<<"2 2\n1 1";
return 0;
}
dfs1(1,1);
int best=dp[1][0]<dp[1][1];
cout<<dp[1][best].cnt<<" "<<dp[1][best].sum<<"\n";
dfs2(1,1,best);
for(int i=1;i<=n;i++)
cout<<w[i]<<" ";
}

E. Power Board

显而易见的是只有最小底数相同的才有可能相同,例如,2和3底数不相同,2和4和8的底数相同 那我们把底数相同的单独摘出来

以底数2举例

都写成最小底数形式

既然底数都一样,那就不看他了

底数3的矩阵最后也能化成这样的矩阵

底数5的矩阵最后也能化成这样的矩阵

······

那么只需要求这个矩阵有多少个不同的元素就好了,跟底数是多少没有关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool pd[20202020],v[1010101];
ll sum[1010101];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=20;i++){
ll cnt=0;
for(int j=1;j<=m;j++){
if(!pd[i*j]){
pd[i*j]=1;
cnt++;
}
}
sum[i]=sum[i-1]+cnt;
}
ll ans=1;
for(int i=2;i<=n;i++){
if(v[i])continue;
ll cnt=0;
for(ll j=i;j<=n;j*=i){
v[j]=1;
cnt++;
}
ans+=sum[cnt];
}
cout<<ans;
}

Codeforces Round #774 (Div. 2)

http://blog.therehello.top/cf1646/

发布于

2022-03-07

更新于

2022-03-08

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...