#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

#define endl '\n'
#define fi first
#define se second
#define ppb pop_back
#define pb push_back
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof x)
#define rep(i, l, r) for(int i = l; i <= (r); ++ i)
#define per(i, r, l) for(int i = r; i >= (l); -- i)
#define reps(i, l, r, d) for(int i = l; i <= (r); i += d)
#define pers(i, r, l, d) for(int i = r; i >= (l); i -= d)

const int N = 300, M = 1e5 + 10;
const LL p = 1e9 + 7;

int n, edx, edy;
int x[N], y[N], t[N];
int type[N][N]; // 0 是 \ , 1 是 / , -1 代表没有镜子
bool st[N][N][4]; // st[i][j][op] , 标记 i, j 点从 op 方向射过来

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

vector <int> ax, ay;
int find(vector<int> & alls, int x){
    return lower_bound(all(alls), x) - alls.begin() + 1;
}

bool dfs(int nowx, int nowy, int op){
    if(st[nowx][nowy][op]) return 0;
    st[nowx][nowy][op] = 1; // 排除环，防止死循环

    nowx += dx[op], nowy += dy[op];
    if(nowx == find(ax, edx) && nowy == find(ay, edy)) return 1; // 到了终点
    if(nowx < 1 || nowy < 1 || nowx > ax.size() || nowy > ay.size()) return 0; // 越界

    if(type[nowx][nowy] == 0) op = 3 - op;
    if(type[nowx][nowy] == 1)  op ^= 1; // 反射，更改方向

    if(dfs(nowx, nowy, op)) return 1;
    return 0;
}

int main()
{
    ios;

    mset(type, -1);

    cin >> n >> edx >> edy;
    ax = {0, edx}, ay = {0, edy};
    rep(i, 1, n){
        char ch; cin >> x[i] >> y[i] >> ch;
        ax.pb(x[i]), ay.pb(y[i]);
        t[i] = ch == '\\' ? 0 : 1;
    }

    sort(all(ax)), sort(all(ay));
    ax.erase(unique(all(ax)), ax.end());
    ay.erase(unique(all(ay)), ay.end());

    rep(i, 1, n) type[find(ax, x[i])][find(ay, y[i])] = t[i];


    int ans = -1, stx = find(ax, 0), sty = find(ay, 0);
    if(dfs(stx, sty, 1) || dfs(stx, sty, 0)) ans = 0;
    else{
        rep(i, 1, n){
            mset(st, 0);
            int nowx = find(ax, x[i]), nowy = find(ay, y[i]);
            type[nowx][nowy] ^= 1;
            if(dfs(stx, sty, 1) || dfs(stx, sty, 0)) ans = i;
            type[nowx][nowy] ^= 1;
            if(ans >= 1) break;
        }
    }

    cout << ans;


    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for(int i = l; i <= (r); ++ i)

int main()
{
    int n, m; cin >> n >> m;
    string a, b;
    rep(i, 1, n){
        int d; char ch; cin >> d >> ch;
        a += string(d, ch);
    }
    rep(i, 1, m){
        int d; char ch; cin >> d >> ch;
        b += string(d, ch);
    }

    int s1 = 0, s2 = 0, ans = 0;

    rep(i, 0, max(a.size(), b.size()) - 1){
        int t1 = s1, t2 = s2;
        if(i < a.size()) s1 += a[i] == 'L' ? -1 : 1;
        if(i < b.size()) s2 += b[i] == 'L' ? -1 : 1;
        if(t1 != t2 && s1 == s2) ans ++ ;
    }

    cout << ans;


    return 0;
}

写了个$n^2 \times {\log (n ^ 2)}$ 的代码，被卡 $\log$ 了

九个月之前被卡好长时间的题今天终于a掉了，泪目

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;

#define inf_int 0x3f3f3f3f
#define inf_LL 0x3f3f3f3f3f3f3f3f
#define ninf_int (int)0xc1c1c1c1
#define ninf_LL (LL)0xc1c1c1c1c1c1c1c1

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


const int N = 1e5 + 10, M = 2 * N;

struct edge{
    int u, v, w;
    bool operator < (const edge x) const {
        return w < x.w;
    }
}e[3 * N];

int pa[N];
int n, m;
bool vise[M];
int fa[N][17], dep[N];
LL maxx0[N][17], maxx1[N][17];

LL dis[N];
int cnt;

int he[N], ne[M], v[M], w[M], idx;

void add(int a, int b, int c){
    v[idx] = b, w[idx] = c;
    ne[idx] = he[a], he[a] = idx ++ ;
}

int find(int x){
    if(pa[x] == -1) return x;
    return pa[x] = find(pa[x]);
}

void dfs(int now, int pre)
{
    dep[now] = dep[pre] + 1, fa[now][0] = pre;
    for(int i = 1; i <= 16; i ++ ){
        int anc = fa[now][i - 1];
        fa[now][i] = fa[anc][i - 1];

        cnt = 0;
        dis[cnt ++ ] = maxx0[now][i - 1];
        dis[cnt ++ ] = maxx1[now][i - 1];
        dis[cnt ++ ] = maxx0[anc][i - 1];
        dis[cnt ++ ] = maxx1[anc][i - 1];

        for(int j = 0; j < 4; j ++ ){
            LL d = dis[j];
            if(d > maxx0[now][i]) maxx1[now][i] = maxx0[now][i], maxx0[now][i] = d;
            else if(d < maxx0[now][i] && d > maxx1[now][i]) maxx1[now][i] = d;
        }
    }
    for(int i = he[now]; ~i; i = ne[i]){
        int to = v[i];
        if(to == pre) continue;
        maxx0[to][0] = w[i];
        dfs(to, now);
    }
}

void lca(int x, int y, LL & max0, LL & max1)
{
    if(dep[x] < dep[y]) swap(x, y);
    cnt = 0;
    for(int i = 16; i >= 0; i -- )
        if(dep[fa[x][i]] >= dep[y]){
            dis[cnt ++ ] = maxx0[x][i];
            dis[cnt ++ ] = maxx1[x][i];
            x = fa[x][i];
        }

    if(x != y){
        for(int i = 16; i >= 0; i -- )
            if(fa[x][i] != fa[y][i]){
                dis[cnt ++ ] = maxx0[x][i];
                dis[cnt ++ ] = maxx1[x][i];
                dis[cnt ++ ] = maxx0[y][i];
                dis[cnt ++ ] = maxx1[y][i];
                x = fa[x][i];
                y = fa[y][i];
        }
    }
    dis[cnt ++ ] = maxx0[x][0];
    dis[cnt ++ ] = maxx1[x][0];
    dis[cnt ++ ] = maxx0[y][0];
    dis[cnt ++ ] = maxx1[y][0];

    for(int i = 0; i < cnt; i ++ ){
        LL d = dis[i];
        if(d > max0) max1 = max0, max0 = d;
        else if(d < max0 && d > max1) max1 = d;
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(pa, -1, sizeof pa);
    memset(he, -1, sizeof he);
    memset(maxx0, -0x3f, sizeof maxx0);
    memset(maxx1, -0x3f, sizeof maxx1);

    for(int i=0; i < m; i ++ ){
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        if(x == y) { i -- ; m -- ; continue; }
        e[i] = {x, y, z};
    }

    sort(e, e + m);

    LL sum = 0, del = LONG_LONG_MAX;

    for(int i=0; i < m; i ++ ){
        int u = find(e[i].u), v = find(e[i].v);
        if(u != v){
            pa[u] = v;
            vise[i] = 1;
            sum += e[i].w;
            add(e[i].u, e[i].v, e[i].w);
            add(e[i].v, e[i].u, e[i].w);
        }
    }

    dfs(1, 0);

    for(int i=0; i < m; i ++ )
        if(vise[i] == 0)
        {
            int u = e[i].u, v = e[i].v, w = e[i].w;
            LL max0 = ninf_LL, max1 = ninf_LL;
            lca(u, v, max0, max1);
            if(max0 != ninf_LL && max0 != w) del = min(del, w - max0);
            else if(max1 != ninf_LL) del = min(del, w - max1);
        }

    printf("%lld", sum + del);

    system("pause");
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~