HowardY

2012

RyanMoriarty

ohh_5
WearSpring
xu111

zouruiyang
404NotFound.

_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;//储存所有待处理的数值/下标

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;

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());

//处理插入
{
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;
}
};


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;

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))
{
}
}
}
cout << bfs() << endl;
}


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


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;

{
int v, w;

//记录食材需求情况
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++)
{
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;
}
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;
}



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


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


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