UOJ Logo kczno1的博客

博客

求hack

2017-12-13 14:44:08 By kczno1

http://uoj.ac/problem/219

为什么这题单取模哈希也没被$hack$啊。。

求教如何$hack$

( 而且$O(nlog^2n)$还拿了$rank1$ )

bzoj3508

2017-11-29 14:29:06 By kczno1

定义数组$a:$$a[i]=1$表示最终第$i$个灯泡亮,$0$表示暗。

则操作相当于对$a$区间异或。

差分,即令$b[i]=a[i]$ $xor$ $a[i-1]$

则$a$的区间$[l,r]$异或等价于$b[l],b[r+1]$异或。

把所有$b[i]=1$的$i$拿出来,记作数组$q$

就是每次解决掉一对$q[i],q[j]$,代价为$g[q[j]-q[i]]$

( $g$可以$O(nl)$ $bfs$得到 )

状压$dp$,$O(2^{len}*len)$ ($len$为$q$的长度,$<=2*k$)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)

template <typename T> inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}

const int N=1e4+5,L=100+5,K=10,inf=N*N;
int n,k,l;
int a[N],b[N],g[N];
int top,q[K*2];
int dp[1<<K*2];

namespace GET_G
{
int q[N];
int a[L];
void get()
{
    rep(i,1,l)a[i]=read();
    rep(i,1,n) g[i]=N;
    g[0]=0;
    int tail=1;
    q[1]=0;
    rep(head,1,tail)
    {
        int x=q[head];
        rep(i,1,l)
        {
            int y=x+a[i];
            if(y<=n&&g[y]==N) g[q[++tail]=y]=g[x]+1;
            y=x-a[i];
            if(y>0&&g[y]==N) g[q[++tail]=y]=g[x]+1;
        }
    }
}
};

int DP(int u)
{
    if(dp[u]!=-1)return dp[u];
    dp[u]=inf;
    int i=0;
    while(!(u&(1<<i))) ++i;
    rep(j,i+1,top-1)
    if(g[q[j]-q[i]]!=N)
    if(u&(1<<j)) chmin(dp[u],DP(u-(1<<i)-(1<<j))+g[q[j]-q[i]]);
    return dp[u];
}

int main()
{
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
    int tt;
    cin>>tt;
    while(tt--)
    {
        cin>>n>>k>>l;

        memset(a,0,sizeof(a));
        rep(i,1,k)a[read()]=1;
        top=0;
        rep(i,1,n+1)
        if(a[i]^a[i-1])q[top++]=i;

        GET_G::get();

        int u=(1<<top)-1;
        memset(dp+1,-1,u*sizeof(int));
        dp[0]=0;
        DP(u);
        if(dp[u]==inf) puts("-1");
        else printf("%d\n",dp[u]);
    }
}

一道挺妙的矩乘优化递推的题

2017-11-06 21:27:45 By kczno1

题意:

$f_{n}=\sum_{i=1..20} w_i*f_{n-i}$ (模一个常数)

给定$w_{1..20}$ , $f_{1..20}$ , 询问$f_n$

其中$n$以$k$进制给出,$k<=10$,$n$的位数$l<=1000$

$T$组询问,$k$都一样($T<=200$)

题解:

朴素想法是将$n$转化成$2$进制($O(l^2)$),快速幂优化矩乘($ O(l * \log_{2}{10} * 20^3 ) $)

然而这两个操作复杂度都过高,会$TLE$

考虑直接使用$k$进制,

$dp$求出所有$M^{j*k^i} ( j\in[0,k) )$

但这样$dp$复杂度为$O(l * 10 * 20^3 )$

但注意到只用$dp$一遍而不是$T$遍,所以是可以接受的。

这样单次询问复杂度就变成$ O(l * 20^3 ) $

注意到,我们要算的其实是一个$1*20$的矩阵乘多个$20*20$的矩阵

其实不用先把$20*20$的都乘起来再乘$1*20$的

可以直接依次乘

这样就只用$1*20$的乘$20*20$的

复杂度变成$ O(l * 20^2 ) $

可以通过。

srm 691 div1 - 500的各种做法

2017-10-17 19:34:30 By kczno1

题意:

$n$场比赛

打第i场加 $a_{i}$ 经验,且打完获得当前经验 * $b_{i}$ 的奖金

打完$n/2$场获得$x$的经验(保证$n$为偶数)

任意安排顺序,求最大奖金

$b_i<=10,n<=50,x和a_i<=10^5$

题解:

1 dp(标算)

如果不考虑$x$的话是可以贪心的。

因为考虑相邻两个$a_1,b_1,a_2,b_2$

交换后的变化=$a_2*b_1-a_1*b_2$

所以交换更优<=>$a_2/b_2>a_1/b_2$

只有$a/b$降序时无法交换,达到最优

所以$1..n/2$场与$n/2+1..n$场都是按$a/b$降序的。

按$a/b$降序排序后

枚举$n/2+1..n$场的$b_i$的和

然后dp,记录打了前几场,有几场在后面一半打,以及后面一半打的$b_i$的和。

复杂度$O(n^4*b^2)$ ,常数较小

2 随机化

先按$a/b$降序排序

然后考虑随机哪些点在后面一半打之后就可以贪心了

先让在后面一半的在后面一半打作为初始解

每次随机交换一个在前面的和在后面的

退火,甚至只有更优才交换,都能过。。

可以极快ac。

我目前也不知道怎么卡。。。

3 贪心+枚举

注意到$b$很小,而$b$一样的必定要让$a$大的在前面

(其实一开始想的是利用这一点暴力dp,但发现状态数会达到6^10,时空都炸)

利用这一点,暴力枚举每个$b$在后面$n/2$个占几个 然后在$O(n)$检验

最差情况下就是每个$b$都有$5$的$a$,差不多要枚举$10^7$次

勉强能过吧

[Usaco2012 Open]Bookshelf 的O(n)做法

2017-09-23 22:53:10 By kczno1

官方,网上题解似乎都是$O(nlogn)$的

前面应该都差不多:

$dp[i]$表示$1..i$的$min$

则$dp[i]=min(dp[j-1]+max(h[j..i]))$ 且$w(j)+..w(i)<=L$

从左到右枚举$i$,

则所有$j$被所有$h[k]=max(h[k..i])$的$k$分成一段一段

每段由于$dp[j]$的单调递增肯定取最左边的那个$j$

$k$可以用单调栈维护

由于$w(j)+..w(i)$的限制,可以的$j$的左边界是单调左移的

所以问题就变成了两端删除,一端插入,维护最值。

我想了一个$O(n)$的方法,而且是能解决两端插入的 (求问有没有别的方法)

就是左右各开一个栈维护最值,

左边删除插入就用左边的

右边删除插入就用右边的

如果左或右的栈删没了,就重构,把队列分成两半,左边分一半,右边分一半

每次重构的时间复杂度和下次删完所需的时间是一样的,所以复杂度是线性的。

卡常后拿了bzoj rank1

kczno1 Avatar