今天是毕业的学长给高二的同学测试。组队比赛,ACM赛制,于是就愉快的和学姐一队啦。
看到英文题面感到恐慌,不过好在不难读懂。
A:并没有什么技术含量的模拟题;
B:字符串题,给定一些比赛和每个队胜利的场数,判断是否合法。
[[a-b]-[c-d]],a 2,b 0,c,1,d 0就是合法的。(意思是:a和b比一场,c和d比一场,两场的胜者再一起比一场)
递归地读入形成一个树的结构,从最基础的比赛层层check上去。
# include <cstdio>
# include <iostream>
# include <cstring>
# include <string> using namespace std; int l,a,b,v[],x,cnt=,ap=;
bool vis[],f=true;
char p,s[];
struct race
{
int x,y,w;
}r[]; int read (int x)
{
int pos=x+,a,b;
if(s[pos]=='[')
{
pos=read(pos);
a=cnt;
}else
a=s[pos]-'a';
pos+=;
if(s[pos]=='[')
{
pos=read(pos);
b=cnt;
}else
b=s[pos]-'a';
r[++cnt].x=a;
r[cnt].y=b;
return pos+;
} int main()
{
scanf("%s",s+);
read();
l=strlen(s+);
for (int i=;i<=l;++i)
if(s[i]>='a'&&s[i]<='z'&&vis[ s[i]-'a' ]==false)
vis[ s[i]-'a' ]=true,ap++;
for (int i=;i<=ap;++i)
{
cin>>p>>x;
v[p-'a']=x;
}
for (int i=;i<=cnt;++i)
{
race now=r[i];
if(now.x<)
a=now.x;
else
a=r[now.x].w;
if(now.y<)
b=now.y;
else
b=r[now.y].w;
if(v[a]==&&v[b]!=)
{
r[i].w=b;
v[b]--;
}
else if(v[a]!=&&v[b]==)
{
r[i].w=a;
v[a]--;
}
else f=false;
}
for (int i=;i<;++i)
if(v[i]) f=false;
if(f) printf("Yes\n");
else printf("No\n");
return ;
}
B
C:求在$[l,r]$区间内素因子个数为质数的数。$1<=l,r<=1e9$
学姐做的这个题,是素数筛一类的思想。
#include <cstdio>
#include <cmath> const int N = ; bool notp[N+];
int prm[N+], tot, a[N+], b[N+], l, r, ans; void prime() {
notp[] = notp[] = ;
for (int i = ; i <= N; ++i) {
if (!notp[i]) prm[++tot] = i;
for (int j = ; i * prm[j] <= N && j <= tot; ++j) {
notp[i*prm[j]] = ;
if (i % prm[j] == ) break;
}
}
} int main() {
scanf("%d%d", &l, &r);
prime();
for (int i = l; i <= r; ++i) b[i-l+] = i;
for (int i = ; i <= tot; ++i) {
if (prm[i] > r) break;
int j = l / prm[i];
if (prm[i] * j < l) ++j;
for (j; prm[i] * j <= r; ++j) {
while (b[prm[i]*j-l+] % prm[i] == )
++a[prm[i]*j-l+], b[prm[i]*j-l+] /= prm[i];
}
}
for (int i = l; i <= r; ++i) {
if (b[i-l+] > ) ++a[i-l+];
if (!notp[a[i-l+]]) ++ans;
}
printf("%d\n", ans);
return ;
}
C
D,E,F,G:咕咕咕;
H:点开H题可能是我整场比赛最正确的决定了。正好是我之前想过的一个题,类似于那道L语言,但是要判断方案数,数据范围非常大,但是抱着反正不会交了不亏的思想写了一个交上去,A了…而且还比AC自动机快?果然做题要有信仰。
# include <cstdio>
# include <iostream>
# include <cstring>
# include <string>
# define R register int
# define mod using namespace std; const int maxn=;
int n,cnt=;
char c[];
int ch[maxn][],l;
bool vis[maxn];
int dp[]; inline void ins()
{
int n,x=,l=strlen(c+);
for (R i=;i<=l;++i)
{
n=c[i]-'a';
if(!ch[x][n]) ch[x][n]=++cnt;
x=ch[x][n];
}
vis[x]=true;
} inline void Find (int pos)
{
int x=,n;
for (R i=pos;i<=l;++i)
{
n=c[i]-'a';
if(!ch[x][n]) break;
x=ch[x][n];
if(vis[x])
{
dp[i]+=dp[pos-];
if(dp[i]>=mod) dp[i]-=mod;
}
}
} int main()
{
scanf("%d",&n);
for (R i=;i<=n;++i)
{
scanf("%s",c+);
ins();
}
dp[]=;
scanf("%s",c+);
l=strlen(c+);
for (R i=;i<l;++i)
if(dp[i]) Find(i+);
printf("%d\n",dp[l]);
return ;
}
H
I,J,K:咕咕咕;
—shzr