[poi2012]bon-vouchers----你敢模拟吗？(代码片段)

关键词：

链接：https://www.luogu.org/problemnew/show/P3536

题意：

定义n个数为幸运数字，一共有n批人，设第i批人有x个，则它们会依次取走余下的x的倍数中最小的x个，问哪些人去走了幸运数字

题解：

考虑暴力吧。

枚举每一天，从第一个能买的开始买。对于相同的顾客数量，就记录一下las[x]吧，下次从这里继续往后枚举。。

交一发。——AC了！！

为什么感觉n^2实际上这么快？？

复杂度证明：n<=1e6,

如果每一天人都不一样，最坏情况下是：n/1+n/2+n/3+n/4...=nlogn

这是最坏情况下，实际远远不到这个上界。

对于有相同的情况，因为记录了一下last，就直接从这里开始，复杂度更低。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
bool vis[N],is[N];
int last[N];
int top;ll now,ans[N];

int main()

    int n,x;scanf("%d",&n);
    while (n--)   scanf("%d",&x);is[x]=1; 
    scanf("%d",&n);
    vis[0]=1;
    for(int k=1;k<=n;k++)
    
        scanf("%d",&x);
        int &i=last[x],j=x;
        for (;j;--j)
        
            while (i<=N&&vis[i]) i+=x;
            if(i>N)break; 
            vis[i]=1;++now;
            if (is[i]) ans[++top]=now;
        
        now+=j;
    
    printf("%d
",top); 
    for (int i=1;i<=top;++i) printf("%lld
",ans[i]);

bzoj2796[poi2012]fibonaccirepresentation

【bzoj2796】[Poi2012]FibonacciRepresentationDescriptionFib数列0,1,1,2,3,5,8,13,21。给出一个数字，用FIB数列各项加加减减来得到。例如10=5+519=21-217=13+5-11070=987+89-5-1InputInthefirstlineofthestandardinputasinglepositiveintegeri 查看详情

bzoj2802[poi2012]warehousestorestl

 [Poi2012]WarehouseStoreTimeLimit: 10Sec  MemoryLimit: 64MBSec  SpecialJudgeSubmit: 621  Solved: 295[Submit][Status][Discuss]Description有一家专卖一种商品 查看详情

[poi2012]festival

[Poi2012]Festival题目有n个正整数X1,X2,...,Xn，再给出m1+m2个限制条件，限制分为两类：1.给出a,b(1<=a,b<=n)，要求满足Xa+1=Xb2.给出c,d(1<=c,d<=n)，要求满足Xc<=Xd在满足所有限制的条件下，求集合{Xi}大小的最大值。INPUT第一行三个... 查看详情

[poi2012]squarks(代码片段)

[POI2012]Squarks题目大意：设有(n)个互不相同的正整数(X_1,X_2,...,X_n)，任取两个(X_i,X_j(iej))，能算出(X_i+X_j)。现在所有取法共(fracn(n-1)2)个和，要你求出(X_i)的取值方案数，并求出所有方案的(X_1,X_2,ldots,X_n)。思路：设(X_i)两两之和构 查看详情

bzoj2795[poi2012]ahorriblepoemhash

【BZOJ2795】[Poi2012]AHorriblePoemDescription给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。Input第一行一个正整数n(n<=500,000)... 查看详情

bzoj2789[poi2012]letters*

bzoj2789[Poi2012]Letters题意：给出两个长度相同且由大写英文字母组成的字符串A、B，保证A和B中每种字母出现的次数相同。现在每次可以交换A中相邻两个字符，求最少需要交换多少次可以使得A变成B。长度≤1000000题解：把A串中所... 查看详情

bzoj2803[poi2012]prefixuffix结论题

【BZOJ2803】[Poi2012]PrefixuffixDescription对于两个串S1、S2，如果能够将S1的一个后缀移动到开头后变成S2，就称S1和S2循环相同。例如串ababba和串abbaab是循环相同的。给出一个长度为n的串S，求满足下面条件的最大的L：1.L<=n/22.S的L前缀... 查看详情

bzoj2789[poi2012]letters树状数组

【BZOJ2789】[Poi2012]LettersDescription给出两个长度相同且由大写英文字母组成的字符串A、B，保证A和B中每种字母出现的次数相同。现在每次可以交换A中相邻两个字符，求最少需要交换多少次可以使得A变成B。Input第一行一个正整数n(2&... 查看详情

#13bzoj2794[poi2012]cloakroom

题解：感觉真是很智障。。连这么简单的题都没想出来一直在想这么做动态背包。。发现不会首先显然我们将询问按照m序列按照a[i]排序然后怎么满足b呢其实很简单啊。。只需要记录f[i]表示前面这些物品达到i体积时最小值最大... 查看详情

poi2012odl-distance(代码片段)

链接P3532[POI2012]ODL-Distance设(f_i,j)表示他给定的函数，(g_i)表示(i)的质因数个数那么[f_i,j=g_fraci*jgcd^2]考虑线性筛(g_i)。那么对于每一个数(w_i)考虑枚举他的因子作为(gcd)。也就是枚举(x)，对于(x)，枚举所有(x)的倍数(y)。所以我们预处... 查看详情

bzoj2793:[poi2012]vouchers

　　傻逼题...　　直接记录x倍数已经扫到哪里了，每次接着上次的扫就好，因为幸运数范围只有100w，扫到100w就停，根据调和级数复杂度为O(NlogN)。　　记得开longlong！！！TT#include<iostream>#include<cstring>#include<cstdlib>#i... 查看详情

bzoj2796[poi2012]fibonaccirepresentation

给出一个数字，用FIB数列各项加加减减来得到。问最少要多少个（可以重复使用）大概试了一下，fibonacci数列的增长是很快的，大概到了90+项就超过了题目范围……所以每次找一个最近的fibonacci数试一下就好，实测跑得飞快。1#i... 查看详情

[bzoj2789][poi2012]letters

　　结论是..把A串中的字符挪到B串里最近的出现这个字符的地方就能最优了。。。　　求出A串中的每个位置上的字符，之后要挪到哪个位置。然后求一波逆序对就是答案了。1#include<cstdio>2#include<iostream>3#include<cstring&g... 查看详情

[poi2012]ahorriblepoembzoj2795

分析：这是今天下午的考试题，推了2个小时，考试中A掉了首先，循环串通过字符串hash可以O(1)判断：get_hash(l,r-len)==get_hash(l+len,r);显然可证。我们其次可以发现，循环串的长度是所求串的长度的约数之后我们可以发现，如果两个... 查看详情

[bzoj2790][poi2012]distance

题意　　给定长度为n的序列a[1],a[2],...,a[n].　　对于每个数i,求出j,满足dist(a[i],a[j])最小,且i!=j.　　dist(x,y)表示由x变为y的最小步数,每次变换可以乘上素数p,或除以素数p.　　2<=n<=100000,1<=a[i]<=1000000. 分析　　从前往后... 查看详情

p3539[poi2012]roz-fibonaccirepresentation(代码片段)

题目描述TheFibonaccisequenceisasequenceofintegers,calledFibonaccinumbers,definedasfollows:Fib0=0,Fib1=1,Fibn=Fibn−2+Fibn−1 for n>1Fib_0=0,Fib_1=1,Fib_n=Fib_n-2+Fib_n-1\f 查看详情

[poi2012]festival变态差分约束题

题意有n个正整数X1,X2,...,Xn，再给出m1+m2个限制条件，限制分为两类：1.给出a,b(1<=a,b<=n)，要求满足Xa+1=Xb2.给出c,d(1<=c,d<=n)，要求满足Xc<=Xd在满足所有限制的条件下，求集合{Xi}大小的最大值。(自己注：求集合中不相同的... 查看详情

bzoj_2788_[poi2012]festival_差分约束+tarjan+floyed

BZOJ_2788_[Poi2012]Festival_差分约束+tarjan+floyedDescription有n个正整数X1,X2,...,Xn，再给出m1+m2个限制条件，限制分为两类：1.给出a,b(1<=a,b<=n)，要求满足Xa+1=Xb2.给出c,d(1<=c,d<=n)，要求满足Xc<=Xd在满足所有限制的条件下，求集合Xi... 查看详情