小 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;
}
inline 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 \
mir.out
3 1
【數據規模】
對於 20%的數據：N=1
對於 40%的數據：N<=1000
對於 40%的數據：M<=1000
對於 40%的數據：T<=1000000
題解
預處理出每面鏡子向4個方向反射出光線會到達的鏡子是的編號後模擬並判環即可。
