Codeforces1047


A.Little C Loves 3 I

题意:给定一个整数N,问是否存在整数a b c使得a+b+c=N且a b c均不为3的倍数

题解:考虑到mod3的余数只有0 1 2,所以直接取1,1,N-2 或 1,2,N-3 或 2,2,N-4

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

int N;

int main(){
    cin >> N;

    if((N-2)%3) cout << 1 << ' ' << 1 << ' ' << N-2 << endl;
    else if((N-3)%3) cout << 1 << ' ' << 2 << ' ' << N-3 << endl;
    else cout << 2 << ' ' << 2 << ' ' << N-4 << endl;

    return 0;
}
View Code

B.Cover Points

题意:给定平面上N个第一象限内的整数点,求一条斜率为-1的直线,使得所有点都在这条直线的下方

题解:找截距最大的就行

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

int Ans,N;

int main(){
    cin >> N;
    for(int i=1,x,y;i<=N;i++){
        cin >> x >> y;
        Ans=max(Ans,x+y);
    }
    cout << Ans << endl;

    return 0;
}
View Code

C.Enlarge GCD

题意:给定N个数,求删除最少的数,使得剩余数的最大公约数严格大于原来的最大公约数

题解:先把所有的数除以最大公约数,则问题转化为求最大公因数不为1的最多的个数。枚举因子,统计答案。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN=300000+2;
const int MAXM=15000000+2;
int a[MAXN],N,g,c[MAXM],Ans,U;
bool Flag[MAXM];

int gcd(int a,int b){
    if(a<b) swap(a,b);
    return b?gcd(b,a%b):a;
}

int main(){
    cin >> N;
    for(int i=1;i<=N;i++){
        cin >> a[i];
        g=(g?gcd(g,a[i]):a[i]);
    }
    for(int i=1;i<=N;i++) a[i]/=g,c[a[i]]++,U=max(U,a[i]);

    for(int i=2,S=0;i<=U;i++,S=0){
        if(!Flag[i])
            for(int j=i;j<=U;j+=i) S+=c[j],Flag[j]=1;
        Ans=max(Ans,S);
    }
    cout << (Ans?N-Ans:-1) << endl;

    return 0;
}
View Code

D.Little C Loves 3 II

题意:在一个网格图上放尽量多的点对,使得每个点对的曼哈顿距离均为3

题解:假设N<M,先特判掉N==1的情况,然后可以发现N=2时,只有M=2 3 7无法完全放满;N=3时,都可以放满。因此对于更大的N,可以直接拆成2和3的和。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long

ll N,M;

int main(){
    cin >> N >> M;
    if(N>M) swap(N,M);

    if(N==1){
        if(M%6==0) cout << M << endl;
        else if(M%6<=3) cout << M-(M%6) << endl;
        else cout << M-(6-M%6) << endl;
    }
    else if(N==2 && M==2) cout << 0 << endl;
    else if(N==2 && M==3) cout << 4 << endl;
    else if(N==2 && M==7) cout << 12 << endl;
    else{
        if((N&1) && (M&1)) cout << N*M-1 << endl;
        else cout << N*M << endl;
    }

    return 0;
}
View Code

E.Region Separation

题意:给定一颗点权树,每次可以删除任意数量的边,求每个联通块的点权和相同的切割方案。

题解:挺神的一道题,看了题解才会……假定限制了联通块的数量k,令t=整棵树的点权和/k,那么一个子树的点权和x对答案有贡献当且仅当t|x,即(S/gcd(S,x))|k,那么我们按照k分类求合法子树的数量。记c[k]表示树中点权和x满足:S/gcd(S,x)为k的因子的子树的数量(即其对k的答案有贡献),假如c[i]>=i,那么就存在分成i份的合法方案,统计之。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long

const int MAXN=1000000+2;
const ll MOD=1e9+7;
int N,p[MAXN];
ll s[MAXN],c[MAXN],f[MAXN],Ans;

ll gcd(ll a,ll b){
    if(a<b) swap(a,b);
    return b?gcd(b,a%b):a;
}

int main(){
    cin >> N;
    for(int i=1;i<=N;i++) scanf("%lld",s+i);
    for(int i=2;i<=N;i++) scanf("%d",p+i);

    for(int i=N;i;i--) s[p[i]]+=s[i];
    for(int i=N;i;i--){
        s[i]=s[1]/gcd(s[1],s[i]);
        if(s[i]<=N) c[s[i]]++;
    }
    for(int i=N;i;i--)
        for(int j=2*i;j<=N;j+=i) c[j]=(c[j]+c[i])%MOD;

    f[1]=1;
    for(int i=1;i<=N;i++)
        if(c[i]>=i)
            for(int j=2*i;j<=N;j+=i) f[j]=(f[j]+f[i])%MOD;
    for(int i=1;i<=N;i++)
        if(c[i]>=i) Ans=(Ans+f[i])%MOD;
    cout << Ans << endl;

    return 0;
}
View Code

优质内容筛选与推荐>>
1、高性能的代理服务-Envoy
2、[剑指Offer] 5 替换空格
3、美剧中的英文表达积累
4、SIW 带通滤波器
5、极限编程与敏捷开发


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn