头像

HowardY




离线:1小时前


最近来访(29)
用户头像
RyanMoriarty
用户头像
蓬蒿人阿
用户头像
ohh_5
用户头像
WearSpring
用户头像
xu111
用户头像
一十七画生
用户头像
zouruiyang
用户头像
404NotFound.
用户头像
无名_2
用户头像
从此不做大鲨鱼
用户头像
_accept
用户头像
梨小畅
用户头像
rarestark


HowardY
9天前

在映射时注意是在alls中查找x的位置

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

const int N = 300010;

vector<int> alls;//储存所有待处理的数值/下标
vector<PII> add, query;

int a[N], s[N];//a是被映射的数组,从1开始的自然数

int find (int x){

    int l = 0, r = alls.size() - 1;

    while(l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;//在alls中找到x
        else l = mid + 1;
    }

    return r + 1;
}

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0 ; i < n ; i ++ ) 
    {
        int x, c;
        cin >> x >> c;

        add.push_back({x, c});

        alls.push_back(x);

    }

    for (int i = 0; i < m ; i ++ )
    {
        int l, r;
        cin >> l >> r;

        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);
    }

    //排序 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(),alls.end()), alls.end());

    //处理插入
    for (auto item : add)
    {
        int x = find (item.first);
        a[x] += item.second;
    }

    //初始前缀和
    for (int i = 1 ; i <= alls.size() ; i ++ )
    {
        s[i] = s[i-1] + a[i];
    }

    //查询
    for (auto item : query)
    {
        int l = find (item.first);
        int r = find (item.second);

        int res = s[r] - s[l - 1];

        printf("%d\n",res);
    }

    return 0;
}



HowardY
3个月前
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        int m = matrix[0].size();
        int i = 0, j = m - 1;
        while(i<n && j>=0)
        {
            int t = matrix[i][j];
            if(t == target) return true;
            else if(t>target) j--;
            else i++;
        }
        return false;
    }
};


活动打卡代码 AcWing 3200. 无线网络

HowardY
4个月前
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
using namespace std;

typedef long long LL;

typedef pair<int, int> PII;

const int MAXN = 210;

int n, m, k, r;

vector<int> Adj[MAXN];

PII point[MAXN];

bool check(int i, int j)
{
    LL dx = point[i].first - point[j].first;
    LL dy = point[i].second - point[j].second;
    return dx * dx + dy * dy <= (LL)r * r;
}

const int MAXK = 110;

bool st[MAXN][MAXK];

int dist[MAXN][MAXK];

int bfs()
{
    queue<PII> q;
    q.push({1, 0});
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof(st));
    dist[1][0] = 0;
    st[1][0] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t.first][t.second] = false;
        int u = t.first;
        for (int i = 0; i < Adj[u].size(); i++)
        {
            int v = Adj[u][i], j = t.second;
            if (v > n)
            {
                j++;
            }
            if (j <= k && dist[v][j] > dist[t.first][t.second] + 1)
            {
                dist[v][j] = dist[t.first][t.second] + 1;
                if (st[v][j] == false)
                {
                    q.push({v, j});
                    st[v][j] = true;
                }
            }
        }
    }

    int res = 1e8;
    for (int i = 0; i <= k; i++)
        res = min(res, dist[2][i]);
    return res - 1;
}

int main()
{
    cin >> n >> m >> k >> r;
    for (int i = 1; i <= n; i++)
        cin >> point[i].first >> point[i].second;
    for (int i = n + 1; i <= n + m; i++)
        cin >> point[i].first >> point[i].second;
    for (int i = 1; i <= m + n; i++)
    {
        for (int j = i + 1; j <= m + n; j++)
        {
            if (check(i, j))
            {
                Adj[i].push_back(j);
                Adj[j].push_back(i);
            }
        }
    }
    cout << bfs() << endl;
}


活动打卡代码 AcWing 3414. 校门外的树

HowardY
5个月前
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 1010;

const int MAXM = 1e5 + 10;

const int MOD = 1e9 + 7;

int a[MAXN];

int f[MAXN];

bool st[MAXM];

typedef long long LL;

vector<int> ys[MAXM];

//预处理,先得到各个数的约数
void init()
{
    for (int i = 1; i < MAXM; i++)
    {
        for (int j = 2 * i; j < MAXM; j += i)
        {
            ys[j].push_back(i);
        }
    }
}

int n;

int main()
{
    init();
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    f[0] = 1;
    for (int i = 1; i < n; i++)
    {
        memset(st, 0, sizeof(st));
        for (int j = i - 1; j >= 0; j--)
        {
            int d = a[i] - a[j];
            int cnt = 0;
            for (auto c : ys[d])
            {
                if (!st[c])
                {
                    cnt++;
                    st[c] = true;
                }
            }
            st[d] = true;
            f[i] = (f[i] + (LL)f[j] * cnt) % MOD;
        }
    }
    cout << f[n - 1] << endl;
}



HowardY
5个月前
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int, int> PTT;

const int MAXM = 1e5 + 10;

int num0[MAXM], num1[MAXM];

int m;

PTT input[MAXM];

int main()
{
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &input[i].first, &input[i].second);
    }
    sort(input + 1, input + 1 + m);
    for (int i = 1; i <= m; i++)
    {
        if (input[i].second == 0)
        {
            num0[i] = num0[i - 1] + 1;
            num1[i] = num1[i - 1];
        }
        else
        {
            num0[i] = num0[i - 1];
            num1[i] = num1[i - 1] + 1;
        }
    }
    int ans = -1, maxCorret = -1;
    for (int i = 1; i <= m; i++)
    {
        int temp = num1[m] - num1[i - 1] + num0[i - 1];
        if (temp >= maxCorret)
        {
            maxCorret = temp;
            ans = input[i].first;
        }
        int j = i + 1;
        while (j <= m && input[j].first == input[i].first)
            j++;
        i = j - 1;
    }
    cout << ans << endl;
}



HowardY
5个月前
#include <iostream>
#include <algorithm>
using namespace std;

int n;

int main()
{
    cin >> n;
    int ans = 0;
    int w, s;
    while (n--)
    {
        cin >> w >> s;
        ans += w * s;
    }
    cout << max(0, ans) << endl;
}


活动打卡代码 AcWing 3300. 食材运输

HowardY
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef pair<int, int> PII;

const int MAXN = 110;
const int MAXMK = 20;

typedef struct Road
{
    int v, w;
} Road;

vector<Road> Adj[MAXN];

//记录食材需求情况
int need[MAXN][MAXMK];

//d[i][j]记录从第i个点运送完所有的j食材需要的最短时间
int d[MAXN][MAXMK];

int n, m, k;

PII dfs(int u, int fa, int j)
{
    //first表示所有“关键路径和的2倍”,second表示与当前节点距离最远的需求j种货物的节点之间的距离
    PII ans(0, -1); //-1表示没有这样的点
    if (need[u][j] == 1)
    {
        ans.second = 0;
    }
    for (int i = 0; i < Adj[u].size(); i++)
    {
        int v = Adj[u][i].v, w = Adj[u][i].w;
        if (v == fa)
        {
            continue; //不能往回遍历啊
        }
        auto res = dfs(v, u, j);
        if (res.second != -1)
        {
            ans.first += res.first + 2 * w;
            ans.second = max(ans.second, res.second + w);
        }
    }
    return ans;
}

//state[i]记录从节点i出发,在mid时间内是否能够遍历完所有需要j种货物的节点
int state[MAXN];

//f[j]表示覆盖情况为j时需要的最少的行数
int f[1 << MAXMK];

bool check(int mid)
{
    memset(state, 0, sizeof(state));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < k; j++)
        {
            if (d[i][j] <= mid)
            {
                state[i] |= 1 << j;
            }
        }
    }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0; //覆盖情况为000..0时,需要的行数为0
    for (int i = 0; i < 1 << k; i++)
    { //遍历所有的状态,
        for (int j = 1; j <= n; j++)
        { //在原有的状态上添加第i行,产生新状态
            f[i | state[j]] = min(f[i | state[j]], f[i] + 1);
        }
    }
    return f[(1 << k) - 1] <= m;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < k; j++)
        {
            cin >> need[i][j];
        }
    }
    for (int C = 0; C < n - 1; C++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        Adj[u].push_back({v, w});
        Adj[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < k; j++)
        {
            auto a = dfs(i, -1, j);
            if (a.second != -1)
            {
                d[i][j] = a.first - a.second;
            }
        }
    }
    int l = 0, r = 2e8;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << l << endl;
}



活动打卡代码 AcWing 3293. 风险人群筛查

HowardY
5个月前
//一位居民的位置记录包含 t 个平面坐标
//高危区域则可以抽象为一个矩形区域(含边界),左下角和右上角的坐标分别为 (xl,yd) 和 (xr,yu),
//如果其中连续 k 个或更多坐标均位于矩形内(含边界),则认为该居民曾在高危区域逗留。

#include <iostream>
#include <set>
#include <algorithm>
#include <map>
using namespace std;

typedef pair<int, int> PII;

const int MAXT = 1010;

PII record[MAXT];

int n, k, t, xl, yd, xr, yu;

bool in(PII a)
{
    int x = a.first, y = a.second;
    if (xl <= x && x <= xr && yd <= y && y <= yu)
        return true;
    return false;
}

int ans1 = 0; //经过危险地区的个数

int ans2 = 0; //逗留危险地区的个数

int main()
{
    int cnt = 1;
    scanf("%d%d%d%d%d%d%d", &n, &k, &t, &xl, &yd, &xr, &yu);
    while (n--)
    {
        for (int i = 0; i < t; i++)
        {
            scanf("%d%d", &record[i].first, &record[i].second);
        }
        bool flag1 = false, flag2 = false;
        for (int i = 0; i < t; i++)
        {
            if (in(record[i]))
            {
                flag1 = true;
                int j = i + 1;
                while (j < t && in(record[j]))
                    j++;
                int num = j - i;
                if (num >= k)
                {
                    flag2 = true;
                    break;
                }
                i = j;
            }
        }
        if (flag1)
            ans1++;
        if (flag2)
            ans2++;
    }
    printf("%d\n%d\n", ans1, ans2);
}


活动打卡代码 AcWing 3292. 称检测点查询

HowardY
5个月前
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n, X, Y;

inline int sqr(int x)
{
    return x * x;
}

typedef struct Node
{
    int id;
    int x, y;
    int dis;
    Node() {}
    Node(int id, int x, int y)
        : id(id), x(x), y(y)
    {
        dis = sqr(x - X) + sqr(y - Y);
    }
    bool operator<(const Node &b) const
    {
        if (this->dis != b.dis)
        {
            return this->dis < b.dis;
        }
        else
        {
            return this->id < b.id;
        }
    }
} Node;

const int N = 210;

Node input[N];

int main()
{
    cin >> n >> X >> Y;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        input[i] = Node(i + 1, x, y);
    }
    sort(input, input + n);
    for (int i = 0; i < 3; i++)
    {
        cout << input[i].id << endl;
    }
}


活动打卡代码 AcWing 3295. 星际旅行

HowardY
5个月前
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 110;

const int MAXM = 2010;

double point[MAXM][MAXN];

double o[MAXN]; //球心的坐标

double d[MAXM]; //各个点与球心的距离

double rd[MAXM];

double ans[MAXM];

int n, m;

double r;

inline double sqr(double x)
{
    return x * x;
}

int main()
{
    scanf("%d%d%lf", &n, &m, &r);
    for (int i = 0; i < n; i++)
    {
        scanf("%lf", &o[i]);
    }
    for (int i = 0; i < m; i++)
    {
        double s = 0;
        for (int j = 0; j < n; j++)
        {
            scanf("%lf", &point[i][j]);
            s += sqr(point[i][j] - o[j]);
        }
        d[i] = sqrt(s);
        rd[i] = sqrt(s - sqr(r));
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < i; j++)
        {
            double s = 0;
            for (int k = 0; k < n; k++)
            {
                s += sqr(point[i][k] - point[j][k]);
            }
            double c = sqrt(s);
            double a = d[i], b = d[j];
            double p = (a + b + c) / 2;
            double area = sqrt(p * (p - a) * (p - b) * (p - c));
            double h = 2 * area / c;
            if (h >= r || sqr(b) >= sqr(a) + s || sqr(a) >= sqr(b) + s)
            {
                ans[i] += c;
                ans[j] += c;
            }
            else
            {
                double r1 = acos((sqr(a) + sqr(b) - s) / (2 * a * b));
                double r2 = acos(r / a);
                double r3 = acos(r / b);
                double t = (r1 - r2 - r3) * r + rd[i] + rd[j];
                ans[i] += t, ans[j] += t;
            }
        }
    }
    for (int i = 0; i < m; i++)
    {
        printf("%.12lf\n", ans[i]);
    }
}