1351. 密码锁【难度: 一般 / 知识点: 枚举 容斥原理】

1351. 密码锁【难度: 一般 / 知识点: 枚举 容斥原理】
https://www.acwing.com/problem/content/1353/
暴力枚举:

#include<bits/stdc++.h>
using namespace std;
int a,b,c,a1,b1,c1,n,cnt;
bool f(int a,int b)
{
    for(int i=0;i<=2;i++) 
    {
        int temp1=a+i;//向前转动
        if(temp1>n) temp1=temp1%n;
        int temp2=a-i;//向后转动
        if(temp2<=0) temp2=(n+temp2);
        if(temp1==b||temp2==b) return true;
    }
    return false;
}
bool check(int x,int y,int z)
{
    bool flag=0;
    if(f(x,a)&&f(y,b)&&f(z,c)) flag=1;
    if(f(x,a1)&&f(y,b1)&&f(z,c1)) flag=1;
    return flag;
}
int main(void)
{
    cin>>n;
    cin>>a>>b>>c>>a1>>b1>>c1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int z=1;z<=n;z++) if(check(i,j,z)) cnt++;
    cout<<cnt<<endl;
    return 0;
}

容斥原理: (A + B - A ∩ B)

#include<bits/stdc++.h>
using namespace std;
int a[5],b[5],n,cnt;
int f1()
{
    int res=1;
    for(int i=0;i<3;i++) res*=min(n,5);
    return res;
}
int f2()
{
    if(n<5) return n*n*n;
    int res=1;
    for(int i=0;i<3;i++)
    {
        int d=min( abs(a[i]-b[i]) , n-abs(a[i]-b[i]) );//俩点相离的距离
        res=res*max(0,5-d);
    }
    return res;
}
int main(void)
{
    cin>>n;
    for(int i=0;i<3;i++) cin>>a[i];
    for(int i=0;i<3;i++) cin>>b[i];
    cout<<f1()+f1()-f2()<<endl;
    return 0;
}
上一篇:python王者归来第五章部分习题答案


下一篇:C语言学习笔记---结构体的定义和初始化