DAY 1

起床困难综合症

　　没怎么想正解，打了一个70分暴力

　　考虑到OR与OR之间的运算顺序对答案没有影响，即 ( ans OR x ) OR y 与 ( ans OR y ) OR x 相等，可以将多个连续的OR运算合并成一个，AND，XOR 同理

　　暴力枚举初始攻击力 0 ~ m

　　又存在多个数 OR/XOR/AND x 答案相等，如 5 OR 10 = 15,   6 OR 10 = 15,   13 OR 10 = 15，可记忆化

#include 
using namespace std;
const int N = 100005;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

int n, m, num;
setint, int> >st;

struct node
{
    char op; int x;
    node(){}
    node(char o, int xx) {op = o; x = xx;}
}q[N];

int main()
{
    n = read(); m = read();
    for(int i = 1; i <= n; i++)
    {
        char s[5]; scanf("%s", s);
        if(s[0] != q[num].op) q[++num] = node(s[0], read());
        else
        {
            int x = read();
            if(q[num].op == 'O') q[num].x |= x;
            else if(q[num].op == 'X') q[num].x ^= x;
            else q[num].x &= x;
        }
        if(q[num].op == 'A' && !q[num].op)
        {
            num = 1;
            q[num] = node('A', 0);
        }
    }
    int ans = 0;
    for(int x = 0; x <= m; x++)
    {
        int t = x; bool fail = false;
        for(int i = 1; i <= num; i++)
        {
            if(q[i].op == 'O') t |= q[i].x;
            else if(q[i].op == 'X') t ^= q[i].x;
            else t &= q[i].x;
            if(st.find(make_pair(i, t)) == st.end()) st.insert(make_pair(i, t));
            else {fail = true; break;}
        }
        if(!fail) ans = max(ans, t);
    }
    cout << ans;
    return 0;
}

　　emmm......

　　然后又想了一下正解，也很简单啊，早知道就不去耗第三题了

　　单独考虑二进制下的每一位，分别计算初始值选择 0 / 1 得到的最终答案

　　初始值有上限，所以当选 0 / 1 效果相同时选 0，仅当选 1 效果更优且不会使值大于 m 时选 1

#include 
using namespace std;
const int N = 100005;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

int n, m, num;
setint, int> >st;

struct node
{
    char op; int x;
    node(){}
    node(char o, int xx) {op = o; x = xx;}
}q[N];

int deal(int k, int i, int x)
{
    if(k != -1)
    {
        int t = (q[i].x & (1 << k))? 1:0;
        if(q[i].op == 'O') return x | t;
        if(q[i].op == 'X') return x ^ t;
        if(q[i].op == 'A') return x & t;
    }
    else
    {
        if(q[i].op == 'O') return x | q[i].x;
        if(q[i].op == 'X') return x ^ q[i].x;
        if(q[i].op == 'A') return x & q[i].x;
    }
}

int main()
{
    n = read(); m = read();
    for(int i = 1; i <= n; i++)
    {
        char s[5]; scanf("%s", s);
        if(s[0] != q[num].op) q[++num] = node(s[0], read());
        else
        {
            int x = read();
            if(q[num].op == 'O') q[num].x |= x;
            else if(q[num].op == 'X') q[num].x ^= x;
            else q[num].x &= x;
        }
        if(q[num].op == 'A' && !q[num].op)
        {
            num = 1;
            q[num] = node('A', 0);
        }
    }
    int ans = 0;
    for(int k = 30; k >= 0; k--)
    {
        if((1 << k) > m) continue;
        int x[2] = {0, 1};
        for(int i = 1; i <= num; i++)
        {
            x[0] = deal(k, i, x[0]);
            x[1] = deal(k, i, x[1]);
        }
        if(x[1] && !x[0])
            if(ans + (1 << k) <= m) ans += (1 << k);
    }
    for(int i = 1; i <= num; i++) ans = deal(-1, i, ans);
    cout << ans;
    return 0;
}

魔法森林

　　数据有点水啊，二分 + dfs有20分，竟然过掉了一个500,3000的点

#include 
using namespace std;
const int N = 50005;
const int M = 200005;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

int n, m, ax, bx;

int num, tmp1[M], to[M], tmp2[M], va[M], tmp3[M], vb[M], tmp4[M], nt[M], tmp5[M], p[N];
void add(int x, int y, int a, int b) {to[++num] = y; va[num] = a; vb[num] = b; nt[num] = p[x]; p[x] = num;}

bool tmp[M], vis[N];
bool dfs(int x, int a, int b, int mx)
{
    if(a + b > mx) return false;
    if(x == n) return true;
    bool f = false;
    for(int e = p[x]; e; e = nt[e])
    {
        if(vis[to[e]]) continue;
        vis[to[e]] = true;
        if(dfs(to[e], max(a, va[e]), max(b, vb[e]), mx)) return true;
        vis[to[e]] = false;
    }
    return false;
}

int main()
{
    n = read(); m = read();
    for(int i = 1; i <= m; i++)
    {
        int x = read(), y = read(), a = read(), b = read();
        if(x == y) continue;
        add(x, y, a, b); add(y, x, a, b);
        ax = max(ax, a); bx = max(bx, b);
    }
    int l = 0, r = ax + bx, ans = -1;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        memset(vis, false, sizeof(vis)); vis[1] = true;
        if(dfs(1, 0, 0, mid)) {ans = mid; r = mid - 1;}
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}

　　若只存在一个权值，即求最大边权最小，直接 spfa 即可

　　对于两种权值限制，可先对a进行排序，依次加边并对 b 跑 spfa，ans = max( a_i + dis[n] );

　　每次添加的边仅对两端点有影响，不必重跑 spfa

#include 
using namespace std;
const int N = 50005;
const int M = 200005;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

int n, m;

struct node
{
    int x, y, a, b;
    node(){}
    node(int xx, int yy, int aa, int bb) {x = xx; y = yy; a = aa; b = bb;}
}q[M];

bool cmp(node A, node B) {return A.a < B.a;}

int num, to[M], w[M], nt[M], p[N];
void add(int x, int y, int v) {to[++num] = y; w[num] = v; nt[num] = p[x]; p[x] = num;}

int dis[N]; bool vis[N]; queue<int> Q;
void spfa()
{
    while(!Q.empty())
    {
        int k = Q.front(); Q.pop(); vis[k] = false;
        for(int e = p[k]; e; e = nt[e])
        {
            if(dis[to[e]] > max(dis[k], w[e]))
            {
                dis[to[e]] = max(dis[k], w[e]);
                if(!vis[to[e]]) {vis[to[e]] = true; Q.push(to[e]);}
            }
        }
    }
}

int main()
{
    n = read(); m = read();
    for(int i = 1; i <= m; i++)
    {
        q[i].x = read(); q[i].y = read(); q[i].a = read(); q[i].b = read();
    }
    sort(q + 1, q + 1 + m, cmp);
    memset(dis, 63, sizeof(dis)); dis[1] = 0;
    int ans = 1e8;
    for(int i = 1; i <= m; i++)
    {
        add(q[i].x, q[i].y, q[i].b); add(q[i].y, q[i].x, q[i].b);
        Q.push(q[i].x); Q.push(q[i].y); vis[q[i].x] = vis[q[i].y] = true;
        spfa();
        ans = min(ans, dis[n] + q[i].a);
    }
    if(ans == 1e8) cout << -1; else cout << ans;
    return 0;
}

　　显然复杂度太玄学过不了

　　哎呀，好尴尬

　　显然复杂度太玄学过不掉

　　再次考虑先前的操作，对 b 求经过的最小的最大边权，可用最小生成树求解

 　　按 a 从小到大依次加边，即维护动态最小生成树，lct

还没写完。。。

消除游戏

　　太麻烦啦，不想写

day1小结

　　第一次提交：70 + 10 + 0

　　不看题解进行修改：100 + 20 + 0

　　emmmmm，NOI要真考成这要得出大事。。。