木棒切割（二分+DP+滚动数组优化）

木棒切割

题意

有n个木棒，最多能切m下，接下来n行，给出n个木棒的长度，求出切割后最大长度的最小值，并求出有多少种切割方式，取模10007

n<=50000，0<=m<=min(n-1,1000)，1<=Li<=1000

思路

二分答案，low=0，high=sum[n]。

得到最小值ans。

接下来用DP，求出切割种数。

dp[i][j]表示前i个木棒切割j下的种数，设sum[i] 是前i个木棒的长度和 ，那么dp[i][j]=求和{ dp[k][j-1] }，满足条件：k<i && sum[i] - sum[k]<=ans 。

但是写完之后，我们发现，诶，这个时间复杂度……O(n^2 * m)，这不超时有鬼……

于是我们可以进行下面的优化：

1、空间

由于当前的dp[][j]只与dp[][j-1]有关，所以呢，我们可以用滚动数组，用dp[][now]代替dp[i][j]，用dp[][pre]代替dp[][j-1]，其中pre=now^1。

这样空间就小啦~

2、时间

这个好难理解啊我觉得……大概是太笨了哼唧

对于dp[i][now],其实是dp[Mink][pre]……dp[i-1][Mink]的和！！Mink 就是满足 k<i && sum[i]-sum[k]<=ans的最小的k。那么，对于从 1 到 n 枚举的 i ，相对应的 Mink 也一定是非递减的（因为 Sum[i] 是递增的）。我们记录下 dp[1][pre]…dp[i-1][pre] 的和 S ，Mink 初始设为 1，每次对于 i 将 Mink 向后推移，推移的同时将被舍弃的 p 对应的 dp[p][pre] 从 S 中减去。那么 dp[i][Now] 就是 S 的值。

时间复杂度O(nm)。

看！代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
const int MOD=10007;
int n,m,ans;
int a[50010],sum[50010];
int cnt=0;

int check(int mid) //看看有没有单比mid还大的 或者分割不了的
{
    int s=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        s+=a[i];
        if(s>mid) cnt++,s=a[i];
        if(cnt>m) return 0;
        if(a[i]>mid) return 0;
    }
    return 1;
}

void solve() //二分答案
{
    int l=0,r=sum[n];
    int mid;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1; 
        else l=mid+1;
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    sum[0]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    solve();
    int dp[50010][2]={0}; //滚动数组，前i块切j下的数量
    int now=0,pre=1,s,Mink; //mink 最小的满足k<j && s[i]-s[k]<=ans 的
    int res=0;
    for(int i=0;i<=m;i++) //切i下
    {
         s=0,Mink=1; 
         for(int j=1;j<=n;j++) //前j块
         {
             if(i==0) //如果一下不割
             {
                 if(sum[j]<=ans) dp[j][now]=1; //如果这块东西比要求的要小，就前j块割0下是1钟
                 else dp[j][now]=0;
             }
             else
             {
                 //s=sum{dp[k][j-1]} k<j&&s[i]-s[k]<=ans ，sum也相当于减去那些不满足条件的，
                 //因为这东西肯定单调非递减，所以一直找到最小的满足的k就好
                 while(Mink<j&&(sum[j]-sum[Mink])>ans) //找到最小的满足条件的k
                 {
                     s-=dp[Mink][pre]; //减去前mink块不符合条件的 切了i-1下的
                     s=(s+MOD)%MOD;
                     Mink++;
                 }
                 dp[j][now]=s%MOD; //别忘了取模
             }
             s=(s+dp[j][pre])%MOD; // s加上前j块割i-1下的
         }
         res=(res+dp[n][now])%MOD; //总数相当于总数加上n块割i下的
         now^=1; //滚动数组
         pre=now^1;
    }
    printf("%d %d\n",ans,res);
    return 0;
}

展开全文 >>

Buy a ticket (最短路SPFA)

Buy a ticket

题意

给你n个城市，m条无向路，每条路有vi的权值（>0），每个城市有ai的音乐会花费。

某人想去看音乐会，如果她在i城，他要去j城看演出，那么要花费的钱相当于来回的路费加上j城的演唱会的钱（也可以在自家看演出）。求的是，每个城市的人看一场音乐会的最少花费。

思路

很熟悉的思路，定义一个超级原点，将超级原点和每个城市连起来，路的权值设为该城市的音乐会花费，同时加其他的路的权值设为原来的两倍（来回的花费），那么从原点到每个城市的最小花费就是每个城市的人看音乐会的最小花费。（最短路）

开头用dijkstra写，看了一下复杂度肯定会T，o(n^2)的样子，然后交了一发。后来换用SPFA，队列啥的，还是T，然后看了一下过的人的代码，发现他们用优先队列优化，将花费大的放在了前面。

看！代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m;
struct  node{
    int to; //目的
    long long val; //花费
};
struct  Node{
    int to;   
    long long val;
    bool operator<(const Node k)const{
        return val>k.val; 
    }
};
vector<node>Next[200005]; //路
int vis[200005]={0}; //在Q里的情况
long long dis[200005];  //距离原点的最短距离
void SPFA()
{
    memset(dis,INF,sizeof(dis)); 
    priority_queue<Node> Q; //修改成优先队列，默认路径花费大的放前面，是的
    Node temp;
    temp.to=0;temp.val=0;
    Q.push(temp);  //把原点先入队
    vis[0]=1;dis[0]=0; //原点到原点当然是0啦  
    int now,a;
    while(!Q.empty())
    {
        temp=Q.top();
        Q.pop();
        now=temp.to;
        vis[now]=0;  //出队的点vis更新
        for(int i=0;i<Next[now].size();i++)  //遍历连接的城市
        {
            a=Next[now][i].to;  
            if(dis[a]>(dis[now]+Next[now][i].val)) //如果从原点到这个城市的距离比中间接这个城市跳转要远
            {
                dis[a]=dis[now]+Next[now][i].val;
                if(vis[a]==0) //如果a不在队列里
                {
                    vis[a]=1;temp.to=a;temp.val=dis[a];
                    Q.push(temp);
                }
            }
        }
    }
}

int main()
{
    int ori,to;
    node temp;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%lld",&ori,&to,&temp.val);
        temp.to=to;
        temp.val*=2;
        Next[ori].push_back(temp);
        temp.to=ori;
        Next[to].push_back(temp);
    }
    dis[0]=0;
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&dis[i+1]);
        temp.to=i+1;temp.val=dis[i+1];
        Next[0].push_back(temp);
    }
    SPFA();
    for(int i=1;i<=n-1;i++) printf("%lld ",dis[i]);
    printf("%lld\n",dis[n]);
    return 0;
}

展开全文 >>

Cashback (DP 区间最小值)

Cashback

题意

输入n和c。接下来给出长度为n的数组A。你可以将数组A划分成任意个子数组，假设其中一个子数组的长度为k，那么可以减去这个子数组内前k/c个（向下取整）小的数。要使划分后数组内的元素和最小，问最小的和为多少？

思路

预感到是DP，但是没有什么L用……

分析一下：如果其中一个子数组的长度k< c，那么这个数组就一个也不能减少；如果长度k=c，那么就刚好减少一个；如果长度在c< k< 2c之间，并没有任何贡献，还是只能少一个。也就是说，长度正好为c的数组是优秀的。那么长度为2c的数组呢？我们假设[0,c-1]内，最小的数字为min1，第二小的是min2，[c,2c-1]内，最小的数字为min3，那么，如果min2< min3，对于划分（2个长度为c）来说，消去的数字是min1+min3，而对于划分（1个长度为2c），消去的数字就是min1+min2，显然是两个c长度的划算。如果min2>=min3，对于划分成（2个长度为c）来说，消去的数字就是min1+min3，对于划分（一个长度为2c），消去的数字为min1+min3，两者是相等的。因此综上而言，将数组划分成长度为c的小数组更划算一些。

那么就用到dp了，dp[i]指 前i个数字的最小和。

对于一个数字a[i]来说，（i>c）dp[i] 要么是接受前一个数字的dp再加上自己的大小，要么就是重新进入一个长度是c的数组，起始index为i-c+1，dp[i]=dp[i-c] (前i-c的最小和）+sum[i]-sum[i-c] （这一段新的长度为c的数组的总和）- min{a[i-c+1], … , a[i] }（这一段长度是c的区间里的最小值），即：

dp[i] = min(dp[i-1]+a[i] , dp[i-c] + sum[i] - sum[i-c] - min{a[i-c+1], … , a[i] } )

对于区间最小值min，用一个multiset维护就好了。multiset里只放当前i为最后一个数字的c个数字。而multiset中的.begin() 会返回容器中最小的数的指针。如果去掉最前面一个放进来的数字呢？. erase( .find(a[i-c+1]))就好了。

看！代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int MAX=100010;
int n,c;
long long dp[MAX],a[MAX]; //dp[i]指前i个元素相加的最小和
long long sum[MAX]; //前i个元素和
multiset<long long>s; //s用来维护长度为c的区间内的最小值
int main()
{
	scanf("%d%d",&n,&c);
	sum[0]=0;
	for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
		dp[i]=sum[i]=sum[i-1]+a[i]; 
		//初始化dp值，显然长度不足c的dp值为前i个数之和，其他的默认初始值为前i个数之和
    }
    for(int i=1;i<c;i++)
        s.insert(a[i]);
    for(int i=c;i<=n;i++)
    {
        s.insert(a[i]);
        dp[i]=min(dp[i-1]+a[i],dp[i-c]+sum[i]-sum[i-c]-*s.begin());
        //前一个数加上自己的和，前一个c区间及之前的最小和加上这个新的c区间的总和，减去这个区间的最小值
        s.erase(s.find(a[i-c+1]));//删去下一步到了区间外的数字
    }
	printf("%lld",dp[n]);
	return 0;
}

展开全文 >>

二数(就没啥)

二数

题意

一个T<=100,一个n, 1<=n<=10^100000-1

二数：十进制下每一位都是偶数的数

求离n最近的二数

思路

用字符串存。

思考可以得到，对于n要么向小了变，要么向大了变。

遍历，对于遇到的第一个奇数k，

1、变小：k–

​ 然后其他所有的数字都变成‘8’

2、变大：k++

​ 然后其他所有数字变成’0‘

对于k==’9’的情况，直接取变小就好了，因为变小的代价肯定小于变大的代价。

然后比较谁更近的话，从高位开始一位一位的比较差值大小就好了……

输出的时候去掉前导0，就好了……

（代码依旧丑，其实很多地方可以改进，但我也懒得……）

看！代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t,len,flag;
    cin>>t;
    string s,sm,sb;
    while(t--)
    {
        cin>>s;
        len=s.size(),flag=0;
        if(len==1&&(s[0]=='1'||s[0]=='0')) { printf("0\n");continue; } //1 0特判一下
        sm=sb=s;
        for(int i=0;i<len;i++) //向下,
        {
            if((sm[i]-'0')%2==1)
            {
                if(flag==0) sm[i]--,flag=1; //第一个数变小
                else  //后面的数变大
                    if(sm[i]=='9') sm[i]='8'; //9变8
                    else sm[i]='8'; //其他数字变8
                continue;
            }
            if(flag==1)
                sm[i]='8'; //其他数字变8
        }
        flag=0;
        for(int i=0;i<len;i++) //向上
        {
            if((sb[i]-'0')%2==1)
            {
                if(sb[i]=='9'&&flag==0) //9同sm
                {
                    sb=sm;break;
                }
                if(flag==0)  sb[i]++,flag=1;//第一个变大
                else sb[i]='0';
                continue;
            }
            if(flag==1) sb[i]='0';
        }
        //比较

        flag=0;
        for(int i=0;i<len;i++)
        {
            if((s[i]-sm[i])<(sb[i]-s[i])) //前者小
            {
                flag=-1;break;
            }
            else if((s[i]-sm[i])>(sb[i]-s[i])) //后者小
            {
                flag=1;break;
            }
        }
        if(flag==1) s=sb;
        else s=sm;
        flag=0;
        for(int i=0;i<len;i++)
            if(s[i]!='0') { flag=1; printf("%c",s[i]); }
            else
                if(flag==0) continue;
                else printf("%c",s[i]);
        printf("\n");
    }
    return 0;
}

展开全文 >>

K序列（DP）

K序列

题目

给一个数组 a，长度为 n，若某个子序列中的和为 K 的倍数，那么这个序列被称为“K 序列”。对数组 a 求出最长的子序列的长度，满足这个序列是 K 序列。

输入一个n，k，接下来输入n个整数，表示A[1]~A[n] ,1<=n<=1e5,1<=a[i]<=1e9,1<=nK<=1e7。输出最长子序列的长度。

思路

又一道DP。

dp[i][j] : 表示前i个数中，对k取模余数为j的最长的子序列长度

dp[i][j] =max (dp[i-1][j],dp[i-1][(k-a[i]%k+j)%k]+1)

解释一下，指的是上一层（前i-1个数字）余数一样的，和上一层再加上a[i]（前i个数字）[余数]+1。

这里有个条件是要判断一下这个取模的余数是否已经存在了，不然就不能比较。

讲的不太清楚，看代码吧。

（这里用二维 vector存dp）

看！代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    vector<vector<int> >dp(n+5);
    for(int i=0;i<=n;i++)
        dp[i].resize(k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<k;j++)
        {
            if(a[i]%k==j) dp[i][j]=1;
            dp[i][j]=max(dp[i-1][j],dp[i][j]);
            if(dp[i-1][(j-a[i]%k+k)%k]!=0)
                dp[i][j]=max(dp[i][j],dp[i-1][(j-a[i]%k+k)%k]+1);
        }
    printf("%d\n",dp[n][0]);
    return 0;
}

展开全文 >>

1+2=3?(奇怪的斐波那契规律题)

1+2=3？

题目

输入一个T，接下来T行，每行一个N，输出满足 x异或2x== 3x 的第N个数字。

T<=100,N<=1e12

思路

打了表，整数数列百科全书中找到符合规律的数列，观察二进制形式后发现：

规律

斐波那契数列：

1 2 3 5 8 13 21 34 55 ……

题中若N=60，则60= 55 + 5 （第9项+第4项）

则第60个满足条件的数为：1(9)00001(4)000 = 264 (4、9号位数为1，其他都是0)

由于1e12小于斐波那契的第59项，故开一个59大的数组，里面存斐波那契数，然后对于每一个N寻找最少的组成它的斐波那契数，找到他是第x项，那么ans+2^x即可。

（问题是我的代码怎么这么丑= =）

看！代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    vector<long long>fei; //算斐波那契 1 2 3 5这样的
    fei.push_back(1);fei.push_back(2);
    while(fei[fei.size()-1]<(1e12+5)) fei.push_back(fei[fei.size()-1]+fei[fei.size()-2]);
 
    while(t--)
    {
        long long n,temp;
        scanf("%lld",&n);
        temp=n;
        long long weishu[100],x=1,ans=0;
        for(int i=0;i<60;i++)
            weishu[i]=x,x*=2; //计算2的i次
      
        for(int i=57;i>=0;i--)
            if(temp>=fei[i]) //找能组成他的斐波那契数，直接算
                temp-=fei[i],ans+=weishu[i];
      
        printf("%lld\n",ans);
    }
    return 0;
}

展开全文 >>

归途

如果拉杆箱会飞

回家，带着我的拉杆箱。

拉杆箱好沉啊，下着雨，要撑伞。红色的卫衣，薄荷绿的伞。


城隍百味

城隍庙地铁站

食

和小可爱在一起。

“我要吃三色杯！”

“上口爱！”

“给我尝一口！”

“好冷呐哥！”

“我要吃炸鱿鱼！”

“好脆呀！”

“别扯呀别扯！”

“我没我咬不动！”

“看你满嘴！”

“哼！”

“老板来三根肉串！”

“还吃……”

“臭豆腐要吗！”

“……要！”

“来一口！”

“哇呜是香菜！！TOT “

“很香！”

“哦这个味道！”

“这才是真正的臭豆腐！”

“霉的很完美！”

“……”


城隍庙臭豆腐

遇

老地方，又遇见了一个乞讨的老爷爷，但是好像没有人愿意给他钱。

以前也遇到过一次，等饮料的时候，他伸出破烂的碗，看着我，上下颠一颠，几块钱硬币在碗里面当啷响。

我犹豫着响掏出一点碎钱，被小可爱制止了。

貌似有些残酷的冲老爷爷摆摆手，然后拿了饮料转身离开，给他一个背影。

后来我们往下走，在风很大的路口遇见了一个卖报纸的老婆婆，忘记了多少钱一份，两块还是三块？只记得小可爱二话不说就买了一份。报纸还是过期的，早就不知道哪儿去了。

记得他当时这样说：

“如果我们刚才给了那个乞丐钱，那对这个辛苦卖报的老婆婆是不是不公平？”


归途

不断更新着的一切

高楼 大厦

人

萬達新樓

清明时节雨 纷纷

潮湿的

展开全文 >>

CF 957C Three-level Laser (二分)

Three-level Laser

题意

输入一个n，m，n代表接下来有n个数字（从小到大），

接下来从n个数字中选3个数字i，j，k（i<j<k），

使得k-j/k-i 最大，且（k-i）<=m。(n<1e5)

思路

开头直接写，j=1开始遍历，要让值最大，i=j-1,（必定），k为可允许内最大的值。

用for找k，会T，于是改用二分，输出用.15f（精度限制，double到.6）。

看！代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 7;
int a[N];
int main()
{
    int n,U;
    scanf("%d%d",&n,&U);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    double res=-1.0;
    for(int i=1;i<=n-2;i++) 
    {
        int t1=a[i],t2=a[i+1],up=U+t1;
        int k=upper_bound(a+1,a+1+n,up)-a-1;
        if(k<i+2) continue;
        res=max(res,(a[k]-t2*1.0)/(a[k]-t1));
    }
    printf("%.15f\n",res);
    return 0;
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

小可爱的小可爱，<br/>拖肥的娘亲，<br/>划水的ACMer，<br/>努力中的小菜鸡，<br/>想要自信和一往无前的勇气。