Codeforces 935 简单几何求圆心 DP快速幂求与逆元

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-8;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

//const int maxn = 3e5 + 10;

const int  maxm = ;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

ll mod = 3e7;

int weight;

int from,to;

vector<pair<int,int> > place[];

int main()

{

    int anser=;

    int n;

    cin  >> n;

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

    {

        if(n%i==)

            anser++;

    }

    cout<<anser<<endl;

}

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-8;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

//const int maxn = 3e5 + 10;

const int  maxm = ;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

ll mod = 3e7;

int num[];

int  check(int x,int y)

{

    if(x==y)

        return ;

    if(x>y)

        return ;

    return ;

}

int main()

{

    int n;

    int anser=;

    int nowx,nowy;

    nowx=nowy=;

    cin >> n;

    string a;

    cin >> a;

    int now=;

    int belong=;

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

    {

        if(a[i]=='U')

            nowy++;

        else

            nowx++;

        belong=check(nowx,nowy);

        num[i]=belong;

        if(i>=)

            if(num[i]+num[i-]==)

                anser++;

//        cout<<i<<" "<<nowx<<" "<<nowy<<endl;

//        cout<<anser<<endl;

    }

    cout<<anser<<endl;

}

简单几何题意题

给你一个圆和一个点，让你在给定圆内画一个圆，使得答案圆不能包含给定点，而且使得给定圆没有被答案圆覆盖的面积最小。输出答案圆的圆心和半径即可。

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-8;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

//const int maxn = 3e5 + 10;

const int  maxm = ;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

ll mod = 3e7;

int num[];

int main()

{

    double R,x1,x2,y1,y2;

    cin >>R >> x1 >> y1 >> x2 >> y2;

    double  xap,yap,r;

    double len=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);

    double dis1=sqrt(len);

    if(len>=R*R)

    {

        printf("%.7f %.7f %lf",x1,y1,R);

        return ;

    }

    if(x1==x2&&y1==y2)

    {

        printf("%.7f %.7f %.7f",x1+R/,y1,R/);

        return ;

    }

    r=(R+dis1)/2.0;

    xap=x2+(x1-x2)*(r/dis1);

    yap=y2+(y1-y2)*(r/dis1);

    printf("%.7f %.7f %lf",xap,yap,r);

}

给你两个长为N包含0的数字串 0可以变化为1-k的任何数

要求你求出第一个串比第二个大的可能性（一个分数）模上1e9+7

总共的可能性数量很好想是K的0数量次方再把分数转化为求逆元就变为：比原串大的方案数乘以总方案数对MOD的逆元模MOD

dp[i][0]表示到第i个两个字典序相等的方案数 dp[i][1]表示到第i个第一个比第二个字典序大的方案数

dp[i][1]可以由dp[i-1][0]与dp[i-1][1]转换而来而 dp[i][0]只能由dp[i-1][0]转换而来

所以分类讨论

1.a=ai b=bi时

相等时

dp[i][0]=dp[i-1][0]

dp[i][1]=dp[i-1][1]

前大于后时

dp[i][1]=dp[i-1][0]+dp[i-1][1]

dp[i][0]=0

后大于前时

dp[i][1]=dp[i][0]=0

2.a=0 b=bi时

dp[i][0]=dp[i-1][0]

dp[i][1]=dp[i-1][1]*k+dp[i-1][0]*(k-bi)

3.a=ai b=0时

dp[i][0]=dp[i-1][0]

dp[i][1]=dp[i-1][1]*k+dp[i-1][0]*(b-1)

4.a=b=0

dp[i][0]=dp[i-1][0]*k

dp[i][1]=dp[i-1][1]*k*k+dp[i-1][0]*(k-1)*k/2

一直dp到n

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-8;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

const int mod = 1e9+;

int sum=;

ll dp[][];

int num[][];

ll quickpow(ll x,ll n)

{

    ll res=;

    while(n)

    {

        if(n&)res=res*x%mod;

        x=x*x%mod;

        n/=;

    }

    return res;

}

int main()

{

    ll n,m;

    cin >> n >> m;

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

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

        {

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

        }

    mem(dp,);

    dp[][]=;

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

    {

        sum+=(num[][i]==);

        sum+=(num[][i]==);

        if(num[][i]&&num[][i])

        {

            if(num[][i]==num[][i])

            {

                dp[i][]=dp[i-][];

                dp[i][]=dp[i-][];

            }

            else if(num[][i]>num[][i])

            {

                dp[i][]=(dp[i-][]+dp[i-][])%mod;

                dp[i][]=;

            }

            else

            {

                dp[i][]=;

                dp[i][]=dp[i-][];

            }

        }

        else if(num[][i]==&&num[][i]==)

        {

            dp[i][]=dp[i-][]*m%mod;

            dp[i][]=((dp[i-][]*((m*m)%mod)%mod+dp[i-][]*((m-)*m/)%mod)%mod)%mod;

        }

        else if(num[][i]==)

        {

            dp[i][]=dp[i-][]%mod;

            dp[i][]=(dp[i-][]*m%mod+dp[i-][]*(m-num[][i])%mod)%mod;

        }

        else if(num[][i]==)

        {

            dp[i][]=dp[i-][]%mod;

            dp[i][]=(dp[i-][]*m%mod+dp[i-][]*(num[][i]-)%mod)%mod;

        }

    }

    ll anser=dp[n][]*quickpow(quickpow(m,sum),mod-)%mod;

    cout<<anser<<endl;

}