[2019 ICPC Universidad Nacional de Colombia Programming Contest] 题解
A. Amazon
Amazon has grown so much these days, it has decided to build its own subway lines to be able to supply the demand of its products. To maximize efficiency, every line is completely straight. As Jeff Bezos is the richest man on the planet, every subway line is large enough to be considered infinite on a 2D representation since good old Jeff will pay as much as necessary to cover all the planet.
Such long subway lines come with a catch: to be able to move products from one line to the other, the intersections must be strong enough to handle the weight of the cargo which is moved. After thorough research amazon scientists have concluded that an intersection is strong enough only when its subway lines form a right angle.
The engineering team has gathered pairs of locations which typically ship products between each other, for each pair the team wants to build a subway line. The team also wants to build as much strong intersections as possible. Note that is possible that more than one pair of locations may share the same subway line.
How many intersections will be built? The team wants you to help with this problem.
Input
The first line contains the number of test cases TT (1≤T≤100)(1≤T≤100).
Each test case starts with an integer nn (1≤n≤105)(1≤n≤105) which denotes the number of location pairs, next there will be nn lines with four integers x1,y1,x2,y2x1,y1,x2,y2 where (x1,y1)(x1,y1) and (x2,y2)(x2,y2) are a location pair (−2∗104≤x1,y1,x2,y2≤2∗104)(−2∗104≤x1,y1,x2,y2≤2∗104).
Output
For each test case print the number of intersections to build.
Example
input
Copy
3
3
-3 2 2 2
3 1 3 -3
-3 -3 -1 -3
3
2 -2 -4 7
0 -2 6 2
4 -2 0 0
2
0 -1 -6 1
2 5 -3 0
output
Copy
2
1
0
题意：
\(\mathit T\)组数据，每一组数据有\(\mathit n\)个直线，问这\(\mathit n\)个直线构成多少个不用的“十字路口”。
思路：
首先将直线转成斜率+一个点的表达形式，
先观察直线的点斜式公式：\(y=K*x+B,K=\frac{\Delta y}{\Delta x}\)
为了避免使用浮点数，我们用\(K=\frac{\Delta y}{\Delta x}\)的最简形式\(K=\frac{\Delta y/g}{\Delta x/g},g=gcd(\Delta y,\Delta x)\)的向量形式\((\Delta x/g,\Delta y/g)\)来表示斜率。
令\(\Delta y=\Delta y/g,\Delta x=\Delta x/g\)
为了避免\(\mathit B\)为浮点数，可以将点斜式化简为：\(\Delta{x} * y-\Delta y*x=B*\Delta x\)
因为一条之直线的\(B,\Delta x\)均是唯一的，所以可以用\(B*\Delta x\)来代替\(\mathit B\)。
然后将直线去重后需要考虑两个直线的垂直关系，
我们知道：方向向量为\(\frac{\Delta y}{\Delta x}\)的直线与方向向量为\(\frac{-\Delta y}{\Delta x}=\frac{\Delta y}{-\Delta x}\)的直线垂直。
为了避免负号在上还是在下的问题，我们统一规定负号在\(\Delta y\)上即可。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <unordered_map>
// #include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '\n' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '\n' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
struct vec
{
int x, y;
vec() {}
vec(int xx, int yy)
{
x = xx;
y = yy;
int g = gcd(x, y);
x /= g;
y /= g;
if (x < 0)
{
x = -x;
y = -y;
}
if (x == 0)y = abs(y);
}
bool operator < ( const vec & bb )const
{
if (bb.x != x)
{
return x < bb.x;
} else
{
return y < bb.y;
}
}
bool operator == ( const vec & bb )const
{
return x == bb.x && y == bb.y;
}
};
int n;
std::vector<pair<vec, int> > v;
map<vec, int> m;
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
int t;
t = readint();
while (t--)
{
v.clear();
m.clear();
n = readint();
int xa, ya, xb, yb;
vec now;
repd(i, 1, n)
{
xa = readint();
ya = readint();
xb = readint();
yb = readint();
now = vec(xa - xb, ya - yb);
v.pb(mp(now, now.x * ya - now.y * xa));
}
sort(ALL(v));
v.erase(unique(ALL(v)), v.end());
ll ans = 0ll;
for (auto &temp : v)
{
ans += m[vec(temp.fi.y, -temp.fi.x)];
m[temp.fi]++;
}
printf("%lld\n", ans );
}
return 0;
}
B. Boring Non-Palindrome
Holidays are almost over and our dear friend Mr. Potato Head wants to enjoy his last days of vacations with different fun activities like solving equations, calculating areas of figures, among others.
Currently, he is playing with different strings, although he finds that most of strings are boring non-palindromic strings. That is why Mr. Potato Head will transform any string into a palindrome inserting characters at the end of the corresponding string.
However, Mr. Potato Head does not want to spend his lasts days of holidays only inserting characters in strings, so he will insert the minimum possible of characters to convert the boring non-palindromic string into a fun palindromic one.
Can you guess the fun strings Mr. Potato Head created from boring ones?
Input
Input consists of a single line with a non-empty string without spaces.
The length of the string is at most 50005000.
Output
Print one single line with the string after the changes of Mr. Potato Head.
Examples
input
Copy
helloworld
output
Copy
helloworldlrowolleh
input
Copy
anitalavalatina
output
Copy
anitalavalatina
Note
A palindrome is a string that reads the same backwards as forwards
题意：
给定一个字符串，你可以在字符串尾部加入尽力少的任意字符，使其字符串变成回文串。
思路：
枚举加给定字符串的前缀，将其前缀翻转后加到给定字符串尾部判断是否为回文串。
代码：
/*** TEMPLATE CODE * * STARTS HERE ***/
#define DEBUG_Switch 0
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
string str;
cin >> str;
int n = str.size();
repd(i, 0, n - 1)
{
string left = str.substr(0, i);
reverse(ALL(left));
string now = str + left;
string rev = now;
reverse(ALL(rev));
if (now == rev)
{
cout << now << endl;
break;
}
}
return 0;
}
C. Common Subsequence
Manuel thinks that Diego is his long lost brother. But Diego thinks Manuel is wrong, and to prove it, he got DNA samples from himself and Manuel. Now Diego has given you the DNA samples and it is your task to say whether they are brothers or not.
The DNA samples of Diego and Manuel are strings AA and BB, both have length nn (1≤n≤1051≤n≤105) and consist of only the characters 'A', 'T', 'G' and 'C'. If there is a common subsequence of AA and BB that has length greater than or equal to 0.99×n0.99×n, then Diego and Manuel are brothers, in other case, they are not.
Input
The input consists of two lines with strings AA and BB, respectively.
Output
You should output a single line with "Long lost brothers D:" (without quotes) if Diego and Manuel are brothers, and "Not brothers 😦" (without quotes) if they are not.
Examples
input
Copy
GAATTGCGTACAATGC
GAATTGCGTACAATGC
output
Copy
Long lost brothers D:
input
Copy
CCATAGAGAA
CGATAGAGAA
output
Copy
Not brothers :(
Note
A subsequence of a string XX is any string that you can get by removing any number of characters from XX.
A common subsequence of strings XX and YY is a string that is a subsequence of both XX and YY.
题意：
给定两个长度均为\(\mathit n\)的字符串\(A,B\) ，如果\(A,B\)的最长公共子序列的长度大于\(0.99 \times n\)就输出“Long lost brothers D:”，否则输出“Not brothers 😦”。
思路：
定义动态规划状态：\(dp[i][j]\)为字符串\(\mathit A\)摒弃了\(\mathit i\)个字符，字符串\(\mathit B\) 摒弃了\(\mathit j\)个字符后获得的LCS长度。
当\(i>0.01 \times n \or j> 0.01 \times n\)时，\(dp[i][j]\)一定小于\(0.99 \times n\)，所以我们\(i,j\)只需要枚举到\(0.01 \times n\)即可。
代码：
char a[maxn];
char b[maxn];
int n;
int dp[1010][1010];
int main()
{
#if DEBUG_Switch
freopen("C:\\code\\input.txt", "r", stdin);
#endif
//freopen("C:\\code\\output.txt","r",stdin);
scanf("%s", a);
scanf("%s", b);
n = strlen(a);
int m = n / 100 + 1;
int ans = 0;
repd(i, 0, m - 1)
{
repd(j, 0, m - 1)
{
while (i + dp[i][j] < n && j + dp[i][j] < n && a[i + dp[i][j]] == b[j + dp[i][j]])
{
dp[i][j]++;
}
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
ans = max(ans, dp[i][j]);
}
}
if (ans * 100 >= n * 99)
{
printf("Long lost brothers D:\n");
} else
{
printf("Not brothers :(\n");
}
return 0;
}
剩下题待补。
京公网安备 11010502036488号