欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

AtCoder Beginner Contest 173(E 思维模拟 F 容斥 思维题 )

程序员文章站 2022-05-06 21:59:41
题目链接自从第一次打了AT 差一题AK,后面的AT 总是差两题,唉。。好菜啊E - Multiplication 4题意:给你n个数,要求选出k个值 使得k个值得乘积最大。做法:记得做过类似得题,也是超出long long 求乘积最大,好像是用了log 判断大小。但这里有负数 就不太好搞了。做法参考来自:博客思路感觉很对,但是他代码交。wa在了 after_contest_01.txt, 大概就是被hack了。想了半天感觉没什么问题啊,不知道为什么wa了。#pra.....

题目链接

自从第一次打了AT 差一题AK,后面的AT 总是差两题,唉。。好菜啊

E - Multiplication 4

AtCoder Beginner Contest 173(E 思维模拟 F 容斥 思维题 )

题意:给你n个数,要求选出k个值 使得k个值得乘积最大。

做法:记得做过类似得题,也是超出long long  求乘积最大,好像是用了log 判断大小。但这里有负数 就不太好搞了。

做法参考来自:博客

AtCoder Beginner Contest 173(E 思维模拟 F 容斥 思维题 )

思路感觉很对,但是他代码交。wa在了 after_contest_01.txt, 大概就是被hack了。想了半天感觉没什么问题啊,不知道为什么wa了。

 

经过几番研究 ,终于发现了 坑点,感谢网友提供的数据:

7 5
35 25 5 -25 -25 -25 -25

答案应该是13671875

所以 这里的坑点就是  当能凑到正数情况  且 当k为奇数时  先取正数最大的,再考虑正数与负数两两乘积最大

 

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
const ll mod=1e9+7;
const int N=2e5+10;
ll a[N],n,k;
vector<ll>G1,G2;
bool cmp2(ll x,ll y)
{
    return abs(x)<abs(y);
}
bool cmp1(ll x,ll y)
{
    return x>y;
}
bool cmp3(ll x,ll y)
{
    return x<y;
}
void run1()
{
    //puts("***");
    sort(G1.begin(),G1.end(),cmp1);
    sort(G2.begin(),G2.end(),cmp3);
//    for(ll v:G1) printf("%lld ",v);puts("");
//    for(ll v:G2) printf("%lld ",v);puts("");

    int id1=0,id2=0;
    ll ans=1;
    if(k%2){
        ans=G1[id1++];
    }
    while(id1+1<G1.size()&&id2+1<G2.size()&&id1+id2+2<=k){
        //printf("id1:%d id2:%d\n",id1,id2);

        if(G1[id1]*G1[id1+1]>G2[id2]*G2[id2+1]){
            ans=ans*G1[id1]%mod*G1[id1+1]%mod;
            id1+=2;
        }
        else{
            ans=ans*G2[id2]%mod*G2[id2+1]%mod;
            id2+=2;
        }
    }
    //printf("id1:%d id2:%d sz:%d\n",id1,id2,G1.size());

    while(id2+1<G2.size()&&id1+id2+2<=k){
        ans=ans*G2[id2]%mod*G2[id2+1]%mod;
        id2+=2;
    }
    while(id1+1<G1.size()&&id1+id2+2<=k){
        ans=ans*G1[id1]%mod*G1[id1+1]%mod;
        id1+=2;
    }
    //if(id1+id2<k) ans=ans*G1[id1++]%mod;
    printf("%lld\n",(ans+mod)%mod);

}
int main()
{
    n=read(),k=read();
    int zero=0;
    rep(i,1,n)
    {
        a[i]=read();
        if(a[i]>0) G1.emplace_back(a[i]);
        else if(a[i]<0) G2.emplace_back(a[i]);
        else zero++;
    }
    if(G2.size()-(G2.size()&1)+G1.size()>=k&&(k&1)<=G1.size()){
        run1();
    }
    else if(zero){
        puts("0");
    }
    else{
        sort(a+1,a+1+n,cmp2);
        ll ans=1;
        rep(i,1,k) ans=ans*a[i]%mod;
        printf("%lld\n",(ans+mod)%mod);
    }

}

/*
7 5
35 25 5 -25 -25 -25 -25
*/

 

F - Intervals on Tree

AtCoder Beginner Contest 173(E 思维模拟 F 容斥 思维题 )

题意:看了半天都没怎么懂的题意。大概就是 枚举l、r  然后集合包括[l,r]内的数。问集合内的联通块是多少,并求和输出。

做法:参考来自:博客

AtCoder Beginner Contest 173(E 思维模拟 F 容斥 思维题 )

很妙的做法。。。容斥的方法

#include<bits/stdc++.h>
using namespace std;

int n;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans+=(long long)(n-i+1)*i;
    }
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        if(a>b)swap(a,b);
        ans-=(long long)a*(n-b+1);
    }
    cout<<ans<<endl;

    return 0;
}

 

本文地址:https://blog.csdn.net/qq_41286356/article/details/107170143