ACM模拟赛

　　今天是毕业的学长给高二的同学测试。组队比赛，ACM赛制，于是就愉快的和学姐一队啦。

　　看到英文题面感到恐慌，不过好在不难读懂。

　　A：并没有什么技术含量的模拟题；

　　B:字符串题，给定一些比赛和每个队胜利的场数，判断是否合法。

　　[[a-b]-[c-d]],a 2,b 0,c,1,d 0就是合法的。(意思是:a和b比一场，c和d比一场，两场的胜者再一起比一场）

　　递归地读入形成一个树的结构，从最基础的比赛层层check上去。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <string>
 5 
 6 using namespace std;
 7 
 8 int l,a,b,v[30],x,cnt=26,ap=0;
 9 bool vis[30],f=true;
10 char p,s[1000];
11 struct race
12 {
13     int x,y,w;
14 }r[1000];
15 
16 int read (int x)
17 {
18     int pos=x+1,a,b;
19     if(s[pos]=='[')
20     {
21         pos=read(pos);
22         a=cnt;
23     }else
24         a=s[pos]-'a';    
25     pos+=2;
26     if(s[pos]=='[')
27     {
28         pos=read(pos);
29         b=cnt;
30     }else
31         b=s[pos]-'a';    
32     r[++cnt].x=a;
33     r[cnt].y=b;
34     return pos+1;
35 }
36 
37 int main()
38 {
39     scanf("%s",s+1);
40     read(1);
41     l=strlen(s+1);
42     for (int i=1;i<=l;++i)
43         if(s[i]>='a'&&s[i]<='z'&&vis[ s[i]-'a' ]==false) 
44             vis[ s[i]-'a' ]=true,ap++;
45     for (int i=1;i<=ap;++i)
46     {
47         cin>>p>>x;
48         v[p-'a']=x;
49     }
50     for (int i=27;i<=cnt;++i)
51     {
52         race now=r[i];
53         if(now.x<26) 
54             a=now.x;
55         else
56             a=r[now.x].w;
57         if(now.y<26) 
58             b=now.y;
59         else
60             b=r[now.y].w;
61         if(v[a]==0&&v[b]!=0)
62         {
63             r[i].w=b;
64             v[b]--;
65         }
66         else if(v[a]!=0&&v[b]==0)
67         {
68             r[i].w=a;
69             v[a]--;
70         }
71         else f=false;
72     }
73     for (int i=0;i<26;++i)
74         if(v[i]) f=false;
75     if(f) printf("Yes
");
76     else printf("No
");
77     return 0;
78 }

　　C:求在$[l,r]$区间内素因子个数为质数的数。$1<=l,r<=1e9$

　　学姐做的这个题，是素数筛一类的思想。

 1 #include <cstdio>
 2 #include <cmath>
 3 
 4 const int N = 1000000;
 5 
 6 bool notp[N+5];
 7 int prm[N+5], tot, a[N+5], b[N+5], l, r, ans;
 8 
 9 void prime() {
10     notp[0] = notp[1] = 1;
11     for (int i = 2; i <= N; ++i) {
12         if (!notp[i]) prm[++tot] = i;
13         for (int j = 1; i * prm[j] <= N && j <= tot; ++j) {
14             notp[i*prm[j]] = 1;
15             if (i % prm[j] == 0) break;
16         }
17     }
18 }
19 
20 int main() {
21     scanf("%d%d", &l, &r);
22     prime();
23     for (int i = l; i <= r; ++i) b[i-l+1] = i;
24     for (int i = 1; i <= tot; ++i) {
25         if (prm[i] > r) break;
26         int j = l / prm[i];
27         if (prm[i] * j < l) ++j;
28         for (j; prm[i] * j <= r; ++j) {
29             while (b[prm[i]*j-l+1] % prm[i] == 0)
30                 ++a[prm[i]*j-l+1], b[prm[i]*j-l+1] /= prm[i];
31         }
32     }
33     for (int i = l; i <= r; ++i) {
34         if (b[i-l+1] > 1) ++a[i-l+1];
35         if (!notp[a[i-l+1]]) ++ans;
36     }
37     printf("%d
", ans);
38     return 0;
39 }

　　D,E,F,G:咕咕咕；

　　H:点开H题可能是我整场比赛最正确的决定了。正好是我之前想过的一个题，类似于那道L语言，但是要判断方案数，数据范围非常大，但是抱着反正不会交了不亏的思想写了一个交上去，A了...而且还比AC自动机快？果然做题要有信仰。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <string>
 5 # define R register int
 6 # define mod 1000000007
 7 
 8 using namespace std;
 9 
10 const int maxn=200009;
11 int n,cnt=1;
12 char c[100005];
13 int ch[maxn][26],l;
14 bool vis[maxn];
15 int dp[100005];
16 
17 inline void ins()
18 {
19     int n,x=1,l=strlen(c+1);
20     for (R i=1;i<=l;++i)
21     {
22         n=c[i]-'a';
23         if(!ch[x][n]) ch[x][n]=++cnt;
24         x=ch[x][n];
25     }
26     vis[x]=true;
27 }
28 
29 inline void Find (int pos)
30 {
31     int x=1,n;
32     for (R i=pos;i<=l;++i)
33     {
34         n=c[i]-'a';
35         if(!ch[x][n]) break;
36         x=ch[x][n];
37         if(vis[x]) 
38         {
39             dp[i]+=dp[pos-1];
40             if(dp[i]>=mod) dp[i]-=mod;
41         }
42     }
43 }
44 
45 int main()
46 {
47     scanf("%d",&n);
48     for (R i=1;i<=n;++i)
49     {
50         scanf("%s",c+1);
51         ins();
52     }
53     dp[0]=1;
54     scanf("%s",c+1);
55     l=strlen(c+1);
56     for (R i=0;i<l;++i)
57         if(dp[i]) Find(i+1);
58     printf("%d
",dp[l]);
59     return 0;
60 }

　　I,J,K：咕咕咕；

　　---shzr