• 写在前面
• T1
• T2
• T3

写在前面

因为没有什么任务，不知道干什么，所以就跟着一区玩了玩这套模拟赛题。

比赛地址

期望得分：\(100+100+0=200\)

实际得分：\(90+90+0=180\)

小细节没处理好，导致两个题都挂分了/kx

这套模拟赛整体难度略低吧，做着非常顺手。

最后一题竟然是个思路题，然而自己一直在想数据结构维护。/kx （暴力应该能拿 \(60\)，懒得打了）

T1

给定一个数 \(x\)，求一个最大的 \(\le x\) 的数，要求这个数的每一位单调不降。
\(x \le 10^{10^5}\)

比较显然的是：\(x\) 从高位往低位取，能取满就取满。

不能取满的情况是存在一个 \(i\)，满足 \(a_i > a_{i+1}\)。 （a_i 是从高到低的第 \(i\) 位）

这个时候考虑从前面找一个位 \(-1\)，然后把剩下的都填成 \(9\)。

正确找法就是从 \(i\) 向前找，找到第一个满足 \(a_i > a_{i-1}\) 的位置，位置 \(i\) 就是要减一的位置。

注意特判最高位为 \(1\) 的情况和 \(x=0\) 的情况。

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 2e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

char s[MAXN];
int a[MAXN], n;
int b[MAXN];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

int main()
{
//    freopen("in.in","r",stdin);
//    freopen("out.out","w",stdout);
	cin >> s + 1;
	n = strlen(s + 1);
	if(n == 1 && s[1] == '0') {
	    puts("0");
	    return 0;
    }
	for(int i = 1; i <= n; ++i) a[i] = s[i] - '0';
	for(int i = 1; i <= n; ++i) {
	    b[i] = a[i];
	    if(i != n && a[i] > a[i + 1]) {
	        for(int j = i; j >= 1; --j) {
	            if(a[j] > a[j - 1]) {
	                b[j]--;
	                for(int k = j + 1; k <= n; ++k) b[k] = 9;
	                break;
                }
            }
            break;
        }
    }
    if(b[1] == 0) {
        for(int i = 1; i < n; ++i) printf("9");
        puts("");
    } else {
        for(int i = 1; i <= n; ++i) printf("%d", b[i]);
        puts("");
    }
    return 0;
}

T2

给你一个长度为 \(n\) 的序列 \(a\)，求：

\[\sum_{l = 1}^{n} \sum_{r=l}^{n} \sum_{i=l}^{r} \sum_{j = i+1,a_j<a_i}^{r} a_i \times a_j \]

对 \(10^{12}+7\) 取模。
\(n \le 4 \times 10^4, 1 \le a_i \le 10^{12}\)

朴素的暴力是 \(\mathcal O(n^4)\)，不多说了。

考虑最后两个 \(\sum\)，考虑枚举 \(j\)，把 \(a\) 离散化一下，把值域当下标用树状数组维护 所有 \(i < j, a_i > a_j\) 的贡献，每个 \(j\) 和多少 \(a_i\) 有贡献直接查即可。时间复杂度 \(\mathcal O(n^3 \log n)\)

考虑一对满足 \(a_i > a_j, i < j\) 的 \((i,j)\)，会做出多少次贡献，这取决与 \(l,r\) 的取值方案，共 \(i \times (n-j+1)\) 种。

所以一个有贡献的 \((i,j)\) 造成的总贡献为 \(i \times a_i \times (n-j+1) \times a_j\)，可以像上面那个做法一样，把前两项放一起扔进树状数组统计，然后枚举后面的 \(j\)，总复杂度 \(\mathcal O(n \log n)\)。

注意模数为 \(10^{12}+7\)，相乘可能会爆 long long。如果使用快速乘会多一个 \(\log\)，使用 __int128 的话不带 \(\log\)。

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e12+7;

int n, ans = 0;
int a[MAXN], b[MAXN], date[MAXN], Cnt = 0;
int sum[MAXN];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

namespace Bit {
    int sum[MAXN];
    int lb(int x) { return x & -x; }
    void Modify(int x, int k) { for(; x <= Cnt; x += lb(x)) sum[x] = (sum[x] + k) % mod; }
    int Query(int x) { int res = 0; for(; x; x -= lb(x)) res = (res + sum[x]) % mod; return res; }
}

void Print(int x) {
    if(x > 9) Print(x / 10);
    putchar(x % 10 + '0');
}

int Mul(int x, int p) {
    int res = 0;
    while(p) {
        if(p & 1) res = (res + x) % mod;
        x = (x + x) % mod, p >>= 1;
    }
    return res;
}

signed main()
{
//    freopen("B.in","r",stdin);
//    freopen("B.out","w",stdout);
	n = read();
	for(int i = 1; i <= n; ++i) date[i] = a[i] = read();
    sort(date + 1, date + n + 1), date[0] = -INF;
    for(int i = 1; i <= n; ++i) if(date[i] != date[i - 1]) date[++Cnt] = date[i];
    for(int i = 1; i <= n; ++i) b[i] = lower_bound(date + 1, date + Cnt + 1, a[i]) - date;
    for(int i = 1; i <= n; ++i) {
        int res = (Bit::Query(Cnt) - Bit::Query(b[i]) + mod) % mod;
        ans = (ans + Mul(Mul(res, a[i]), (n - i + 1))) % mod;
        Bit::Modify(b[i], Mul(a[i], i));
    }
    printf("%lld\n", (ans + mod) % mod);
    return 0; 
}

T3

给你 \(n\) 个矩形，看看能不能不重叠的组成一个大矩形，边相交只算覆盖一次。每个矩形以 \((a,b,c,d)\) 的形式给出，\((a,b)\) 表示左下角坐标， \((c,d)\) 表示右上角。

对于 \(a_i \le 200\) 的数据和 \(n \le 1000\) 的数据都可以用二维差分在 \(\mathcal O(n^2)\) 的复杂度内判断出来，预计得分 \(60\)，懒得写了。

来看正解：

这是一个思路题，通过手模样例可以发现一个完美的矩形除了四个顶点可能会出现 \(1\) 个点，其他的地方都会出现 \(2\) 或 \(4\) 个点。

然后扔个 \(map\) 维护就做完了，记得清空。

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

int T, n;
int Maxx = -INF, Minx = INF, Maxy = -INF, Miny = INF;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
map<int, map<int, int>> Map;

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

bool Check() {
    int cnt = 0;
    Map.clear();
    for(int i = 1; i <= n; ++i) {
        Map[a[i]][b[i]]++, Map[c[i]][d[i]]++, Map[a[i]][d[i]]++, Map[c[i]][b[i]]++;
    }
    for(int i = 1; i <= n; ++i) {
        if(Map[a[i]][b[i]] != 2 && Map[a[i]][b[i]] != 4) cnt++;
        if(Map[a[i]][d[i]] != 2 && Map[a[i]][d[i]] != 4) cnt++;
        if(Map[c[i]][b[i]] != 2 && Map[c[i]][b[i]] != 4) cnt++;
        if(Map[c[i]][d[i]] != 2 && Map[c[i]][d[i]] != 4) cnt++;
    }
    return cnt == 4;
}

signed main()
{
	T = read();
	while(T--) {
	    n = read(); int sum = 0;
	    Maxx = -INF, Minx = INF, Maxy = -INF, Miny = INF;
	    for(int i = 1; i <= n; ++i) {
	        a[i] = read(), b[i] = read(), c[i] = read(), d[i] = read();
	        if(a[i] > c[i]) swap(a[i], c[i]);
	        if(b[i] > d[i]) swap(b[i], d[i]);
	        Minx = min(Minx, a[i]);
	        Maxx = max(Maxx, c[i]);
	        Miny = min(Miny, b[i]);
	        Maxy = max(Maxy, d[i]);
	        sum += (c[i] - a[i]) * (d[i] - b[i]);
        }
        if(sum != (Maxx - Minx) * (Maxy - Miny)) {
            puts("Guguwansui");
            continue;
        }
        if(Check()) puts("Perfect");
        else puts("Guguwansui");
    }
    return 0;
}