2016 Multi-University Training Contest 3(部分) - dblank

2016 Multi-University Training Contest 3(部分)

<h2>1001 Sqrt Bo</h2>
2连续平方5次是2^32, 所以满足连续开根5次以内的数都是小于2^32的,可以以字符串的形式读入那个数,然后和2^32次方比大小,比它小的话直接模拟计算次数,比它大直接输出no,特判0的情况。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 10000 + 10, Mod = 1000000000;
typedef long long ll;
typedef pair<int, int> P;
char s[110];
ll x;
int main()
{
    x = 1;
    char ss[] = "4294967296";
    while(~scanf("%s", s))
    {
        if(strcmp(s, ss)<0 && strlen(s) == 10 || strlen(s) < 10)
        {
            ll num = 0;
            for(int i = 0; s[i]; i++)
            {
                num = num*10 + s[i] - '0';
            }
            int cnt = 0;
            while(cnt <=5 && num!=1)
            {
                num = ll(floor(sqrt(num)+0.0000001));
                cnt++;
            }
            if(num == 1)
            cout<<cnt<<endl;
            else cout<<"TAT"<<endl;
        }
        else
            cout<<"TAT"<<endl;
    }
    return 0;
}

<h2>1002 Permutation Bo</h2>
对于 开始和结尾的数,它满足的概率是(j-1)/(n-1),对于中间的概率是(j-1)(j-2)/(n-2)(n-1),然后对于每一位我们可以枚举j,累加起来。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 10000 + 10, Mod = 1000000000;
typedef long long ll;
typedef pair<int, int> P;
double c[N];
int main()
{
    int n;
    while(cin>>n)
    {
        double ans = 0;
        for(int i = 1; i<=n; i++)
            scanf("%lf", &c[i]);
            if(n == 1)
            {
                printf("%.10fn", c[1]);
                continue;
            }
        for(int i = 1; i<=n; i++)
        {
            for(int j = 1; j<=n; j++)
            {
                if(i == 1 || i == n)
                    ans += c[i]1.0(j-1)/(n-1)/n;
                else
                {
                    if(j>=2)
                    ans += c[i]1.0(j-1)*(j-2)/(n-1)/(n-2)/n;
                }
            }
        }
        printf("%.10fn", ans);
    }
    return 0;
}

<h2>1003 Life Winner Bo</h2>
对于king的情况,如果剩余的行和列都是偶数的话,那么我后手我就可以跟着先手的前进方法前进,最后一定是后手到达(n,m),对于不是都是偶数,先手可以往奇数的行和列或者斜下一步,让局面变成后手必胜的局面,这个时候就是先手必胜了。

对于rock的情况,如果m==n,那么先手选择前进行的话,往后手就前进列,这样后手必然先到达(n,m),对于先手,如果n!=m,先手可以行动后让n==m,变成后手必胜的局面,于是先手必胜。

对于knight的情况,这个画图就可以找到规律了,也是唯一会出现平局的type。

对于queen的情况,还记得威佐夫博弈吗,有两堆石子,每次可以在一堆里面选任意多的石子,或者两堆选同样多的,最后拿的获胜。这里的queen剩余的行数和列数就是这样的。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1000+ 10, Mod = 1000000000;
typedef long long ll;
const double Gv = (1.0 + sqrt(5.0))/2;
int dp[N];
int cheak(int type, int n, int m)
{
    if(n>m) swap(n, m);
    if(type == 2)
        return n == m ? 2:1;
    if(type == 4)
    {
        n--;
        m--;
        if(n>m)
            swap(n, m);
        int x = n * (Gv-1);
        if(n ==(int)(x  Gv) && m == n + x || n ==(int)((x+1)Gv) && n + x+ 1 == m)
            return 2;
        return 1;
    }
    if(type == 1)
        return ((n&1) && (m&1)) ? 2:1;
    if(type == 3)
    {
        if(n == m && n % 3 == 1)
            return 2;
        else if(n == m-1 && m % 3 == 0)
            return 1;
        return 3;
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int type, n, m;
        scanf("%d%d%d", &type, &n, &m);
        int ans = cheak(type, n, m);
        if(ans == 1)
            printf("Bn");
        else if(ans == 2)
            printf("Gn");
        else printf("Dn");
    }
    return 0;
}

 
<h2>1011 Teacher Bo</h2>
因为M很小,所以但N很大的时候一定会有解的,大胆的n^2循环。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000 + 10, Mod = 1000000000;
typedef long long ll;
typedef pair<int, int> P;
P p[N];
int a[N*10];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(a, 0, sizeof(a));
        int n, m;
        int k = 0;
        scanf("%d%d", &n, &m);
        for(int i = 0; i<n; i++)
            scanf("%d%d", &p[i].first, &p[i].second);
            int l, ok = 0;
        for(int i = 0; i<n; i++)
        {
            for(int j = i+1; j<n; j++)
            {
                l = abs(p[i].first - p[j].first) + abs(p[i].second - p[j].second);
                a[l]++;
                if(a[l] >=2){
                    ok = 1;
                    break;
                }
            }
            if(ok) break;
        }
        if(ok) puts("YES");
        else puts("NO");
    }
    return 0;
}

 

相关文章

发表新评论