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

# POJ 3126.Prime Path 素数筛+双向BFS

#### 题目

http://poj.org/problem?id=3126

#### 源码

``````//
//  3126.cpp
//  test
//
//  Created by bytedance on 2020/9/8.
//
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
bool pre[10000]={false};
vector<string> p;
int main(){
int time;
cin >> time;

string s,e;
for(int i = 2;i <= 9999;++i){
for(int j = i*2;j<=9999;j+=i)pre[j]=true;
}
for(int i = 1000;i<=9999;++i){
if(!pre[i])p.push_back(to_string(i));
}
while(time--){
cin >> s>>e;
//素数集合构造完毕
int idx = 0;
queue<string> q[2];
map<string,bool> vis[2];
q[0].push(s);
q[1].push(e);
vis[0][s]=true;
vis[1][e]=true;
int cnt = 0;
bool f = true;
while(!q[0].empty()&&!q[1].empty()&&f){
idx=idx^1;
int sz = q[idx].size();
while(sz--&&f){
string crt = q[idx].front();
q[idx].pop();
if(vis[idx^1][crt]==true){ cout<< cnt; f=false;}
for(int i = 0;i < 4&&f;++i){
char c = crt[i];
for(int j = '0';j <='9'&&f;++j){
crt[i] = j;
if(j==c||vis[idx][crt]||find(p.begin(),p.end(),crt)==p.end())continue;
q[idx].push(crt);
vis[idx][crt]=true;
}
crt[i] = c;
}
}
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;
}

``````

# leetcode 560. Subarray Sum Equals K

#### 题目

https://leetcode.com/problems/subarray-sum-equals-k/
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Constraints:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

#### 源码

``````class Solution {
public:
unordered_map<int,int> m;
int sum[20005];
int res = 0;
int subarraySum(vector<int>& nums, int k) {
sum[0] = 0;
m[0] = 1;
for(int i = 1;i <= nums.size();++i){
int s = sum[i-1]+nums[i-1];
sum[i] = s;
int re = s-k;
if(m.find(re)!=m.end()){
res+=m[re];
}
if(m.find(s)==m.end()){
m[s]=1;
}else{
m[s]++;
}
}
return res;
}
};
``````

# leetcode 974. Subarray Sums Divisible by K 前缀和+同余定理

#### 题目

https://leetcode.com/problems/subarray-sums-divisible-by-k/
Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

#### 源码

``````class Solution {
public:
int sum[30005];
int res = 0;
map<int,int> m;
int subarraysDivByK(vector<int>& A, int K) {
if(A.size()==0)return res;
sum[0] = 0;
m[0] = 1;
for(int i = 1;i <= A.size();++i){
sum[i] = sum[i-1]+A[i-1];
int yu = sum[i]%K;
if(m.count(yu)==0){
m[yu] = 1;
}else{
m[yu]++;
}
res+=(m[yu]-1);
}
return res;
}
};
``````