AtCoder Beginner Contest 262

A - World Cup

題解:回圈判斷即可

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin>>n;
    for(int i=n;;i++)
    {
        if(i%4==2)
        {
            cout<<i<<'\n';
            return;
        }
    }
}
int main()
{
    int T=1;
    while(T--) solve();
    return 0^0;
}

B - Triangle (Easier)

題意: 給定\(n\)點,\(m\)條邊,如果\(a,b,c\)相連,那么\(ans++\),求\(ans\)

題解:觀察到\(n\) \(\le\) \(100\) 可以直接暴力回圈判斷,然后直接搞

#include <bits/stdc++.h>
using namespace std;
const double PI=acos(-1.0);
typedef pair<int,int> PII;
void solve()
{
    int n,m;
    cin>>n>>m;
    map<PII,int> mp;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        mp[{a,b}]++;//模擬連邊
        mp[{b,a}]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            for(int k=j+1;k<=n;k++)
            {
                if(mp[{i,j}]&&mp[{i,k}]&&mp[{j,k}])//表示連接了
                {
                    ans++;
                }
            }
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    int T=1;
 //   cin>>T;
    while(T--) solve();
    return 0^0;
}

C - Min Max Pair

題意:給定\(n\)個數字,并且數字范圍是\(1\)到\(n\),然后如果滿足以下等式那么就\(ans\)++,求\(ans\)的個數:

1. \(1 \le i<j \le N\)
2. \(min(a_i,a_j)=i\)
3. \(max(a_i,a_j)=j\)

題解:這里有兩種情況要考慮.

1. 當\(a_i=i\)的時候,這時候另一個就是\(a_j=j\),這里可以發現所以的\(a_i=i\)兩兩之間都可以進行相應的排列組合,,比并且這里就是組合數\(C_{n}^{2}\)(就是兩兩組合)
2. 當\(a_i!=i\)的時候,那么他肯定是這樣的\(a_i=j\)和\(a_j=i\)這兩個組合,那么就可以直接找,然后進判斷.

code

#include <bits/stdc++.h>
using namespace std;
const double PI=acos(-1.0);
typedef long long ll;
void solve()
{
    int n;
    cin>>n;
    vector<int> q(n+1);
    for(int i=1;i<=n;i++) cin>>q[i];
    ll ans=0;
    vector<int> st(n+1,true);
    for(int i=1;i<=n;i++)
    {
        if(q[i]!=i)
        {
            if(q[q[i]]==i&&st[i]&&st[q[i]])
            {
                ans++;//這個統計的是第二種情況,
                st[i]=false;//防止重復出現
                st[q[i]]=false;
            }
        }
    }
    // cout<<ans<<'\n';
    ll temp=0;
    for(int i=1;i<=n;i++) temp+=(q[i]==i);//第一種情況
    // cout<<temp<<'\n';
    ans+=(ll)(temp*(temp-1)/2);//組合數C_{n}^{2}
    cout<<ans<<'\n';
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0^0;
}

D - I Hate Non-integer Number

題意:給定\(n\)個數字,對于\(n\)個數字組成的所有的非空子集,他的子集元素所組成的算數平均數是整數的子集個數有多少個? 答案對于\(998244353\)進行取模

題解: 顯示要考慮\(DP\),但是比賽的時候并不會,還是賽后會的...

設\(f[i][j][k][b]\)表示前\(i\)個數字,選\(j\)個,\(模k\)的情況下等于b的方案數

1. \(f[i+1][j+1][k][(b+x)\% k]+=f[i][j][k][b]%mod\);選\(x\)這個數字
2. \(f[i+1][j][k][b]+=f[i][j][k][b]\);不選\(x\)這個數字

code

#include <bits/stdc++.h>
using namespace std;
const int N=101;
const int mod=998244353;;
ll f[N][N][N][N];
//表示的是前i個數字,選j個,在模k的情況下等于b的方案數
void solve()
{
    int n;
    cin>>n;
    for(int i=0;i<=n;i++) f[0][0][i][0]=1;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        for(int j=0;j<=i;j++)
        {
            for(int k=1;k<=n;k++)
            {
                for(int b=0;b<=n;b++)
                {
                    f[i+1][j+1][k][(b+x)%k]=(f[i+1][j+1][k][(b+x)%k]+f[i][j][k][b])%mod;//選這個數字
                    f[i+1][j][k][b]=(f[i+1][j][k][b]+f[i][j][k][b])%mod;//不選這個數字
                }
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++) ans=(ans+f[n][i][i][0])%mod;
    cout<<ans<<'\n';
}
int main()
{
    int T=1;

    while(T--) solve();
    return 0^0;
}

標籤：其他

上一篇：leetcode 504. Base 7 七進制數 (簡單)

下一篇：leetcode 448. Find All Numbers Disappeared in an Array 找到所有陣列中消失的數字(簡單)