机房模拟赛 2017年9月26日数据结构

加帕里的聚会

256MB / 1s ; japari.cpp / c / pas / in / out

【题目描述】

加帕里公园里有n个区域，n-1条道路将它们连接到了一起，形成了一个树的结构。开始时，第i个区域有Ai个friends，但是由于砂之星的作用，有时从x区域到y区域的简单路径上的所有区域的friends数量都会增加v，有时从x区域到y区域的简单路径上所有区域的friends数量都会变成v。
有时，从x区域到y区域的简单路径上所有区域的friends想要聚会，聚会时需要从所有参加聚会的friends中选择一部分作为staff。加帕里的friends都很喜欢质数，因此她们希望staff和非staff的参与者的数量都是质数。
请你告诉她们，每次聚会是否存在一种方案满足她们的要求。

【输入格式】

第一行两个整数n,m，表示friends数量和事件数量。
接下来一行n个数，第i个数表示Ai。
接下来n-1行，每行2个数x,y，表示x和y之间有一条无向道路。
接下来m行，每行第一个整数opt表示事件类型。
若opt=1，接下来三个整数x,y,v，表示从x区域到y区域的简单路径上的所有区域的friends数量都增加v。
若opt=2，接下来三个整数x,y,v，表示从x区域到y区域的简单路径上的所有区域的friends数量都变为v。
若opt=3，接下来两个整数x,y，表示从x区域到y区域的简单路径上的所有区域的friends进行聚会。

【输出格式】

对于每个3事件，若可以让staff和非staff的数量都为质数，输出一行SUGOI，否则输出一行TANOSHI。

【样例数据】

japari1.in

3 4
1 2 1
2 1
3 2
2 2 1 4
1 3 3 -1
2 2 2 2
3 1 3

japari1.out

SUGOI

japari2.in

4 6
2 4 0 0
2 1
3 2
4 3
2 1 4 2
1 4 4 9
1 3 2 -2
2 4 2 5
3 1 4
3 4 4

japari2.out

TANOSHI
SUGOI

【样例解释】

在第一个样例中，三个区域的friends数量依次为4、2、0，询问的friends和为6，可以分成两组，每组的friends数量都为3。
在第二个样例中，四个区域的friends数量依次为2、5、5、5，第一个询问的friends和为17，无法分成两组。第二个询问的friends和为5，可以分为两组，每组的friends数量分别为2、3。

【数据范围】

对于30%的数据，n,m≤5000。
对于另30%的数据，对于i＞1，第i个区域与第i-1个区域直接相连。
对于100%的数据，1≤n,m≤100000，1≤x,y≤n，一直满足0≤Ai,S≤10000000。在增加事件中v可能为负数。

就是裸树剖，真是调到吐血

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 100000 * 2;
int n, m, a[ MAXN + 20 ], prime[ 2000000 + 20 ], head[ MAXN + 20 ], sz[ MAXN + 20 ], son[ MAXN + 20 ], tail, timer, dfn[ MAXN + 20 ], tid[ MAXN + 20 ], fa[ MAXN + 20 ], dp[ MAXN + 20 ], top[ MAXN + 20 ];
bool is_not_prime[ 10000000 + 20 ];
int opt;
struct Tree{ int sum, mark, add; }tree[  MAXN * 4 +20 ];
struct Line{ int to, nxt; }line[ MAXN * 2 + 20 ];
void add_line( int from, int to ) { line[++tail].to = to; line[tail].nxt = head[from]; head[from] = tail; }
void dfs1( int u, int fat, int dep ) {
    dp[u] = dep;
    fa[u] = fat;
    sz[u] = 1;
for( register int i = head[u]; i ; i = line[i].nxt ) {
int v = line[i].to;
if( v == fat ) continue;
        dfs1( v, u, dep + 1 );
        sz[u] += sz[v];
if( son[u] == -1 || sz[son[u]] < sz[v] ) son[u] = v;
    }
}
void dfs2( int u, int tp ) {
    top[u] = tp;
    dfn[u] = ++timer;
    tid[timer] = u;
if( son[u] == -1 ) return;
    dfs2( son[u], tp );
for( register int i = head[u]; i ; i = line[i].nxt ) {
int v = line[i].to;
if( v == fa[u] || v == son[u] ) continue;
        dfs2( v, v );
    }
}
//*********************DFS*************************//
inline void get_ss( ) {
for( register int i = 2; i <= 10000000; i++ ) {
if( !is_not_prime[i] ) prime[ ++prime[0] ] = i;
for( register int j = 1; j <= prime[0] && i * prime[j] <= 10000000; j++ ) {
            is_not_prime[ i * prime[j] ] = true;
if( i % prime[j] == 0 ) break;
        }
    }
}
//*********************线筛*************************//
void pushup( int rt ) { tree[rt].sum = tree[ rt << 1 ].sum + tree[ rt << 1 | 1 ].sum; }
void pushdown( int l, int r, int rt ) {
int mid = ( l + r ) >> 1;
if( tree[rt].mark != -1) {
        tree[ rt << 1 ].mark = tree[rt].mark;
        tree[ rt << 1 | 1 ].mark = tree[rt].mark;
        tree[ rt << 1 ].sum = ( mid - l + 1 ) * tree[rt].mark;
        tree[ rt << 1 | 1 ].sum = ( r - mid ) * tree[rt].mark;
        tree[rt].mark = -1;
        tree[ rt << 1 ].add = tree[ rt << 1 | 1 ].add = 0;
    }
if( tree[rt].add != 0 ) {
        tree[ rt << 1 ].add += tree[rt].add;
        tree[ rt << 1 | 1 ].add += tree[rt].add;
        tree[ rt << 1 ].sum += ( mid - l + 1 ) * tree[rt].add;
        tree[ rt << 1 | 1 ].sum += ( r - mid ) * tree[rt].add;
        tree[rt].add = 0;
    }
}
void build( int l, int r, int rt ) {
    tree[rt].mark = -1; tree[rt].add = 0;
if( l == r ) { tree[rt].sum = a[ tid[l] ]; return; }
int mid = ( l + r ) >> 1;
    build( l, mid, rt << 1 );
    build( mid + 1, r, rt << 1 | 1 );
    pushup( rt );
}
void modifyadd( int L, int R, int add, int l, int r, int rt ) {
if( L <= l && R >= r ) {
        tree[rt].add += add;
        tree[rt].sum += ( r - l + 1 ) * add;
return;
    }
int mid = ( l + r ) >> 1;
    pushdown( l, r, rt );
if( L <= mid ) modifyadd( L, R, add, l, mid, rt << 1 );
if( R >  mid ) modifyadd( L, R, add, mid + 1, r, rt << 1 | 1 );
    pushup( rt );
}
void modifyre( int L, int R, int mark, int l, int r, int rt ) {
if( L <= l && R >= r ) {
        tree[rt].add = 0;
        tree[rt].mark = mark;
        tree[rt].sum = ( r - l + 1 ) * mark;
return;
    }
    pushdown( l, r, rt );
int mid = ( l + r ) >> 1 ;
if( L <= mid ) modifyre( L, R, mark, l, mid, rt << 1 );
if( R >  mid ) modifyre( L, R, mark, mid + 1, r, rt << 1 | 1 );
    pushup( rt );
}
int query( int L, int R, int l, int r, int rt ) {
if( L <= l && R >= r ) { return tree[rt].sum; }
int mid = ( l + r ) >> 1;
    pushdown( l, r, rt );
int tmp = 0;
if( L <= mid ) tmp += query( L, R, l, mid, rt << 1 );
if( R >  mid ) tmp += query( L, R, mid + 1, r, rt << 1 | 1 );
return tmp;
}
//*********************线段树*************************//
void modifyadd( int x, int y, int v ) {
while( top[x] != top[y] ) {
if( dp[top[x]] < dp[top[y]] ) swap( x, y );
        modifyadd( dfn[top[x]], dfn[x], v, 1, n, 1 );
        x = fa[top[x]];
    }
if( dp[x] < dp[y] ) swap( x, y );
    modifyadd( dfn[y], dfn[x], v, 1, n, 1 );
}
void modifyre( int x, int y, int v ) {
while( top[x] != top[y] ) {
if( dp[top[x]] < dp[top[y]] ) swap( x, y );
        modifyre( dfn[top[x]], dfn[x], v, 1, n, 1 );
        x = fa[top[x]];
     }
if( dp[x] < dp[y] ) swap( x, y );
     modifyre( dfn[y], dfn[x], v, 1, n, 1 );
}
void query( int x, int y ) {
int sum = 0;
while( top[x] != top[y] ) {
if( dp[top[x]] < dp[top[y]] ) swap( x, y );
        sum += query( dfn[top[x]], dfn[x], 1, n, 1 );
        x = fa[top[x]];
    }
if( dp[x] < dp[y] ) swap( x, y );
    sum += query( dfn[y], dfn[x], 1, n, 1 );
if( sum <= 3 ) { printf( "TANOSHI\n" ); return; }
if( sum % 2 == 0 ) { printf( "SUGOI\n" ); return; }
int tmp = sum - 2;
if( is_not_prime[tmp] ) { printf( "TANOSHI\n" ); return; }
else                    { printf( "SUGOI\n" );   return; }
}
//*********************树链剖分*************************//
int main( ) {
    freopen( "japari.in", "r", stdin );
    freopen( "japari.out", "w", stdout );
    get_ss( );
scanf( "%d%d", &n, &m ); memset( son, -1, sizeof(son) );
for( register int i = 1; i <= n; i++ ) scanf( "%d", &a[i] );
for( register int i = 1; i <= n - 1; i++ ) { int ff, tt;
scanf( "%d%d", &ff, &tt );
        add_line( ff, tt ); add_line( tt, ff );
    }
    dfs1( 1, 0, 0 );
    dfs2( 1, 1 );
    build( 1, n, 1 );
for( register int i = 1; i <= m; i++ ) {
scanf( "%d", &opt ); int x, y, v; 
if( opt == 1 ) {
scanf( "%d%d%d", &x, &y, &v );
            modifyadd( x, y, v );
        } else if( opt == 2 ) {
scanf( "%d%d%d", &x, &y, &v );
            modifyre( x, y, v );
        } else {
scanf( "%d%d", &x, &y );
            query( x, y );
        }
    }
return 0;
}

黑白熊的密码

256MB / 1s ; monokuma.cpp / c / pas / in / out

【题目描述】

苗木诚发现了脱出装置，它可以帮助所有人逃脱希望之峰学园。但是要想使用它，必须输入一个十进制的n位数密码（没有前导0）。为了让游戏变得更加有趣，黑白熊提供了m条信息，其中第i条信息指出这个数的第Li位到Ri位和第li位到ri位完全相同。
苗木诚决定随机选择一个满足要求的n位数输入。请你告诉他他碰对密码的概率是多少。

【输入格式】

第一行两个整数n,m，表示数的位数和黑白熊提供的信息数。
接下来m行，每行四个正整数Li,Ri,li,ri。

【输出格式】

输出一行一个整数，表示苗木诚碰对密码的概率，对998244353取模。

【样例数据】

monokuma.in

4 2
1 2 3 4
3 3 3 3

monokuma.out

144190851

【样例解释】

答案是1/90在模998244353意义下的值。

【数据范围】

对于30%的数据，n,m≤2000。
对于100%的数据，1≤n,m≤100000，1≤Li≤Ri≤n，1≤li≤ri≤n，且保证Ri-Li=ri-li。

BZOJ 原题，一点原创性都没有，XGG naive

题解：

就是一个并查集操作，倍增思想，先把大区间放到一个集合里面，然后每次再pushdown，可以减少很多重复操作，保证复杂度是n带一个log的而不是带一个n的
这题还有点意思

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
long long p;
const long long mod = 998244353LL;
const int MAXN = 100000;
int fa[20][ MAXN * 2 ], pow[ MAXN * 2 ], n, m, L, R, l, r, len;
long long fast_pow( long long x, long long y ) {
long long BASE = x, tmp = 1;
while( y ) {
if( y & 1 ) tmp = ( tmp * BASE ) % mod;
        BASE = BASE * BASE % mod;
        y >>= 1; 
    }
return tmp;
}
int find( int M, int x ) {
if( fa[M][x] == x ) return x;
else                return fa[M][x] = find( M, fa[M][x] );
}
void Union( int M, int x, int y ) {
int fax = find( M, x ), fay = find( M, y );
if( fax != fay ) fa[M][fax] = fa[M][fay];
} 
void exgcd( long long a, long long b, long long &d, long long &x, long long &y ) {
if( b == 0 ) { d = a; x = 1; y = 0; return ; }
else { exgcd( b, a % b, d, y, x ); y -= x * ( a / b ); }
} 
long long inverse( long long a, long long b ) {
long long x, y, d;
    exgcd( a, b, d, x, y );
return ( x % mod + mod ) % mod;
} 
int main( ) {
    freopen( "monokuma.in", "r", stdin );
    freopen( "monokuma.out", "w", stdout );
scanf( "%d", &n );
for( register int i = 2; i <= n; i++ ) pow[i] = pow[ i >> 1 ] + 1; 
for( register int i = pow[n]; i >= 0 ; i-- )  for( register int j = 1; j <= n; j++ ) fa[i][j] = j;
scanf( "%d", &m );
while( m-- ) {
scanf( "%d%d%d%d", &L, &R, &l, &r );
        len = R - L + 1; int M = pow[len];
        Union( M, L, l );
        Union( M, R - ( 1 << M ) + 1, r - ( 1 << M) + 1 );
    }
for( register int j = pow[n]; j; j-- ) {
for( register int i = 1; i + ( 1 << j ) - 1 <= n; i++ ) {
int fat = find( j, i );
            Union( j - 1, i, fat );
            Union( j - 1, i + ( 1 << ( j - 1 ) ), fat + ( 1 << ( j - 1 ) ) );
        }
    }
for( register int i = 1; i <= n; i++ )
if( find( 0, i ) == i ) p++;
long long ans; long long tmp = 9LL;
    ans = tmp * fast_pow( 10LL, p - 1 ) % mod;
printf( "%I64d\n", inverse( ans, mod ) );
return 0;
}

初音未来的巡游

128MB / 1s ; cruise.cpp / c / pas / in / out

【题目描述】

Miku决定在n个地点中选择一些地点进行巡游。这n个地点由n-1条道路连接，两两之间有且仅有一条路径可以互相到达。Miku希望在这些道路中选择一些放上葱，使得Miku可以选择一种方式只经过有葱的道路而巡游完所有她选择的地点（一条道路可以被多次经过，起点任选）。
Miku想知道她至少需要准备多少葱。由于她的巡游计划可能更改，她希望你能在更改后即时回答她的疑问。

【输入格式】

第一行两个整数n,m，表示地点数和事件数。
第2至n行，每行两个整数x,y，表示地点x和地点y之间有一条无向道路。
接下来一行n个0/1数，若第i个数为1则表示i号地点初始时被选，为0则表示不选。
接下来一行m个整数，依次表示修改事件。第i个数Ai表示Ai号地点的状态发生变化，即若当前被选则改为不选，当前不选则改为被选。

【输出格式】

输出m行，第i行一个整数表示第i次事件后初音最少需要准备多少葱。
+0

【样例数据】

cruise.in cruise.out
5 8
1 2
1 3
2 4
2 5
1 0 0 1 0
5 4 2 1 2 5 3 2 3
2
2
1
0
0
0
2

【数据范围】

对于30%的数据，n,m≤3000。
对于另30%的数据，开始时所有地点都不选，保证修改操作的地点当前是不选状态。
对于100%的数据，1≤n,m≤200000，1≤x,y,Ai≤n。

可以证明答案的两倍为按DFS序排序后相邻两个选择点的距离和加上首尾点的距离，则预处理LCA，使用set维护选择的点，进行修改时根据DFS序的前驱和后继点更新答案即可。
复杂度优越 nlogn+mlogn。

代码不想写了，八十分代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

const int maxn = 222222;
int dis[maxn], dfn[maxn], fa[maxn][20];
vector<int> vec[maxn];
int rdfn[maxn];
int n, m;
int tot = 0;
set<int> st;

typedef long long ll;

void dfs(int u, int f) {
    dfn[u] = ++tot, fa[u][0] = f; rdfn[dfn[u]] = u;
for (int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i];
if (v == f) continue;
        dis[v] = dis[u]+1;
        dfs(v, u);
    }
}

void init() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j < 20; j++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
}

int lca(int u, int v) {
if (dis[u] < dis[v]) swap(u, v);
if (dis[u] > dis[v]) {
int t = dis[u]-dis[v];
for (int i = 0; i < 20; i++) {
if ((t>>i)&1) u = fa[u][i];
        }
    }
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    }
return fa[u][0];
}

int query(int u, int v) {
if (u == 0 || v == 0) return 0;
return dis[u] + dis[v] - 2*dis[lca(u,v)];
}

int selected[maxn];

int pre(int x) {
set<int>::iterator it = st.lower_bound(x);
if (it == st.begin()) return 0;
return *(--it);
}

int nex(int x) {
set<int>::iterator it = st.lower_bound(x);
if ((*it) > x) return *it;
if (it == st.end()) return 0;
return *(++it);
}

ll ans = 0;

int main() {
    freopen("cruise.in", "r", stdin);
    freopen("cruise.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
        vec[u].push_back(v), vec[v].push_back(u);
    }
for (int i = 1; i <= n; i++) {
scanf("%d", &selected[i]);
    }
    dfs(1, 0);
    init();
for (int i = 1; i <= n; i++) {
if (selected[i]) {
int a = pre(dfn[i]), b = nex(dfn[i]);
            ans -= query(rdfn[a], rdfn[b]);
            ans += query(rdfn[a], i) + query(i, rdfn[b]);
            st.insert(dfn[i]);
        }
    }
for (int i = 1; i <= m; i++) {
int t = 0;
scanf("%d", &t);
if (selected[t]) {
int a = pre(dfn[t]), b = nex(dfn[t]);
            ans += query(rdfn[a], rdfn[b]);
            ans -= query(rdfn[a], t) + query(t, rdfn[b]);
            st.erase(dfn[t]);
        } else {
int a = pre(dfn[t]), b = nex(dfn[t]);
            ans -= query(rdfn[a], rdfn[b]);
            ans += query(rdfn[a], t) + query(t, rdfn[b]);
            st.insert(dfn[t]);
        }
        selected[t] ^= 1;
        ll tmp = ans;
if (st.size() > 1) {
set<int>::iterator b = st.begin(), e = st.end();
            -- e;
            tmp += query(rdfn[*b], rdfn[*e]);
        }
printf("%lld\n", tmp/2);
    }
return 0;
}

秒客网

机房模拟赛 2017年9月26日数据结构

加帕里的聚会

【题目描述】

【输入格式】

【输出格式】

【样例数据】

【样例解释】

【数据范围】

黑白熊的密码

【题目描述】

【输入格式】

【输出格式】

【样例数据】

【样例解释】

【数据范围】

题解：

初音未来的巡游

【题目描述】

【输入格式】

【输出格式】

【样例数据】

【数据范围】

相关文章

机房模拟赛 2017年9月26日 数据结构

加帕里的聚会

【题目描述】

【输入格式】

【输出格式】

【样例数据】

【样例解释】

【数据范围】

黑白熊的密码

【题目描述】

【输入格式】

【输出格式】

【样例数据】

【样例解释】

【数据范围】

题解：

初音未来的巡游

【题目描述】

【输入格式】

【输出格式】

【样例数据】

【数据范围】

相关文章

机房模拟赛 2017年9月26日数据结构