Codeforces Round 886 (Div. 4) 12
A. To My Critics
直接模拟
void solve(){
int a,b,c; cin>>a>>b>>c;
if(a+b>=10||a+c>=10||b+c>=10) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return ;
}
B. Ten Words of Wisdom
可以通过顺序遍历直接找到最小值或者是直接按照某个要求排序
struct code{
int x,id;
bool operator<(const code&t)const{
return x>t.x;
}
}e[N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
int a,b; cin>>a>>b;
if(a>10) b=-1;
e[i]={b,i};
}
sort(e+1,e+1+n);
cout<<e[1].id<<endl;
}
C. Word on the Paper
直接找到目标即可
void solve(){
n=8;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>s[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(s[i][j]!='.'){
while(i<=n && s[i][j]!='.'){
cout<<s[i][j];
i++;
}
cout<<endl;
return ;
}
}
D. Balanced Round
区间特性直接双指针
void solve(){
cin>>n>>m;
vector<int> a(n);
for(auto&v:a) cin>>v;
sort(a.begin(),a.end());
int ans=n;
for(int i=0;i<n;i++){
int j=i;
while(j+1<n && a[j+1]-a[j]<=m) j++;
ans=min(ans,n-(j-i+1));
i=j;
}
cout<<ans<<endl;
}
E. Cardboard for Pictures
注意二分的细节
void solve(){
cin>>n>>m;
vector<int> a(n);
for(auto&v:a) cin>>v;
auto check = [&](LL mid){
LL ans=0;
for(auto&v:a){
ans+=(LL)(v+2*mid)*(v+2*mid);
if(ans>m) return false;// 防止爆LL直接使用每次都特殊判断
}
return ans<=m;
};
LL l=1,r=1e9;
while(l<r){
LL mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
F. We Were Both Children
埃斯筛原理
void solve(){
cin>>n;
map<int,int> mp;
for(int i=1;i<=n;i++){
int x; cin>>x;
mp[x]++;
}
vector<int> ton(n+1);
for(auto&[v,w]:mp)
for(int j=v;j<=n;j+=v)
ton[j]+=w;
int ans=0;
for(auto&v:ton) ans=max(ans,v);
cout<<ans<<endl;
}
G. The Morning Star
八皇后对角线的判断
void solve(){
map<int,int> mp[5];
cin>>n;
LL ans=0;
while(n--){
int x,y; cin>>x>>y;
ans+=mp[1][x]+mp[2][y]+mp[3][x+y]+mp[4][x-y];
mp[1][x]++;
mp[2][y]++;
mp[3][x+y]++;
mp[4][x-y]++;
}
ans*=2;
cout<<ans<<endl;
}
H. The Third Letter
1.注意带权并查集的原理和思维即可
int find(int x){
if(x!=p[x]){
int t=find(p[x]);
d[x]+=d[p[x]];
p[x]=t;
}
return p[x];
}
void solve(){
bool ok=true;
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i,d[i]=0;
while(m--){
int a,b,c; cin>>a>>b>>c;
int fa=find(a),fb=find(b);
if(fa!=fb){
p[fb]=fa;
d[fb]=d[a]+c-d[b];
}
else{
if(d[b]-d[a]!=c) ok=false;
}
}
cout<<(ok ? "YES" : "NO")<<endl;
}
2.或者直接使用dfs去找是否有不满足的即可
void solve(){
bool ok=true;
cin>>n>>m;
vector<bool> st(n+1);
vector<vector<pair<int,int>>> g(n+1);
vector<LL> d(n+1);
while(m--){
int a,b,c; cin>>a>>b>>c;
g[a].push_back({b,c});
g[b].push_back({a,-c});
}
function<void(int u)> dfs = [&](int u){
st[u]=true;
for(auto&[v,w]:g[u]){
if(st[v]){
if(d[v]!=d[u]+w){
ok=false;
return ;
}
}
else{
d[v]=d[u]+w;
dfs(v);
}
}
};
for(int i=1;i<=n;i++)
if(!st[i]){
dfs(i);
}
cout<<(ok ? "YES" : "NO")<<endl;
}