2019  2.15模拟赛

分裂

【问题描述】

你有一个大小为?的?????，每次你可以从你已有的?????中选择一 个大小不为1的?????，设他的大小为?，然后把它分裂成?和? − ?，其 中1 ≤ ? < ?，这样你获得的收益是? * (? − ?) 给定?，?，求最少分裂几次才能得到至少?的收益

 

 

【输入格式】

从文件 split.in 中读入数据。 第一行两个正整数?，?

【输出格式】

输出到文件 split.out 中。 输出一个非负整数表示答案 如果无法达到?的收益输出−1

 

【样例输入】

765 271828

【样例输出】

14

 

【数据规模】

对于30%的数据，有? ≤ 10

对于100%的数据，有2 ≤ ? ≤ 1000，1 ≤ ? ≤ 10⁹

 

sol：首先对于30%的数据，各种乱搞都可以做。但我写了个dp，dp[i][j]表示大小为 i 的Jabby，切 j 刀可得的最大权值，事实可以过到200，但没有这档分。标算是这么想的：因为要把一个物体切成 j 个，肯定是尽量平均的最优，就枚举 j，然后模拟切得过程，n²水过，其实是可以n*logn的，j显然是可以二分的

inline void Solve_30pts(){    int i,j,k,l;    dp[1][0]=0;    for(i=2;i<=S;i++)    {        dp[i][0]=0;        for(j=1;j<=i/2;j++)        {            for(k=0;k<=j;k++)            {                for(l=0;l<=i-j;l++) dp[i][k+l+1]=max(dp[i][k+l+1],dp[j][k]+dp[i-j][l]+j*(i-j));            }        }    }    for(i=0;i<=S;i++)    {        if(dp[S][i]>=M)        {            Wl(i);            return;        }    }}

#include 
      
       using namespace std;typedef int ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-'); ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-'); x=-x;    }    if(x<10)    {        putchar(x+'0'); return;    }    write(x/10);    putchar((x%10)+'0');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')int S,M;int main(){    freopen("split.in","r",stdin);    freopen("split.out","w",stdout);    int i,j;    R(S); R(M);    for(i=2;i<=S;i++)    {        int tmp=S/i,opt=S%i;        int Now=0,Sum=S;        for(j=1;j<=i;j++)        {            int oo=tmp+((opt>=j)?1:0);            Now+=oo*(Sum-=oo);        }        if(Now>=M)        {            Wl(i-1); return 0;        }    }    puts("-1");    return 0;}
      

 

异或计数

【问题描述】

给定长度为?的非负整数序列?，问有多少个长度为?的非负整数序列?， 满足： ?? ≤ ?? ?1 ??? ?2 ???...??? ?? = ?1 ??? ?2 ???...??? ?? 答案对1000000009取模

 

【输入格式】

从文件 xor.in 中读入数据。 第一行一个正整数? 第二行?个非负整数??

【输出格式】

输出到文件 xor.out 中。 输出一个数字，表示答案

 

【样例输入】

4

1 2 3 4 

【样例输出】

6

 

【数据规模】

对于30%的数据，1 ≤ ? ≤ 10，?? ≤ 10³

对于50%的数据，1 ≤ ? ≤ 20

对于70%的数据，1 ≤ ? ≤ 40

对于100%的数据，1 ≤ ? ≤ 10⁵，?? ≤ 2 ³⁰

 

sol：完全参照题解做法，连中间两档部分分也不会。。。

dp[i][j][0,1]表示前i个数字，当前这位的异或和是j,是否有至少一位小于上限

考虑转移

枚举当前位Bit

{

　　枚举0~n-1

　　如果ai+1 Bit位是1         dp[i][j][k]*(a[i+1] and (2^Bit-1-1)+1) ----> dp[i+1][j^1][k]   //使得取满

　　　　　　　　　　　　 dp[i][j][k]*2^Bit-1--->dp[i+1][j][k|1]         //使得小于上限

　　如果ai+1 Bit位是0        dp[i][j][k]*(a[i+1] and (2^Bit-1-1)+1) -----> dp[i+1][j][k] //取满

}

统计的时候加上dp[n][(Sum>>Bit)&1][1] / 2^Bit-1（至少有一位小于上限，统计完后ans+一种ai=bi的情况）

但我想不明白为什么要除以2^Bit-1     。。。。。。。。。。。

updata：想明白了跑回来填坑：因为统计的是当前这位的贡献，并且为了方便，加答案时加上的是至少一位小于上限的，所以对于一个小于上限的数，其0~Bit-1位可以乱填，就能保证0~Bit-1位异或和的正确性了，所以其实满足正确性的只有一种，因此要除以2^Bit-1  

Ps：处理的时候有个小优化，因为and 2^Bit-1-1 这东西很烦，所以直接倒着枚举Bit，每次如果ai 在Bit位是1，就ai-2^Bit

#include 
      
       using namespace std;typedef long long ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-'); ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-'); x=-x;    }    if(x<10)    {        putchar(x+'0'); return;    }    write(x/10);    putchar((x%10)+'0');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) write(x),putchar('\n')const int N=100005;const ll Mod=1000000009;int n,a[N];ll Bin[35],dp[N][2][2];//dp[i][j][0,1]表示前i个数字，当前这位的异或和是j,是否有至少一位小于上限inline void Ad(ll &x,ll y){    x+=y;    x-=(x>=Mod)?Mod:0;    return;}inline ll Ksm(ll x,ll y,ll Mod){    ll ans=1;    while(y)    {        if(y&1) ans=ans*x%Mod;        x=x*x%Mod;        y>>=1;    }    return ans;}int main(){    freopen("xor.in","r",stdin);    freopen("xor.out","w",stdout);    int Bit,i;    ll ans=0,Sum=0;    R(n);    for(i=1;i<=n;i++) {R(a[i]); Sum^=a[i];}    for(Bit=29;Bit>=0;Bit--)    {        int o1,o2,oo=0;        memset(dp,0,sizeof dp); dp[0][0][0]=1;        for(i=1;i<=n;i++)        {            if(a[i]&(1<
      

 

 

brainfuck

【问题描述】

?????????是一种很有趣的语言，该题只考虑他的简化版。

这个语言的程序是一段字符串，一开始命令指针指在位置1，每次执行 后往后跳1格 一开始你有一个变量?，

这个语言有4种指令：

(1)+ : ? + +

(2)− : ? − −

(3)[:若?等于0，则命令指针跳到这个括号匹配的]

(4)] :若?不等于0，则命令指针跳到这个括号匹配的[

通俗的理解的话就是： [− − −− > ?ℎ???(?){ ] − − − − >}

一段程序是合法的当且仅当：括号都是匹配的，且程序不死循环

现在白鸟阳想知道长度为?的合法程序有多少个，答案对?取模

 

 

【输入格式】

从文件 brainfuck.in 中读入数据。 第一行两个正整数?,?

【输出格式】

输出到文件 brainfuck.out 中。 第一行一个整数，表示答案

 

【样例输入】

2 1000000000

【样例输出】

5

 

【数据规模】

对于30%的数据，1 ≤ ? ≤ 10

对于50%的数据，1 ≤ ? ≤ 50

对于100%的数据，1 ≤ ? ≤ 100，1 ≤ ? ≤ 10⁹

 

sol：30分看上去很好写 4¹⁰次，开个栈模拟，但我没打，考场上写了一个不能套括号的dp，到死都没发现自己看错题了

标算好像不难理解，但我抄了zyy的，所以就按另一种方法（其实很像的）

转移都在代码注释了（其实是我还有些小地方不是很理解）

#include 
      
       using namespace std;typedef long long ll;inline ll read(){    ll s=0;    bool f=0;    char ch=' ';    while(!isdigit(ch))    {        f|=(ch=='-');        ch=getchar();    }    while(isdigit(ch))    {        s=(s<<3)+(s<<1)+(ch^48);        ch=getchar();    }    return (f)?(-s):(s);}#define R(x) x=read()inline void write(ll x){    if(x<0)    {        putchar('-');        x=-x;    }    if(x<10)    {        putchar(x+'0');        return;    }    write(x/10);    putchar((x%10)+'0');    return;}inline void writeln(ll x){    write(x);    putchar('\n');    return;}#define W(x) write(x),putchar(' ')#define Wl(x) writeln(x)const int N=105;int n;ll Mod;ll g[N][N<<1],f[N][N<<1],dp_Pre[N][N<<1];ll Perfect[N];ll dp[N][N][N<<1]; //dp[i][j][k]表示长度为i，除当前位外(k!=0)的个数，当前变量x的值为k的方案数 inline void Ad(ll &x,ll y){    x+=y;    x-=(x>=Mod)?Mod:0;    return;}int main(){    freopen("brainfuck.in","r",stdin);    freopen("brainfuck.out","w",stdout);    int i,j,k,l;    R(n); R(Mod);    f[0][n]=1;    for(i=0;i<=n-1;i++)    {        for(j=-i;j<=i;j++)        {            Ad(f[i+1][j+n+1],f[i][j+n]);            Ad(f[i+1][j+n-1],f[i][j+n]);        }    }    //f[Len][delta] 把x放进去变成x+delta    for(l=1;l<=n-2;l++)    {        for(i=1;i<=n;i++)        {            for(j=1;j