layout: post
title: Codeforces Beta Round 84 (Div. 2 Only)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
传送门
不得不说这远古场太简单了
A - Nearly Lucky Number （签到）
题意
给出一个数字 求其中7和4的数目是否是7和4组成
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+9;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
string s;
cin>>s;
int len=s.size();
int sum=0;
for(int i=0;i<len;i++){
if(s[i]=='4'||s[i]=='7'){
sum++;
}
}
if(sum==4||sum==7){
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
return 0;
}
B - Lucky String(贪心构造)
题意
让你构造一个字典序最小字符串 其中每个字符之间的间隔都必须是4和7组成的幸运数字
思路
直接ABCD四个一循环就行
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+9;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char s[5]={'a','b','c','d'};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
cin>>n;
for(int i=0;i<n;i++){
cout<<s[i%4];
}
return 0;
}
C - Lucky Sum of Digits （构造）
题意
给出一个N问你能否存在一个由4和7组成并且各位之和为N的数字并且各位之和为N的数字
有输出最小的 没有输出-1
思路
7×A+4×B=N
要最小 那就是长度最短 所以经可能让7多
因为数据1e6 直接枚举时间过得去
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+9;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char s[5]={'a','b','c','d'};
int seven,four;
string ans="999";
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
cin>>n;
bool flag=0;
for(int i=0;i<=n/7;i++){
int fo=n-i*7;
if(fo%4==0){
seven=i;
flag=1;
four=fo/4;
}
}
if(!flag)cout<<-1;
else{
for(int i=0;i<four;i++){
cout<<4;
}
for(int i=0;i<seven;i++)
cout<<7;
}
return 0;
}
D - Lucky Probability (区间枚举)
题意
出个两个（P,V）范围在1e9的正整数区间，分别从其中随机选出一个数，选出的两个数作为一个新区间的左右端点。要求新区间内的幸运数刚好为k个的概率（幸运数指一个数的数位只有4或7）。
思路
直接做肯定爆炸，我们发现1e9范围内最多2^10个幸运数字
然后我们就直接判断幸运数字 的区间，使得一个在min，一个在max
注意就是K==1的时候要去重一下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+9;
const int maxn=3e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll has[maxn];
int num=0;
ll get(ll al,ll ar,ll ql,ll qr){
ll l=max(al,ql);
ll r=min(ar,qr);
return l<=r?(r-l+1LL):0;
}
vector<ll>pre,nex;
void init(){
pre.push_back(0);
for(int i=0;i<10;i++){
nex.clear();
for(auto i:pre){
ll now=i*10LL+4LL;
nex.push_back(now);
has[++num]=now;
now=i*10LL+7LL;
nex.push_back(now);
has[++num]=now;
}
pre=nex;
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
init();
ll pl,pr,vl,vr,k;
cin>>pl>>pr>>vl>>vr>>k;
ll down=1LL*(pr-pl+1LL)*(vr-vl+1LL);
ll ans=0;
for(ll i=1;i<=2040;i++){
ll pre=i,next=i+k-1;
ans+=get(has[pre-1]+1,has[pre],pl,pr)*get(has[next],has[next+1]-1,vl,vr);
ans+=get(has[pre-1]+1,has[pre],vl,vr)*get(has[next],has[next+1]-1,pl,pr);
}
if(k==1){
for(int i=1;i<=2040;i++){
ans-=get(has[i],has[i],pl,pr)*get(has[i],has[i],vl,vr);
}
}
cout<<fixed;
cout<<setprecision(13)<<double(ans*1.0/down*1.0)<<endl;
return 0;
}
E - Lucky Tree(并查集)
题意
给你一个树，让你求有多少个三元组(a,b,c)满足a,b,c不同并且a到b至少有一个为幸运数字的边 a到c之间也至少有一个幸运数字的边
问这个三元组有多少个
思路
首先 没有幸运数字为边的点可以缩成一个点，因为他们之间肯定不能连线对答案没有贡献
这时候其他的点就和这个点相连就有贡献了
所以直接并查集缩点就行
比赛题目没看完就结束了 难过
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int fa[maxn],sz[maxn];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void fix(int a,int b){
a=find(a),b=find(b);
if(sz[a]>sz[b])swap(a,b);
sz[b]+=sz[a];
sz[a]=0;
fa[a]=b;
}
bool luck(int x){
while(x){
if(x%10!=4&&x%10!=7)return false;
x/=10;
}
return true;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)sz[fa[i]=i]=1;
for(int i=1;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
if(!luck(c))fix(a,b);
}
ll ans=0;
for(int i=1;i<=n;i++){
if(sz[i]){
ans+=1LL*(sz[i])*(1LL*n-sz[i])*(n-sz[i]-1LL);
}
}
cout<<ans;
return 0;
}