首页 > > 程序设计 > C/C++ >

【2016常州一中夏令营Day2】

2018-06-17 23:53:13来源：未知阅读 ()

小 W 学数学
【问题描述】
为了测试小 W 的数学水平，果果给了小 W N 个点，问他这 N 个点能构成的三角形个数。
【输入格式】
第一行一个整数 N，代表点数。
接下来 N 行，每行两个非负整数 X、Y，表示一个点的坐标。
【输出格式】
一个非负整数，即构成三角形个数。
【输入输出样例】
tri.in
5
0 0
1 0
2 0
0 1
1 1

tri.out
9

【数据规模】
对于 20%的数据：N=3
对于另外 40%的数据：保证任意 3 点不在同一直线上
对于 100%的数据：N<=100，保证任意两点不重合，坐标<=10000

题解

暴力枚举用斜率或叉积判断是否共线，统计一下答案即可。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n,ans;
int x[105],y[105];

int main()
{
    int i,j,k;
    freopen("tri.in","r",stdin);
    freopen("tri.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]);
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            for(k=j+1;k<=n;k++)
                if((y[k]-y[j])*(x[j]-x[i])!=(y[j]-y[i])*(x[k]-x[j])) ans++;
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

小 W 学英语
【问题描述】
为了测试小 M 的英语水平，Mr.R 让小 M 写英语作文，小 M 则把作文交给了小 W 写。然而 Mr.R 总结出了那个小 W 写作文的习惯，也就是某些关键的字符串。如果一篇作文中这若干个关键字符串都出现，他就认为这是小 W 写的。注意，小 W 可能写多篇作文。
【输入格式】
第一行一个整数 N，表示关键字符串的个数，N<=100。
接下来 N 行，每行为一个长度不超过 100 的字符串。
最后是若干段文本，每段文本以 $ 结尾。
由于写作文的人太疯狂，每篇作文最长可以达到 1350000 个字符，但作文的个数不超过 10。
【输出格式】
对于每一段文本对应一行输出。‘Yes’表示是小 W 的作文，‘No’表示不是。
请注意大小写。
【输入输出样例】
letter.in
3 i
love
m
ilovem$
lovem$

letter.out
Yes
No
【数据规模】
对于 50%的数据：N<=7

题解

AC自动机即可

感谢我学习时TonyFang提供的关于AC自动机的教材在此分享
关于Fail指针 http://www.acyume.com/archives/19
关于AC自动机 http://blog.csdn.net/jw72jw/article/details/6843700

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
 
int n,x,siz;
int len[110],fail[2000005],last[2000005],cnt[2000005],ch[2000005][27];
char ask[2000005],str[1005];
bool val[2000005];
queue<int> q; 

void ACinsert() 
{
    int i,p,len,c;
    p=0;
    len=strlen(str);
    for(i=0;i<len;i++) 
    {
        c=str[i]-'a';
        if(!ch[p][c]) ch[p][c]=++siz;
        p=ch[p][c];
    }
    val[p]=true;
}
 

void ACgetfail() 
{
    int i,j,c,p,v,now;
    fail[0]=0;
    for(c=0;c<26;c++) 
    {
        p=ch[0][c];
        if(p) 
        {
            fail[p]=last[p]=0;
            q.push(p);
        }
    }
    while(!q.empty()) 
    {
        now=q.front();
        q.pop();
        for(c=0; c<26; ++c) 
        {
            p=ch[now][c];
            if(!p) continue;
            q.push(p);
            v=fail[now];
            while(v&&!ch[v][c]) v=fail[v];
            fail[p]=ch[v][c];
            last[p]=val[fail[p]]?fail[p]:last[fail[p]];
        }
    }
}
 
void ACadd(int x) 
{
    for(;x;x=last[x]) 
        cnt[x]=1;
}
 
void ACfind() 
{
    int i,j,p,len,c;
    p=0;
    len=strlen(ask);
    memset(cnt,0,sizeof(cnt));
    for(i=0;i<len-1;i++) 
    {
        c=ask[i]-'a';
        while(p&&!ch[p][c]) p=fail[p];
        p=ch[p][c];
        if(val[p]) ACadd(p);
        else if(last[p]) ACadd(last[p]);
    }
}
 
 
int main() 
{
    int i,j;
    bool flag;
    freopen("letter.in","r",stdin);
    freopen("letter.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%s",str);
        ACinsert();
    }
    ACgetfail();
    while(~scanf("%s",ask)) 
    {
        ACfind();
        flag=false;
        for(i=1;i<=siz;i++) 
            if(val[i]!=0)
                if(cnt[i]==0) 
                {
                    flag=true;
                    break;
               }
        if(flag) puts("No");
        else puts("Yes");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

小 W 学物理
【问题描述】
为了测试小 W 的物理水平，Mr.X 在二维坐标系中放了 N 面镜子（镜子坐标绝对值不超过 M），镜子均与坐标轴成 45°角，所以一共有两种类型“/”和“\”。原点不会有镜子，任意一点最多只有一面镜子。镜子两个面都能反光，而中间不透光，例如，对于一个“/”型镜子，下方向射入的光线会被反射到右方向，左方向射入的光线会被反射到上方向。
现在有一条光线从原点沿 X 轴正方向射出，求走过 T 路程后所在位置。
【输入格式】
第一行三个整数 N，M，T。
第 2 到 N+1 行，每行两个整数 Xi,Yi,表示镜子坐标，一个字符 Si 表示镜子类型。
【输出格式】
一行两个整数，表示走过 T 路程后的坐标。
【输入输出样例】
mir.in
5 2 8
0 1 \
0 2 /
1 0 /
1 1 \
1 2 \