QBXT模拟赛1
总结
期望得分：(100 + 80 + 10 = 190)
实际得分：(90 + 80 + 10 = 180)
这是在清北的第一场考试，也是在清北考的最高的一次了吧。。本来以为能拿(190)的，没想到强者太多，(AK)的一群，(200)分大众分。。我好菜
思路&&代码
T1
(T1)是个简单题，却因为(1-1=0)这个点忘记去除前导零而失去了(10)分，以后要多对拍，多注意细节
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 11;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
char s[N];
string a;
int len, now, whe, pos;
int main() {
scanf("%s", s + 1);
len = strlen(s + 1), now = s[1] - '0', whe = 1, pos = 1;
for(int i = 2, x; i <= len; i++) {
x = s[i] - '0';
if(x > now) {
now = x;
whe = i;
pos = i;
}
else if(x == now) pos = i;
if(x < now) break;
}
if(whe == len || pos == len) return cout << (s + 1) << '
', 0;
for(int i = 1; i < whe; i++) a += s[i];
if(s[whe] - 1 != '0') a += s[whe] - 1;
for(int i = whe + 1; i <= len; i++) a += '9';
cout << a;
return 0;
}
T2
看式子不懂，之后手算一下发现就是个逆序对，进而发现可以转化为求哪些区间包含这对逆序对，然后这对逆序对的值乘以区间个数，式子如下
[sum_j a_j * (n - j + 1) *sum_{a_i > a_j, i < j} a_i * i
]
后面的可以用数据结构维护，发现模数是(1e12+7),两个(10^12)的数相乘会爆(long long)，所以要用快速乘
然后就做完了
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) (x & -x)
#define int long long
using namespace std;
const int N = 5e5 + 11;
const int mod = 1e12 + 7;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
int n;
int a[N], ans = 0;
int b[N], p[N], f[N];
inline int mul(int a, int b, int res = 0) {
while(b) {
if(b & 1) ans = (ans + a) % mod;
a = a + a % mod; b >>= 1;
}
return res;
}
inline int query(int x) {
int ans = 0;
for(int i = x; i; i -= lowbit(i)) ans = (ans + p[i]) % mod;
return ans;
}
const int MAX = 1e5;
inline void add(int x, int val) {
for(int i = x; i <= MAX; i += lowbit(i)) p[i] = (p[i] + val) % mod;
return;
}
signed main() {
n = read();
for(int i = 1; i <= n; i++) b[i] = a[i] = read();
sort(b + 1, b + 1 + n);
for(int i = 1; i <= n; i++) f[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
for(int i = 1; i <= n; i++) {
int now = query(n) - query(f[i]);
now = (now % mod + mod) % mod;
ans = ans + mul(now * (n - i + 1), a[i]);
ans = (ans % mod + mod) % mod;
add(f[i], a[i] * i);
}
ans = (ans % mod + mod) % mod;
cout << ans << '
';
return 0;
}
T3
直接用线段树扫描线就(over)了
还有一种神奇做法。。
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define PII pair<int, int>
#define mk(x, y) make_pair(x, y)
using namespace std;
const int N = 5e4 + 11;
const int M = 1e6 + 11;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
int n, m, a[N], b[N], c[N], d[N];
int mina, minb, maxc, maxd;
map<pair<int, int>, int> mp;
int main() {
int T = read();
while(T--) {
n = read();
mina = minb = INF;
maxc = maxd = -INF;
mp.clear();
for(int i = 1; i <= n; i++) {
a[i] = read(), b[i] = read(), c[i] = read(), d[i] = read();
mina = min(mina, a[i]);
minb = min(minb, b[i]);
maxc = max(maxc, c[i]);
maxd = max(maxd, d[i]);
mp[mk(a[i], b[i])]++;
mp[mk(a[i], d[i])]++;
mp[mk(c[i], b[i])]++;
mp[mk(c[i], d[i])]++;
}
int cnt = 0;
if(mp[mk(mina, minb)] == 1) cnt++;
if(mp[mk(mina, maxd)] == 1) cnt++;
if(mp[mk(maxc, minb)] == 1) cnt++;
if(mp[mk(maxc, maxd)] == 1) cnt++;
if(cnt != 4) {
puts("Guguwansui");
continue;
}
cnt = 0;
for(int i = 1; i <= n; i++) {
if(mp[mk(a[i], b[i])] == 1) cnt++;
if(mp[mk(a[i], d[i])] == 1) cnt++;
if(mp[mk(c[i], b[i])] == 1) cnt++;
if(mp[mk(c[i], d[i])] == 1) cnt++;
}
if(cnt == 4) puts("Perfect");
else puts("Guguwansui");
}
return 0;
}
//这题太神了我不会。