牛客OI测试赛2

题目链接：https://www.nowcoder.com/acm/contest/185#question

A.无序组数

暴力求出A和B的因子，注意二元组是无序的，因此还要考虑有些因子在A和B中都存在的情况

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=100006;

int a[maxn],ans[maxn];

int vis[maxn];

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        int m,n;

        scanf("%d%d",&m,&n);

        for(int i=1;i<=max(m,n);i++)

            vis[i]=0;

        int x=m,y=n,cnt=0,sum1=0,sum2=0;

        for(int i=1;i<=m;i++){

                if(m%i==0&&vis[i]==0){

                    sum1++;

                    vis[i]=1;

                }

        }

        for(int i=1;i<=n;i++){

            if(n%i==0){

                sum2++;

                if(vis[i]==1)

                    cnt++;

            }

        }

    printf("%d\n",sum1*sum2-(cnt-1)*cnt/2);

    }

}

B.路径数量

$dp[v][i]$表示从1号点到$v$号点长度为i的路径数目，则$dp[v][i]=dp[v][i]+dp[j][i-1]$,其中$i$与$j$间有边直接相连

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<stack>

#include<vector>

using namespace std;

typedef long long ll;

const int maxn=36;

vector<int> g[maxn];

ll dp[maxn][maxn];

int main(){

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++){

        int z;

        scanf("%d",&z);

        if(z==1){

            g[i].push_back(j);

            if(i==1)

            dp[j][1]=1;

        }

    }

    for(int i=1;i<=k;i++)

        for(int j=1;j<=n;j++)

        for(int z=0;z<g[j].size();z++)

        {

            int v=g[j][z];

            dp[v][i]=dp[v][i]+dp[j][i-1];

        }

    cout<<dp[n][k]<<endl;

}

C.数列下标

暴力。。。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=100006;

int a[maxn],ans[maxn];

int main(){

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d",&a[i]);

    for(int i=1;i<=n;i++){

        for(int j=i+1;j<=n;j++){

            if(a[j]>a[i]){

                ans[i]=j;

                break;

            }

        }

    }

    for(int i=1;i<n;i++)

        printf("%d ",ans[i]);

    printf("%d\n",ans[n]);

}

D.星光晚餐

前$n$个数当中，只有因子数为奇数个的星星最后会亮，若$i$为$n$的因子，则$n/i$也是$n$的因子，当$i\ne n/i$时，因子数总是成对出现，因此最后亮的星星都是完全平方数

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

const int maxn=100006;

int a[maxn],ans[maxn];

int vis[maxn];

int main(){

    long long n;

    cin>>n;

    cout<<(long long )sqrt(n)<<endl;

}

E.括号序列

和括号匹配想法一样，每次遇到左括号sum++，遇到右括号如果sum为零，说明需要交换，使sum++，ans++，如果sum为正，则sum--

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<stack>

using namespace std;

const int maxn=10000006;

int a[maxn],ans[maxn];

int vis[maxn];

char s[maxn];

int main(){

    int n;

    int sum=0;

    int ans=0;

    scanf("%d",&n);

    scanf("%s",s+1);

    //cout<<s+1<<endl;

    for(int i=1;i<=n;i++)

        if(s[i]=='(')

            sum++;

        else if(s[i]==')'){

            if(sum>0)

                sum--;

            else if(sum<=0){

                sum++;

                ans++;

            }

        }

        cout<<ans<<endl;

}

F.假的数学游戏

根据斯特林公式：$n！\approx\sqrt{2\pi n}{(\frac{n}{e})}^n$，两边同时取对数，再对$n$进行二分即可

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<stack>

#include<vector>

using namespace std;

typedef long long ll;

const int maxn=36;

vector<int> g[maxn];

ll dp[maxn][maxn];

int main(){

    ll l=0,r=1e12,mid;

    ll x;

    scanf("%lld",&x);

    for(int i=1;i<1000;i++){

        mid=(l+r)/2.0;

        if(log(sqrt(2*acos(-1)*mid))+mid*log(mid/exp(1.0))<x*log(x))

            l=mid;

        else r=mid;

    }

    cout<<r<<endl;

}

秒客网