A - fraction
咕
B - three arrays
咕
C - geometric problem
咕
D - equation
求出所有使绝对值号内表达式变号的 x 分界点并排序,然后对于分成的若干个区间去绝对值号解方程即可。
E - permutation 1
由于 K 较小,当 N 较大时,差值序列字典序第 K 小的排列一定形如 n,1,2,3\dots,所以不断地确定最终排列的前若干位,直到剩余的排列个数恰好大于等于 K,然后暴力枚举排列并排序即可。
F - string matching
咕
G - permutation 2
咕
H - line symmetric
咕
I - discrete logarithm problem
咕
J - find hidden array
咕
Code
A - fraction
B - three arrays
C - geometric problem
D - equation
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 100005
#define INF 0x3f3f3f3f
#define pii pair<int, int>
#define int long long
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
struct Frac {
int u, d;
Frac() {}
Frac(int _u, int _d) {
int sgn = 1;
if (_u < 0) {
_u *= -1, sgn *= -1;
}
if (_d < 0) {
_d *= -1, sgn *= -1;
}
int g = gcd(_u, _d);
u = _u * sgn / g, d = _d / g;
}
friend ostream &operator<<(ostream &out, const Frac &a) {
out << a.u << "/" << a.d;
return out;
}
friend bool operator<(const Frac &a, const Frac &b) {
return a.u * b.d < b.u * a.d;
}
friend bool operator>(const Frac &a, const Frac &b) {
return a.u * b.d > b.u * a.d;
}
friend bool operator==(const Frac &a, const Frac &b) {
return a.u * b.d == b.u * a.d;
}
friend bool operator<=(const Frac &a, const Frac &b) {
return a.u * b.d <= b.u * a.d;
}
};
int T, n, c;
int a[MAX_N];
int b[MAX_N];
int id[MAX_N];
Frac p[MAX_N];
int cmp(int a, int b) {
return p[a] > p[b];
}
signed main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n >> c;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
b[i] = -b[i];
}
for (int i = 1; i <= n; i++) {
p[i] = Frac(b[i], a[i]);
id[i] = i;
}
sort(id + 1, id + 1 + n, cmp);
vector<Frac> v;
int sa = 0, sb = 0;
for (int i = 1; i <= n; i++) {
sa += a[i], sb += b[i];
}
if (!sa && !(c + sb)) {
cout << "-1" << endl;
continue;
}
if (sa) {
Frac res(c + sb, sa);
if (p[id[1]] <= res && res <= Frac(INF, 1)) {
v.push_back(res);
}
}
p[n + 1] = Frac(-INF, 1), id[n + 1] = n + 1;
bool flag = false;
for (int i = 1; i <= n; i++) {
sa -= 2 * a[id[i]], sb -= 2 * b[id[i]];
if (!sa && !(c + sb)) {
flag = true;
break;
}
if (sa) {
Frac res(c + sb, sa);
if (p[id[i + 1]] <= res && res <= p[id[i]]) {
v.push_back(res);
}
}
}
if (flag) {
cout << "-1" << endl;
} else {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
cout << (int)v.size();
for (int i = 0; i < v.size(); i++) {
cout << " " << v[i];
}
cout << endl;
}
}
}
E - permutation 1
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 25
using namespace std;
int T, n, K, cnt;
int p[MAX_N];
bool vis[MAX_N];
int getmin() {
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
vis[i] = true;
return i;
}
}
return -1;
}
int getfac(int x) {
int ans = 1;
for (int i = 2; i <= x; i++) {
ans = ans * i;
if (ans > K) {
return ans;
}
}
return ans;
}
bool cmp(const vector<int> &a, const vector<int> &b) {
int ta, tb;
if (cnt) {
ta = a[0] - p[cnt], tb = b[0] - p[cnt];
if (ta != tb) {
return ta < tb;
}
}
for (int i = 0; i < a.size() - 1; i++) {
ta = a[i + 1] - a[i];
tb = b[i + 1] - b[i];
if (ta != tb) {
return ta < tb;
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n >> K;
for (int i = 1; i <= n; i++) {
vis[i] = false;
}
int t = n;
cnt = 0;
if (getfac(t - 2) > K) {
p[++cnt] = n, vis[n] = true, t--;
p[++cnt] = 1, vis[1] = true, t--;
while (getfac(t - 1) > K) {
p[++cnt] = getmin(), t--;
}
}
vector<int> v;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
v.push_back(i);
}
}
vector<vector<int> > vs;
do {
vs.push_back(v);
} while (next_permutation(v.begin(), v.end()));
sort(vs.begin(), vs.end(), cmp);
for (int x : vs[K - 1]) {
p[++cnt] = x;
}
cout << p[1];
for (int i = 2; i <= n; i++) {
cout << " " << p[i];
}
cout << endl;
}
}
F - string matching
G - permutation 2
H - line symmetric
I - discrete logarithm problem
J - find hidden array