首页 > 代码库 > 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 }
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 }
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 }
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 }
1007，分奇数和偶数作为起点进行扫描，维护遇到的最小的前缀和并更新答案即可。
1008，结论题。如果两点是相邻的则能追到，否则不行。理由是如果距离大于等于2，走的人走哪里，打断下一条路即可。
1009，分情况讨论即可。注意即使一开始全部相同，也必须要交换（也就是说要满足，只能换相同的两个字母）。
1010，因为位数少，直接暴力即可。如果位数多，可以考虑数位dp。
2017杭电ACM集训队单人排位赛 - 2 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。