两个东西
1. IDI-Open 2016 - Building Fences
题目大概意思是给 K 根不同长度的木棍求截得至少 N 根且剩下的木棍总长度不长于这 N 根木棍的最小截取次数.
二分一下枚举这 N 段木棍的长度即可(一开始没搞得清还以为要整数TwT)
这里枚举得到的木棍长度 len 精度控制在 eps.
之后因为要计算长度为 L 的木棍截成长度为 len 的木棍需要 cut 的次数 num, 如果正好 num * len == L 那就需要 cut num - 1 次否则就是 num 次.
这里判断 num * len 和 L 的差的绝对值的时候不能再用 eps 来判断了, 因为 len 乘了 num 所以误差相应的扩大了 num, 所以应该是 fabs(num * len - L) < eps * num
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
double p[10007];
const double eps = 1e-8;
int main()
{
int K, N, cnt;
double l, r, mid, maxlen, num;
while(scanf("%d%d", &K, &N) != EOF){
for(int i = 0; i < K; i++) scanf("%lf", &p[i]);
l = 0.0, r = 10000.0, maxlen = 0.0;
while(r - l > eps){
mid = (l + r) * 0.5;
cnt = 0;
for(int i = 0; i < K; i++) cnt += (int)(p[i] / mid);
if(cnt >= N) maxlen = l = mid;
else r = mid;
}
cnt = 0;
for(int i = 0; i < K; i++){
if(fabs(p[i] - maxlen) < eps) continue;
num = (int)(p[i] / maxlen);
if(fabs(p[i] / maxlen - (double)num) < eps * num) cnt += num - 1;
else cnt += num;
}
printf("%d\n", cnt);
}
return 0;
}
2. 2017 Multi-University Training Contest - Team 1 - Balala Power!
for(int i = cnt - 1; i > pos; i--) order[i - 1] = order[i];
for(int i = pos; i < cnt - 1; i++) order[i] = order[i + 1];
目标: 把 pos 位置之后的元素依次往前移动一个覆盖掉 pos 位置的元素.
实现所用时间: 24h
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const long long MOD = 1e9 + 7;
long long Count[27][100007], mod[100007];
char s[100007];
int order[27], maxlen, cnt, link[27];
bool vis[27], zero[27];
inline bool cmp(int u, int v){
for(int i = maxlen + 4; i >= 0; i--) if(Count[u][i] != Count[v][i]) return Count[u][i] > Count[v][i];
return false;
}
int main()
{
int n, len, pos, temp, cas = 1;
long long ans;
mod[0] = 1, mod[1] = 26;
for(int i = 2; i <= 100007; i++) mod[i] = (long long)mod[i - 1] * 26 % MOD;
while(scanf("%d", &n) != EOF){
memset(Count, 0, sizeof(Count));
memset(vis, false, sizeof(vis));
memset(zero, false, sizeof(zero));
maxlen = cnt = 0;
for(int i = 0; i < n; i++){
scanf("%s", s);
len = strlen(s);
for(int j = 0; j < len; j++){
Count[s[j] - 'a'][len - 1 - j]++;
if(!vis[s[j] - 'a']) vis[s[j] - 'a'] = true, order[cnt] = s[j] - 'a', cnt++;
}
if(len > 1 && !zero[s[0] - 'a']) zero[s[0] - 'a'] = true;
if(len > maxlen) maxlen = len;
}
for(int i = 0; i < 26; i++){
if(vis[i]) for(int j = 0; j < maxlen + 4; j++){
if(Count[i][j] >= 26) Count[i][j + 1] += Count[i][j] / 26, Count[i][j] %= 26;
}
}
sort(order, order + cnt, cmp);
if(cnt == 26 && zero[order[cnt - 1]]){
for(pos = cnt - 1; pos >= 0; pos--) if(!zero[order[pos]]) break;
temp = order[pos];
for(int i = pos; i < cnt - 1; i++) order[i] = order[i + 1];
order[cnt - 1] = temp;
}
ans = 0;
for(int i = 25; i > 25 - cnt; i--){
if(i == 0) break;
for(int j = maxlen + 4; j >= 0; j--)
ans = (ans + (Count[order[25 - i]][j] * mod[j] % MOD) * i % MOD) % MOD;
}
printf("Case #%d: %I64d\n", cas++, ans);
}
return 0;
}
最好的谎言是九分真一分假最难找的bug是别的地方全都没问题就这一个地方莫名其妙写崩了
大概以后要引入模块化设计和单元测试吧(迫真
