头像

Lemon_kk




离线:1天前



class Solution {
public:
    vector<bool> st;
    vector<int> path;
    int n;

    bool dfs(int u){
        if(u >= 2 * n - 1) return true;
        if(path[u]) return dfs(u + 1);
        for(int i = n;i > 1;i -- ){
            if(st[i] || i + u >= 2 * n - 1 || path[u + i]) continue;
            st[i] = true;
            path[u] = path[u + i] = i;
            if(dfs(u + 1)) return true;
            st[i] = false;
            path[u] = path[u + i] = 0;
        }
        if(!st[1]){
            st[1] = true;
            path[u] = 1;
            if(dfs(u + 1)) return true;
            st[1] = false;
            path[u] = 0;
        }

        return false;
    }
    vector<int> constructDistancedSequence(int _n) {
        n = _n;
        st.resize(n + 1, false);
        path.resize(n * 2 - 1, 0);
        dfs(0);
        return path;
    }
};



贪心找最大 可以过小样例

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int res = 0;
        if(x < y){
            swap(x, y);
            for(auto &c : s)
                if(c == 'a') c = 'b';
                else if(c == 'b') c = 'a';
        }
        string last = "";
        while(true){
            for(int i = 0;i + 1 < s.size();i ++ ){
                if(s[i] != 'a' && s[i] != 'b') continue;
                int j = i + 1;
                while(j < s.size() && s[j] == 'A') j ++ ;
                if(s[i] == 'a' && s[j] == 'b'){
                    res += x;
                    s[i] = 'A';
                    s[j] = 'A';
                }
            }
            if(last == s) break;
            last = s;
        }

        while(true){
            for(int i = 0;i + 1 < s.size();i ++ ){
                if(s[i] != 'a' && s[i] != 'b') continue;
                int j = i + 1;
                while(j < s.size() && s[j] == 'A') j ++ ;
                if(s[i] == 'b' && s[j] == 'a'){
                    res += y;
                    s[i] = 'A';
                    s[j] = 'A';
                }
            }
            if(last == s) break;
            last = s;
        }

        return res;
    }
};

正解

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int res = 0;
        if(x < y){
            swap(x, y);
            for(auto &c : s)
                if(c == 'a') c = 'b';
                else if(c == 'b') c = 'a';
        }
        for(int i = 0;i < s.size();i ++ ){
            if(s[i] != 'a' && s[i] != 'b') continue;
            int j = i;
            while(j < s.size() && (s[j] == 'a' || s[j] == 'b')) j ++ ;
            int a = 0, b = 0, c = 0;
            for(int k = j - 1, t = 0;k >= i;k -- ){
                if(s[k] == 'a'){
                    a ++ ;
                    if(t){
                        t -- ;
                        c ++ ;
                    }
                }else if(s[k] == 'b'){
                    b ++ ;
                    t ++ ;
                }
            }
            res += c * x + y * (min(a, b) - c);
            i = j - 1;
        }

        return res;
    }
};



class Solution {
public:
    int totalMoney(int n) {
        int sum = 0, last = 0, now = 0;
        for(int i = 1;i <= n;i ++ ){
            if(i % 7 == 1) last ++ , now = last;
            sum += now ++ ;
        }
        return sum;
    }
};



一维

选取中位数求和

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main(){
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++ ) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    int ans = 0;
    for(int i = 1;i <= n;i ++ ){
        ans += abs(a[i] - a[1 + n / 2]);
    }

    cout << ans << endl;
    return 0;
}

拓展:二维的欧式距离最短

题目: 星星还是树

第一种:三分套三分

讲解链接:Ternary Search


根据dist = sum(sqrt(dx * dx + dy * dy));
dist 对 x 的二阶偏导大于零 所以是凹函数
三分极小值即可
当 x 固定 dist 对于 y 也是一个凹函数

#include <cmath>
#include <cstdio>
#include <cstring>

#define INF double(1e10)

using namespace std;

const int N = 150;

int n, x[N], y[N];
double dist = INF;
double eps = 1e-3;
double lx, rx, ly, ry;

double get_dist(double xx, double yy){
    double res = 0;
    for (int i = 1; i <= n; ++i) {
        double dx = x[i] - xx, dy = y[i] - yy;
        res += sqrt(dx * dx + dy * dy);
    }
    return res;
}

double f(double x){
    ly = 0, ry = 10010;
    while(ry - ly > eps){
        double lmid = (ly + ry) / 2;
        double rmid = (lmid + ry) / 2;
        if(get_dist(x, lmid) < get_dist(x, rmid)) ry = rmid;
        else ly = lmid;
    }
    dist = min(dist, get_dist(x, ly));
    return ly;
}

int main() {

    scanf("%d", &n);
    for (int i = 1;i <= n;i ++ ) scanf("%d%d", &x[i], &y[i]);

    lx = 0, rx = 10010;
    while(rx - lx > eps){
        double lmid = (lx + rx) / 2;
        double rmid = (lmid + rx) / 2;
        if(get_dist(lmid, f(lmid)) < get_dist(rmid, f(rmid))) rx = rmid;
        else lx = lmid;
    }

    printf("%.lf\n", dist);

    return 0;
}

第二种:模拟退火

讲解链接:模拟退火

#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>

using namespace std;

const int N = 150;

int n, x[N], y[N];
double ansx, ansy, dist;

double Rand() { return (double)rand() / RAND_MAX; }
double get_dist(double xx, double yy){
    double res = 0;
    for (int i = 1; i <= n; ++i) {
        double dx = x[i] - xx, dy = y[i] - yy;
        res += sqrt(dx * dx + dy * dy);
    }
    // if(res < dist) dist = res, ansx = xx, ansy = yy;
    return res;
}

void simulateAnneal(){
    double T = 1e5; // 初始温度要足够大
    double eps = 1e-6; // 结束温度足够低
    double down = 0.99; // 降温时间足够长
    double nowx = ansx, nowy = ansy;
    while(T > eps){
        // 随机 计算数值
        double nxtx = nowx + T * (Rand() * 2 - 1);
        double nxty = nowy + T * (Rand() * 2 - 1);
        double delta = get_dist(nxtx, nxty) - get_dist(nowx, nowy);
        if(delta < 0) nowx = nxtx, nowy = nxty, dist = dist + delta;
        T *= down;
    }

    ansx = nowx, ansy = nowy;
    for (int i = 1; i <= 1000; ++i) {
        double nxtx = ansx + T * (Rand() * 2 - 1);
        double nxty = ansy + T * (Rand() * 2 - 1);
        double z = get_dist(nxtx, nxty);
        if(z < dist) dist = z, ansx = nxtx, ansy = nxty;
    }
}
int main() {

    srand(time(0));
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &x[i], &y[i]);
        ansx += x[i], ansy += y[i];
    }
    // 初始化 初解
    ansx /= n, ansy /= n, dist = get_dist(ansx, ansy);
    // 模拟退火
    simulateAnneal();
    // printf("%.3lf %.3lf\n", ansx, ansy);
    printf("%.lf\n", get_dist(ansx, ansy));

    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main(){
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++ ) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    int ans = 0;
    for(int i = 1;i <= n;i ++ ){
        ans += abs(a[i] - a[1 + n / 2]);
    }

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1382. 比特串

Lemon_kk
18天前
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 45;

LL n, L, I;
LL c[N][N];
LL f[N][N];

int main(){

    cin >> n >> L >> I;
    for(int i = 0;i < N;i ++ )
        for(int j = 0;j <= i;j ++ )
            if(!j) c[i][j] = 1;
            else c[i][j] = c[i - 1][j - 1] + c[i - 1][j];

    for(int i = 0;i < N;i ++ )
        for(int j = 0;j < N;j ++ )
            for(int k = 0;k <= j;k ++ )
                f[i][j] += c[i][k];

    LL sum = 0;
    for(int i = 1;i <= n;i ++ ){
        LL x = f[n - i][L - sum];
        if(x >= I){
            cout << 0;
        }else{
            I -= x;
            cout << 1;
            sum ++ ;
        }
    }
    return 0;
}


活动打卡代码 AcWing 1379. 联系

Lemon_kk
29天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010, M = 1 << 14;

int A, B, n, m;
int cnt[M];
struct Data{
    int k, val;
    bool operator<(const Data& t)const{
        if(k != t.k) return k > t.k;
        return val < t.val;
    }
    string get_string(){
        string res;
        for(int i = val;i;i >>= 1) res += (i & 1) + '0';
        res.pop_back();
        reverse(res.begin(), res.end());
        return res;
    }
}q[N];

int main(){
    string line, str;
    cin >> A >> B >> m;
    while(cin >> line) str += line;
    n = str.size();

    for(int i = A;i <= B;i ++ ){
        for(int j = 0, num = 0;j < n;j ++ ){
            num = num * 2 + str[j] - '0';
            if(j - i >= 0) num -= str[j - i] - '0' << i;
            if(j + 1 >= i) cnt[num + (1 << i)] ++ ;
        }
    }

    for(int i = 0;i < M;i ++ )
        q[i] = {cnt[i], i};

    sort(q, q + M);

    for(int i = 0, cnt = 0;i < M && cnt < m;cnt ++ ){
        if(!q[i].k) break;
        int j = i;
        while(j < M && q[j].k == q[i].k) j ++ ;
        cout << q[i].k << endl;
        for(int a = i, b = 1;a < j;a ++ , b ++ ){
            cout << q[a].get_string();
            if(b % 6 == 0) cout << endl;
            else cout << ' ';
        }
        if((j - i) % 6) cout << endl;
        i = j;
    }

    return 0;
}


活动打卡代码 AcWing 1380. 邮票

Lemon_kk
29天前
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100, K = 210, M = 2000010;

int k, n, m;
int f[M];

int main(){
    scanf("%d%d", &k, &n);
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    m = M - 1;
    for(int i = 1;i <= n;i ++ ){
        int x; cin >> x;
        for(int j = x;j <= m;j ++ )
            f[j] = min(f[j], f[j - x] + 1);
    }

    int t = 0;
    while(f[t] <= k) t ++ ;
    cout << t - 1 << endl;

    return 0;
}


活动打卡代码 AcWing 1378. 谦虚数字

Lemon_kk
29天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, M = 110;
const LL INF = 1e17;

int n, k;
int p[N], q[N];
vector<LL> res;

int main(){

    scanf("%d%d", &n, &k);
    for(int i = 1;i <= n;i ++ ) scanf("%d", &p[i]);

    res.push_back(1);
    for(int i = 1;i <= k;i ++ ){
        LL t = INF;
        for(int j = 1;j <= n;j ++ )
            t = min(t, res[q[j]] * p[j]);
        for(int j = 1;j <= n;j ++ )
            if(res[q[j]] * p[j] == t)
                q[j] ++ ;
        res.push_back(t);
    }

    cout << res.back() << endl;

    return 0;
}


活动打卡代码 AcWing 1377. 得分通胀

Lemon_kk
29天前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e4 + 10;

int n, m;
int p, t;
int f[N];

int main(){

    scanf("%d%d", &m, &n);
    for(int i = 1;i <= n;i ++ ){
        cin >> p >> t;
        for(int j = t;j <= m;j ++ )
            f[j] = max(f[j], f[j - t] + p);
    }

    cout << f[m] << endl;


    return 0;
}