首页 > 代码库 > 2017杭电ACM集训队单人排位赛 - 2 题解

2017杭电ACM集训队单人排位赛 - 2 题解

  1001,水题,直接模拟即可。比赛中开局连wa三发,因为把int写成了bool..

  1002,积分题,比赛中找到了下面这个积分公式,

技术分享

  但是并没什么用,,因为带入以后存在误差,估计是展开了以后出现了误差。然后用自适应simpson即可。大白书上的模板不怎么好用(虽然能过),优化版的模板如下(本题AC代码):

技术分享
 1 #include<iostream> 
 2 #include<cstdio> 
 3 #include<string> 
 4 #include<cstring> 
 5 #include<map> 
 6 #include<set> 
 7 #include<queue>
 8 #include<stack> 
 9 #include<ctime> 
10 #include<algorithm> 
11 #include<cmath> 
12 #include<vector> 
13 #include<list> 
14 #include<fstream> 
15 #include<sstream> 
16 #include<cassert> 
17 #include<bitset> 
18 #define showtime printf(stderr,"time = %.15f\n",clock() / (double)CLOCKS_PER_SEC) 
19 #pragma comment(linker, "/STACK:1024000000,1024000000") 
20 using namespace std; 
21 typedef long long ll; 
22 typedef long long LL; 
23 typedef unsigned long long ull; 
24 #define MP make_pair 
25 #define PII pair<int,int> 
26 #define PFI pair<double,int> 
27 #define PLL pair<ll,ll> 
28 #define lson l,mid,rt<<1 
29 #define rson mid+1,r,rt<<1|1 
30 //freopen("data.in","r",stdin); 
31 //freopen("data.out","w",stdout); 
32 typedef vector<long long> vec; 
33 typedef vector<vec> mat; 
34 inline int popcnt(int x){return __builtin_popcount(x); } 
35 inline int clz(int x){return __builtin_clz(x);} //末尾的 0,即对 lowbit 取log 
36 inline int clz(LL x){return __builtin_clzll(x);} 
37 inline int lg2(int x){ return !x ? -1 : 31-clz(x);} 
38 inline int lg2(LL x){ return !x ? -1 : 63-clz(x);} 
39 inline int __lcm(int x, int y){ return x / __gcd(x, y) * y; }
40 const double eps = 1e-6; 
41 const double PI = acos(-1.); 
42 const double E = 2.71828182845904523536; 
43 const int MOD = (int)1e9+7; 
44 const int INF = 0x3f3f3f3f; 
45 const ll INFLL = 0x3f3f3f3f3f3f3f3f; 
46 const ull BAS = 233;
47 const int M = 1e5 + 7; 
48 const int N = 1e5 + 7; 
49 
50 double v1, v2, x, k;
51 
52 double f(double t){
53     // 表达式 
54     return k / (((x-v2*t)*(x-v2*t)) + (t*v1) * (t*v1));
55 }
56 double simpson(double l,double r){ // simpson公式
57     return 1.0 / 6.0 * (r - l) * (f(l) + 4 * f((l+r)/2.0) + f(r));
58 }
59 double integral(double l,double r){
60     double mid = (l + r) / 2.0;
61     double ret = simpson(l,r);  // 二分逼近
62     if(fabs(ret - simpson(l,mid)-simpson(mid,r)) < eps)
63         return ret;
64     else 
65         return integral(l,mid) + integral(mid,r);
66 }
67 /*
68                     k
69 ---------------------
70 (x-v2*t)^2 + (t*v1)^2
71 */
72 int main(){
73     int T;
74     cin >> T;
75     while(T --){
76         cin >> v1 >> v2 >> x >> k;
77         printf("%.2f\n", integral(0, 1e18));
78     }
79     return 0;
80 }
1002

  

  1003,用dfs不能过,因为有环,那么谁先更新谁后更新对答案有偏差,因此采用优先队列的dij来做。代码如下:

技术分享
 1 #include <bits/stdc++.h>
 2 #define t_mid (l+r>>1)
 3 #define ls (o<<1)
 4 #define rs (o<<1|1)
 5 #define lson ls,l,t_mid
 6 #define rson rs,t_mid+1,r
 7 using namespace std;
 8 const int N = 1e5 + 100;
 9 typedef long long ll;
10 typedef pair<int,int> pii;
11 const int mod = 1e9 + 7;
12 
13 int T;
14 int n, m;
15 int a[N];
16 vector<pii> G[N];
17 
18 int main()
19 {
20     scanf("%d",&T);
21     while(T--)
22     {
23         scanf("%d%d",&n,&m);
24         priority_queue<pii,vector<pii>,greater<pii> > Q;
25         for(int i=1;i<=n;i++) {scanf("%d",a+i); Q.push(pii(a[i], i)); G[i].clear();}
26         for(int i=1;i<=m;i++)
27         {
28             int x, y, z;
29             scanf("%d%d%d",&x,&y,&z);
30             G[x].push_back(pii(y,z));
31             G[y].push_back(pii(x,z));
32         }
33         while(!Q.empty())
34         {
35             pii p = Q.top(); Q.pop();
36             int u1 = p.second;
37             for(pii pp : G[u1])
38             {
39                 int u2 = pp.first;
40                 int v = pp.second;
41                 if(a[v] > a[u1] + a[u2])
42                 {
43                     a[v] = a[u1] + a[u2];
44                     Q.push(pii(a[v], v));
45                 }
46             }
47         }
48         for(int i=1;i<=n;i++) printf("%d%c",a[i],i==n?\n: );
49     }
50     return 0;
51 }
1003

 

  1004,水题。

  1005,3!枚举一下3种字符的排列顺序,得到此时的目标串,然后和原串匹配一下得到在目标串中的连续的最长的子串,这个长度就是不需要动的牌,然后所有情况比较得到最优解即可。需要是连续的是因为每次只能把牌放到最前和最后,不难证明可以成立。同时这个匹配的方法可以dp,也可以暴力。这个dp的转移还是需要注意一下的。代码如下:

技术分享
  1 #include <bits/stdc++.h>
  2 #define t_mid (l+r>>1)
  3 #define ls (o<<1)
  4 #define rs (o<<1|1)
  5 #define lson ls,l,t_mid
  6 #define rson rs,t_mid+1,r
  7 using namespace std;
  8 const int N = 1e5 + 100;
  9 typedef long long ll;
 10 typedef pair<int,int> pii;
 11 const int mod = 1e9 + 7;
 12 
 13 int T;
 14 char s[20];
 15 char t[20];
 16 int cnt[4];
 17 char need[4][20];
 18 char str[60];
 19 int ans;
 20 
 21 int dp[20][20];
 22 void solve()
 23 {
 24     // s -> str
 25     //printf("%s -- %s\n",s+1,str+1);
 26     for(int l=1;l<=13;l++)
 27     {
 28         for(int r=l+1;r<=13;r++)
 29         {
 30             int temp = 0;
 31             for(int i=1;i<=13;i++)
 32             {
 33                 if(s[i] == str[l+temp])
 34                 {
 35                     temp++;
 36                 }
 37             }
 38             if(temp == r - l + 1) ans = max(ans, r - l + 1);
 39         }
 40     }
 41     /*memset(dp,0,sizeof dp);
 42     for(int i=1;i<=13;i++)
 43     {
 44         for(int j=1;j<=13;j++)
 45         {
 46             if(s[i] == str[j])
 47             {
 48                 dp[i][j] = dp[i-1][j-1] + 1;
 49             }
 50             else dp[i][j] = dp[i-1][j];
 51             ans = max(ans, dp[i][j]);
 52         }
 53     }*/
 54 }
 55 
 56 int main()
 57 {
 58     // 3 1 2
 59     //printf("%d %d %d ?\n",‘a‘,‘1‘,‘A‘);
 60     scanf("%d",&T);
 61     while(T--)
 62     {
 63         scanf("%s",s+1);
 64         memcpy(t,s,sizeof t);
 65         sort(t+1,t+1+13);
 66         memset(cnt,0,sizeof cnt);
 67         memset(need,0,sizeof need);
 68         int now = 1;
 69         int p = 0;
 70         for(;;now++)
 71         {
 72             if(!isdigit(t[now])) break;
 73             need[1][++p] = t[now];
 74         }
 75         cnt[1] = now - 1;
 76         p = 0;
 77         for(;;now++)
 78         {
 79             if(t[now] < A || t[now] > Z) break;
 80             need[2][++p] = t[now];
 81         }
 82         cnt[2] = p;
 83         p = 0;
 84         for(;now<=13;now++)
 85         {
 86             need[3][++p] = t[now];
 87         }
 88         cnt[3] = p;
 89 
 90         ans = 1;
 91         memset(str,0,sizeof str);
 92         strcat(str+1,need[1]+1); strcat(str+1,need[2]+1); strcat(str+1,need[3]+1);
 93         solve();
 94         memset(str,0,sizeof str);
 95         strcat(str+1,need[1]+1); strcat(str+1,need[3]+1); strcat(str+1,need[2]+1);
 96         solve();
 97         memset(str,0,sizeof str);
 98         strcat(str+1,need[2]+1); strcat(str+1,need[1]+1); strcat(str+1,need[3]+1);
 99         solve();
100         memset(str,0,sizeof str);
101         strcat(str+1,need[2]+1); strcat(str+1,need[3]+1); strcat(str+1,need[1]+1);
102         solve();
103         memset(str,0,sizeof str);
104         strcat(str+1,need[3]+1); strcat(str+1,need[1]+1); strcat(str+1,need[2]+1);
105         solve();
106         memset(str,0,sizeof str);
107         strcat(str+1,need[3]+1); strcat(str+1,need[2]+1); strcat(str+1,need[1]+1);
108         solve();
109         printf("%d\n",13-ans);
110     }
111     return 0;
112 }
1005

 

  1006,做这题前可以先做一下hdu2045。在该题中两个颜色相同的位置(称之为分隔处)把这个串分成了两部分,这两个相同颜色的位置假设颜色已经固定了(最后只要把答案再乘以k即可),那么剩余的有(k-1)种颜色可选择,设f[i]为长度为i的合理串的种数,那么这个状态可以从以下两个状态转移过来:

  1.长度为i-1的合理的串,那么其最后一个颜色一定与分隔处不同,那么第i个位置只剩下了(k-2)种选择,贡献为(k-2)*f[i-1]。

  2.长度为i-1的不合理的串,那么前i-2个必须合理,否则不能转移到i处,同时不可能是i-2和i-1处的颜色不同(如果不同也无法转移到i处),只能是i-1处和分隔处的颜色相同才行,那么i这个地方有(k-1)种选择,贡献为(k-1)*f[i-2]。

  综上可得,f[i] = f[i-1]*(k-2) + f[i-2]*(k-1)(可以发现这种推算f的方式和hdu2045中类似)。边界处手算一下即可。得到了以后就可以做了。假设分隔位置为l和r,那么新的两部分的长度为别为Len1=|r-l|-1,Len2=n-|r-l|-1。那么最后的答案为k*f[Len1]*f[Len2] % mod。

  同时,还有别的方法推f数组,每次扩张一个新长度时,只有k-1种选择(因为不能和分隔处颜色相同),所以总次数为(k-1)^i,这其中有重复的,计算方法如下:如果i-1处和分隔处颜色相同,那么i这个位置一定不会和相邻位置颜色相同;当i-1处和分隔处颜色不同,这时才有可能i的颜色和i-1处的重合,这种情况的总数是,前i-1个位置的正确总数,即f[i-1],那么f[i] = (k-1)^i - f[i-1]。后面的计算方法类似。

  代码如下(第一种推算f数组的方法):

技术分享
 1 #include <bits/stdc++.h>
 2 #define t_mid (l+r>>1)
 3 #define ls (o<<1)
 4 #define rs (o<<1|1)
 5 #define lson ls,l,t_mid
 6 #define rson rs,t_mid+1,r
 7 using namespace std;
 8 const int N = 1e5 + 100;
 9 typedef long long ll;
10 typedef pair<int,int> pii;
11 const int mod = 1e9 + 7;
12 
13 int n,m,k;
14 int f[N];
15 
16 int main()
17 {
18     while(scanf("%d%d%d",&n,&m,&k) == 3)
19     {
20         f[1] = k-1;
21         f[2] = (ll)(k-1) * (k-2) % mod;
22         for(int i=3;i<=n;i++)
23         {
24             f[i] = ((ll)(k-2)*f[i-1] + (ll)(k-1)*f[i-2]) % mod;
25         }
26         while(m--)
27         {
28             int l, r;
29             scanf("%d%d",&l,&r);
30             int ans = (ll)k*f[abs(r-l)-1] % mod * (f[n-abs(r-l)-1]) % mod;
31             printf("%d\n",ans);
32         }
33     }
34     return 0;
35 }
1006

 

  1007,分奇数和偶数作为起点进行扫描,维护遇到的最小的前缀和并更新答案即可。

  1008,结论题。如果两点是相邻的则能追到,否则不行。理由是如果距离大于等于2,走的人走哪里,打断下一条路即可。

  1009,分情况讨论即可。注意即使一开始全部相同,也必须要交换(也就是说要满足,只能换相同的两个字母)。

  1010,因为位数少,直接暴力即可。如果位数多,可以考虑数位dp。

技术分享

2017杭电ACM集训队单人排位赛 - 2 题解