NOI 4135:月度开销

题目

http://bailian.openjudge.cn/practice/4135/

思路

开始使用的 dp,但是后来发现 Memory 超了,一看确实 m,n 最大到10w,开个二维数组肯定超了
这题使用二分搜索,使用 isTrue 检验是否合法,合法就将右边界变成mid,否则 left = mid+1

源码

//
//  4135.cpp
//  test
//
//  Created by bytedance on 2020/9/9.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;


vector<int> cost;
int m,n;
bool isTrue(int target){
    int sum = 0;
    int cnt = 1;
    for(int i = 0;i < cost.size();++i){
        if(cost[i] > target)return false;
        if(sum+cost[i]>target){
            sum=cost[i];cnt++;
        }else{
            sum+=cost[i];
        }
        if(cnt>m)return false;
    }
    return true;
}
int main(){

    cin >> n >>m;
    int left=0,right=0,mid;
    int t = n;
    while(t--){
        int a;
        cin >> a;
        left = max(left,a);
        right += a;
        cost.push_back(a);
    }
    while(left<right){
        mid = left+(right-left)/2;
       // cout << left<<" "<<right<<endl;
        if(isTrue(mid)){
           // cout << mid<<" t"<<endl;
            right = mid;
        }else{
            left = mid + 1;
            //cout << mid<<" f"<<endl;
        }
    }
  //  cout << isTrue(1900);
    cout<<left;

    return 0;
}

NOI 2387:Til the Cows Come Home

题目

http://bailian.openjudge.cn/practice/2387/

思路

狄杰斯特拉,优先级队列和 d 数组保持同步即可,使用邻接表的话,Edge 中的 from 字段可以省略

源码

//
//  2387.cpp
//  test
//
//  Created by bytedance on 2020/9/8.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#define inf 99999999
using namespace std;
struct Edge{
    int from,to,dis;
    Edge(int from,int to,int dis):from(from),to(to),dis(dis){};
    bool operator < (const Edge &e) const{
        return e.dis<dis;
    }
};

int n, t;

int main(){
    cin >> t >> n;
    vector<vector<Edge>> edges(n+1,vector<Edge>());
    priority_queue<Edge> q;
    vector<int> d(n+1,inf);
    vector<bool> done(n+1);
    while(t--){
        int a,b,c;
        cin >> a>>b>>c;
        Edge e(a,b,c);
        edges[a].push_back(e);
        Edge e2(b,a,c);
        edges[b].push_back(e2);
    }
    //边读入ok,初始化距离数组
    q.push(Edge(1,1,0));
    d[1]=0;
    while(!q.empty()){
        int node  = q.top().to;q.pop();
        if(done[node])continue;
        done[node] = true;
        for(int i = 0;i < edges[node].size();++i){
            Edge e = edges[node][i];
            if(d[e.to]>d[node]+e.dis){
                d[e.to] = d[node]+e.dis;
                q.push(Edge(1,e.to,d[e.to]));
            }
        }
    }
    cout << d[n];
    return 0;
}

NOI 1840:Eqs

题目

http://bailian.openjudge.cn/practice/1840/

思路

把等式右移三项,遍历左边的两项可能的取值用 map 存下来,遍历右边值而后从map中取出对应个数相加

源码

//
//  1840.cpp
//  test
//
//  Created by bytedance on 2020/9/8.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <map>
#include <math.h>
using namespace std;

int main(){
    int cnt = 0;
    map<int,int> m;
    int a1,a2,a3,a4,a5;
    cin >> a1>>a2>>a3>>a4>>a5;
    for(int i = -50;i <= 50;++i){
        int res1 = i*i*i*a1;
        for(int j = -50;j <= 50;++j){
            int res = res1+j*j*j*a2;
            if(i==0||j==0)continue;
            if(m.find(res)!=m.end()){
                m[res]++;
            }else{
                m[res] = 1;
            }

        }
    }
    //    for(map<int,int>::iterator it = m.begin();it!=m.end();++it){
    //        cout <<it->first<<" "<<it->second<<endl;
    //    }

    for(int i = -50;i <= 50;++i){
        for(int j = -50;j <=50;++j){
            for(int k = -50;k <= 50;++k){
                if(i==0||j==0||k==0)continue;
                int res = i*i*i*a3+j*j*j*a4+k*k*k*a5;
                res = -res;
                if(m.find(res)!=m.end()){
                    cnt+=m[res];
                }
            }
        }
    }
    cout << cnt;
    return 0;
}

NOI 2355:Railway tickets dp

题目

http://bailian.openjudge.cn/practice/2355/

思路

我觉得可以用 狄杰斯特拉但是我写完 wa 了不知道为啥
dp[i]表示到i的最短路径,直接 dp 求解,i 从 1到n遍历求解dp[i],只会用到 dp[k] k < i

源码

//
//  2355.cpp
//  test
//
//  Created by bytedance on 2020/9/7.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <iostream>
#include <vector>
#define INF 999999999999
using namespace std;

long c1,c2,c3,l1,l2,l3;
int n,s,e;
long pre[10005]={0};
int main(){
    cin >>l1>>l2>>l3;
    cin >> c1>>c2>>c3;
    cin >> n;
    cin >>s>>e;
    if(s>e)swap(s,e);
    for(int i = 2;i <= n;++i){
        cin >> pre[i];
    }
    vector<long>d(n+1,INF);
    d[s] = 0;
    for(int i = s+1;i <= n;++i){
        for(int j = i-1;j>=s;--j){
            long dis = pre[i]-pre[j];
            if(dis<=l1)d[i]=min(d[i],d[j]+c1);
            else if(dis<=l2)d[i] = min(d[i],d[j]+c2);
            else if(dis<=l3)d[i] = min(d[i],d[j]+c3);
            else break;
        }
    }
    cout<<d[e];
    return 0;
}

NOI 3247:回文素数

题目

http://bailian.openjudge.cn/practice/3247/

思路

判断素数直接遍历根号因子,本题需要生成n位的回文数字同时需要知道以下性质
偶数位的回文数字都可以被11整除,只考虑基数位的回文数字,同时我采用的构造方法是遍历对称轴前方的数字,而后中间插入0-9,但实际上可以直接带着对称轴数字直接便利,只不过在生成回文数的时候提前除10

源码

//
//  3247.cpp
//  test
//
//  Created by bytedance on 2020/9/7.
//  Copyright © 2020 bytedance. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

bool isP(int n){
    int sq = sqrt(n)+1;
    for(int i = 2;i <= sq;++i){
        if(n%i==0)return false;
    }
    return true;
}
int main(){
    int n;
    cin >> n;
    if(n == 1){
        cout <<"4\n2 3 5 7";
    }else if(n==2)cout<<"1\n11";
    else if(n==4||n==6||n==8) cout<<"0";
    else{
        int len = n/2;
        int mn = pow(10,len-1);
        int mx = pow(10,len)-1;
        int cnt;
        vector<int> res;
        for(int i = mn;i <= mx;++i){
            vector<int> hui(10,i);
            int temp = i;
            for(int i = 0;i < 10;++i){
                hui[i]=hui[i]*10+i;

            }
            while(temp!=0){
                for(int i = 0;i < 10;++i){
                    hui[i]=hui[i]*10+temp%10;
                }
                temp/=10;
            }
//            cout<<i<<endl;
            for(int i = 0;i < 10;++i){
                if(isP(hui[i]))res.push_back(hui[i]);
//                cout << hui[i]<<" ";
            }
        }
        cout << res.size()<<endl;
                  for(int i = 0;i < res.size();++i){
                      cout <<res[i]<<" ";
                  }
    }
    return 0;
}

NOI 22:因子分解 唯一分解定理

题目

http://noi.openjudge.cn/ch0113/22/

思路

素数筛,p开始筛选掉所有的2p,3p,4p,而后使用唯一分解定理

源码

//
//  22.cpp
//  test
//
//  Created by bytedance on 2020/9/7.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;


int ps[1000];
int main(){
    int n;
    cin >> n;
    memset(ps,0,sizeof(ps));
    for(int i = 2;i < 1000;++i){
        for(int j = i*2;j<1000;j+=i){
            ps[j] = 1;
        }
    }
    string res = "";
    for(int i = 2;i<1000;++i){
        if(ps[i]==1||n==1)continue;
        int cnt = 0;
        while(n%i==0){
            n/=i;
            cnt++;
        }
        if(cnt!=0){
            if(cnt==1)res=res+"*"+to_string(i);
            else res=res+"*"+to_string(i)+"^"+to_string(cnt);
        }
    }
    res.erase(res.begin());
    cout <<res;
    return 0;
}

4.5算法之动态规划 193:棋盘分割 区间dp

题目

http://noi.openjudge.cn/ch0405/193/
描述
将一个8*8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。
均方差,其中平均值,xi为第i块矩形棋盘的总分。
请编程对给出的棋盘及n,求出O’的最小值。
输入
第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
输出
仅一个数,为O’(四舍五入精确到小数点后三位)。

思路

区间 dp, dp[k][x1][y1][x2][y2] 表示将,(x1,y1):(x2,y2)区间内的矩形分成 k 块,均方误差的最小值
该问题是一个一对多问题,即两个子矩形的最优解拼接为一个大矩形后不一定为最优解,但是一个大矩形的最优解一定可以由两个子矩形的解拼接而成,所以针对子矩形遍历其横向划分和纵向划分。

其中要最小化平方和即可,具体推导过程参考该博客
https://blog.csdn.net/nnnnnnnnnnnny/article/details/51592665

源码

//
//  193.cpp
//  test
//
//  Created by sgxm on 2020/8/3.
//  Copyright © 2020 sgxm. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <memory.h>
#include <iomanip>
#include <string.h>
#define maxn 15
using namespace std;

int dp[15][8][8][8][8];
int s[8][8][8][8];
int tb[8][8];
int n;
int calSum(int x1,int y1,int x2,int y2){
    int sum = 0;
    for(int i = x1;i<=x2;++i){
        for(int j = y1;j <= y2;++j){
            sum+=tb[i][j];
        }
    }
    return sum*sum;
}
int calDp(int k,int x1,int y1,int x2,int y2){
    int MIN = 99999999;

    if(dp[k][x1][y1][x2][y2]!=-1){
        return dp[k][x1][y1][x2][y2];
    }
    if(k == 1){
        return dp[k][x1][y1][x2][y2]=s[x1][y1][x2][y2];
    }
    dp[k][x1][y1][x2][y2]=MIN;
    //横向划分
    for(int x = x1;x<x2;++x){
        int t1 = calDp(k-1, x1, y1, x, y2);
        int t2 = calDp(k-1,x+1,y1,x2,y2);
        int t = min(t1+s[x+1][y1][x2][y2],t2+s[x1][y1][x][y2]);
        MIN = min(MIN,t);
    }
    for(int y = y1;y<y2;++y){
        int t1 = calDp(k-1,x1,y1,x2,y);
        int t2 = calDp(k-1,x1,y+1, x2, y2);
        int t = min(t1+s[x1][y+1][x2][y2],t2+s[x1][y1][x2][y]);
        MIN = min(MIN,t);
    }
    MIN=min(MIN,dp[k][x1][y1][x2][y2]);
    //cout<<k<< " "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" = "<<MIN<<endl;
    return  dp[k][x1][y1][x2][y2]=MIN;

}
int main(){
    cin >> n;
    for(int i = 0;i < 8;++i){
        for(int j = 0;j < 8;++j){
            cin >> tb[i][j];
        }
    }
    memset(dp, -1,sizeof(dp));
    //init Sum
    for(int x1 = 0;x1 < 8;++x1){
        for(int y1 = 0;y1 < 8;++y1){
            for(int x2 = x1;x2<8;++x2){
                for(int y2 = y1;y2<8;++y2){
                    s[x1][y1][x2][y2]=calSum(x1,y1,x2,y2);
                }
            }
        }
    }
    //calDp(2,5,5,6,7);
    int sum2 = calDp(n, 0, 0, 7, 7);
    double res = 1.0*n*calDp(n, 0, 0, 7, 7)-s[0][0][7][7];
    cout<<setiosflags(ios::fixed)<<setprecision(3)<<sqrt(res/(n*n))<<endl;
    return 0;
}

4.5算法之动态规划 191:钉子和小球 概率

题目

http://noi.openjudge.cn/ch0405/191/
描述
有一个三角形木板,竖直立放,上面钉着n(n+1)/2颗钉子,还有(n+1)个格子(当n=5时如图1)。每颗钉子和周围的钉子的距离都等于d,每个格子的宽度也都等于d,且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落,小球每碰到一个钉子都可能落向左边或右边(概率各1/2),且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi=,其中i为格子的编号,从左至右依次为0,1,…,n。
现在的问题是计算拔掉某些钉子后,小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。

输入
第1行为整数n(2 <= n <= 50)和m(0 <= m <= n)。以下n行依次为木板上从上至下n行钉子的信息,每行中’*’表示钉子还在,’.’表示钉子被拔去,注意在这n行中空格符可能出现在任何位置。
输出
仅一行,是一个既约分数(0写成0/1),为小球落在编号为m的格子中的概pm。既约分数的定义:A/B是既约分数,当且仅当A、B为正整数且A和B没有大于1的公因子。

思路

n = 2 时,第 0 层为钉子的上一层,初始小球 2^n
从第 0 层开始,第一个钉子编号为 1,第一个坑位编号为 0,对于每一个坑位考虑
– 其上方钉子空则上两层对应小球数量直接累加
– 左侧钉子不空则左侧钉子上方小球数量一半累加到该位置
– 右侧同理

最后辗转相除法求最大公约数,约分

源码

//
//  191.cpp
//  test
//
//  Created by bytedance on 2020/7/30.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
vector<vector<long long>> dp;
vector<vector<char>> cnt;
long long gcd(long long x,long long y){
    return y?gcd(y,x%y):x;
}
int main(){
    long long n,m;
    cin >> n >> m;
    cnt.resize(n+1,vector<char>(n+1));
    dp.resize(n+1,vector<long long>(n+1,0));
    for(long long i = 1;i <= n; ++i){
        for(long long j = 1;j <= i; ++j){
            char c;
            cin >> c;
            cnt[i][j]=c;
        }
    }
    //
    dp[0][0] = pow(2,n);
    for(long long i = 1;i <= n;++i){
        for(long long j = 0;j <= i; ++j){
            //处理左右边界
            if(j == 0){
                if(cnt[i][j+1]=='*'){
                    dp[i][j]=dp[i-1][j]/2;
                }else{
                    dp[i][j]=0;
                }
            }else if(j == i){
                if(cnt[i][j]=='*'){
                    dp[i][j]=dp[i-1][j-1]/2;
                }else{
                    dp[i][j]=0;
                }
            }else{
                if(cnt[i-1][j]=='.'){
                    dp[i][j]+=dp[i-2][j-1];
                }
                if(cnt[i][j]=='*'){
                    dp[i][j]+=dp[i-1][j-1]/2;
                }
                if(cnt[i][j+1]=='*'){
                    dp[i][j]+=dp[i-1][j]/2;
                }
            }
        }
    }

    long long a = dp[n][m],b = dp[0][0];
    long long gc=gcd(b,a);
    a/=gc;
    b/=gc;
    cout << a<<"/"<<b;

    return 0;
}

4.5算法之动态规划 1413:Mondriaan’s Dream

http://noi.openjudge.cn/ch0405/1413/

题目

描述
Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his ‘toilet series’ (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.

Expert as he was in this material, he saw at a glance that he’ll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won’t turn into a nightmare!
输入
The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.
输出
For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

思路

基于一下两个思路
0表示下一层对应位置必须为1,即竖向砖块的第一块砖,1表示下一层可为0可为1,无影响
dp思路
dp[i][status] = sum(dp[i-1][k]) k in [0,2^w-1]
其中 sum 求和时要对 status 和 k 进行校验
– status|k == 2^w-1,及保证竖向不会出现连续的两个0这种非法情况
– status&k 要保证所有出现的 1 都为连续的2 个 1,否则意味着出现了单格的错位,010的下层必定为101,则在最低端无法满足全1的要求与操作取到的1为横放的块(1有两种含义),只要保证横放的块都符合规则即可。

源码

//
//  1413.cpp
//  test
//
//  Created by bytedance on 2020/7/29.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <vector>
#include <iostream>

using namespace std;
long long w,h;

//bool check(long long x){
//
//}
vector<vector<long long>> dp;
bool check(long long x){
    for(long long i = 0;i < w;++i){
        if((x&(1<<i))!=0){
            if((x&(1<<(i+1)))!=0){
                ++i;
            }else{
                return false;
            }
        }
    }
    return true;
}
int main(){

    while(cin >> h >> w){
        if(h==0&&w==0)break;
        if(h*w%2==1){
            cout<<0<<endl;
            continue;
        }
        long long statusNum = 1<<w;
        dp.clear();
        dp.resize(h+1,vector<long long>(1<<w,0));
        for(long long i = 0;i < statusNum;++i){
            if(check(i))
                dp[1][i]=1;
        }
        for(long long i = 2;i <= h;++i){
            for(long long now = 0;now < statusNum; ++now){
                for(long long up = 0;up < statusNum;++up){
                    if((now|up)==statusNum-1){
                        if(check(now&up))
                            dp[i][now]+=dp[i-1][up];
                    }
                }
            }
        }
        cout << dp[h][statusNum-1]<<endl;
    }
    return 0;
}

4.5算法之动态规划 1249:Humble Numbers 优先级队列

http://noi.openjudge.cn/ch0405/1249/

思路

取出队头,遍历乘四放入队列,即可保证当前队头为最小值

源码

//
//  1249.cpp
//  test
//
//  Created by bytedance on 2020/7/28.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int m[4]={2,3,5,7};
priority_queue<long long,vector<long long>,greater<long long>> q;
int main(){
    q.push(1);
    int idx = 0;
    int i;
    long long pre = 0;
    while(cin >> i){
        if(i == 0){
            break;
        }

        while(idx<i){
            while(q.top()==pre){
                q.pop();
            }
            pre = q.top();
            idx++;
            for(int i = 0;i < 4;++i){
                q.push(pre*m[i]);
            }
        }
        if(i%100>=10&&i%100<=20)
            printf("The %dth humble number is %lld.\n",i,pre);
        else if(i%10==1)
            printf("The %dst humble number is %lld.\n",i,pre);
        else if(i%10==2)
            printf("The %dnd humble number is %lld.\n",i,pre);
        else if(i%10==3)
            printf("The %drd humble number is %lld.\n",i,pre);
        else
            printf("The %dth humble number is %lld.\n",i,pre);
    }
    return 0;
}