Codeforces Round #588 (Div. 1)

A. Marcin and Training Camp

题面:

给出n个人,每个人都有一个技能值和一个价格,我们规定对于两个人x,y,如果x|(1<,那么我们就称xy厉害,然后你要选出一些人,使得其中任何一个人不能比所有人厉害,问你最大代价…

分析:

我们考虑要满足一个数不比另一个人厉害,一定满足(y \ XOR \ x)+x==y,也就是说我们选出的这些数中每个数都有满足上面这个式子的数..
然后我们发现如果一个人不比另一个人厉害,那么他一定小于另一个人,那我们从大到小删数,遇到不符合条件的删掉就是答案…

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<LL,LL>
#define fi first
#define se second
const LL N=1e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
LL n,ans,vis[N];
P x[N];
signed main()
{
    read(n);
    for(int i=1;i<=n;i++) read(x[i].fi);
    for(int i=1;i<=n;i++) read(x[i].se),ans+=x[i].se;
    sort(x+1,x+n+1);
    for(int i=n;i>=1;i--) 
    {
        int flag=1;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&i!=j&&(x[i].fi^x[j].fi)+x[i].fi==x[j].fi)
                flag=0;
        if(flag)
            vis[i]=1,ans-=x[i].se;
    }
    printf("%lld\n",ans);
    return 0;
}

B. Kamil and Making a Stream

题面:

给出一棵树,我们规定1是根,我们规定函数f(x,y)=GCD(val_x,val_{xnext},….val_y),就是xy路径上所有值的GCD.然后我们要求出

\sum_{\mathclap{u \ if \ a \ ancesroe \ of \ v}} f(u,v)

分析:

我们可以知道对很多数进行连续的GCD,得到是值最多只有log_2(n)个,然后我们就可以在直接暴力,我们对于每个点直接暴力记录它向上连的方案和值,然后暴力转移到儿子节点…

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define P pair<LL,LL>
#define fi first
#define se second
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
LL val[N],ans;
map<LL,int> Map[N];
map<LL,int>::iterator it;
int n,head[N],cnt;
struct Edge{int next,to;} edge[N<<1];
void add(int from,int to) {edge[++cnt]={head[from],to}; head[from]=cnt;}
void insert(int u,int v) { add(u,v);add(v,u);}
void dfs(int now,int fa)
{
    for(it=Map[fa].begin();it!=Map[fa].end();it++)
    {
        (Map[now][__gcd(val[now],it->fi)]+=it->se%mod)%=mod;
        (ans+=__gcd(val[now],it->fi)*it->se%mod)%=mod;
    }
    Map[now][val[now]]++;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs(to,now);
    }
}
signed main()
{
    read(n);
    for(int i=1;i<=n;i++) read(val[i]),(ans+=val[i]%mod)%=mod;
    for(int i=1,u,v;i<n;i++) read(u),read(v),insert(u,v);
    dfs(1,1);
    printf("%lld\n",ans%mod);
    return 0;
}

C. Konrad and Company Evaluation

题面:

给出n个人,m对关系,每对关系有两个人,如果a工资比b高,它就会嘲笑b,对于第i个人初始工资是i
每次我们可以选定一个人给他加上n的工资,然后询问我们有多少个三元组满足a嘲笑b,b嘲笑c

分析:

感性理解一下,我们直接暴力,记录比每一个数大的关系和比他小的,乘起来就是答案,正确性可以上网看….

代码:

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
#define fi first
#define se second
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,out[N],q,ans;
vector<int> vec[N];
int get(int now) {return vec[now].size()*out[now];}
signed main()
{
    read(n),read(m);
    for(int i=1,u,v;i<=m;i++)
    {
        read(u),read(v);
        if(u>v) swap(u,v);
        out[v]++;   
        vec[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
        ans+=get(i);
    printf("%lld\n",ans);
    read(q);
    for(int cas=1,now;cas<=q;cas++)
    {
        read(now);
        ans-=get(now);
        for(auto i:vec[now])
        {
            ans-=get(i);
            out[i]--;
            vec[i].push_back(now);
            ans+=get(i);
            out[now]++;
        }
        vec[now].clear();
        printf("%lld\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注