头像

I-AK-IOI

CCF_NOI(伪)


访客:1520

离线:1个月前



I-AK-IOI
7个月前

二分答案转化为判定

根据复杂度理论,判定的难度小于求解

#include<bits/stdc++.h> 
using namespace std;
int a, b;
int main() {
    cin >> a >> b;
    int l = -1e9, r = 1e9;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (mid >= a + b) r = mid;
        else l = mid + 1;
    }
    cout << l;
}

时间复杂度$O(\log 10^9)$



活动打卡代码 AcWing 253. 普通平衡树

I-AK-IOI
8个月前
#include<bits/stdc++.h>
struct fhq_treap{
    int ls, rs, val, dat, size;
}tr[100010];
int tot, root;
inline int read(){
    int res = 0;
    bool negative = 0;
    char ch = getchar();
    while(!isdigit(ch)) negative |= ch == '-', ch = getchar();
    while(isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return negative ? -res : res;
}
inline void update(int p){
    tr[p].size = tr[tr[p].ls].size + tr[tr[p].rs].size + 1;
}
inline int New(int val){
    tr[++tot].val = val;
    tr[tot].dat = rand();
    tr[tot].size = 1;
    return tot;
}
int merge(int x, int y){
    if(!x || !y) return x + y;
    if(tr[x].dat < tr[y].dat) {
        tr[x].rs = merge(tr[x].rs, y);
        update(x);
        return x;
    }else{
        tr[y].ls = merge(x, tr[y].ls);
        update(y);
        return y;
    }
}
void split(int now, int val, int &x, int &y){
    if(!now){
        x = y = 0;
        return;
    }
    if(tr[now].val <= val)
        x = now, split(tr[now].rs, val, tr[now].rs, y);
    else
        y = now, split(tr[now].ls, val, x, tr[now].ls);
    update(now);
}
void write(int x){
    if(x < 0) putchar('-'), write(-x);
    else if(x < 10) putchar(x + '0');
    else write(x / 10), putchar(x % 10 + '0');
}
int kth(int now, int k){
    while(now){
        if(k <= tr[tr[now].ls].size) now = tr[now].ls;
        else{
            if(k == tr[tr[now].ls].size + 1) return now;
            k -= tr[tr[now].ls].size + 1, now = tr[now].rs;
        }
    }
}
int n;
int main(){
    n = read();
    while(n--){
        int opt = read(), val = read();
        int a, b, x, y, z;
        switch(opt){
            case 1:
                split(root, val, x, y);
                root = merge(merge(x, New(val)), y);
                break;
            case 2:
                split(root, val, x, z);
                split(x, val - 1, x, y);
                y = merge(tr[y].ls, tr[y].rs);
                root = merge(merge(x, y), z);
                break;
            case 3:
                split(root, val - 1, x, y);
                write(tr[x].size + 1), putchar('\n');
                root = merge(x, y);
                break;
            case 4:
                write(tr[kth(root, val)].val), putchar('\n');
                break;
            case 5:
                split(root, val - 1, x, y);
                write(tr[kth(x, tr[x].size)].val), putchar('\n');
                root = merge(x, y);
                break;
            case 6:
                split(root, val, x, y);
                write(tr[kth(y, 1)].val), putchar('\n');
                root = merge(x, y);
                break;
        }
    }
} 
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 179. 八数码

I-AK-IOI
8个月前

fork的版本

//Author:WFZWF
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
string st, ed;
int depth, ans[50];
int hfunc(string st) {
    int ans = 0;
    for (register int i = 0; i < st.size(); ++i) {
        if (st[i] == '0') continue;
        int j = ed.find(st[i]), r = i / 3, c = i % 3;
        int x = j / 3, y = j % 3;
        ans += abs(r - x) + abs(c - y);
    }
    return ans;
}
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}, step[4] = {'u', 'l', 'd', 'r'};
bool dfs(int now, int pre) {
    int cnt = hfunc(st);
    if (!cnt) return 1;
    if (now + cnt > depth) return 0;
    int pos = st.find('0'), x = pos / 3, y = pos % 3;
    for (register int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx > 2 || ny < 0 || ny > 2 || nx * 3 + ny == pre) continue;
        swap(st[pos], st[nx * 3 + ny]);
        ans[now + 1] = step[i];
        if (dfs(now + 1, pos)) return 1;
        swap(st[pos], st[nx * 3 + ny]);
    }
    return 0;
}
int main() {
    for (register int i = 1; i <= 9; ++i) {
        char s[2];
        scanf("%s", s);
        st += s[0] == 'x' ? '0' : s[0];
    }
    int cnt = 0;
    for (register int i = 0; i < st.size(); ++i)
        if (st[i] != '0')
            for (register int j = 0; j < i; ++j)
                if (st[j] != '0') cnt += st[i] > st[j];
    if (cnt & 1) {
        puts("unsolvable");
        return 0;
    }
    ed = "123456780";
    for (depth = hfunc(st); !dfs(0, -1); ++depth);
    for (register int i = 1; i <= depth; ++i)
        putchar(ans[i]);
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 102. 最佳牛围栏

I-AK-IOI
8个月前
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#include <iostream>
using namespace std;
double a[100001], sum[100001]; 
int n, m;
const double eps = 1e-4;
int main() {
    cin >> n >> m;
    for (register int i = 1; i <= n; ++i) scanf("%lf", a + i);
    double l = -1e6, r = 1e6;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        for (register int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i] - mid;
        double ans = -1e9, min_val = 1e9;
        for (register int i = m; i <= n; ++i) {
            min_val = min(min_val, sum[i - m]);
            ans = max(ans, sum[i] - min_val);
        }
        if (ans >= 0) l = mid;
        else r = mid;
    }
    cout << int(r * 1000);
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 274. 移动服务

I-AK-IOI
8个月前
#include<bits/stdc++.h>
using namespace std;
int a[201][201], f[1001][201][201], n, L, p[1001];
#define min(a, b) ((a) < (b) ? (a) : (b)) 
int main() {
    cin >> L >> n;
    for (register int i = 1; i <= L; ++i)
        for (register int j = 1; j <= L; ++j)
            scanf("%d", a[i] + j);
    for (register int i = 1; i <= n; ++i) scanf("%d", p + i);
    p[0] = 3;
    for (register int i = 0; i <= n; ++i)
        for (register int x = 1; x <= L; ++x)
            for (register int y = 1; y <= L; ++y)
                f[i][x][y] = 0x3f3f3f3f; 
    f[0][1][2] = 0;
    for (register int i = 0; i < n; ++i)
        for (register int x = 1; x <= L; ++x)
            for (register int y = 1; y <= L; ++y) {
                if (x == y || x == p[i] || y == p[i]) continue;
                f[i + 1][x][y] = min(f[i + 1][x][y], f[i][x][y] + a[p[i]][p[i + 1]]);
                f[i + 1][x][p[i]] = min(f[i + 1][x][p[i]], f[i][x][y] + a[y][p[i + 1]]);
                f[i + 1][p[i]][y] = min(f[i + 1][p[i]][y], f[i][x][y] + a[x][p[i + 1]]);
            }
    int ans = 0x3f3f3f3f;
    for (register int i = 1; i <= L; ++i)
        for (register int j = 1; j <= L; ++j)
            ans = min(ans, f[n][i][j]);
    cout << ans;
} 



I-AK-IOI
9个月前

大水题

直接上代码

class Solution {
public:
    int getUglyNumber(int n) {
        set<int> s;
        s.insert(1);
        while (--n) {
            int x = *s.begin();
            s.erase(s.begin());
            s.insert(x << 1);
            s.insert((x << 1) + x);
            s.insert((x << 2) + x);
        }
        return *s.begin();
    }
};

洛谷博客

洛谷上的题




I-AK-IOI
9个月前

fork的版本终于通过了

如果想要更好的体验,可以到我的博客去看

我使用的算法是IDA_star

好处在于效率高,不用hash

我们想想,假设每一步都是有意义的,那么一个数字成功对上也要移动他们的曼哈顿距离次

所以,我们将估价函数设计为所有数字与目标状态中数字的曼哈顿距离之和(当然0不算,否则你就可以高兴的WA了)

还有一个显然的优化,就是记录上一次的操作

而且我们不一定要用二维数组,可以用一个string来保存状态。对于一个string中的下标i,纵坐标为i/3, 横坐标为i%3。对于二维数组下标x, y, string中的下标便为x * 3 + y

还有不明白的,请看代码

//Author:WFZWF
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
string st, ed;
int depth, ans[50];
int hfunc(string st) {
    int ans = 0;
    for (register int i = 0; i < st.size(); ++i) {
        if (st[i] == '0') continue;
        int j = ed.find(st[i]), r = i / 3, c = i % 3;
        int x = j / 3, y = j % 3;
        ans += abs(r - x) + abs(c - y);
    }
    return ans;
}
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}, step[4] = {'u', 'l', 'd', 'r'};
bool dfs(int now, int pre) {
    int cnt = hfunc(st);
    if (!cnt) return 1;
    if (now + cnt > depth) return 0;
    int pos = st.find('0'), x = pos / 3, y = pos % 3;
    for (register int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx > 2 || ny < 0 || ny > 2 || nx * 3 + ny == pre) continue;
        swap(st[pos], st[nx * 3 + ny]);
        ans[now + 1] = step[i];
        if (dfs(now + 1, pos)) return 1;
        swap(st[pos], st[nx * 3 + ny]);
    }
    return 0;
}
int main() {
    for (register int i = 1; i <= 9; ++i) {
        char s[2];
        scanf("%s", s);
        st += s[0] == 'x' ? '0' : s[0];
    }
    int cnt = 0;
    for (register int i = 0; i < st.size(); ++i)
        if (st[i] != '0')
            for (register int j = 0; j < i; ++j)
                if (st[j] != '0') cnt += st[i] > st[j];
    if (cnt & 1) {
        puts("unsolvable");
        return 0;
    }
    ed = "123456780";
    for (depth = hfunc(st); !dfs(0, -1); ++depth);
    for (register int i = 1; i <= depth; ++i)
        putchar(ans[i]);
}



I-AK-IOI
9个月前

如果想要更好的体验,可以到我的博客去看

我使用的算法是IDA_star

好处在于效率高,不用hash

我们想想,假设每一步都是有意义的,那么一个数字成功对上也要移动他们的曼哈顿距离次

所以,我们将估价函数设计为所有数字与目标状态中数字的曼哈顿距离之和(当然0不算,否则你就可以高兴的WA了)

还有一个显然的优化,就是记录上一次的操作

而且我们不一定要用二维数组,可以用一个string来保存状态。对于一个string中的下标i,纵坐标为i/3, 横坐标为i%3。对于二维数组下标x, y, string中的下标便为x * 3 + y

还有不明白的,请看代码

//Author:WFZWF
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
string st, ed;
int depth;
int hfunc(string st) {
    int ans = 0;
    for (register int i = 0; i < st.size(); ++i) {
        if (st[i] == '0') continue;
        int j = ed.find(st[i]), r = i / 3, c = i % 3;
        int x = j / 3, y = j % 3;
        ans += abs(r - x) + abs(c - y);
    }
    return ans;
}
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
bool dfs(int now, int pre) {
    int cnt = hfunc(st);
    if (!cnt) return 1;
    if (now + cnt > depth) return 0;
    int pos = st.find('0'), x = pos / 3, y = pos % 3;
    for (register int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx > 2 || ny < 0 || ny > 2 || nx * 3 + ny == pre) continue;
        swap(st[pos], st[nx * 3 + ny]);
        if (dfs(now + 1, pos)) return 1;
        swap(st[pos], st[nx * 3 + ny]);
    }
    return 0;
}
int main() {
    for (register int i = 1; i <= 9; ++i) {
        char s[2];
        scanf("%s", s);
        st += s[0] == 'x' ? '0' : s[0];
    }
    int cnt = 0;
    for (register int i = 0; i < st.size(); ++i)
        if (st[i] != '0')
            for (register int j = 0; j < i; ++j)
                if (st[j] != '0') cnt += st[i] > st[j];
    if (cnt & 1) {
        puts("-1");
        return 0;
    }
    ed = "123456780";
    for (depth = hfunc(st); !dfs(0, -1); ++depth);
    cout << depth;
}



I-AK-IOI
9个月前

本题就是让我们求一个长度不大于m的最大子序和

设$sum_{i}$为前$i$个数的前缀和

容易列出状态转移方程

$ans=\max \limits_{i \le n} \lbrace {sum_i-\min\limits_{i-m \le j \le i}\lbrace sum_j \rbrace }\rbrace$

但如果暴力枚举,时间复杂度是$O(nm)$的

考虑用单调队列进行优化

不妨比较任意两个位置$j_{1}, j_{2}$, 如果 $j_{1} < j_{2} , sum[j_{1}] \ge sum[j_{2}]$, 那么$j_{1}$就是无用决策

因为$j_{1}$能取到的地方,$j_{2}$也能取到,所以
$j_{1}$永远不会成为最优决策

综上所述,我们维护一个下标位置递增,对应前缀和sum也递增的单调队列, 只有这个队列中的决策,才有可能成为最优决策。

我们对每个$i$每次执行三个步骤

1.判断队头决策与$i$的距离是否超出$m$的范围,若超出则出队
2.此时队头就是右端点为$i$时,左端点$j$的最优选择

3.不断删除队尾决策,直到队尾对应的$sum$值小于$sum_{i}$。最后把$i$作为一个新的决策入队

#include<bits/stdc++.h>
using namespace std;
char buf[100010], *p1, *p2;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++
template<class item>
inline item read() {
    item res = 0;
    bool negative = 0;
    char ch = getchar();
    while (!isdigit(ch)) negative |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return negative ? -res : res;
}
template<class item>
inline item read(item & t) {
    t = read<item>();
    return t;
}
#define max(a, b)  (!((a) < (b)) ? (a) : (b))
#define min(a, b)  ((a) < (b) ? (a) : (b))
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
    read(t), read(args...);
}
//快读,长了点 
int sum[500010], n, q[500010], m, ans = -1e9;
int main() {
    cin >> n >> m;
    for (register int i = 1; i <= n; ++i) read(sum[i]), sum[i] += sum[i - 1];
    int l = 1, r = 1;
    for (register int i = 1; i <= n; ++i) {
        while (l <= r && q[l] < i - m) ++l;//排除不可能决策 
        ans = max(ans, sum[i] - sum[q[l]]);
        while (l <= r && sum[q[r]] >= sum[i]) --r;//排除无用决策 
        q[++r] = i;//插入新决策 
    }
    cout << max(ans, 0);//被这个坑了,好像可以什么也不选 
}

最后还是提醒大家多到我的博客看题解,多点几个赞