2019 Multi-University Training Contest 5
A.fraction
先解决这样一个问题:找到最小的(x,y),求解(frac{a}{b}leq frac{x}{y}leq frac{c}{d})。
这个问题可以递归求解:
若(lceilfrac{a}{b}
ceilleq lfloorfrac{c}{d}
floor),直接令(x=lceilfrac{a}{b}
ceil,y=1)即可;
否则,令式子减去左边的整数部分,然后取倒数递归即可,即:
令(t=lceilfrac{a}{b}
ceil),有
[frac{a-(t-1)*b}{b}leq frac{x-(t-1)*y}{y}leq frac{c-(t-1)*d}{d}
]
取反后即为:
[frac{c-(t-1)*d}{d}leq frac{y}{x-(t-1)*y}leq frac{b}{a-(t-1)*b}
]
之后递归求解即可。
代码如下:
void gao(ll a, ll b, ll c, ll d, ll &x, ll &y) { // a/b < x/y < c/d
ll t = (a + b - 1) / b;
if(c / d >= t) {
y = 1; x = t;
return;
}
a -= (t - 1) * b;
c -= (t - 1) * d;
gao(d, c, b, a, y, x);
x += (t - 1) * y;
}
递归中传入的是(y,x),也就是说有:
[x'=x-(t-1)*y,y'=y
]
即
[x=x'+(t-1)*y,y=y'
]
所以这个问题就解决了。
回到此题,题目要求(a=bxmod p),变换一下即有:(a=bx-py)。
根据题目条件:(0<a<b),式子即可化为:
[frac{p}{x}<frac{b}{y}<frac{p}{x-1}
]
之后问题就转化为刚才的问题了。
代码如下:
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int T;
void gao(ll a, ll b, ll c, ll d, ll &x, ll &y) { // a/b < x/y < c/d
ll t = (a + b - 1) / b;
if(c / d >= t) {
y = 1; x = t;
return;
}
a -= (t - 1) * b;
c -= (t - 1) * d;
gao(d, c, b, a, y, x);
x += (t - 1) * y;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> T;
ll p, x;
while(T--) {
cin >> p >> x;
ll b, y;
gao(p, x, p, x - 1, b, y);
ll a = b * x - p * y;
cout << a << '/' << b << '
';
}
return 0;
}
B.three arrays
考虑分别对(a,b)数组建两颗字典树,然后贪心取最长相同前缀即可。
题解的做法比较神奇,就贪心找一条(a->b->acdots)这样的链,每个数选择一个异或最小的连边。可以证明最终会形成长度不超过(2)的环,并且这样的一对是最恩爱优的。
所以找到环后将它们取出来继续重复上面过程即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int T, n;
int a[N], b[N];
struct Trie{
int ch[N * 30][2], cnt[N * 30];
int tot;
void init() {
tot = 0;
memset(ch[tot], 0, sizeof(ch[tot]));
}
int New_node() {
memset(ch[++tot], 0, sizeof(ch[tot]));
return tot;
}
void Insert(int x) {
int u = 0;
for(int i = 29; i >= 0; i--) {
int p = ((x >> i & 1) ? 1 : 0);
if(!ch[u][p]) ch[u][p] = New_node();
u = ch[u][p];
cnt[u]++;
}
}
}t1, t2;
vector <int> work() {
int u1, u2;
vector <int> ans;
while(n--) {
u1 = u2 = 0;
int x = 0;
for(int p = 29; p >= 0; p--) {
if(t1.cnt[t1.ch[u1][0]] && t2.cnt[t2.ch[u2][0]]) {
t1.cnt[t1.ch[u1][0]]--;
t2.cnt[t2.ch[u2][0]]--;
u1 = t1.ch[u1][0]; u2 = t2.ch[u2][0];
} else if(t1.cnt[t1.ch[u1][1]] && t2.cnt[t2.ch[u2][1]]) {
t1.cnt[t1.ch[u1][1]]--;
t2.cnt[t2.ch[u2][1]]--;
u1 = t1.ch[u1][1]; u2 = t2.ch[u2][1];
} else if(t1.cnt[t1.ch[u1][0]] && t2.cnt[t2.ch[u2][1]]) {
t1.cnt[t1.ch[u1][0]]--;
t2.cnt[t2.ch[u2][1]]--;
u1 = t1.ch[u1][0]; u2 = t2.ch[u2][1];
x ^= (1 << p);
} else {
t1.cnt[t1.ch[u1][1]]--;
t2.cnt[t2.ch[u2][0]]--;
u1 = t1.ch[u1][1]; u2 = t2.ch[u2][0];
x ^= (1 << p);
}
}
ans.push_back(x);
}
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> T;
while(T--) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
t1.init(); t2.init();
for(int i = 1; i <= n; i++) t1.Insert(a[i]);
for(int i = 1; i <= n; i++) t2.Insert(b[i]);
vector <int> ans = work();
sort(ans.begin(), ans.end());
for(int i = 0; i < ans.size(); i++) cout << ans[i] << "
"[i == ans.size() - 1];
}
return 0;
}
D.equation
高中数学知识即可解决,按照每部分的零点排序,然后去掉绝对值依次统计答案即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 1e5 + 5, INF = 0x3f3f3f3f;
int t, n, C;
bool cmp(ll a, ll b, ll c, ll d) {
if (a < 0)a = -a, b = -b;
if (c < 0)c = -c, d = -d;
return b * c <= a * d;
}
bool cmp2(ll a, ll b, ll c, ll d) {
if (a < 0)a = -a, b = -b;
if (c < 0)c = -c, d = -d;
return b * c < a * d;
}
struct node {
int a, b;
bool operator <(const node &rhs)const {
return cmp2(a, -b, rhs.a, -rhs.b);
}
}s[MAXN];
struct res {
int a, b;
bool operator <(const res &rhs)const {
return cmp2(b, a, rhs.b, rhs.a);
}
};
vector<res> ans;
vector <pair<ll, ll>> cc;
ll gcd(ll a, ll b) {
return !b ? a : gcd(b, a%b);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> t;
while (t--) {
cin >> n >> C;
ans.clear(); cc.clear();
for (int i = 1; i <= n; i++) {
cin >> s[i].a >> s[i].b;
}
sort(s + 1, s + 1 + n);
s[0].a = 1; s[0].b = 2000; s[n + 1].a = 1; s[n + 1].b = -2000;
ll A = 0, B = 0;
for (int i = 1; i <= n; i++) {
A -= s[i].a;
B -= s[i].b;
}
bool is_infinite = false;
for (int i = 1; i <= n + 1; i++) {
if (A == 0 && C - B == 0) {
is_infinite = true;
cout << "-1
";
break;
}
if (A == 0 && C - B != 0) {
A += 2 * s[i].a;
B += 2 * s[i].b;
continue;
}
if (cmp2(s[i - 1].a, -1 * s[i - 1].b, A, C - B)) {
if (cmp(A, C - B, s[i].a, -1 * s[i].b)) {
ans.push_back({ (int)(C - B),(int)A });
}
}
A += 2 * s[i].a;
B += 2 * s[i].b;
}
if (is_infinite) {
continue;
}
ll g;
for (int i = 0; i < ans.size(); i++) {
g = gcd(ans[i].a, ans[i].b);
ans[i].a /= g; ans[i].b /= g;
if (ans[i].a < 0 && ans[i].b < 0)ans[i].a = -ans[i].a, ans[i].b = -ans[i].b;
if (ans[i].a > 0 && ans[i].b < 0)ans[i].a = -ans[i].a, ans[i].b = -ans[i].b;
}
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++) {
cc.push_back({ ans[i].a,ans[i].b });
}
cc.erase(unique(cc.begin(), cc.end()), cc.end());
cout << cc.size() << "
"[cc.size() == 0];
for (int i = 0; i < cc.size(); i++) {
if (cc[i].first == 0)cout << "0/1" << '
';
else {
cout << cc[i].first << "/" << cc[i].second << "
"[i == cc.size() - 1];
}
}
}
return 0;
}
E.permutation 1
注意(n,k)的范围,因为有(kleq min(10^4,N!),nleq 20),那么当(nleq 9)时直接枚举所有全排列暴力即可;当(n>9)时,打表可以发现,这种情况下的差值字典序大小与原来的字典序大小相对应,并且前两位一定是(n,1),所以直接暴力枚举后面每一位即可。
代码写得有点丑陋...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 25;
int T;
int n, k;
int a[N], b[N];
ll fac[N];
bool vis[N];
void work(int n) {
vector <int> ans;
ans.push_back(n); ans.push_back(1);
memset(vis, 0, sizeof(vis));
vis[1] = vis[n] = 1;
for(int i = 3; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(vis[j]) continue;
if(fac[n - i] < k) {
k -= fac[n - i];
} else {
ans.push_back(j);
vis[j] = 1;
break;
}
}
}
for(int i = 0; i < n - 1; i++) cout << ans[i] << ' ';
cout << ans[n - 1] << '
';
}
void solve(int n) {
for(int i = 1; i <= n; i++) a[i] = i;
vector <int> ans[fac[n] + 1];
int tot = 0;
do {
tot++;
for(int i = 1; i < n; i++) ans[tot].push_back(a[i + 1] - a[i]);
} while(next_permutation(a + 1, a + n + 1));
sort(ans + 1, ans + tot + 1);
sort(a + 1, a + n + 1);
do {
int ok = 1;
for(int i = 1; i < n; i++) {
if(a[i + 1] - a[i] != ans[k][i - 1]) {
ok = 0; break;
}
}
if(ok) {
for(int i = 1; i < n; i++) cout << a[i] << ' ';
cout << a[n] << '
';
break;
}
} while(next_permutation(a + 1, a + n + 1));
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
fac[0] = 1;
for(int i = 1; i < N; i++) fac[i] = fac[i - 1] * i;
cin >> T;
while(T--) {
cin >> n >> k;
if(n >= 10) work(n);
else solve(n);
}
return 0;
}
F.string matching
扩展(KMP)模板题。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
struct ExKmp{
int Next[N];
int extend[N];
void get_next(char *s) {
int len = strlen(s + 1), p = 1, pos;
Next[1] = len;
while(p + 1 <= len && s[p] == s[p + 1]) p++;
Next[pos = 2] = p - 1;
for(int i = 3; i <= len; i++) {
int l = Next[i - pos + 1];
if(i + l < p + 1) Next[i] = l;
else {
int j = max(p - i + 1, 0);
while(i + j <= len && s[j + 1] == s[i + j]) ++j;
p = i + (Next[pos = i] = j) - 1;
}
}
}
void work(char *s, char *t) {
get_next(t);
int lens = strlen(s + 1), lent = strlen(t + 1), p = 1, pos;
while(p <= lent && s[p] == t[p]) ++p;
p = extend[pos = 1] = p - 1;
for(int i = 2; i <= lens; i++) {
int len = Next[i - pos + 1];
if(len + i < p + 1) extend[i] = len;
else {
int j = max(p - i + 1, 0);
while(i + j <= lens && j <= lent && t[j + 1] == s[i + j]) j++;
p = i + (extend[pos = i]) - 1;
}
}
}
}exkmp;
int T, n;
char s[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> T;
while(T--) {
cin >> s + 1;
exkmp.get_next(s);
n = strlen(s + 1);
ll ans = 0;
for(int i = 2; i <= n; i++) {
if(i + exkmp.Next[i] - 1 == n) ans += n - i + 1;
else ans += exkmp.Next[i] + 1;
}
cout << ans << '
';
}
return 0;
}
G.permutation 2
注意到只有中间上升的某段会对答案产生贡献,之后对上升的情况打表找规律即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, MOD = 998244353;
int n;
int x, y;
int T;
ll f[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> T;
f[1] = f[2] = f[3] = 1;
for(int i = 4; i < N; i++) f[i] = (f[i - 1] + f[i - 3]) % MOD;
while(T--) {
cin >> n >> x >> y;
int d;
if(x == 1 && y == n) {
d = n;
} else if(x == 1) {
d = y - 1;
} else if(y == n) {
d = n - x;
} else {
d = y - 1 - (x + 1) + 1;
}
cout << f[d] << '
';
}
return 0;
}