T1 Luogu P5427 [USACO19OPEN]Left Out
Luogu P5427 [USACO19OPEN]Left Out
正解：
把第一行第一列全化为0
若有解，则解只有以下三种位置：（1，1）、第一行或第一列（除（1，1）外）、剩下的区域中。我们称剩下的区域为S。
若答案在S中，目标位置此时一定为1并且S的其他部分全部为0
若答案在（1，1），则S一定此时全部为1（翻转第一行再翻转第一列后，图中只有（1，1）为0）
若答案在第一行或第一列（除（1，1））上，则目标位置所在列或行在S区域中一定全部为1且S区域其他部分全部为0（翻转该列或行后，图中只有目标位置为1）
若不符合这三种情况，则无解
CODE
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, a[MAXN][MAXN], r[MAXN], c[MAXN];
char s[MAXN];
inline void revR(int i) { for(int j = 1; j <= n; ++j) a[i][j] ^= 1; }
inline void revC(int i) { for(int j = 1; j <= n; ++j) a[j][i] ^= 1; }
int main () {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%s", s+1);
for(int j = 1; j <= n; ++j)
a[i][j] = s[j] == 'L';
}
for(int i = 1; i <= n; ++i) if(a[i][1]) revR(i);
for(int i = 1; i <= n; ++i) if(a[1][i]) revC(i);
int sum = 0;
for(int i = 2; i <= n; ++i)
for(int j = 2; j <= n; ++j)
r[i] += a[i][j], c[j] += a[i][j],
sum += a[i][j];
if(sum == (n-1)*(n-1)) { printf("1 1
"); return 0; }
if(sum == n-1) {
for(int i = 2; i <= n; ++i)
if(c[i] == sum) { printf("%d %d
", 1, i); return 0; }
for(int i = 2; i <= n; ++i)
if(r[i] == sum) { printf("%d %d
", i, 1); return 0; }
}
if(sum == 1) {
for(int i = 2; i <= n; ++i)
for(int j = 2; j <= n; ++j)
if(a[i][j]) { printf("%d %d
", i, j); return 0; }
}
puts("-1");
}
考试时看了看，想到枚举(i,j)作为答案，然后把i行j列全清为0，然后判断剩下的是否全是1，但是这样是n^4，然后就没想了，直接去写了第二题，然后这题就没写。（貌似有人n^4加bitset优化，然后遇到不满足的就break然后过掉了。。）没有想到正解。最后时间没了。。
T2 [USACO19OPEN]Cow Steeplechase II
[USACO19OPEN]Cow Steeplechase II
正解：
扫描线+set，没有相交前线段相对位置是不变的，于是用set维护，每次插入删除就特判一下相邻的线段
是否有交就行了。
CODE
代码写得比较丑
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
int n; LL X;
struct point {
LL x, y; point(){} point(LL x, LL y):x(x), y(y){}
inline point operator -(const point &o)const { return point(x-o.x, y-o.y); }
};
struct node {
LL v; int tp, id;
node(){}
node(LL v, int tp, int id): v(v), tp(tp), id(id){}
inline bool operator <(const node &o)const {
return v == o.v ? tp < o.tp : v < o.v;
}
}q[MAXN<<1];
struct line {
point u, v; int id;
inline bool operator <(const line &o)const {
double Y = v.x == u.x ? u.y : u.y + 1.0 * (v.y - u.y) / (1.0*v.x - u.x) * (X - u.x);
double oY = o.v.x == o.u.x ? o.u.y : o.u.y + 1.0 * (o.v.y - o.u.y) / (1.0*o.v.x - o.u.x) * (X - o.u.x);
return Y < oY;
}
}L[MAXN];
set<line>st;
set<line>::iterator it1, it2;
inline double Cross(point A, point B) { return 1.0 * A.x * B.y - 1.0 * A.y * B.x; }
inline bool jiao(line i, line j) {
return Cross(i.v-i.u, j.u-i.u) * Cross(i.v-i.u, j.v-i.u) <= 0 && Cross(j.v-j.u, i.u-j.u) * Cross(j.v-j.u, i.v-j.u) <= 0;
}
int main () {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%lld%lld%lld%lld", &L[i].u.x, &L[i].u.y, &L[i].v.x, &L[i].v.y);
if(L[i].u.x > L[i].v.x) swap(L[i].u, L[i].v);
q[i] = node(L[i].u.x, 0, i);
q[n+i] = node(L[i].v.x, 1, i);
L[i].id = i;
}
sort(q + 1, q + n*2 + 1);
int IDx, IDy;
for(int i = 1; i <= 2*n; ++i) {
X = q[i].v;
if(q[i].tp == 0) {
it1 = st.lower_bound(L[q[i].id]);
if(it1 != st.end()) {
if(jiao((*it1), L[q[i].id])) { IDx = (*it1).id, IDy = q[i].id; break; }
}
if((it1) != st.begin()) { it1--;
if(jiao((*it1), L[q[i].id])) { IDx = (*it1).id, IDy = q[i].id; break; }
}
st.insert(L[q[i].id]);
}
else {
st.erase(L[q[i].id]);
it1 = st.lower_bound(L[q[i].id]);
if(it1 != st.begin() && it1 != st.end()) {
it2 = it1, --it2;
if(jiao((*it1), (*it2))) { IDx = (*it1).id, IDy = (*it2).id; break; }
}
}
}
assert(IDx <= n && IDy <= n);
for(int i = 1; i <= n; ++i) if(i != IDx && i != IDy){
if(jiao(L[IDx], L[i])) return printf("%d
", IDx), 0;
if(jiao(L[IDy], L[i])) return printf("%d
", IDy), 0;
}
printf("%d
", min(IDx, IDy));
}
考试时写了正解，但是写挂了。
T3
就是个naive的O(n)三角形前缀和。
然后我更naive，离线+BIT最后搞了个log^2的算法。只有50分。
CODE
代码略