# NOI 4135:月度开销

#### 题目

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

#### 源码

``````//
//  4135.cpp
//  test
//
//  Created by bytedance on 2020/9/9.
//

#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/

#### 源码

``````//
//  2387.cpp
//  test
//
//  Created by bytedance on 2020/9/8.
//

#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/

#### 源码

``````//
//  1840.cpp
//  test
//
//  Created by bytedance on 2020/9/8.
//

#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/

#### 思路

dp[i]表示到i的最短路径，直接 dp 求解，i 从 1到n遍历求解dp[i],只会用到 dp[k] k < i

#### 源码

``````//
//  2355.cpp
//  test
//
//  Created by bytedance on 2020/9/7.
//

#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/

#### 源码

``````//
//  3247.cpp
//  test
//
//  Created by bytedance on 2020/9/7.
//
#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/

#### 源码

``````//
//  22.cpp
//  test
//
//  Created by bytedance on 2020/9/7.
//

#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/

#### 思路

https://blog.csdn.net/nnnnnnnnnnnny/article/details/51592665

#### 源码

``````//
//  193.cpp
//  test
//
//  Created by sgxm on 2020/8/3.
//

#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 = 2 时，第 0 层为钉子的上一层，初始小球

– 其上方钉子空则上两层对应小球数量直接累加
– 左侧钉子不空则左侧钉子上方小球数量一半累加到该位置
– 右侧同理

#### 源码

``````//
//  191.cpp
//  test
//
//  Created by bytedance on 2020/7/30.
//

#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]

– 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.
//

#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.
//

#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;
}

``````