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

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

题目

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

思路

素数筛给出4位素数,双向 BFS

源码

//
//  3126.cpp
//  test
//
//  Created by bytedance on 2020/9/8.
//  Copyright © 2020 bytedance. All rights reserved.
//
#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/

思路

我觉得可以用 狄杰斯特拉但是我写完 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;
}

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

思路

记录向前累计和,而后向前查找距离目标k的差值出现多少次,区间问题尽量转换为向前累计和的操作,而不是区间和的问题

源码

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

思路

前缀和而后dp同余即可,任意范围的子数组和(i,j] = sum[j]-sum[i],我们要确保他mod K = 0,根据同余定理可知要求 sum[i] mod K == sum[j] mod K 即 sum[i] 同余 sum[j], 所以使用 hashmap 记录余数的个数,后面直接累加

源码

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

1498. Number of Subsequences That Satisfy the Given Sum Condition 区间最大最小

题目

https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/submissions/
Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)
Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don’t satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 – 2 = 61).
Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 – 1) = 127

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6

思路

首先对数组进行排序
遍历以各元素开始的子序列,针对起始元素例如3,target为9时要求max最大为6,则找到最后一个小于等于6的位置,计算该长度内以3开头的子序列数量。
我们知道大小为3的数组的子集为 2^3-1,其中以第一个元素开头的子序列数量为 2^2,原理为第一位确定后,第二位可以要可以不要2种选择,第三位同理
注意 不要写r+=a%b,写 r = (r+a)%b

源码

class Solution {
public:
    long long res = 0;
    int pows[100005]={0};
    int numSubseq(vector<int>& nums, int k) {
        vector<int> re;
        sort(nums.begin(),nums.end());
        re = nums;
        reverse(re.begin(),re.end());

        pow2();
        for(int i = 0;i < nums.size();++i){
            if(nums[i] > k)break;
            int bd = k - nums[i];
            auto idx = lower_bound(re.begin(),re.end()-i,bd,greater<int>());   
            int len = (re.end()-idx)-i;
            cout <<len<<endl;
            if(len!=0)
            res = (res+pows[len-1])%(int)(1e9+7);
           // cout<<res<<endl;
        }
        return res;
    }
    void pow2(){
        pows[0]=1;
        for(int i = 1;i <= 1e5;++i){
            pows[i] = (2*pows[i-1])%(int)(1e9+7);
           // cout <<pows[i]<<endl;
        }
    }
};