榜单终于公布了，这应该是第二长的榜单公布吧。（最长的一次是去年八月，拖到九月开始后才公布）
T1 是傻逼数据结构不说了吧，对于每个点枚举以他为角的 $k\times k$ 的四个正方形算一下点的数量，用 $cdq$ 或者扫描线都行。
看这个题目编号是 $81$，看来是很久以前就出的题这个月没题了凑出来的。
T2 是我认为比较好的一道题，虽然一眼看出诈骗。
先分析题目类型，显然是 DP，$m$ 一定要计入时间复杂度的，$n$ 应该也有，复杂度就是 $O(n\times m)$。
这点时间够什么？可以够预处理 $f_{i,j}$，就是后 $i$ 位随便填能不能模 $m$ 余 $j$。
这点东西能有什么用？我们发现，两个数的位数相等，如果一个数的第一位大于另一个数的第一位，那么这个数后面就算全是 $0$ 也比另外一个数字大，有了这个结论，这一题就很简单了。
从高到低逐位确定，先从 $9$ 开始是，如果后面可以拼出适当的模数使得其是 $m$ 的倍数，那就选它，继续往第一位的地方试就可以了。
#include <bits/stdc++.h>
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
#define foR(i, a, b) for (int i = (a); i >= (b); i --)
using namespace std;
int m;
int f[2005][2005], pre[2005];
char s[2005];
int main () {
scanf ("%s%d", s + 1, &m);
int len = strlen (s + 1);
pre[0] = 1;
For (i, 1, 2000) pre[i] = pre[i - 1] * 10 % m;
f[len + 1][0] = 1;
foR (i, len + 1, 2) {
if (s[i - 1] == '?') {
For (k, 0, 9)
For (j, 0, m - 1) f[i - 1][(j + pre[len + 1 - i] * k % m) % m] |= f[i][j];
} else {
For (j, 0, m - 1)
f[i - 1][(j + pre[len + 1 - i] * (s[i - 1] - '0') ) % m] |= f[i][j];
}
}
if (!f[1][0]) {
cout << "Impossible";
return 0;
}
int cur = 0;
For (i, 1, len) {
if (s[i] == '?') {
foR (j, 9, 0) {
if (f[i + 1][(cur - pre[len - i] * j % m + m) % m]) {
cout << j;
cur = (cur - pre[len - i] * j % m + m) % m;
break;
}
}
} else {
cout << s[i];
cur = (cur - pre[len - i] * (s[i] - '0') % m + m) % m;
}
}
return 0;
}
T3 居然是原！二话没说直接贺！讲下大概思路吧。如果有任意两幅画是包含关系，那么只取大的就行了，这样以后按长升序排序必然有宽单调下降。
设 $f_i$ 为打包 $1\cdots i$ 的最小花费，$f_i=\min{f_{j-1} + b_j * a_i}$，显然是个斜率优化，然而直接贺数组开小也就挂了 $20pts$？
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#define ll long long
#define reg register
#define fo(a,b,c) for(reg ll a=b;a<=c;a++)
#define re(a,b,c) for(reg ll a=b;a>=c;a--)
#define pii pair<ll,ll>
#define fi first
#define pb push_back
#define se second
#define mod 1000000007
#define inf mod
using namespace std;
inline ll gi()
{
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
ll _=1;
const int N=300005;
ll ans[N],f[N];
struct IO
{
ll x,y;
}p[N],pp[N];
pii q[N];
bool co(IO a,IO b)
{
if(a.x!=b.x) return a.x<b.x;
else return a.y>b.y;
}
ll X(ll a,ll b)
{
return a-b;
}
ll Y(ll a,ll b)
{
return a-b;
}
ll stk[N];
void sol()
{
ll n=gi(),h=1,t=1;
fo(i,1,n)
{
pp[i].x=gi(),pp[i].y=gi();
}
ll top=0;
sort(pp+1,pp+1+n,co);
fo(i,1,n)
{
while(top&&pp[i].y>pp[stk[top]].y)
{
top--;
}
top++;
stk[top]=i;
}
fo(i,1,top)
{
p[i]=pp[stk[i]];
}
n=top;
/* cout<<'\n';
fo(i,1,n)
{
cout<<p[i].x<<" "<<p[i].y<<'\n';
}*/
q[1].fi=-p[1].y;
ll la=0;
fo(i,1,n)
{
while(h<t&&X(q[h+1].fi,q[h].fi)*p[i].x>=Y(q[h+1].se,q[h].se))
{
h++;
}
/* fo(j,h,t)
{
cout<<"TEST "<<i<<" "<<j<<" "<<q[j].fi<<" "<<q[j].se<<'\n';
}*/
// cout<<q[h].fi<<" "<<q[h].se<<'\n';
f[i]=q[h].se-q[h].fi*p[i].x;
ll x=-p[i+1].y,y=f[i];
while(h<t&&Y(y,q[t].se)*X(q[t].fi,q[t-1].fi)<=Y(q[t].se,q[t-1].se)*X(x,q[t].fi))
{
t--;
}
t++;
q[t].fi=x;
q[t].se=y;
}
/* fo(i,1,n)
{
cout<<f[i]<<" ";
}*/
cout<<f[n];
}
int main()
{
// _=gi();
while(_--)
{
sol();
// printf("\n");
}
return 0;
}
标签：YACS,pp,ch,题解,ll,甲组,include,top,define From： https://www.cnblogs.com/Xy-top/p/17768492.html