互补二元组

Xi + Xj = Yi + Yj等价于Xi - Yi + Xj - Yj = 0 ，对每个二元组计算其x与y的差，每次加上其相反数的个数。

#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include

void makedata() {
freopen("input.txt", "w", stdout);
fclose(stdout);
}

map mp;

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
//makedata();
std::ios::sync_with_stdio(), cin.tie();
int n, x, y;
lint ans = ;
cin >> n;
for (int i = ; i < n; i++) { cin >> x >> y;
if (mp.find(y - x) != mp.end()) ans += mp[y - x];
mp[x - y]++;
}
cout << ans << endl;
return ;
}

寻找切线

找到横坐标最大的点，如果这样的点不止一个，直接输出2个。否则计算其他所有点到这一点的斜率，取最大或最小的那个点。

#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include

void makedata() {
freopen("input.txt", "w", stdout);
fclose(stdout);
}

double k[], x[], y[];

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
//makedata();
std::ios::sync_with_stdio(), cin.tie();
int n, i1 = , i2 = -;
cin >> n;
for (int i = ; i < n; i++) { cin >> x[i] >> y[i];
if (x[i] >= x[i1]) i1 = i;
}
for (int i = ; i < n; i++) { if (x[i] == x[i1] && i != i1) i2 = i; } if (i2 != -) { if (i1 > i2) swap(i1, i2);
cout << i1 + << ' ' << i2 + << endl; return ; } for (int i = ; i < n; i++) { if (i == i1) k[i] = -1e10; else k[i] = (y[i] - y[i1]) / (x[i] - x[i1]); } i2 = ; for (int i = ; i < n; i++) { if (k[i] > k[i2]) i2 = i;
}
if (i1 > i2) swap(i1, i2);
cout << i1 + << ' ' << i2 + << endl;
return ;
}

LR问题

这题出的有问题，因为并不存在什么“最少多少步”的说法，能的话步数是一定的，不能就不能。首先，不看_的话，两个串L和R的顺序应该是一样的。s中L的位置应在t中其对应的L的位置的右边，R在左边，每次加上对应位置坐标的差值就可以。

#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include

void makedata() {
freopen("input.txt", "w", stdout);
fclose(stdout);
}

char s[], t[];
VI vs, vt;

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
//makedata();
//std::ios::sync_with_stdio(0), cin.tie(0);
scanf("%s", s);
scanf("%s", t);
int n = strlen(s);
vs.clear();
vt.clear();
for (int i = ; i < n; i++) { if (s[i] != '_') vs.push_back(s[i]); if (t[i] != '_') vt.push_back(t[i]); } bool ok = true; if (vs.size() != vt.size()) ok = false; for (int i = ; i < min(vs.size(), vt.size()); i++) { if (vs[i] != vt[i]) { ok = false; break; } } if (!ok) { cout << - << endl; return ; } int ans = ; vs.clear(); vt.clear(); for (int i = ; i < n; i++) { if (s[i] == 'L') vs.push_back(i); if (t[i] == 'L') vt.push_back(i); } for (int i = ; i < min(vs.size(), vt.size()); i++) { if (vs[i] < vt[i]) ok = false; else ans += vs[i] - vt[i]; } vs.clear(); vt.clear(); for (int i = ; i < n; i++) { if (s[i] == 'R') vs.push_back(i); if (t[i] == 'R') vt.push_back(i); } for (int i = ; i < min(vs.size(), vt.size()); i++) { if (vs[i] > vt[i]) ok = false;
else ans += vt[i] - vs[i];
}
if (!ok) cout << - << endl;
else cout << ans << endl;
return ;
}

推断大小关系

对于x<y，连一条从x指向y的边；对于x=y，连一条从x指向y的边和从y指向x的边。当存在从1到n或从n到1的路径时，能推断大小关系。

#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include

void makedata() {
freopen("input.txt", "w", stdout);
fclose(stdout);
}

bool f1[], fn[];
VI G[];
void dfs1(int x) {
if (f1[x]) return;
f1[x] = true;
for (int i = ; i < G[x].size(); i++) dfs1(G[x][i]);
}

void dfsn(int x) {
if (fn[x]) return;
fn[x] = true;
for (int i = ; i < G[x].size(); i++) dfsn(G[x][i]);
}

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
//makedata();
//std::ios::sync_with_stdio(0), cin.tie(0);
int n, m, x, y;
char ch;
memset(f1, false, sizeof(f1));
memset(fn, false, sizeof(fn));
scanf("%d%d\n", &n, &m);
f1[] = true, fn[n] = true;
for (int i = ; i <= m; i++) {
scanf("A%d %c A%d\n", &x, &ch, &y);
G[x].push_back(y);
if (f1[x]) dfs1(y);
if (fn[x]) dfsn(y);
if (ch == '=') {
G[y].push_back(x);
if (f1[y]) dfs1(x);
if (fn[y]) dfsn(x);
}
if (f1[n] || fn[]) {
printf("%d\n", i);
return ;
}
}
printf("-1\n");
return ;
}