引子

这套题目是我在上个星期五期中考以后做的,整体难度还行,其中A题是递推,C题是Hash,D题则是简单的模拟,但从难度来讲也都不算很大,另外我们也可以看出题目难度并不一定是按顺序递增的(好吧,其实我只看出了这一点)

Problem A

题解

可以发现要使结果相同,则必须为A->B->A,于是在每次加入一个新数i时,它可以自己和自己配对,这样有F[i-1]种情况,或者和i-1个数进行配对,这样有$(i-1)*F[i-2]$种情况。

代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=2000000+10;
const LL prime=1000000007;
LL T,n,casen;
LL F[maxn];
void solve()
{
    F[1]=1;
    F[2]=2;
    for(int i=3;i<=maxn-1;i++)
    {
        F[i]=(F[i-1]+(i-1)*F[i-2])%prime;
        if(F[i]<0)
            F[i]+=prime;
    }
}
int main()
{
//    freopen("1.sb","r",stdin);
    solve();
    scanf("%I64d",&T);
    while(T--)
    {
        casen++;
        scanf("%d",&n);
        printf("Case #%I64d:\n%I64d\n",casen,F[n]);
    }
    return 0;
}

Problem B

看着烦,然后就没做….

Problem C

题解

把字符串处理一下取出数来,进行&操作,再hash,insert到set里去即可,较裸。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<set>
using namespace std;
typedef long long LL;
const int maxn=1000+10;
string s;
vector<int>G1[maxn],G2[maxn];
set<LL>D;
int T,n,m,casen=0;
char ch[100];
LL x;

int main()
{
//    freopen("1.sb","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        casen++;
        printf("Case #%d:\n",casen);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            G1[i].clear();
        for(int i=1;i<=m;i++)
            G2[i].clear();
        for(int k=1;k<=n;k++)
        {
            scanf("%s",&ch);
            //printf("%s\n",ch); 
            int len=strlen(ch);
            x=0;
            ch[len]='.';
            //printf("%s\n",ch);
            for(int i=0;i<=len;i++)
            {
                if(ch[i]!='.')
                {
                    x*=10;
                    x+=ch[i]-'0';    
                }
                else
                {
                    G1[k].push_back(x);
                    //cout<<x<<endl;
                    x=0;
                }
            }
        }
        for(int k=1;k<=m;k++)
        {
            scanf("%s",&ch);
            int len=strlen(ch);
            x=0;
            ch[len]='.';
            for(int i=0;i<=len;i++)
            {
                if(ch[i]!='.')
                {
                    x*=10;
                    x+=ch[i]-'0';
                }
                else
                {
                    G2[k].push_back(x);
                    x=0;
                }
            }
        }
//        cout<<"-----"<<endl;
//        for(int i=1;i<=n;i++)
//        {
//            for(int k=0;k<4;k++)
//            {
//                cout<<G1[i][k]<<' ';
//            }
//            cout<<endl;
//        }
//        cout<<"-----"<<endl;
//        for(int i=1;i<=m;i++)
//        {
//            for(int k=0;k<4;k++)
//            {
//                cout<<G2[i][k]<<' ';
//            }
//            cout<<endl;
//        }
//        cout<<"-----"<<endl;
        
        for(int i=1;i<=m;i++)
        {
            D.clear();
            for(int j=1;j<=n;j++)
            {
                x=1;
                for(int k=0;k<4;k++)
                {
                    LL cur=(G2[i][k]&G1[j][k]);
                    //cout<<cur<<endl;
                    x*=1000;
                    x+=cur;
                }
                D.insert(x);
                //cout<<x<<endl;
            }
            //for(int i=1;i<=
            printf("%d\n",D.size());
            
        }
    }
    return 0;
}

Problem D

题解

Hint里写的很清楚,只要直径小于等于对角线长度即可。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define Pi 3.1415926
const int maxn=1000+10;
int T,n,casen;
double a,r;
int main()
{
//    freopen("1.sb","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        casen++;
        printf("Case #%d:\n",casen);
        scanf("%d%lf%lf",&n,&a,&r);
        double R=a/2/tan(Pi/n);
        if(R>=r)
            printf("Give me a kiss!\n");
        else
            printf("I want to kiss you!\n");
    }
}