2019 牛客 多校赛 第三场
slove 2/10
rank 261
补题 5/10
--------------------------------------------------------
https://ac.nowcoder.com/acm/contest/883#question
B、Crazy Binary String
题意：给一个01串，求出使01个数相等的最长子串和最长子序列，输出长度。
思路：记录每个位置前缀的0-1的数量，如果这个数量是第一次出现，存一下当前这个数量对应的下标，否则，直接更新答案
Code：
#include <bits/stdc++.h>
using namespace std;
char s[100005];
map<int, int>mp;
int main()
{
int n;
scanf("%d", &n);
scanf("%s", s);
int cnt10 = 0, ans = 0;
int one = 0, zero = 0;
mp[0] = -1;
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
{
cnt10++;
one++;
}
else
{
cnt10--;
zero++;
}
if (mp[cnt10] == 0)
mp[cnt10] = i;
else
ans = max(ans, i - mp[cnt10]);
}
int ans1 = min(one, zero);
ans1 *= 2;
printf("%d %d", ans,ans1);
} F、Planting Trees
题意：给一个n*n的矩阵，定义一个矩阵合法，当且仅当矩阵的最大值减最小值小于等于M，要求你找出合法子矩阵的最大面积。
思路：暴力上下边界和右边界，然后单调栈维护左端点的最大值和最小值，如果当前矩阵不合法，那么左端点肯定要右移，然后维护最大最小值就可以了
Code：
#include <bits/stdc++.h>
using namespace std;
int a[1005][1005];
int maxn[1005], minn[1005];//维护纵坐标为i时，一行的前缀最大最小值
//deque<int>demax, demin;
int demax[1005], demin[1005];
int head1, tail1, head2, tail2;
int main()
{
int n, m;
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
int ans = 0;
for (int i = 1; i <= n; i++)//上边界
{
for (int j = 1; j <= n; j++)
{
maxn[j] = 0;
minn[j] = 100005;
}
for (int j = i; j <= n; j++)//下边界
{
//demin.clear(), demax.clear();
head1 = 0, tail1 = 0, head2 = 0, tail2 = 0;
int index = 0;//左端点
for (int k = 1; k <= n; k++)//右边界
{
maxn[k] = max(maxn[k], a[j][k]);
minn[k] = min(minn[k], a[j][k]);
}
for (int k = 1; k <= n; k++)//右边界
{
while (head1 < tail1 && maxn[demax[tail1 - 1]] <= maxn[k])//维护最大值的递减序列
tail1--;
while (head2 < tail2 && minn[demin[tail2 - 1]] >= minn[k])//维护最小值的递增序列
tail2--;
demax[tail1++] = k;
demin[tail2++] = k;
while (head1 < tail1 && head2 < tail2 && maxn[demax[head1]] - minn[demin[head2]] > m)//如果此时区间不满足于要求，左端点右移
{
if (demax[head1] < demin[head2])
{
index = demax[head1];//更新左端点
head1++;
}
else
{
index = demin[head2];//更新左端点
head2++;
}
}
ans = max(ans, (j - i + 1) * (k - index));
}
}
}
printf("%d\n", ans);
}
} G、Removing Stones
给一个区间，找出所有满足区间和大于等于区间最大值*2的区间的数量。
对于每个点，我们假设这个点是区间的最大值，那么左端点一定小于等于 i ，右端点一定大于等于 i ，那么我们可以知道他可以往左边取最多多少个数字，然后每次判断是否还能向右取，右端点的数量就是固定左端点的答案贡献，然后每次将左端点右移，重复上述步骤，知道左端点为空
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll a[300005];
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n;
sc("%d", &n);
for (int i = 1; i <= n; i++)
sc("%lld", &a[i]);
ll ans = 0;
for (int i = 1; i <= n; i++)
{
int l = i, r = i;
ll sum = 0;
//固定左端点的值
while (l > 1 && sum + a[l - 1] < a[i])
sum += a[--l];
while (l <= i)
{
//判断右端点的个数
while (r < n && sum + a[r + 1] < a[i])
sum += a[++r];
ans += r - i + 1;
sum -= a[l++];//左端点右移
}
}
printf("%lld\n", 1LL * n * (n + 1) / 2 - ans);
}
} H、Magic Line
题意：给你N个点，N是偶数，要求你画出一条直线，将这N个点划分为两个集合，输出直线的左右顶点（要是整数）
思路：排个序。找到分界点，如果不在同一行，瞎搞，如果在同一行y，取(-3000,y-1)，然后搞一下公式，找到这个点和两个分界点的线与9e8的交点，然后在他们的交点上随便选一个整数点就可以了。
Code：
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>
#define ll long long
const double eps = 1e-6;
const double PI = acos(-1.0); // PI = 180°= 3.14
using namespace std;
//判断符号
int sign(double x)
{
if (fabs(x) < eps)
return 0;
return x > 0 ? 1 : -1;
}
struct node
{
ll x;
ll y;
node operator + (const node& other) { return node{ x + other.x, y + other.y }; }
node operator - (const node& other) { return node{ x - other.x, y - other.y }; }
node operator * (int k) { return node{ x * k, y * k }; }
node operator / (int k) { return node{ x / k, y / k }; }
};
//叉积
ll cross(node a, node b)
{
return a.x * b.y - b.x * a.y;
}
double calc(double a, double b, double c, double d)
{
double ans = (d - b) / (c - a) * 900000000 - (c * (d - b) / (c - a)) + d;
return ans;
}
node in[100005];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%lld%lld", &in[i].x, &in[i].y);
}
sort(in, in + n, [](node q, node w) {
if (q.y == w.y)
return q.x < w.x;
return q.y > w.y;
});
node a = in[n / 2 - 1];
node b = in[n / 2];
if (a.y != b.y)
{
printf("-1000000000 %d 1000000000 %d\n", b.y, a.y);
continue;
}
int now = a.y;
node o = node{ -3100,now - 1 };
node l1 = node{ 900000000,1 };
node l2 = node{ 900000000,-1 };
double y1 = calc(o.x, o.y, a.x, a.y);
double y2 = calc(o.x, o.y, b.x, b.y);
int x = 900000000;
int y = 0;
for (int i = (double)(y1 - 2); i > y2; i--)
{
y = i;
break;
}
printf("-3100 %d %d %d\n", now - 1, x, y);
qwe:;
}
} J、LRU management
题意：两个操作，第一个操作是插入，如果之前存在这个地址，那么将这个地址移到最后面，否则在最后面加入这个地址，第二个操作是查询操作，要先找到某个地址，然后将这个地址前移或者后移或者他本身，并且输出这个地址的值。如果越界或者没找到输出 Invalid
STL瞎搞，map存list中对应的迭代器，就可以logn查找到第N个。
Code：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define Pair pair<string,int>
list<Pair>v;
map<string, list<Pair>::iterator>mp;
struct ioss {
#define endl '\n'
static const int LEN = 20000000;
char obuf[LEN], * oh = obuf;
std::streambuf* fb;
ioss()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
fb = cout.rdbuf();
}
inline char gc() {
static char buf[LEN], * s, * t, buf2[LEN];
return (s == t) && (t = (s = buf) + fread(buf, 1, LEN, stdin)), s == t ? -1 : *s++;
}
inline ioss& operator >> (long long& x) {
static char ch, sgn, * p;
ch = gc(), sgn = 0;
for (; !isdigit(ch); ch = gc()) { if (ch == -1)return *this; sgn |= ch == '-'; }
for (x = 0; isdigit(ch); ch = gc())x = x * 10 + (ch ^ '0');
sgn && (x = -x); return *this;
}
inline ioss& operator >> (int& x) {
static char ch, sgn, * p;
ch = gc(), sgn = 0;
for (; !isdigit(ch); ch = gc()) { if (ch == -1)return *this; sgn |= ch == '-'; }
for (x = 0; isdigit(ch); ch = gc())x = x * 10 + (ch ^ '0');
sgn && (x = -x); return *this;
}
inline ioss& operator >> (char& x)
{
static char ch;
for (; !isalpha(ch); ch = gc())
{
if (ch == -1)return *this;
}
x = ch;
return *this;
}
inline ioss& operator >> (string& x)
{
static char ch, * p, buf2[LEN];
for (; !isalpha(ch) && !isdigit(ch); ch = gc())
if (ch == -1)return *this;
p = buf2;
for (; isalpha(ch) || isdigit(ch); ch = gc())
* p = ch, p++;
*p = '\0';
x = buf2;
return *this;
}
inline ioss& operator <<(string& c)
{
for (auto& p : c)
this->operator<<(p);
return *this;
}
inline ioss& operator <<(const char* c)
{
while (*c != '\0')
{
this->operator<<(*c);
c++;
}
return *this;
}
inline ioss& operator <<(const char& c) {
oh == obuf + LEN ? (fb->sputn(obuf, LEN), oh = obuf) : 0;
*oh++ = c;
return *this;
}
inline ioss& operator <<(int x) {
static int buf[30], cnt;
if (x < 0)
this->operator<<('-'), x = -x;
if (x == 0)
this->operator<<('0');
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) this->operator<<((char)buf[cnt--]);
return *this;
}
inline ioss& operator <<(long long x) {
static int buf[30], cnt;
if (x < 0)
this->operator<<('-'), x = -x;
if (x == 0)
this->operator<<('0');
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) this->operator<<((char)buf[cnt--]);
return *this;
}
~ioss()
{
fb->sputn(obuf, oh - obuf);
}
} io;
int main()
{
int T;
io >> T;
while (T--)
{
int n, m;
io >> n >> m;
v.clear();
mp.clear();
int v_sz = 0;
while (n--)
{
int op, x;
string s;
io >> op >> s >> x;
if (op == 0)//find s and move end
{
if (mp.find(s) != mp.end())//erase s
{
x = mp[s]->second;
io << x << endl;
v.erase(mp[s]);
v.push_back(Pair{ s,x });
auto it = v.end();
it--;
mp[s] = it;
}
else
{
if (v_sz == m)
{
mp.erase(v.begin()->first);
v.erase(v.begin());
}
else
v_sz++;
io << x << endl;
v.push_back(Pair{ s,x });
auto it = v.end();
it--;
mp[s] = it;
}
}
else//find s and add x to value
{
if (mp.find(s) == mp.end())
{
io << "Invalid" << endl;
continue;
}
auto it = mp[s];
if (x == 0)
{
io << it->second << endl;
}
else if (x == -1)
{
if (it == v.begin())
io << "Invalid" << endl;
else
{
it--;
io << it->second << endl;
}
}
else
{
it++;
if (it == v.end())
io << "Invalid" << endl;
else
{
io << it->second << endl;
}
}
}
}
}
}
