2019 牛客 多校赛 第四场
slove 3/11
rank 346
补题 7/11
--------------------------------------------------------
https://ac.nowcoder.com/acm/contest/884#question
A、meeting
求树的直径，打个标记记录合法的点
#include <bits/stdc++.h>
#define Pair pair<int,int>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
struct edge
{
int to;
int w;
int nex;
}e[MAXN * 2];
int head[MAXN], tot;
bool vis[MAXN], in[MAXN];
void add(int in, int to)
{
e[tot] = edge{ to,1,head[in] };
head[in] = tot++;
}
void dfs(int u, int fa)
{
if (in[u] == true)
vis[u] = true;
for (int i = head[u]; i + 1; i = e[i].nex)
{
int v = e[i].to;
if (v != fa)
{
dfs(v, u);
if (vis[v] == true)
vis[u] = true;
}
}
}
void init()
{
memset(head, -1, sizeof(head));
tot = 1;
}
int dp[2][MAXN];
int ans = 0;
void dps(int u, int father)
{
for (int i = head[u]; i + 1; i = e[i].nex)
{
int v = e[i].to;
if (vis[v] == false || v == father)
continue;
dps(v, u);
if (dp[0][u] < dp[0][v] + e[i].w)
{
dp[1][u] = dp[0][u];
dp[0][u] = dp[0][v] + e[i].w;
}
else if (dp[1][u] < dp[0][v] + e[i].w)
dp[1][u] = dp[0][v] + e[i].w;
ans = max(ans, dp[0][u] + dp[1][u]);
}
}
Pair input[MAXN];
int main()
{
int a, b, n, k;
scanf("%d%d", &n, &k);
init();
for (int i = 1; i < n; i++)
{
scanf("%d%d", &a, &b);
input[i] = Pair{ a,b };
add(a, b);
add(b, a);
}
int s = 0;
for (int i = 1; i <= k; i++)
{
scanf("%d", &a);
if (i == 1)
s = i;
in[a] = true;
}
dfs(s, 0);
dps(s, 0);
printf("%d\n", (ans + 1) / 2);
} B、xor
n 组数字，m个询问，每个询问三个数字 l r x，询问第 l 组数字到第 r 组数字中是否存在某一组，是否可以取出一些数字异或等于x。
线段树上维护线性基，线段树上每一个结点表示一个区间的所有数字构成的一个线性基，然后线性基向上合并，最后查询一下能不能插入数字 x ，如果可以的话，就表示可以异或出 x，否则不行。
Code：
#include <bits/stdc++.h>
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
struct LB
{
static const int wei = 32;
ll b[wei + 1], cnt;//cnt是个数
LB()
{
cnt = 0;
memset(b, 0, sizeof(b));
}
bool insert(ll x, int id)//插入
{
for (int i = wei; i >= 0; i--)
{
if (x & (1LL << i))
{
if (!b[i])
{
b[i] = x;
cnt++;
return true;
}
x ^= b[i];
}
}
return false;
}
bool check(ll x)//判是否可以插入，实际上不插入
{
for (int i = wei; i >= 0; i--)
{
if (x & (1LL << i))
{
if (!b[i])
return true;
x ^= b[i];
}
}
return false;
}
LB operator +(const LB o) const
{
LB ans, c = o, d = o;
for (int i = 0; i <= wei; i++)
{
ll x = b[i];
if (!x)
continue;
int j = i; ll T = 0;
for (; j >= 0; --j)
{
if ((x >> j) & 1)
{
if (c.b[j])
{
x ^= c.b[j];
T ^= d.b[j];
}
else
break;
}
}
if (!x)
ans.b[i] = T;
else
{
c.b[j] = x;
d.b[j] = T;
}
}
return ans;
}
}que[50005 * 4];
int n, m, ql, qr;
ll val;
void build(int left = 1, int right = n, int k = 1)
{
if (left == right)
{
int nn;
ll a;
scanf("%d", &nn);
while (nn--)
{
scanf("%lld", &a);
que[k].insert(a, 1);
}
return;
}
imid;
build(lson);
build(rson);
que[k] = que[k << 1] + que[k << 1 | 1];
}
bool query(int left = 1, int right = n, int k = 1)
{
if (qr < left || right < ql)
return true;
if (ql <= left && right <= qr)
return !que[k].check(val);
imid;
return query(lson) & query(rson);
}
int main()
{
scanf("%d%d", &n, &m);
build();
while (m--)
{
scanf("%d%d%lld", &ql, &qr, &val);
puts(query() ? "YES" : "NO");
}
} C、sequence
单调栈维护以 
假设当前 
#include <bits/stdc++.h>
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
#define ll long long
using namespace std;
struct node
{
int l;
int r;
ll minn;
ll maxn;
}que[3000005 * 4];
ll a[3000005], b[3000005];
int n, m, ql, qr;
void up(int k)
{
que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
que[k].minn = min(que[k << 1].minn, que[k << 1 | 1].minn);
}
void build(int left = 1, int right = n, int k = 1)
{
que[k].l = left;
que[k].r = right;
if (left == right)
{
que[k].maxn = b[left];
que[k].minn = b[left];
return;
}
imid;
build(lson);
build(rson);
up(k);
}
ll querymin(int left = 1, int right = n, int k = 1)
{
if (qr < left || right < ql)
return 1e18;
if (ql <= left && right <= qr)
return que[k].minn;
imid;
return min(querymin(lson), querymin(rson));
}
ll querymax(int left = 1, int right = n, int k = 1)
{
if (qr < left || right < ql)
return -1e18;
if (ql <= left && right <= qr)
return que[k].maxn;
imid;
return max(querymax(lson), querymax(rson));
}
int l[3000005], r[3000005];
stack<int>st;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &b[i]);
b[i] += b[i - 1];
}
build();
a[0] = -100000000000000000;
a[n + 1] = -99999999999999999;
st.push(0);
for (int i = 1; i <= n + 1; i++)
{
while (a[st.top()] > a[i])
{
r[st.top()] = i;
st.pop();
}
l[i] = st.top();
st.push(i);
}
ll ans = -10000000000000000;
for (int i = 1; i <= n; i++)
{
if (a[i] >= 0)//max
{
ql = l[i], qr = i - 1;
ll ans1 = querymin();
if (qr == 0)
ans1 = 0;
ql = i, qr = r[i] - 1;
ll ans2 = querymax();
if (qr == 0)
ans2 = 0;
ans = max(ans, a[i] * (ans2 - ans1));
}
else if (a[i] < 0)
{
ql = l[i], qr = i - 1;
ll ans1 = querymax();
if (qr == 0)
ans1 = 0;
ql = i, qr = r[i] - 1;
ll ans2 = querymin();
if (qr == 0)
ans2 = 0;
ans = max(ans, a[i] * (ans2 - ans1));
}
}
printf("%lld\n", ans);
} D、triples I
题意：给你一个数字，把他分成多个可以被3整除的数字 或运算 的结果。
思路：首先，题目保证数据合法，那个一个数字至多需要两个数字来或。对于二进制的每一位 1 2 4 8 等来说 %3的结果是 1 2 1 2 ，所以我们可以分别记录%3=1，=2的个数，然后讨论一下。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
vector<int>one, two;
ll n;
int sum = 0;
scanf("%lld", &n);
for (int i = 0; i <= 62; i++)
{
if (n & (1LL << i))
{
if (i & 1)
{
two.push_back(i);
sum += 2;
}
else
{
one.push_back(i);
sum += 1;
}
}
}
int sz1 = one.size();
int sz2 = two.size();
ll ans1 = 0, ans2 = 0;
if (sum % 3 == 0)
printf("1 %lld\n", n);
else if (sum % 3 == 1)
{
if (sz1 == 0)
{
for (int i = 0; i < 3; i++)
ans1 += (1LL << two[i]);
for (int i = 2; i < sz2; i++)
ans2 += (1LL << two[i]);
}
else if (sz1 == 1)
{
ans1 += (1LL << one[0]);
ans1 += (1LL << two[0]);
for (int i = 0; i < sz2; i++)
ans2 += (1LL << two[i]);
}
else if (sz1 == 2)
{
ans1 += (1LL << one[0]);
ans2 += (1LL << one[1]);
for (int i = 0; i < sz2; i++)
{
ans1 += (1LL << two[i]);
ans2 += (1LL << two[i]);
}
}
else
{
//sz1>=3
for (int i = 0; i < 3; i++)
ans1 += (1LL << one[i]);
for (int i = 1; i < sz1; i++)
ans2 += (1LL << one[i]);
for (int i = 0; i < sz2; i++)
ans2 += (1LL << two[i]);
}
printf("2 %lld %lld\n", ans1, ans2);
}
else if (sum % 3 == 2)
{
if (sz1 == 0)
{
for (int i = 0; i < 3; i++)
ans1 += (1LL << two[i]);
for (int i = 1; i < sz2; i++)
ans2 += (1LL << two[i]);
}
else if (sz1 == 1)
{
ans1 += (1LL << one[0]);
ans2 += (1LL << one[0]);
ans1 += (1LL << two[0]);
ans2 += (1LL << two[1]);
for (int i = 2; i < sz2; i++)
ans2 += (1LL << two[i]);
}
else if (sz1 == 2)
{
for (int i = 0; i < 2; i++)
ans1 += (1LL << one[i]);
for (int i = 0; i < 2; i++)
ans1 += (1LL << two[i]);
for (int i = 0; i < sz2; i++)
ans2 += (1LL << two[i]);
}
else
{
//sz1>=3;
for (int i = 0; i < 3; i++)
ans1 += (1LL << one[i]);
for (int i = 2; i < sz1; i++)
ans2 += (1LL << one[i]);
for (int i = 0; i < sz2; i++)
ans2 += (1LL << two[i]);
}
printf("2 %lld %lld\n", ans1, ans2);
}
}
} I、string
后缀自动机
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int maxc = 26;
char str[N];
struct Suffix_Automaton {
int len[N * 2], //最长子串的长度(该节点字串数量=len[x]-len[link[x]])
link[N * 2], //后缀链接(最短串前部减少一个字符所到达的状态)
cnt[N * 2], //被后缀连接的数
nex[N * 2][maxc], //状态转移(尾部加一个字符的下一个状态)(图)
idx, //节点编号
last; //最后节点
ll epos[N * 2]; // enpos数（该状态子串出现数量）
char str[N];
ll a[N]; //长度为i的子串出现最大次数
void newnode(int l) {
len[idx] = l;
memset(nex[idx], 0, sizeof(nex[idx]));
}
void init() { //初始化
last = idx = 1; //1表示root起始点 空集
link[1] = len[1] = 0;
newnode(0);
}
//SAM建图
void insert(int c) { //插入字符，为字符ascll码值
int x = ++idx; //创建一个新节点x;
newnode(len[last] + 1); // 长度等于最后一个节点+1
epos[x] = 1; //接受节点子串除后缀连接还需加一
int p; //第一个有C转移的节点;
for (p = last; p && !nex[p][c]; p = link[p])
nex[p][c] = x;//沿着后缀连接 将所有没有字符c转移的节点直接指向新节点
if (!p)
link[x] = 1, cnt[1]++; //全部都没有c的转移 直接将新节点后缀连接到起点
else {
int q = nex[p][c]; //p通过c转移到的节点
if (len[p] + 1 == len[q]) //pq是连续的
link[x] = q, cnt[q]++; //将新节点后缀连接指向q即可,q节点的被后缀连接数+1
else {
int nq = ++idx; //不连续 需要复制一份q节点
len[nq] = len[p] + 1; //令nq与p连续
link[nq] = link[q]; //因后面link[q]改变此处 不加cnt
memcpy(nex[nq], nex[q], sizeof(nex[q])); //复制q的信息给nq
for (; p && nex[p][c] == q; p = link[p])
nex[p][c] = nq; //沿着后缀连接 将所有通过c转移为q的改为nq
link[q] = link[x] = nq; //将x和q后缀连接改为nq
cnt[nq] += 2; // nq增加两个后缀连接
}
}
last = x; //更新最后处理的节点
}
ll GetSubNum() { //求不相同字串数量
ll ans = 0;
for (int i = 2; i <= idx; i++)
ans += (ll)len[i] - (ll)len[link[i]]; //一状态子串数量等于len[i]-len[link[i]]
return ans;
}
}sam;
struct pam {
int nex[N][26], fail[N];
ll cnt[N];
int num[N], len[N], s[N], q[N << 1]; /*s用来存放已经插入的字符*/
char str[N]; /*cnt 以i结尾的回文串出现次数 num 以i结尾的回文串种类*/
int last, idx, length;
ll ans[N];
int id[N], r[N << 1];
void newnode(int l)
{
len[idx] = l;
memset(nex[idx], 0, sizeof(nex[idx]));
}
void init()
{
idx = 1, last = 0;
len[0] = 0, len[1] = -1;
cnt[1] = cnt[0] = 0;
num[0] = num[1] = 0;
memset(nex[0], 0, sizeof(nex[0]));
memset(nex[1], 0, sizeof(nex[1]));
length = 0;
s[length] = -1;
fail[0] = 1;
}
int get_fail(int x)
{
while (s[length - len[x] - 1] != s[length])
x = fail[x];
return x;
}
void insert_pam(int c)
{
s[++length] = c;
int p = get_fail(last);
if (!nex[p][c])
{
++idx;
id[idx] = length;
newnode(len[p] + 2);
fail[idx] = nex[get_fail(fail[p])][c];
nex[p][c] = idx;
num[idx] = num[fail[idx]] + 1;
}
last = nex[p][c];
cnt[last]++;
}
void count()
{
for (int i = idx; i >= 2; i--)
cnt[fail[i]] += cnt[i];
}
}pam;
int main()
{
scanf("%s", str);
int n = strlen(str);
sam.init();
for (int i = 0; i < n; i++)
sam.insert(str[i] - 'a');
sam.last = 1;
for (int i = n - 1; i >= 0; i--)
sam.insert(str[i] - 'a');
pam.init();
for (int i = 0; i < n; i++)
pam.insert_pam(str[i] - 'a');
printf("%lld", (0ll+ (ll)sam.GetSubNum() + (ll)pam.idx - 1) / 2);
} J、free
分层图最短路
#include <bits/stdc++.h>
#define Pair pair<ll, int>
#define ll long long
using namespace std;
const int MAXN = 1005;
const ll inf = 1e18 + 7;
struct edge
{
int to;
ll w;
int nex;
}e[MAXN * 2];
int head[MAXN], tot;
void add(int in, int to, ll w)
{
e[tot] = edge{ to,w,head[in] };
head[in] = tot++;
}
struct node
{
ll w;
int u;
int cnt;
bool operator < (const node o) const {
return w > o.w;
}
};
ll dis[1005][1005];
bool vis[1005][1005];
void dij(int s)
{
priority_queue<node>q;
for (int i = 0; i < 1005; i++)
for (int j = 0; j < 1005; j++)
{
dis[i][j] = inf;
vis[i][j] = false;
}
dis[0][s] = 0;
q.push(node{ 0,s,0 });
while (!q.empty())
{
node t = q.top();
int u = t.u;
int k = t.cnt;
q.pop();
if (vis[k][u])
continue;
vis[k][u] = true;
for (int i = head[u]; i + 1; i = e[i].nex)
{
int v = e[i].to;
if (dis[k][v] > dis[k][u] + e[i].w)
{
dis[k][v] = dis[k][u] + e[i].w;
q.push(node{ dis[k][v],v,k });
}
if (dis[k + 1][v] > dis[k][u] && k < 1001)
{
dis[k + 1][v] = dis[k][u];
q.push(node{ dis[k + 1][v],v,k + 1 });
}
}
}
}
void init()
{
memset(head, -1, sizeof(head));
tot = 1;
}
int main()
{
int n, m, s, t, k;
scanf("%d%d%d%d%d", &n, &m, &s, &t, &k);
init();
while (m--)
{
int a, b;
ll c;
scanf("%d%d%lld", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
dij(s);
ll ans = inf;
for (int i = 0; i <= k; i++)
ans = min(ans, dis[i][t]);
printf("%lld\n", ans);
} K、number
找出一个串中所有能整除300的子串。
1、首先找到所有0的块，并且将这个块中0的个数标记在第一个出现的0上面。
2、然后每次遍历累计一个前缀和前缀%3 的余数的个数，然后每次遇到一个0的块，能产生的贡献就是 0的个数减一 乘 前缀出现的当前前缀%3的余数的个数
3、然后再统计0的个数，假设一块0 的个数是a，那么这一块可以取到0的个数就是 a*(a+1)/2
4、将余数为1 2的数量初始化为-1
#include <bits/stdc++.h>
#define ll long long
using namespace std;
char s[100005];
int sub[100005];
ll zero[100005];//当前下标0的个数
ll num[3];
int main()
{
num[2] = num[1] = -1;
scanf("%s", s + 1);
ll ans = 0;
int len = strlen(s + 1);
s[0] = '1';
int pre = 0;
for (int i = 1; i <= len; i++)
{
if (s[i - 1] == '0' && s[i] == '0')
{
zero[pre]++;
}
else if (s[i - 1] != '0' && s[i] == '0')
{
pre = i;
zero[pre]++;
}
}
for (int i = 1; i <= len; i++)
{
sub[i] = (sub[i - 1] + s[i] - '0') % 3;
if (zero[i])
{
int t = sub[i - 1];
ll cnt = num[t];
ans += cnt * (zero[i] - 1);
ans += zero[i] * (zero[i] + 1) / 2;
}
num[sub[i]]++;
}
printf("%lld\n", ans);
}
查看17道真题和解析
