XVII Open Cup named after E.V. Pankratiev. GP of Moscow Workshops
A. Centroid Tree
枚举至多两个重心作为根，检查对于每个点是否都满足$2size[x]\leq size[father[x]]$即可。
#include
#include
#include
#include
#include
#include
#include
#include
B. Completely Multiplicative Function
爆搜每个质数是$1$还是$-1$，加上前$n$项的前缀和的绝对值必须小于$\log n$的剪枝即可通过。
更好的做法：对于质数$p$，若$p\bmod 3=1$，则填$1$，否则填$-1$。
#include
#include
using namespace std;
const int N = 1e6 + 10;
char mu[N] =
{0,1,1,-1,1,1,-1,-1,1,1,1,-1,-1,1,-1,-1,1,1,1,-1,1,1,-1,-1,-1,1,1,-1,-1,1,-1,1,1,1,1,-1,1,-1,-1,-1,1,1,1,-1,-1,1,-1,1,-1,1,1,-1,1,-1,-1,-1,-1,1,1,1,-1,-1,1,-1,1,1,1,-1,1,1,-1,-1,1,1,-1,-1,-1,1,-1,-1,1,1,1,-1,1,1,-1,-1,-1,1,1,-1,-1,-1,1,-1,-1,1,1,-1,1,1,-1,1,1,1,-1,1,-1,-1,-1,1,-1,-1,1,-1,1,1,1,-1,-1,1,-1,-1,1,1,-1,-1,1,1,1,-1,1,1,-1,-1,1,1,1,-1,-1,-1,-1,-1,1,1,1,-1,-1,1,-1,-1,-1,1,1,1,-1,-1,-1,1,1,1,1,-1,1,1,-1,-1,1,1,1,-1,-1,1,-1,-1,-1,-1,1,1,1,1,-1,1,-1,-1,-1,-1,1,1,-1,1,-1,1,1,-1,1,-1,-1,-1,1,1,1,-1,-1,1,1,-1,1,1,1,-1,-1,1,1,-1,-1,-1,-1,-1,-1,1,1,1,-1,1,-1,1,1,-1,-1,-1,1,-1,1,1,1,1,-1,1,-1,1,1,-1,-1,1,-1,-1,1,1,1,-1,-1,1,-1,-1,1,-1,1,1,1,1,-1,-1,1,-1,1,-1,-1,1,-1,-1,1,1,1,-1,1,1,-1,1,-1,1,-1,-1,-1,1,-1,-1,1,1,1,-1,1,-1,-1,1,-1,1,1,-1,-1,1,-1,-1,-1,-1,1,1,1,-1,1,1,-1,1,-1,-1,-1,1,1,-1,1,-1,1,-1,1,1,-1,1,1,-1,1,1,-1,-1,-1,-1,1,-1,1,1,1,-1,-1,-1,-1,1,1,1,-1,1,-1,-1,-1,1,-1,-1,1,1,1,-1,1,1,1,-1,-1,1,1,1,-1,1,-1,1,-1,-1,-1,-1,1,1,1,-1,-1,1,1,-1,-1,1,1,-1,1,1,-1,-1,1,1,-1,-1,-1,-1,-1,-1,1,-1,1,1,1,1,-1,1,-1,-1,1,-1,1,-1,-1,-1,1,1,1,-1,1,-1,-1,1,-1,1,1,1,1,1,-1,1,-1,1,-1,-1,-1,1,-1,-1,-1,1,1,-1,1,1,1,-1,-1,1,1,-1,-1,1,1,-1,1,1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,1,1,1,1,1,1,1,-1,-1,-1,1,1,-1,-1,1,-1,1,1,-1,1,-1,1,1,-1,-1,1,-1,-1,1,1,1,-1,1,1,-1,-1,-1,1,1,-1,-1,-1,-1,-1,1,1,-1,1,1,-1,1,-1,1,-1,1,-1,-1,1,-1,1,1,1,-1,1,1,1,-1,1,-1,-1,1,-1,-1,1,-1,-1,1,-1,1,1,1,-1,-1,-1,1,1,1,1,-1,1,1,-1,-1,1,1,-1,-1,-1,-1,-1,-1,1,1,1,-1,-1,-1,-1,1,1,1,-1,1,1,-1,1,1,1,-1,1,-1,-1,1,1,-1,-1,1,-1,1,1,-1,1,-1,1,1,-1,-1,1,-1,1,-1,1,-1,1,1,-1,1,-1,1,-1,-1,-1,1,1,1,-1,-1,1,1,-1,-1,-1,-1,1,-1,1,1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,-1,1,1,-1,-1,1,-1,1,1,-1,1,1,-1,1,-1,-1,1,-1,-1,-1,-1,-1,1,1,1,-1,-1,1,1,1,-1,1,-1,-1,1,-1,1,-1,1,-1,-1,1,-1,1,1,1,-1,-1,1,1,1,-1,1,-1,1,-1,-1,1,-1,-1,1,-1,-1,1,-1,1,-1,1,-1,-1,1,1,-1,1,-1,1,1,-1,1,-1,1,1,-1,1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,-1,-1,-1,-1,-1,1,1,1,1,-1,1,1,-1,-1,-1,-1,1,1,1,1,-1,1,-1,-1,1,1,1,-1,-1,1,1,-1,1,-1,-1,1,-1,-1,1,-1,1,1,-1,1,-1,1,-1,-1,-1,1,-1,1,-1,1,1,1,-1,-1,1,1,1,-1,1,-1,1,-1,-1,1,1,-1,-1,1,-1,-1,1,1
};
int f[N];
int first[N];
int fac[N];
int prim[N], pnum;
int n;
int lg2[N];void check()
{for (int i = 1; i <= n; i++) f[i] = f[i - 1] + mu[i];for (int i = 1; i <= n; i++)if (abs(f[i]) > 20){printf("f[%d] = %d\n", i, f[i]);while (1);}for (int i = 1; i <= n; ++i){for (int j = 1; i * j <= n; ++j){if (mu[i * j] != mu[i] * mu[j]){printf("%d %d %d %d %d %d\n", i, j, i *j, mu[i], mu[j], mu[i * j]);puts("ERROR");while (1);}}}
}bool FLAG;
inline char abs(char x) { return x > 0 ? x : -x; }
void dfs(int x,char y)
{if (x > n){//puts("YES!");FLAG = 1;return;}while (fac[x]){mu[x] = mu[fac[x]] * mu[first[x]];y+=mu[x];if (abs(y) > lg2[x])return;++x;}if (x > n){//puts("YES!");FLAG = 1;return;}{mu[x] = 1;y++;if (abs(y) <= lg2[x]){dfs(x + 1,y);}if (FLAG)return;mu[x] = -1;y -= 2;if (abs(y) <= lg2[x]){dfs(x + 1,y);}}
}void getprime()
{fac[1] = 1;for (int i = 2; i < N; i++){if (fac[i])continue;prim[pnum++] = i;for (int j = i + i; j < N; j += i){fac[j] = i;}}
}int main()
{getprime();//printf("%d\n", pnum);n = 1e6; fac[n + 1] = 0;lg2[1] = 1;for (int i = 2; i <= n; ++i){lg2[i] = lg2[i / 2] + 1;if (fac[i]){first[i] = i / fac[i];}}for (int i = 1; i <= 820; ++i)f[i] = f[i - 1] + mu[i];dfs(821,f[820]);//check();//for (int i = 1; i <= 3000; i++) printf("%d,", mu[i]);scanf("%d", &n);//n = 10;//for (int i = 1; i <= n; i++)if(!fac[i]) printf("%d %d\n", i,mu[i]);for (int i = 1; i <= n; i++)printf("%d%c", mu[i], i == n ? '\n' : ' ');return 0;
}
C. Even and Odd
求出DFS生成树，只保留树边。
对于每个基环，若它是奇环，那么上面的树边都不能保留；若它是偶环，那么若它与某个奇环相交，将会得到更大的奇环，这些边也不能保留。
用并查集维护每个点向上第一条未删去的树边，树状数组判断路径上是否存在奇环，迭代删除$O(\log n)$轮即可。如果直接用并查集维护有交的树边集合，那么只要集合内存在基本奇环则要删除，可以做到更优秀的复杂度。
预处理结束后，对于每个连通块，当成树统计答案即可。
时间复杂度$O(n\log^2n)$。
#include
const int N=200010,M=400010;
int n,m,i,x,y,g[N],v[M],nxt[M],ed;
int d[N],f[N],vis[N],dfn;
int fa[N],c[N][2];
int dep[N],gg[N];
int q[N],V[M],NXT[M],ED;
int st[N],en[N],lim,bit[M];
long long ans[2];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
int G(int x){return gg[x]==x?x:gg[x]=G(gg[x]);}
inline void ADD(int x,int y){V[++ED]=y;NXT[ED]=q[x];q[x]=ED;}
inline void modify(int x,int p){for(;x<=lim;x+=x&-x)bit[x]+=p;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}
inline void go(int x,int y){//printf("go %d %d\n",x,y);while(1){x=G(x);if(dep[x]<=dep[y])return;//printf("del %d\n",x);modify(st[x],1);modify(en[x],-1);gg[x]=f[x];}
}
void dfs1(int x,int y){f[x]=y;vis[x]=++dfn;d[x]=d[y]^1;dep[x]=dep[y]+1;gg[x]=x;st[x]=++lim;for(int i=g[x];i;i=nxt[i]){int u=v[i];if(u==y)continue;if(!vis[u]){//printf("%d->%d\n",x,u);dfs1(u,x);}}en[x]=++lim;
}
void dfs2(int x,int y){vis[x]=++dfn;for(int i=g[x];i;i=nxt[i]){int u=v[i];if(u==y)continue;if(!vis[u]){dfs2(u,x);}else if(vis[u]ask(st[x]))go(u,x);}
}
int F(int x){return fa[x]==x?x:fa[x]=F(fa[x]);}
inline void merge(int x,int y){//printf("merge %d %d\n",x,y);x=F(x),y=F(y);fa[x]=y;ans[0]+=1LL*c[x][0]*c[y][0];ans[0]+=1LL*c[x][1]*c[y][1];ans[1]+=1LL*c[x][0]*c[y][1];ans[1]+=1LL*c[x][1]*c[y][0];c[y][0]+=c[x][0];c[y][1]+=c[x][1];
}
int main(){scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d",&x,&y);add(x,y),add(y,x);}dfs1(1,0);for(i=1;i<=n;i++)vis[i]=0;for(int _=10;_;_--){for(i=1;i<=n;i++)vis[i]=q[i]=0;dfn=ED=0;dfs2(1,0);}for(i=1;i<=n;i++)fa[i]=i,c[i][d[i]]=1;for(i=2;i<=n;i++)if(gg[i]==i)merge(i,f[i]);printf("%lld %lld",ans[0],ans[1]);
}
/*
4 3
1 2
1 3
1 44 4
1 2
2 3
3 4
4 25 6
1 2
2 3
3 4
4 5
1 4
3 54 5
1 2
1 3
2 4
3 4
2 36 8
1 2
1 3
2 4
3 4
3 5
4 5
4 6
5 6
*/
D. Great Again
设$f[i]$表示前$i$个人分组的最大得分，枚举当前段的得分，线段树优化转移即可。
时间复杂度$O(n\log n)$。
#include
#include
#include
#include
using namespace std;
const int N=300010,M=2222222;
int n,m,j,L,R,i,lim,tmp,a[N],f[N];
int v[M];
multisetT[N*2];
void build(int x,int a,int b){v[x]=-M;if(a==b)return;int mid=(a+b)>>1;build(x<<1,a,mid),build(x<<1|1,mid+1,b);
}
inline void up(int x){v[x]=max(v[x<<1],v[x<<1|1]);}
void ins(int x,int a,int b,int c,int p){if(a==b){T[a].insert(p);v[x]=*T[a].rbegin();return;}int mid=(a+b)>>1;if(c<=mid)ins(x<<1,a,mid,c,p);else ins(x<<1|1,mid+1,b,c,p);up(x);
}
void del(int x,int a,int b,int c,int p){if(a==b){T[a].erase(T[a].find(p));if(T[a].empty())v[x]=-M;elsev[x]=*T[a].rbegin();return;}int mid=(a+b)>>1;if(c<=mid)del(x<<1,a,mid,c,p);else del(x<<1|1,mid+1,b,c,p);up(x);
}
int ask(int x,int a,int b,int c,int d){if(c<=a&&b<=d)return v[x];int mid=(a+b)>>1,t=-M;if(c<=mid)t=ask(x<<1,a,mid,c,d);if(d>mid)t=max(t,ask(x<<1|1,mid+1,b,c,d));return t;
}
int main(){scanf("%d%d%d",&n,&L,&R);for(i=1;i<=n;i++){scanf("%d",&a[i]);a[i]+=a[i-1];}m=n+n;for(i=0;i<=n;i++)a[i]+=n;//0..mbuild(1,0,m);for(i=1,j=0;i<=n;i++){if(i>=L)ins(1,0,m,a[i-L],f[i-L]);if(i-R-1>=0)del(1,0,m,a[i-R-1],f[i-R-1]);f[i]=ask(1,0,m,a[i],a[i]);if(a[i]>0)f[i]=max(f[i],ask(1,0,m,0,a[i]-1)+1);if(a[i]
E. Jumping is Fun
每个点不管跳多少步，能到达的范围必然是一个区间。
设$f[i][j]$表示$j$点跳$2^i$步能到的范围，可以用线段树求出。
从高到低枚举答案的二进制的每一位，利用$f$数组求出范围，然后枚举$x$，判断是否存在$y$满足$x$与$y$都不能相互到达即可。
时间复杂度$O(n\log^2n)$。
#include
#include
using namespace std;
const int N=200010,M=530000,K=18;
int n,i,j,x,pre[N],suf[N],ans;
struct P{int x,y;P(){}P(int _x,int _y){x=_x,y=_y;}P operator+(const P&b){return P(min(x,b.x),max(y,b.y));}
}f[K][N],v[K][M],a[N],b[N];
void build(int o,int x,int a,int b){if(a==b){v[o][x]=f[o][a];return;}int mid=(a+b)>>1;build(o,x<<1,a,mid),build(o,x<<1|1,mid+1,b);v[o][x]=v[o][x<<1]+v[o][x<<1|1];
}
P ask(int o,int x,int a,int b,int c,int d){if(c<=a&&b<=d)return v[o][x];int mid=(a+b)>>1;P t(N,1);if(c<=mid)t=ask(o,x<<1,a,mid,c,d);if(d>mid)t=t+ask(o,x<<1|1,mid+1,b,c,d);return t;
}
inline P go(int o,P b){//if(b.x<1||b.y>n)puts("ERROR");return ask(o,1,1,n,b.x,b.y);
}
inline bool check(int o){//printf("now check %d\n",o);int i;for(i=1;i<=n;i++)b[i]=go(o,a[i]);pre[0]=N;for(i=1;i<=n;i++)pre[i]=min(pre[i-1],b[i].y);suf[n+1]=0;for(i=n;i;i--)suf[i]=max(suf[i+1],b[i].x);for(i=1;i<=n;i++){if(pre[b[i].x-1]i){//printf("to suf x=%d\n",i);return 1;}}return 0;
}
int main(){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&x);f[0][i].x=max(1,i-x);f[0][i].y=min(n,i+x);}build(0,1,1,n);for(i=1;i%d %d %d\n",i,a[i].x,a[i].y);}for(i=K-1;~i;i--){if(check(i)){//printf("checkok %d\n",i);//for(j=1;j<=n;j++)printf("a[%d]=%d %d\n",j,a[j].x,a[j].y);for(j=1;j<=n;j++)a[j]=b[j];//for(j=1;j<=n;j++)printf("b[%d]=%d %d\n",j,a[j].x,a[j].y);ans|=1<
F. Online LCS
将两个串插入同一个后缀自动机，同时维护$v[i][j]$表示节点$i$表示的子串集合是否在串$j$中出现过。
每次加入新的字符的时候，将对应节点到根路径上所有$v$都标记为$1$，当$v[i][0]$与$v[i][1]$同时为$1$时，可以用它的最大长度去更新最长公共子串的长度。
注意到每个点在每种串中只需要被标记一次，故发现标记过则退出即可。
时间复杂度$O(n)$。
#include
#include
const int N=5000010;//5e6
int tot=1,last[2]={1,1},pre[N*2],son[N*2][2],ml[N*2];bool v[N*2][2];
int n,i,ans;long long sum;char a[N];
inline void extend(int o,int w){int p=++tot,x=last[o],r,q;for(ml[last[o]=p]=ml[x]+1;x&&!son[x][w];x=pre[x])son[x][w]=p;if(!x)pre[p]=1;else if(ml[x]+1==ml[q=son[x][w]])pre[p]=q;else{pre[r=++tot]=pre[q];memcpy(son[r],son[q],sizeof son[r]);v[r][0]=v[q][0];v[r][1]=v[q][1];ml[r]=ml[x]+1;pre[p]=pre[q]=r;for(;x&&son[x][w]==q;x=pre[x])son[x][w]=r;}while(p&&!v[p][o]){v[p][o]=1;if(v[p][o^1]&&ml[p]>ans)ans=ml[p];p=pre[p];}
}
int main(){scanf("%d%s",&n,a);for(i=0;i
G. Brawling
只有左侧朝左的若干人以及右侧朝右的若干人不能保留。
#include
#include
#include
#include
#include
#include
#include
#include
H. I Spy
随机选择一个点$P=(x,y)$，在附近找一个辅助点$Q=(x+1,y)$。
因为随机选择，故可以认为对于$P$和$Q$，没有任意两个点离它们的距离相同。
二分半径求出离$P$和$Q$最近的两个点到它们的距离$R_1,R_2$，得到两个圆，在交点附近检查是否存在点即可。
如此反复，即可找出所有点的位置。
#include
#include
#include
#include
#include
#include
#include
#include
I. Rage Minimum Query
若修改是往小修改，那么显然可以$O(1)$直接更新全局最小值。
否则若目前是将最小值往大了修改，那么这是小概率事件，直接$O(n)$重算全局最小值即可。
#include
typedef unsigned int U;
int n,q;
U x0,x1,a,b,c,i,x,v[10000010],mi,ans,p=1;
inline U nxt(){U t=x0*a+x1*b+c;x0=x1;x1=t;return x0>>2;
}
int main(){scanf("%d%d%u%u%u%u%u",&n,&q,&x0,&x1,&a,&b,&c);for(i=0;i>1;mi=~0U>>1;while(q--){i=nxt()%n;x=nxt();if(x<=v[i]){if(xmi){v[i]=x;}else{v[i]=x;mi=x;for(i=0;i
J. Regular Cake
在正$n$边形与正$m$边形之间紧贴一个正$lcm(n,m)$边形，可以得到答案为：
\[\frac{\cos\left(\frac{\pi}{lcm(n,m)}\right)\tan\left(\frac{\pi}{m}\right)}{\sin\left(\frac{\pi}{n}\right)}\]
#include
#include
typedef long long ll;
using namespace std;
const double pi=acos(-1.0);
ll n,m,k;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main(){scanf("%lld%lld",&n,&m);k=n*m/gcd(n,m);printf("%.13f",cos(pi/k)*tan(pi/m)/sin(pi/n));
}
K. Piecemaking
树形DP，设$f[i][j]$表示考虑$i$的子树，$i$点颜色为$j$的最小代价。
时间复杂度$O(n)$。
#include
#include
using namespace std;
typedef long long ll;
const int N=200010;
const ll inf=1LL<<60;
int n,m,i,x,y,z,g[N],v[N<<1],w[N<<1],nxt[N<<1],ed;
int col[N];
ll f[N][3],h[3],ans;
inline void up(ll&a,ll b){a>b?(a=b):0;}
inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int y){for(int i=0;i<3;i++)f[x][i]=inf;f[x][col[x]]=0;for(int i=g[x];i;i=nxt[i]){int u=v[i];if(u==y)continue;dfs(u,x);for(int j=0;j<3;j++)h[j]=inf;for(int j=0;j<3;j++)if(f[x][j]
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！