2017 ACM Arabella Collegiate Programming Contest(solved 11/13)

省选考前单挑做点ACM练练细节还是很不错的嘛～

福利：http://codeforces.com/gym/101350

先来放上惨不忍睹的virtual participate成绩（中间跑去食堂吃饭于是浪费了一点时间）

Problem A DNF

Problem B 1Y(5min)

Problem C 1Y(37min)

Problem D 2Y(9min)

Problem E 4Y(3h58min)

Problem F DNF

Problem G 1Y(4h13min)

Problem H 1Y(13min)

Problem I 1Y(1h7min)

Problem J 1Y(1h26min)

Problem K 1Y(2h36min)

Problem L DNF

Problem M 30Y(3h47min)

先来大体上说一下，整个5h都还算ok，然而这个M题。。。事故啊。。。（之后会说）

感觉这套题有点偏向化，思维量大代码量小，导致容易卡题，也容易柳暗花明。

下面就是题解啦～

Problem A:

这是一个很不错的思维题啊！

比较容易陷入误区的地方在于，这种三元集的题大部分人会先去考虑中间项，然而应该先考虑两边。

我们将1的个数前缀和一下，于是观察出如果(i,j,k)满足题意，那么presum[i]和presum[k]有一些奥妙重重的关系，

然后又发现一个惊人的事实：如果presum[i]和presum[k]满足的话，那么中间的j应该是有且仅有1个可能的，

这样就可以统计答案了。

时间复杂度O(n)，代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long int64;
 4 const int N=220000;
 5 int n, z[N], num=0;
 6 char c[N];
 7 int64 calc ()
 8 {
 9     int64 ans=0;
10     int cnt=0;
11     for (int i=0; i<(int)strlen(c); i++) if (c[i]=='0') cnt++;
12     else z[++num]=cnt+1, cnt=0;
13     z[++num]=cnt+1;
14     int64 a=0, b=0;
15     for (int i=1; i<=num; i=i+2) a+=z[i];
16     for (int i=2; i<=num; i=i+2) b+=z[i];
17     ans=a*b;
18     for (int i=1; i<=num; i++) ans-=2*z[i];
19     ans+=z[1]+z[num];
20     ans+=num-1;
21     return ans;
22 }
23 int main ()
24 {
25     int t, n;
26     scanf("%d", &t);
27     for (int i=1; i<=t; i++)
28     {
29         scanf("%d%s", &n, c);
30         num=0;
31         printf("%I64d
", calc());
32     }
33     return 0;
34 }

Problem B:

你会不会写程序呀～

你会不会比大小呀～

时间复杂度O(1)，代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int T;
 6     cin>>T;
 7     while (T--)
 8     {
 9         int a,b;
10         cin>>a>>b;
11         if (b>a) cout<<"WeWillEatYou"<<endl; else cout<<"FunkyMonkeys"<<endl;
12     }
13     return 0;
14 }

Problem C:

首先这个题有两问，

第一问的答案就是这n个数的总和，O(n)扫一下就好啦～

第二问的答案就是这n个数的最大公约数，O(n)扫一下也好啦～

时间复杂度O(n)，代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int T,n;
 4 int x[100007];
 5 long long ans1,ans2;
 6 int read()
 7 {
 8     int x=0,f=1;char ch=getchar();
 9     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
10     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11     return x*f;
12 }
13 long long gcd(long long a,long long b)
14 {
15     if (b==0) return a;
16     return gcd(b,a%b);
17 }
18 int main()
19 {
20     T=read();
21     while (T--)
22     {
23         n=read();
24         ans1=0,ans2=0;
25         for (int i=1;i<=n;i++) 
26         {
27             x[i]=read();
28             ans1+=x[i];
29             ans2=gcd(x[i],ans2);
30         }
31         cout << ans1 << ' ' << ans2 << endl;
32     }
33     return 0;
34 }

Problem D:

首先很容易发现，不管怎么操作，大家的相对奇偶性是不变的。

然后发现所有数奇偶性相同是答案为yes的充要条件。（因为不可能小于0啊，如果小于0的话先大家都长高一下就好了～）

时间复杂度O(n)，代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int read()
 4 {
 5     int x=0,f=1;char ch=getchar();
 6     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 7     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 8     return x*f;
 9 }
10 int T;
11 int h[100007];
12 int main()
13 {
14     cin>>T;
15     while (T--)
16     {
17         int n;
18         n=read();
19         for (int i=1;i<=n;i++) h[i]=read();
20         bool check=true;
21         for (int i=2;i<=n;i++) if (h[i]%2!=h[1]%2) check=false;
22         if (check) cout <<"yes" << endl; else cout << "no" << endl;
23     }
24     return 0;
25 }

Problem E:

这是个很有趣的题目呀～

大家千万不要被质数这个条件所迷惑啊，这题和这个一点关系也没有。

当n为偶数的时候，只需要先手取最中间两个，然后和后手对称取就能赢了，所以n>2且为偶数时，先手获胜。

当n为奇数的时候，只需要先手取最中间三个，然后和对手对称取就能赢了，所以n>3且为奇数时，先手获胜。

当n=1时，先手获胜。

当n=2时，先手只能取1，后手也取1，后手获胜。

当n=3时，先手只能取2，后手取1，后手获胜。

所以这个题只有n=2或者n=3的时候后手获胜，其他情况都是先手获胜。

自古博弈代码短～～～

时间复杂度O(1)，代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int read()
 4 {
 5     int x=0,f=1;char ch=getchar();
 6     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 7     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 8     return x*f;
 9 }
10 int T,n;
11 int main()
12 {
13     T=read();
14     while (T--)
15     {
16         n=read();
17         if (n==2||n==3) cout << "second" << endl; else cout << "first" << endl;
18     }
19     return 0;
20 }

Problem G:

这个题我是在比较靠后的时间去做的，

第一眼。。。smg。。。完全不会

第二眼。。。n和m这么大，连O(nm)都过不了。。。

第三眼。。。这个k怎么才20啊。。。这不是瞎容斥一下就好了。。。

我们枚举2^k种不同的情况，每个点能不能取，维护出x坐标最小最大值，y坐标最小最大值，剩下的全部数学手推即可。

时间复杂度O(2^k)，代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int read()
 4 {
 5     int x=0,f=1;char ch=getchar();
 6     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 7     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 8     return x*f;
 9 }
10 long long ans;
11 int T,n,m,k,minx,maxx,miny,maxy;
12 int x[25],y[25],path[25];
13 void dfs(int x1,int cnt)
14 {
15     if (x1<=k)
16     {
17         dfs(x1+1,cnt);
18         path[cnt+1]=x1;
19         dfs(x1+1,cnt+1);
20     } else if (cnt>0)
21     {
22         minx=100007,miny=100007;
23         maxx=0,maxy=0;
24         for (int i=1;i<=cnt;i++)
25         {
26             int t=path[i];
27             minx=min(minx,x[t]);
28             maxx=max(maxx,x[t]);
29             miny=min(miny,y[t]);
30             maxy=max(maxy,y[t]);
31         }
32         long long r=1LL*minx*miny*(n-maxx+1)*(m-maxy+1);
33         if (cnt%2==1) ans-=r; else ans+=r;
34     }
35 }
36 int main()
37 {
38     T=read();
39     while (T--)
40     {
41         n=read(),m=read(),k=read();
42         for (int i=1;i<=k;i++) x[i]=read(),y[i]=read();
43         ans=((1LL*n*(n-1))/2+n)*((1LL*m*(m-1))/2+m);
44         dfs(1,0);
45         cout << ans << endl;
46     }
47     return 0;
48 }

Problem H:

这个题模拟一下就好了吧，先扫一遍字母，再扫一遍看一下是否回文。

时间复杂度O(n)，代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int T;
 4 string s;
 5 bool deal(char x)
 6 {
 7     if (x=='A'||x=='H'||x=='I'||x=='M'||x=='O'||x=='T'||x=='U'||x=='V'||x=='W'||x=='X'||x=='Y') return false;
 8     return true;
 9 }
10 int main()
11 {
12     cin>>T;
13     while (T--)
14     {
15         cin>>s;
16         bool check=true;
17         for (int i=0;i<s.length();i++) if (deal(s[i])) check=false;
18         for (int i=0;i<s.length();i++) if (s[i]!=s[s.length()-i-1]) check=false;
19         if (check) cout << "yes" << endl; else cout << "no" << endl;
20     }
21     return 0;
22 }

Problem I:

这个题首先把符合条件的字母搞出来，然后我们枚举回文的中间点，往两侧扩展就行了。

然而回文串有奇数长度，有偶数长度不太好处理。

没关系，我们在每相邻的两个字母之间加一个"#"（任何从未出现的字符都可以），然后扫一下就行了。

（其实这道题最长回文子串可以Manacher做啊，O(n)就够了，然而并不需要QWQ。。。）

时间复杂度O(n^2)，代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int T;
 4 string s,ss;
 5 bool deal(char x)
 6 {
 7     if (x=='A'||x=='H'||x=='I'||x=='M'||x=='O'||x=='T'||x=='U'||x=='V'||x=='W'||x=='X'||x=='Y') return false;
 8     if (x=='#') return false;
 9     return true;
10 }
11 int main()
12 {
13     cin>>T;
14     while (T--)
15     {
16         cin>>ss;
17         int n=ss.length();
18         s.clear();
19         s+="#";
20         for (int i=0;i<n;i++)
21         {
22             s+=ss[i];
23             s+="#";
24         }
25         n=s.length();
26         int ans=0;
27         for (int i=0;i<n;i++)
28         {
29             int now=0,tot=0;
30             while (i-now-1>=0&&i+now+1<n&&s[i-now-1]==s[i+now+1]&&(!deal(s[i-now-1]))) ++now;
31             for (int j=i-now;j<=i+now;j++) if (s[j]!='#') ++tot;
32             if (tot>ans&&(!deal(s[i]))) ans=tot;
33         }
34         cout << ans << endl;
35     }
36     return 0;
37 }

Problem J:

看到这道题题目名字里面有个"physics"的时候吓坏我了一直不敢开，结果点进去一看。。。

初中老师说过～～～弓形面积＝扇形面积－三角形面积，

扇形面积会不会呀～

三角形面积会不会呀～

编程会不会呀（逃。。。）

时间复杂度O(1)，代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int read()
 4 {
 5     int x=0,f=1;char ch=getchar();
 6     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 7     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 8     return x*f;
 9 }
10 int T,L,A;
11 double ans;
12 int main()
13 {
14     T=read();
15     while (T--)
16     {
17         L=read(),A=read();
18         ans=(double)A/360*L*L*M_PI;
19         ans-=(double)0.5*L*L*sin((double)A/180*M_PI);
20         printf("%.6lf
",ans);
21     }
22     return 0;
23 }

Problem K:

我们先暴力扫描出这个集合，然后暴力一下就好了。

时间复杂度O(n)，代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int read()
 4 {
 5     int x=0,f=1;char ch=getchar();
 6     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 7     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 8     return x*f;
 9 }
10 int T,a,b,n;
11 int cnt[150];
12 void deal(int n)
13 {
14     int t[15];
15     memset(t,0,sizeof(t));
16     while (n>0)
17     {
18         ++t[n%10];
19         n=n/10;
20     }
21     int ans=0;
22     for (int i=0;i<=9;i++) ans=max(ans,t[i]);
23     for (int i=0;i<=9;i++) if (t[i]==ans) ++cnt[i];
24 }
25 int main()
26 {
27     T=read();
28     while (T--)
29     {
30         memset(cnt,0,sizeof(cnt));
31         a=read(),b=read(),n=read();
32         for (int i=1;1LL*i*i*a+1LL*b*i<=n;i++)
33             deal(1LL*i*i*a+1LL*b*i);
34         int ans=0;
35         for (int i=0;i<=9;i++) if (cnt[i]>cnt[ans]) ans=i;
36         if (a+b>n) ans=-1;
37         cout << ans << endl;
38     }
39     return 0;
40 }

Problem M:

噩梦的一题。。。

我先写了个二分。。。然后我用的是cin。。。惨遭卡常。。。

于是写了个hash。。。惨遭卡常。。。

然后cin改成了scanf。。。WA了。。。

hash写跪了。。。终于过了。。。

时间复杂度O(n)，代码如下：

 1 #include <bits/stdc++.h>
 2 #define modp 100000007
 3 using namespace std;
 4 int read()
 5 {
 6     int x=0,f=1;char ch=getchar();
 7     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 8     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 9     return x*f;
10 }
11 int T,c,n;
12 string s1;
13 double s2;
14 map<int,double> mp;
15 double a;
16 string r;
17 int hash(string &s)
18 {
19     long long ans=0,now=1;
20     for (int i=0;i<s.length();i++)
21     {
22         ans=(107LL*ans+1LL*now*(s[i]-'A'+1))%modp;
23         now=(17LL*now)%modp;
24     }
25     return ans%modp;
26 }
27 int main()
28 {
29     //freopen("M.in","r",stdin);
30     //freopen("M.out","w",stdout);
31     T=read();
32     while (T--)
33     {
34         c=read(),n=read();
35         mp.clear();
36         for (int i=1;i<=c;i++) 
37         {
38             char ch=getchar();
39             while ((ch<'a'||ch>'z')&&(ch<'A'||ch>'Z')) ch=getchar();
40             long long ans=0,now=1;
41             while (ch!=' ')
42             {
43                 ans=(107LL*ans+1LL*now*(ch-'A'+1))%modp;
44                 now=(17LL*now)%modp;
45                 ch=getchar();
46             }
47             scanf("%lf",&s2);
48             mp[ans%modp]=s2;
49         }
50         r="JD";
51         mp[hash(r)]=1.0;
52         double anss=0.0;
53         for (int i=1;i<=n;i++)
54         {
55             scanf("%lf",&a);
56             char ch=getchar();
57             while ((ch<'a'||ch>'z')&&(ch<'A'||ch>'Z')) ch=getchar();
58             long long ans=0,now=1;
59             while (ch!='
')
60             {
61                 ans=(107LL*ans+1LL*now*(ch-'A'+1))%modp;
62                 now=(17LL*now)%modp;
63                 ch=getchar();
64             }
65             anss+=a*mp[ans%modp];
66         }
67         printf("%.6lf
",anss);
68     }
69     return 0;
70 }

写完啦～撒花～