……
T1
貪心，因為是一個小于等于𝑥的最大的數， 是以找到第一個後邊比前邊要小的數，讓前邊的數減1即可， 注意前導0。
/*
Date:
Source:
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define orz cout << "AK IOI"
using namespace std;
const int maxn = 1000010;
inline int read()
{
int 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 << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 ^ '0');
}
int len, num[maxn], flag, head;
char s[maxn];
int main()
{
scanf("%s", s + 1);
len = strlen(s + 1);
for(int i = 1; i <= len; i++) num[i] = s[i] - '0';
if(len == 1) {printf("%d", num[1]); return 0;}
for(int i = 1; i <= len; i++)
{
if(num[i] < num[i - 1])
{
flag = i - 1;
while(num[flag] == num[flag - 1]) flag--;
num[flag]--;
break;
}
}
for(int i = 1; i <= len; i++)
if(num[i] != 0) {head = i; break;}
for(int i = head; i <= flag; i++) printf("%d", num[i]);
for(int i = flag + 1; i <= len; i++) printf("9");
return 0;
}
T2
60pts
暴力模拟.
80pts
算出每個逆序對做的貢獻就是這個逆序對所在區間的個數，然後利用乘法原理算出這個逆序對所在的區間的個數，就是 \((n - j + 1) \times i\)。
/*
Date:
Source:
konwledge:
*/
#include <iostream>
#include <cstdio>
#define orz cout << "AK IOI"
#define int long long
using namespace std;
const int mod = 1e12 + 7;
const int maxn = 4e4 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) {X = ~(X - 1); putchar('-');}
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, a[maxn], ans;
int get(int x, int y)
{
if(x == 1 || y == n) return 0;
return (n - 2 - (y - x + 1) + 1);
}
signed main()
{
n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
if(a[j] < a[i]) ans = (ans + a[i] * a[j] * (n - j + 1) * i % mod) % mod;
printf("%lld", ans);
return 0;
}
100pts
每個逆序對對答案的貢獻就是\(a[i] \times a[j] \times (n - j + 1) \times i\)。
移項可以得到 \(a[i] \times i \times a[j] \times (n - j + 1)\)。
将平時的樹狀數組求逆序對，修改的權值改為 \(a[i] \times i\)。
每次找到比目前大且出現的早的計算。
/*
Date:
Source:
konwledge:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define orz cout << "AK IOI"
#define int long long
#define lowbit(x) (x & (-x))
using namespace std;
const int mod = 1e12 + 7;
const int maxn = 4e4 + 10;
inline int read()
{
int f = 0, x = 0; char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
inline void print(int X)
{
if(X < 0) {X = ~(X - 1); putchar('-');}
if(X > 9) print(X / 10);
putchar(X % 10 + '0');
}
int n, ans, a[maxn], b[maxn], c[maxn], t[maxn];
void add(int x, int num)
{
while(x <= n) {t[x] += num; x += lowbit(x);}
}
int query(int x)
{
int res = 0;
while(x != 0) {res += t[x]; x -= lowbit(x);}
return res;
}
int mul(int a, int b)
{
int res = 0;
while(b)
{
if(b & 1) res = (res + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return res;
}
signed main()
{
n = read();
for(int i = 1; i <= n; i++) a[i] = c[i] = read();
sort(c + 1, c + n + 1);
int cnt = unique(c + 1, c + n + 1) - c - 1;
for(int i = 1; i <= n; i++) b[i] = lower_bound(c + 1, c + cnt + 1, a[i]) - c;
for(int i = 1; i <= n; i++)
{
int res = (query(cnt) - query(b[i]) + mod) % mod;
ans = (ans + mul(mul(res, a[i]), n - i + 1)) % mod;
add(b[i], mul(a[i], i));
}
printf("%lld\n", (ans + mod) % mod);
return 0;
}
T3
比較坑的地方是它一個是左下角，一個是右上角， 按坐标系那樣來，給不認真讀題的孩子造成了困擾。（比如我）。
思維題，一個完美的矩形除了四個頂點可能會出現1個點，其他的地方都會出現2或4個點。
不過不開 \(O_2\) 會 T。
/*
Date:
Source:
knowledge:
*/
#include <iostream>
#include <cstdio>
#include <map>
#define orz cout << "AK IOI" << "\n"
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define Max(x, y) ((x) > (y) ? (x) : (y))
using namespace std;
const int maxn = 50010;
inline int read()
{
int 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 << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
inline void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 ^ '0');
}
int T, n, a[maxn], b[maxn], c[maxn], d[maxn], sum, mina, minb, maxc, maxd;
map<int, map<int, int> > mp;
void init()
{
mp.clear();
sum = 0, mina = 0x3f3f3f3f, minb = 0x3f3f3f3f, maxc = -0x3f3f3f3f, maxd = -0x3f3f3f3f;
}
void cmp(int a, int b, int c, int d)
{
mina = min(mina, a);
minb = min(minb, b);
maxc = max(maxc, c);
maxd = max(maxd, d);
}
bool check()
{
if(sum != (maxc - mina) * (maxd - minb)) return 0;
int js = 0;
for(int i = 1; i <= n; i++)
{
mp[a[i]][b[i]]++;
mp[a[i]][d[i]]++;
mp[c[i]][b[i]]++;
mp[c[i]][d[i]]++;
if(mp[a[i]][b[i]] != 2 && mp[a[i]][b[i]] != 4) js++;
if(mp[a[i]][d[i]] != 2 && mp[a[i]][d[i]] != 4) js++;
if(mp[c[i]][b[i]] != 2 && mp[c[i]][b[i]] != 4) js++;
if(mp[c[i]][d[i]] != 2 && mp[c[i]][d[i]] != 4) js++;
if(mp[a[i]][b[i]] == 2 || mp[a[i]][b[i]] == 4) js--;
if(mp[a[i]][d[i]] == 2 || mp[a[i]][d[i]] == 4) js--;
if(mp[c[i]][b[i]] == 2 || mp[c[i]][b[i]] == 4) js--;
if(mp[c[i]][d[i]] == 2 || mp[c[i]][d[i]] == 4) js--;
}
return js == 4;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
T = read();
while(T--)
{
n = read();
init();
for(int i = 1; i <= n; i++)
{
a[i] = read(), b[i] = read(), c[i] = read(), d[i] = read();
sum += (c[i] - a[i]) * (d[i] - b[i]);
cmp(a[i], b[i], c[i], d[i]);
}
if(check()) puts("Perfect");
else puts("Guguwansui");
}
//fclose(stdin);
//fclose(stdout);
return 0;
}