8 ffcfffcffcff cffcfff cffcff cffcf ffffcffcfff cffcfffcffffcfffff cff cffc
Case #1: 3 Case #2: 2 Case #3: 2 Case #4: -1 Case #5: 2 Case #6: 4 Case #7: 1 Case #8: -1HintShift the string in the first test case, we will get the string "cffffcfffcff" and it can be split into "cffff", "cfff" and "cff".
题意是找最小的划分 子串在题中已给出 f ff cff cfff cf4 cf5 cf6 cfn 这样只要暴力判两个c之间f的数目即可 如果存在两个c之间f小于2 说明不可划分 否则一定会划分成c的数量个区间 也就是划分的最小数量为c的数量 另外 如果没c 就划分成len/2+len%2 即全划ff或f
额外需要注意的是有空串和其余字符还有串是环串 首尾连在一起的。。。
代码如下:
#include <bits/stdc++.h>
using namespace std;
char str[1111111];
int pos[1111111];
int tp;
int main()
{
int t,i,z,cnt,f,len;
scanf("%d",&t);
getchar();
for(z = 1; z <= t; ++z)
{
gets(str);
tp = 0;
f = 1;
for(i = 0; str[i]; ++i)
{
if(str[i] == 'c') pos[tp++] = i;//记录每个c的位置
else if(str[i] != 'f') f = 0;//有其余字符
}
len = strlen(str);
printf("Case #%d: ",z);
if(!f) puts("-1");//有其余字符
else if(tp == 0)//没有c
{
printf("%d\n",len/2+len%2);
}
else
{
for(i = 0; i < tp-1; ++i)
{
if(pos[i+1]-pos[i]-1 < 2)//两个c之间f数量小于2
{
f = 0;
break;
}
}
if(len-1-pos[tp-1]+pos[0] < 2) f = 0;//特判第一个c和最后一个 因为是成环切割
if(f)
{
printf("%d\n",tp);
}else puts("-1");
}
}
return 0;
}9 5 6 7 8 113 1205 199312 199401 201314
Case #1: 5 Case #2: 16 Case #3: 88 Case #4: 352 Case #5: 318505405 Case #6: 391786781 Case #7: 133875314 Case #8: 83347132 Case #9: 16520782
首先有这么几个数组
pre //首个c到之后c的距离和
post //最后一个c到之前c的距离和
cnt //点数
ans //答案(任意两个c距离和)
f //最大两个c的间距
1 c
2 ff
3 cff
4 ffcff
5 cffffcff
6 ffcffcffffcff
7 cffffcffffcffcffffcff
这是前几项 很容易推出
cnt[i] = cnt[i-2] + cnt[i-1] //点数
f[i] = f[i-2] + f[i-1] + ((i%2 == 0)? 3: 5) //c 最大间距
然后发现 如果有pre 跟post之后 ans也可推出
ans[i] = post[i-2]*cnt[i-1]+pre[i-1]*cnt[i-2]+x*cnt[i-2]*cnt[i-1]+ans[i-1]+ans[i-2]; // x :两串合并后中间cffffc f数量 跟当前串奇偶有关 x = ((i%2 == 0)? 3: 5)
ans = 前串末c到之前所有c的距离和 * 后串c个数 + 后串首c到之后所有c的距离和*前串c的个数 + 中间f数量*两串c数积 + 两串各自c距离和
原理: 组成新串后 后串任意c到前串每个c的距离等于 前串末c到之前每个c距离+生成新串中间新加f数*前串点数
前串c到后串同理 之后再加上两串各自c距离和即可
这样只需要再推出pre跟post即可
pre[i] = x*cnt[i-1]+pre[i-1]+pre[i-2]+f[i-2]*cnt[i-1] //新串首c到之后c的距离和 继承前后串距离和-pre[i-2,i-1] 然后到后串经过 cnt[i-1]*f[i-2] 和 x*cnt[i-1]
post[i] = x*cnt[i-2]+post[i-1]+post[i-2]+f[i-1]*cnt[i-2] //同上
递推结束 O(1)输出答案即可 注意推到过程中步步取余。。烦= =
代码如下:
#include <bits/stdc++.h>
#define mod 530600414
#define ll long long
using namespace std;
ll f[201316];
ll cnt[201316];
ll ans[201316],pre[201316],post[201316];
int main()
{
int i,t,n,x;
cnt[3] = 1;
cnt[4] = 1;
f[3] = 0;
f[4] = 0;
ans[3] = ans[4] = 0;
pre[3] = pre[4] = post[3] = post[4] = 0;
for(i = 5; i <= 201314; ++i)
{
cnt[i] = (cnt[i-1]+cnt[i-2])%mod;
<span style="white-space:pre"> </span>x = i&1? 5: 3;
f[i] = (f[i-1]+f[i-2]+x)%mod;
pre[i] = (((x*cnt[i-1]%mod+pre[i-1])%mod+pre[i-2])%mod+f[i-2]*cnt[i-1]%mod)%mod;
post[i] = (((x*cnt[i-2]%mod+post[i-1])%mod+post[i-2])%mod+f[i-1]*cnt[i-2]%mod)%mod;
ans[i] = (((post[i-2]*cnt[i-1]%mod+pre[i-1]*cnt[i-2]%mod)%mod+x*cnt[i-2]*cnt[i-1]%mod)%mod+ans[i-1]+ans[i-2])%mod;
}
scanf("%d",&t);
for(int z = 1; z <= t; ++z)
{
scanf("%d",&n);
printf("Case #%d: %I64d\n",z,ans[n]);
}
return 0;
}
2 3 2 1 1 2 3 5 -1 0 -3 -3 0 3 3
Case #1: 20 Case #2: 0
两数组排序后直接去第一个判断下标是否一样 一样就比较a取最大*b取次大跟a取次打b最大 输出最大即可
我做的是不断判断。。。
算是个教训 两种都贴上吧
代码如下:
//渣法。。四个判断。。。
#include <bits/stdc++.h>
#define ll long long
#define mx 2000000
#define fwrite() freopen("../out.out","r",stdout)
#define fread() freopen("../in.in","w",stdin)
using namespace std;
ll a,b;
vector <ll> v;
ll gt(ll t1,ll t2)
{
return a*t1*t1+b*t2;
}
int main()
{
//fread();
//fwrite();
int n,i,t,sz,z;
vector<ll>::iterator it,tmp;
ll t1,t2,x,ans;
scanf("%d",&t);
for(z = 1; z <= t; ++z)
{
v.clear();
scanf("%d %I64d %I64d",&n,&a,&b);
for(i = 0; i < n; ++i)
{
scanf("%I64d",&x);
v.push_back(x);
}
sort(v.begin(),v.end());
it = lower_bound(v.begin(),v.end(),0);
sz = v.size();
if(a < 0 && b < 0)//- -
{
tmp = it;
tmp--;
if(it == v.begin() || tmp == v.begin())
{
ans = max(gt(v[1],v[0]),gt(v[0],v[1]));
}
else ans = max(gt(*it,v[0]),gt(*tmp,v[0]));
}
else if(a < 0 && b >= 0)//- +
{
tmp = it;
tmp++;
if(tmp == v.end())
{
ans = max(gt(v[sz-1],v[sz-2]),gt(v[sz-2],v[sz-1]));
}
else if(it == v.begin())
{
ans = gt(v[0],v[sz-1]);
}
else
{
tmp = it--;
ans = max(gt(*it,v[sz-1]),gt(*tmp,v[sz-1]));
}
}
else if(a >= 0 && b <= 0)//+ -
{
ans = max(gt(v[0],v[1]),gt(v[sz-1],v[0]));
}
else//+ +
{
ans = gt(v[0],v[sz-1]);
ans = max(ans,gt(v[sz-1],v[sz-2]));
ans = max(ans,gt(v[sz-2],v[sz-1]));
}
printf("Case #%d: %I64d\n",z,ans);
}
return 0;
}
//排序输出。。。慢 慢又怎样 好想啊…………if渣法卡半天TOT
#include <bits/stdc++.h>
#define ll long long
#define mx 2000000
#define fwrite() freopen("../out.out","r",stdout)
#define fread() freopen("../in.in","w",stdin)
using namespace std;
struct Mult
{
ll ans;
int id;
bool operator < (const struct Mult a)const
{
return ans == a.ans? id < a.id : ans > a.ans;
}
};
Mult mla[6666666],mlb[6666666];
ll a,b;
int main()
{
//fread();
//fwrite();
int n,i,t,z;
ll x;
scanf("%d",&t);
for(z = 1; z <= t; ++z)
{
scanf("%d %I64d %I64d",&n,&a,&b);
for(i = 0; i < n; ++i)
{
scanf("%I64d",&x);
mla[i].ans = a*x*x;
mlb[i].ans = b*x;
mla[i].id = mlb[i].id = i;
}
sort(mla,mla+n);
sort(mlb,mlb+n);
printf("Case #%d: %I64d\n",z,mla[0].id != mlb[0].id? (mla[0].ans+mlb[0].ans): max(mla[0].ans+mlb[1].ans,mla[1].ans+mlb[0].ans));
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
【题解】 2015 ACM/ICPC Asia Regional Shenyang Online
原文：http://blog.csdn.net/challengerrumble/article/details/48706295