喵哈哈村的魔法考试 Round #10 (Div.2) 题解

喵哈哈村与哗啦啦村的大战(一)

最大值就是全部+3,最小值就是全部-3,注意不能降为负数。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int a[maxn],n;
int main(){
while(cin>>n){
int ans1=0,ans2=0;
for(int i=0;i<n;i++){
cin>>a[i];
ans1+=a[i]+3;
ans2+=max(0,a[i]-3);
}
cout<<ans1<<" "<<ans2<<endl;
}
}

喵哈哈村与哗啦啦村的大战(二)

最优答案就是摆成等边三角形,所有点均分过去,使得每个点都在无限靠近三角形的顶点位置。

那么最少摧毁(n+2)/3个点了。

#include<bits/stdc++.h>
using namespace std; int main(){
long long n;
while(cin>>n){
cout<<(n+2LL)/3LL<<endl;
}
}

喵哈哈村与哗啦啦村的大战(三)

考虑贪心,我们统计所有的和之后,我们每次选择ci最小的,即花费最小的进行操作。

然后不停使得和向着s靠拢,如果最后能靠拢的话,就输出答案,否则就输出impossible。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+6;
const int inf = 1e9+7;
int dp[maxn],a[maxn],c[maxn],l[maxn],r[maxn];
vector<pair<int,int> > sp[2];
int main(){
int n,s;
while(scanf("%d%d",&n,&s)!=EOF){
sp[0].clear();
sp[1].clear();
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&a[i],&c[i],&l[i],&r[i]);
}
int sum1=0,sum2=0,sum3=0;
for(int i=1;i<=n;i++){
sum1+=l[i];
sum2+=a[i];
sum3+=r[i];
sp[0].push_back(make_pair(c[i],r[i]-a[i]));
sp[1].push_back(make_pair(c[i],a[i]-l[i]));
}
if(sum1>s){
cout<<"impossible"<<endl;
continue;
}
if(sum3<s){
cout<<"impossible"<<endl;
continue;
}
int order = 0;
if(s>=sum2)order=0;
else order=1;
int sum4=abs(s-sum2);
int ans=0;
sort(sp[order].begin(),sp[order].end());
for(int i=0;i<sp[order].size();i++){
if(sum4>0){
int d=min(sum4,sp[order][i].second);
sum4-=d;
ans+=d*sp[order][i].first;
}
}
cout<<ans<<endl;
}
}

喵哈哈村与哗啦啦村的大战(四)

树形dp

维护dp1[i]表示从下到上大于等于的序列个数。

维护dp2[i]表示从下到上小于等于的序列个数。

这两者相乘,就是好序列的个数。

但是这有重复的项,因为都统计了相等的,所以得减去相等的与相等的之乘积。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
vector<pair<int,int> >E[maxn];
int n,a[maxn];
long long Down[maxn],Up[maxn],Down2[maxn],Up2[maxn];
long long equ[maxn];
long long ans = 0;
void dfs(int x,int fa){
Down[x]=1;
Up[x]=1;
Down2[x]=1;
Up2[x]=1;
equ[x]=1;
long long sumup,sumdown,sumequ;
for(int i=0;i<E[x].size();i++){
int v = E[x][i].second;
if(v==fa)continue;
dfs(v,x);
if(a[x]>=a[v]){
Down[x]+=Down[v];
}
if(a[x]<=a[v]){
Up[x]+=Up[v];
}
if(a[x]==a[v]){
equ[x]+=equ[v];
}
}
sumup=Up[x];
sumdown=Down[x];
sumequ=equ[x];
for(int i=0;i<E[x].size();i++){
int v = E[x][i].second;
if(v==fa)continue;
if(a[x]<=a[v]){
sumup-=Up[v];
}
if(a[x]>=a[v]){
sumdown-=Down[v];
}
if(a[x]==a[v]){
sumequ-=equ[v];
}
if(a[x]>=a[v])
ans+=Down[v]*sumup;
if(a[x]<=a[v])
ans+=Up[v]*sumdown;
if(a[x]==a[v])
ans-=equ[v]*sumequ;
}
}
int main(){
while(scanf("%d",&n)!=EOF){
ans=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),E[i].clear();
for(int i=1;i<n;i++){
int A,B;
scanf("%d%d",&A,&B);
E[A].push_back(make_pair(a[i],B));
E[B].push_back(make_pair(a[i],A));
}
for(int i=1;i<=n;i++)
sort(E[i].begin(),E[i].end());
dfs(1,-1);
cout<<ans<<endl;
}
}

喵哈哈村与哗啦啦村的大战(五)

假设现在考虑到第i个数,第i个数是12=223,那么m[j]统计前i-1个数,前缀为j的个数。

那么gcp为2的答案就是m[2]-m[4]

看懂这个这道题就简单了,自己写就好了。

#include<bits/stdc++.h>
using namespace std; map<int,int> H;
int n;
int a[100005];
int main(){
while(cin>>n){
H.clear();
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
long long ans = 0;
for(int i=0;i<n;i++){
vector<int>tmp;
int now=1;
tmp.push_back(now);
for(int j=2;j*j<=a[i];j++){
while(a[i]%j==0){
now*=j;
tmp.push_back(now);
a[i]/=j;
}
}
if(a[i]!=1){
now*=a[i];
tmp.push_back(now);
}
reverse(tmp.begin(),tmp.end());
long long sum = 0;
for(int j=0;j<tmp.size();j++){
ans+=1ll*tmp[j]*(1ll*H[tmp[j]]-sum);
sum=H[tmp[j]];
H[tmp[j]]++;
}
}
cout<<ans<<endl;
}
}
上一篇:libvirtsAPI


下一篇:(办公)Mysql入门