标题已经说明了一切。
今天下午bhi神过来问我，“机房有人吗？”，我说不知道，然后发现居然有人，就跑进去了。
然后直到放学才出来。干了些什么呢？首先艹了一波ZLXSC的题解，居然被出题人赞了，开心owo
然后发现ZLXSC的时间和UR恰好无缝对接，然后连饭都没吃就开始打UR。
先看题。貌似都不可做……暴力大法好。
A暴力二分+贪心，B暴力DP，C暴力分解质因数。
然后60+20+20=100，Rank50。不过Rating还是涨了，毕竟前面几场都挂了，所以底数很低。
好短啊。。。看来人太傻逼还是写不出来什么有价值的东西吧
附上代码凑字数
A
#include <cstdio>
#define INF 100010
int a[INF];
bool b[INF];
int lsa[INF];
bool lsb[INF];
int n, q;
bool ok(int x)
{
int lsn = n;
for (int i = 1; i <= lsn; i++)
{
lsa[i] = a[i];
lsb[i] = b[i];
}
while (true)
{
int mm = INF, d = 0;
for (int i = 1; i <= lsn; i++)
if (!lsb[i] && mm > lsa[i])
mm = lsa[i], d = i;
if (!d)
return true;
int l = d, r = d;
while (l >= 2 && lsa[l - 1] > lsa[d])
l--;
while (r <= lsn - 1 && lsa[r + 1] > lsa[d])
r++;
if (r - l + 1 < x)
return false;
else
{
lsn--;
for (int i = d; i <= lsn; i++)
{
lsa[i] = lsa[i + 1];
lsb[i] = lsb[i + 1];
}
}
}
}
int check()
{
int l = 1, r = n;
while (r - l > 1)
{
int mid = (l + r) / 2;
if (ok(mid))
{
l = mid;
}
else
{
r = mid - 1;
}
}
return (ok(r) ? r : l);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
scanf("%d", &q);
for (int i = 1; i <= q; i++)
{
for (int j = 1; j <= n; j++)
{
char x = getchar();
while (x < '0' || x > '1')
x = getchar();
b[j] = (x == '1');
}
printf("%d\n", check());
}
return 0;
}
B
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAXN 500010
#define INF 1000000001
using namespace std;
int a[MAXN], b[MAXN];
int n;
long long ans[MAXN];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", a + i, b + i);
a[0] = -INF;
for (int i = 1; i <= n; i++)
{
int j = i;
ans[i] = 1;
while (abs(a[j] - a[j - 1]) <= b[j] - b[j - 1])
j--;
for (int k = j; k < i; k++)
{
if (ans[i] < (long long)(i - k + 1) * (i - k + 1))
ans[i] = (long long)(i - k + 1) * (i - k + 1);
for (int l = 1; l < k; l++)
if (abs(a[k] - a[l]) <= b[k] - b[l])
if (ans[l] + (long long)(i - k + 1) * (i - k + 1) > ans[i])
ans[i] = ans[l] + (long long)(i - k + 1) * (i - k + 1);
}
for (int k = 1; k < j; k++)
{
if (ans[k] + 1 > ans[i] && abs(a[i] - a[k]) <= b[i] - b[k])
ans[i] = ans[k] + 1;
}
}
long long o = 0;
for (int i = 1; i <= n; i++)
if (ans[i] > o)
o = ans[i];
printf("%lld\n", o);
return 0;
}
C
#include <iostream>
#include <cstdio>
using namespace std;
int prime[10010010], cnt;
bool flag[10010010];
void prepare()
{
for (int i = 2; i <= 10010000; i++)
{
if (!flag[i])
prime[cnt++] = i;
for (int j = 0; j < cnt; j++)
{
if (i * prime[j] > 10010000)
break;
flag[i * prime[j]] = true;
if (i % prime[j] == 0)
break;
}
}
}
int main()
{
prepare();
int l, r;
long long ans = 0;
scanf("%d%d", &l, &r);
for (int i = l; i <= r; i++)
{
if (!flag[i])
continue;
int d1 = 0, d2 = 0, ls = i;
for (int j = 0; j < cnt; j++)
{
if (ls % prime[j] == 0)
{
d2 = d1;
d1 = prime[j];
while (ls % prime[j] == 0)
ls /= prime[j];
}
if (!flag[ls])
{
d2 = d1;
break;
}
}
ans = ans + d2;
}
printf("%lld", ans);
return 0;
}
