ZhgDgE

843

Skywalker767

ohh_0
77777777777

hpu_yao
2191279878@qq.com
HZ_3
Andy2035
lordvoldemort
silentInt

IRun
shy_

ctdrm

ZhgDgE
28天前
#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;
}


ZhgDgE
29天前
#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;
}


ZhgDgE
1个月前

ZhgDgE
3个月前

ZhgDgE
3个月前

#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;
}


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


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


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


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


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