因为（省选滚大粗）要去参加pkusc，所以入了WF的巨坑。
WF2012
【BZOJ3979】infiltration
这道题一看就非常神的样子！（我会贪心！）
把序列随机一发，然后按随机的顺序选择直到满足条件为止。（这个可以压位）
随机2W次，提交，过了！
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=110;
int cas,n,i,j,a[M][3],b[M],x[3],y[3];
char s[M];
int main(){
while(scanf("%d",&n)!=EOF){
cas++;
memset(a,0,sizeof a);
memset(x,0,sizeof x);
for (i=1;i<=n;i++){
scanf("%s",s+1);
for (j=1;j<=n;j++)a[i][(j-1)/30]+=(s[j]-'0')*(1<<((j-1)%30));
a[i][(i-1)/30]+=1<<((i-1)%30);
x[(i-1)/30]+=1<<((i-1)%30);
}
int ans=n;
for (i=1;i<=n;i++)b[i]=i;
for (int t=1;t<=20000;t++){
int tmp=0;
random_shuffle(b+1,b+n+1);
memset(y,0,sizeof y);
for (i=1;i<=n;i++){
for (j=0;j<3;j++)y[j]|=a[b[i]][j];
if (y[0]==x[0]&&y[1]==x[1]&&y[2]==x[2])break;
}
ans=min(ans,i);
}
printf("Case %d: %d\n",cas,ans);
}
}
【BZOJ3978】Fibonacci words
令f(i)表示p斐波那契串F(i)中出现了多少次。
那么f(i)=f(i-1)+f(i-2)+g(i)，g(i)表示p越过连接点的匹配数。
显然只要把F(i-1)长度为|p|-1的后缀和F(i-2)长度为|p|-1的前缀拼起来做kmp即可求出g(i)。
维护斐波那契串的前缀和后缀即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=2000010;
int cas,n,m,i,j;
char s[M];
int a[M],b[M],seq[2][M],g[110],fib[M],next[M];
long long f[110];
int cmp(){
int ans=0,i=1,j=1;
while (i<=b[0]){
if (!j||b[i]==a[j]){i++;j++;if (j>m){ans++;j=next[j];}}
else j=next[j];
}
return ans;
}
int main(){
while (scanf("%d",&n)!=EOF){
memset(f,0,sizeof f);
memset(g,0,sizeof g);
cas++;
scanf("%s",s);
printf("Case %d: ",cas);
m=strlen(s);
for (i=1;i<=m;i++)a[i]=s[i-1]-'0';
i=1,j=0,next[1]=0;
while (i<=m){
if (!j||a[i]==a[j]){i++;j++;next[i]=j;}
else j=next[j];
}
fib[0]=1;fib[1]=1;
seq[0][1]=0;seq[1][1]=1;
if (m==1&&a[1]==0)f[0]=1;else if (m==1)f[1]=1;
for (i=2;i<=n;i++){
fib[i]=fib[i-2]+fib[i-1];
if (i>=4&&fib[i-4]>(m-1)*2)break;
b[0]=0;
if (fib[i-1]>=m-1){
for (j=fib[i-1]-m+2;j<=fib[i-1];j++)b[++b[0]]=seq[1][j];
}else for (j=1;j<=fib[i-1];j++)b[++b[0]]=seq[1][j];
if (fib[i-2]>=m-1){
for (j=1;j<=m-1;j++)b[++b[0]]=seq[0][j];
}else for (j=1;j<=fib[i-2];j++)b[++b[0]]=seq[0][j];
if (b[0]>=m)g[i]=cmp();
for (j=1;j<=fib[i-1];j++)b[j]=seq[1][j];
for (j=1;j<=fib[i-2];j++)b[fib[i-1]+j]=seq[0][j];
for (j=1;j<=fib[i-1];j++)seq[0][j]=seq[1][j];
for (j=1;j<=fib[i];j++)seq[1][j]=b[j];
f[i]=f[i-1]+f[i-2]+g[i];
}
for (j=i;j<=n;j++){f[j]=f[j-1]+f[j-2]+g[j-2];g[j]=g[j-2];}
printf("%lld\n",f[n]);
}
}
【BZOJ3983】Takeover Wars
考虑A公司的最优策略。令x表示A的最大子公司规模，y表示A的次大子公司规模，z表示B的最大子公司规模，w表示B的次大子公司规模。
如果x<z或x+y>z+w，那么就合并最大和次大的子公司，否则就除去B的最大子公司，B公司同理。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
typedef long long ll;
using namespace std;
int n,m,i,cas;
ll x;
priority_queue<ll>a,b;
ll geta(){
ll x=a.top();a.pop();
ll y=x+a.top();a.push(x);
return y;
}
ll getb(){
ll x=b.top();b.pop();
ll y=x+b.top();b.push(x);
return y;
}
int main(){
while (scanf("%d%d",&n,&m)!=EOF){
cas++;
while (!a.empty())a.pop();
while (!b.empty())b.pop();
for (i=1;i<=n;i++)scanf("%lld",&x),a.push(x);
for (i=1;i<=m;i++)scanf("%lld",&x),b.push(x);
int now=0;
while ((!a.empty())&&(!b.empty())){
if (!now){
if (a.top()<b.top()){
if (a.size()>1){
x=a.top();a.pop();
x+=a.top();a.pop();
a.push(x);
}
}else{
if (a.size()>1&&b.size()>1&&geta()>getb()){
x=a.top();a.pop();
x+=a.top();a.pop();
a.push(x);
}else b.pop();
}
}else{
if (b.top()<a.top()){
if (b.size()>1){
x=b.top();b.pop();
x+=b.top();b.pop();
b.push(x);
}
}else{
if (a.size()>1&&b.size()>1&&geta()<getb()){
x=b.top();b.pop();
x+=b.top();b.pop();
b.push(x);
}else a.pop();
}
}
now^=1;
}
printf("Case %d: ",cas);
if (a.empty())puts("Buyout Limited");else puts("Takeover Incorporated");
}
}
WF2013
【BZOJ3969】Low Power
谜之签到题。
考虑二分答案，从小到大确定每个机器芯片的能量，显然尽量要选择能量低的电池，因为至少还要从后面选出2(k-1)个电池。
因为每个电池必须被用到，所以如果不存在容纳当前电池的机器，该方案就是不可行的。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,i,l,r;
int a[1000010],flag[1000010];
int check(int x){
memset(flag,0,sizeof flag);
long long tmp=0;
for (int i=1;i<=2*n*m;i++)
if (!flag[i]&&a[i+1]-a[i]<=x)flag[i]=flag[i+1]=1,tmp+=(m-1)*2;
else if (!flag[i]){
tmp--;
if (tmp<0)return 0;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=2*n*m;i++)scanf("%d",&a[i]);
sort(a+1,a+2*n*m+1);
l=0;r=0;for (i=2;i<=2*n*m;i++)r=max(r,a[i]-a[i-1]);
while (l<r){
int mid=l+r>>1;
if (check(mid))r=mid;else l=mid+1;
}
printf("%d\n",l);
}
【BZOJ3967】Factors
[tex]n=\Pi{{p_i}^{x_i}=>f(n)=\frac{(\sum{x_i})!}{\Pi{x_i!}}}[/tex]
考虑枚举xi后贪心地构造n，那么f的值可以同时求出，然后加上一堆剪枝就过了。
（然后因为炸longlong的问题贡献了十多发WA）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
using namespace std;
const ll inf=(1ll<<62)-1+(1ll<<62);
double eps=1e-11;
int i,j,g[110][110],G[110][110];
double LOG[1010];
ll n,ans;
int prime[19]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
int time[19]={0,62,30,20,10,8,7,6,5,4,3,2,1,1,1,1,1,1};
bool work(double a,int b,int c,double d){
return log(a)+LOG[b]-eps<=LOG[c]+log(d);
}
void dfs(int k,int pre,int num,ll tmp,ll x){
if (x>ans)return;
if (tmp==n){ans=min(ans,x);return;}
for (int i=1;i<=pre&&i<=time[k];i++)
if (work(tmp,num+i,i,n)&&work(x,prime[k],1,inf)){
x=x*prime[k];
ll X=g[num+i][i];
tmp=tmp/G[i][X]*G[num+i][X];
if (n%tmp==0)dfs(k+1,i,num+i,tmp,x);
}else break;
}
int main(){
for(i=1;i<=100;i++)for(j=1;j<=100;j++)g[i][j]=__gcd(i,j);
for(i=1;i<=100;i++)for(j=1;j<=100;j++)G[i][j]=i/j;
for(i=1;i<=1000;i++)LOG[i]=log(i);
while (scanf("%lld",&n)!=EOF){
printf("%lld ",n);
if (n==1){puts("2 ");continue;}
ans=inf;
dfs(1,100,0,1,1);
printf("%lld \n",ans);
}
}
评论 (0)
