E

ZRC签到

A

ZRC签到

D

题意：

有一个a数列，将相邻两项求位或得b数列，相邻两项求和得到c数列。已知b，c，问可能的a有多少种。

LYF解：

通过观察得到，c-b数列具有特殊性质，只有当相邻a在某一位的值均为1时c-b在该位值才为1。结合题给的b数列，可以对每一位枚举a_1的取值判断是否可行，计算出答案。

LYF给我讲他的做法时，我还没想通c-b为啥会有性质，他就ac了。题解中才看出来，事实上c-b就是相邻两项的位与…显然

由此得到一个经验：**(a&b)+(a|b)=a+b**

K

题意：

一个无穷大平面，横以间距d分割，纵以间距w分割，形成无穷多个矩形区域。任取一点画一条长度为pi的线，问最多经过几个区域。0<d,w<=5,八位小数。

ZRC解：

首先发现，只需要走无穷小的距离就可以经过四个区域。而且，显然走曲线并非最优决策。利用pi是超越数，不可能是任何格点间直线长度之和的特性，可以把题目转化成：到达格点算作经过四周四个区域，从某个格点出发，用pi的距离最多走几个区域。

首先考虑比较优的一种走法：一直走短边。经过的区域数量为$\frac{\pi}{min(d,w)}\cdot2+4$

然后考虑能否走斜线。最简单的斜线即对角线。一直走对角线的答案为$\frac{\pi}{l}\cdot3+4$，显然有可能选择。对于其余的斜线，日字格走法必定不如走两个短边更优，其余斜线依此类推。

因此只有对角线和短边两种走法。那么设走x次对角线，y次短边，要求的问题即为：
$$
x\cdot min(d,w)+y\cdot l\le \pi\\
求max{ 2x+3y }
$$
显然要么x<3，要么y<2。枚举几种情况即可。

考场上到了最后一步却没有将式子列出来看出性质，实在该吸取教训。

补J

题意：

给定一棵树5e5，指定两个节点S,T为树上两个人的初始节点。两个人轮流走，每走一个节点，原节点就会爆炸。最终两个人走的步数为各自的得分。游戏时双方都希望自己的分数减对方分数的值最大。问游戏结束时双方的分数差。

解：

首先定义S到T之间的链为主链。一旦两个人其中一个离开了主链，显然双方就都不能够互相影响，均会选择当前的最长路径走。若S在主链上的x节点时S首先选择离开主链，此时T一定在主链对应的位置上，那么这种情况下的双方分数差易于求得。若T首先选择离开主链，同理。显然可以方便地用ST表搞这个rmq问题。具体见我改的WD的代码(其中的注释):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//Authorized by qwqbot. Modified by Richard.
#include <bits/stdc++.h>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
using namespace std;
mt19937 rnd(19260817);
const int inf=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int> pii;
///////////////////////read5.1///////////////////////
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
////////////////variables&functions//////////////////
const int maxn=555555;
#define log2(x) (31-__builtin_clz(x))	//Only for INT!!!!!!!!!!!!!!!!!!!!!!Not for LL!!!!!!!!!!
const int logn=log2(maxn);
template <typename T>
struct ST_Table
{
    T a[maxn][logn+1];
    T f(T x,T y)
	{
        return max(x,y);
    }
    void init(int n)
	{
        rep(i,1,logn)
            for (T j=1;j+(1<<i)-1<=n;j++)
                a[j][i]=f(a[j][i-1],a[j+(1<<(i-1))][i-1]);
    }
    T query(int l,int r)
	{
        int s=log2(r-l+1);
        return f(a[l][s],a[r-(1<<s)+1][s]);
    }
    ST_Table<T>(){}
};
ST_Table<int> pp,bb;

vector<int> g[maxn];
int dep[maxn],fa[maxn],n,s,t;
bool dfs(int u,int p)
{
    bool in_main_chain=(u==t);
    fa[u]=p;
    dep[u]=0;
    for (auto v:g[u])
    {
        if (v==p) continue;
        if (dfs(v,u)) in_main_chain=true;
        else dep[u]=max(dep[u],dep[v]+1);//calc the depth of subtrees
    }
    return in_main_chain;
}
int main()
{
    read(n,s,t);
    rep(i,1,n-1)//add edges
    {
        int u,v;
        read(u,v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(s,0);

    //find the main chain
    int tt=t;
    vector<int> main_chain;
    while (tt!=s)
    {
        main_chain.push_back(tt);
        tt=fa[tt];
    }
    main_chain.push_back(s);
    main_chain.push_back(0);
    reverse(main_chain.begin(), main_chain.end());

    //calculate how long would they travel if one player leaves the main chain from main_chain[i], and use ST table to solve RMQ problem
    int m=main_chain.size()-1;
    rep(i,1,m) pp.a[i][0]=dep[main_chain[i]]+i-1;
    per(i,m,1) bb.a[i][0]=dep[main_chain[i]]+(m-i);
    pp.init(m);bb.init(m);

    vector<int> Rans;
    for (int l=1,r=m,i=1;l<=(m+1)/2||r>=(m+1)/2+1;i++)//simulate every step
    {
        if (i&1)
        {
            int u=main_chain[l],anss=dep[u]+l-1,anst=bb.query(l+1,r);//obviously
            if (l==r) anst=m-l;//if they are on the same node, only one of them (who comes first) can go down.
            Rans.push_back(anss-anst);
            l++;
        }
        else
        {
            int u=main_chain[r],anss=pp.query(l,r-1),anst=dep[u]+(m-r);
            if (l==r) anss=r-1;
            Rans.push_back(anss-anst);
            r--;
        }
    }
    bool whose_turn=Rans.size()&1;
    reverse(Rans.begin(),Rans.end());//calculate from back. classical game theory
    int ans=whose_turn?-inf:inf;
    for (auto to:Rans)
    {
        if (whose_turn) ans=max(ans,to);
        else ans=min(ans,to);
        whose_turn^=1;
    }
    cout<<ans<<endl;
    return 0;
}

补F

待补