前言
最无语的一集
T1 数对 原题
给定整数 \(L,R\ (L\ \le\ R)\)，请计算满足以下条件的整数对 \((x,y)\) 的数量：
- \(L\ \le\ x,y\ \le\ R\)
- 设 \(g\) 是 \(x,y\) 的最大公约数，则满足以下条件：
- \(g\ \neq\ 1\) 且 \(\frac{x}{g}\ \neq\ 1\) 且 \(\frac{y}{g}\ \neq\ 1\)
很简单的容斥 考虑原问题拆分成
\(S(m,m)-S(n-1,m)-S(n,m-1)+S(n-1,n-1)\)
其中\(S(n,m)\)函数表示 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(g…)\)
考虑\(S\)函数求法 考虑容斥
先钦定满足： \(g=1\)
非常容易 一个莫比乌斯反演搞定
然后是：\(x=g\) 这个也很简单 只需要枚举 \(g\) 然后算一下即可
\(y=g\) 同理可得
然后看一下钦定满足 \(g=1,x=g\) 很明显 \(x=1\) y能取任意数
看一下钦定满足 \(x=g,y=g\) 很明显 \(x=y\) \(x,y\)能取 \(min(n,m)\)
最后看一下满足三个条件 很明显只有 \(x=y=1\)的情况
容斥即可
时间复杂度\(O(n)\)
ps:\(l=1\)需要特判
Code
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
int isp[N],mu[N];
int P[N],l;
int n,m;
ll ans;
void init(int n)
{
mu[1]=isp[1]=1;
for(int i=2;i<=n;i++)
{
if(!isp[i])
{
P[++l]=i;
mu[i]=-1;
}
for(int j=1;j<=l&&i*P[j]<=n;j++)
{
isp[i*P[j]]=1;
if(i%P[j]==0)
{
mu[i*P[j]]=0;
break;
}
mu[i*P[j]]=-mu[i];
}
}
}
ll solve(int n,int m)
{
ll sum=1ll*n*m;
for(int i=1;i<=n;i++)
sum-=1ll*(n/i)*(m/i)*mu[i];
//task1
for(int i=1;i<=n;i++)
sum-=(m/i);
//task1
for(int i=1;i<=m;i++)
sum-=(n/i);
//task1
sum=sum+n+m+min(n,m); //task2
sum--;//task 3
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
if(n==1) n++;
init(m);
printf("%lld",solve(m,m)-solve(m,n-1)-solve(n-1,m)+solve(n-1,n-1));
return 0;
}
T2 小偷和警察 原题
简要题意：给你一个无向图 给出 \(q\) 个问题 每次问你如果删掉一条点或边后 \(A\) 点是否还能到 \(B\) 点
思考：
考虑缩点
在一个点双中的点就不要管它了 问题就在两个点双 这个问题考虑缩点成树
我们知道 强连通分量中缩点可以将图缩成一个 DAG 变双中找桥也可以缩成一棵树 那么点双的缩点方法是什么？就是圆方树
什么是原方树呢？
考虑一个点双 点双里面所有的圆点连向一个方点 那么只有割点连了多个点双 这样子能保证连通性而且最终一定是一棵树
边怎么搞？找桥！一个桥就是连接多个割点的边
那么怎么找？实际上 我们建的那个方点实际上就代表的一条桥
为什么？因为这是当前割点连向下一个点双的媒介 如果判断出这是桥 这个方点就代表桥了！
然后现在问题就转化成 在路线 \(A\space \to \space B\) 中 是否存在点\(C\)
然后 LCA 分类讨论太麻烦了 我们选择直接大力树剖判断就可以了
Code
#include<bits/stdc++.h>
#define ll long long
#define N 200005
#define M 1000005
using namespace std;
int n,m,g;
vector <int> G[N],E[N];
int col[N],colcnt,id[N],low[N],cnt;
int q[N],l;
int dep[N],fa[N],size[N],Son[N];
int top[N];
map <pair<int,int>,int> mp;
void tarjan(int x,int fa)
{
id[x]=low[x]=++cnt;
q[++l]=x;
int child=0;
for(int i=0;i<G[x].size();i++)
{
int to=G[x][i];
if(to==fa) continue;
if(!id[to])
{
tarjan(to,x);
low[x]=min(low[to],low[x]);
if(low[to]>=id[x])
{
colcnt++;
if(low[to]>id[x]) mp[make_pair(x,to)]=mp[make_pair(to,x)]=colcnt;
while(q[l+1]!=to)
{
int o=q[l--];
E[o].push_back(colcnt);
E[colcnt].push_back(o);
}
E[x].push_back(colcnt);
E[colcnt].push_back(x);
}
child++;
}
else low[x]=min(low[x],id[to]);
}
}
void dfs1(int now,int f)
{
dep[now]=dep[f]+1;
fa[now]=f;
size[now]=1;
int maxx=0;
for(int i=0;i<E[now].size();i++)
{
int son=E[now][i];
if(son==f) continue;
dfs1(son,now);
size[now]+=size[son];
if(size[son]>maxx) maxx=size[son],Son[now]=son;
}
}
void dfs2(int now,int topf)
{
top[now]=topf;
if(!Son[now]) return;
dfs2(Son[now],topf);
for(int i=0;i<E[now].size();i++)
{
int son=E[now][i];
if(son==fa[now]||son==Son[now]) continue;
dfs2(son,son);
}
}
bool lca(int a,int b,int c)
{
bool p=0;
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]]) swap(a,b);
if(top[a]==top[c]&&dep[c]<=dep[a]) p=1;
a=fa[top[a]];
}
if(dep[a]<dep[b]) swap(a,b);
if(top[a]==top[c]&&dep[c]>=dep[b]&&dep[c]<=dep[a]) p=1;
return p;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
colcnt=n;
tarjan(1,0);
dfs1(1,0);
dfs2(1,1);
scanf("%d",&g);
while(g--)
{
int opr;
int a,b,c,d;
scanf("%d%d%d%d",&opr,&a,&b,&c);
if(opr==1)
{
scanf("%d",&d);
int e=mp[make_pair(c,d)];
if(e==0)
{
printf("yes\n");
continue;
}
c=e;
}
if(lca(a,b,c)) printf("no\n");
else printf("yes\n");
}
return 0;
}
T3 无线网络 原题
题意给你一个有向无环图 有一个总父亲 你要给每个点定一个父亲 使得所有点儿子数的最大值最小 输出 字典序最小的方案 方案要保证联通性 总父亲的儿子数不算
思考：
想一下 如果每个点都有一个父亲 只有总结点没有父亲 那么图肯定是保证联通的 因为这就是一棵树 所以 一个点和他的祖父没有关系 所以只需考虑父亲
所以 我们可以把原图抽象成一个二分图 考虑网络流模型
我们设一个原点 \(S\) 连接着左边 \(n\) 个点 流量为1
中间如果有一条有向边 就把左边的点连向右边的对应点 流量为1
还有一些能直接流向总父亲的 直接连一条流向 \(T\) 的边
还有一个汇点 \(T\) 连接着右边\(n\)个点 流量为 \(K\)
我们发现 其实 \(K\) 就是最大儿子数
所以只要跑一遍网络流 如果汇点的值为 \(N\) 那么就存在合法方案
所以可以二分答案
然后是怎么枚举最小字典序
其实每个边暴力枚举父亲即可 记得割掉其他边 特别注意与 \(T\) 相连的边 跑\(N^2\)次网络流 能过
分析一下时间复杂度:\(O(n^2m\log n+n^4m)\)
Code:
#include<bits/stdc++.h>
#define ll long long
#define N 105
using namespace std;
int n,s,t;
char c[N][N];
int tot=2,head[N*2];
struct edge{
int to,next,w;
}e[N*N*8];
void add(int u,int v,int w)
{
e[tot]=(edge){v,head[u],w};
head[u]=tot++;
}
int q[N],l,r;
int pre[N],dis[N];
bool bfs()
{
fill(dis,dis+1+t+1,-1);
l=r=0;
pre[s]=head[s];
dis[s]=0;
q[++r]=s;
while(l<r)
{
int x=q[++l];
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(e[i].w&&dis[to]==-1)
{
dis[to]=dis[x]+1;
pre[to]=head[to];
q[++r]=to;
if(to==t) return 1;
}
}
}
return 0;
}
int dfs(int now,int sum)
{
if(now==t) return sum;
int cnt=0,k;
for(int i=pre[now];i&∑i=e[i].next)
{
pre[now]=i;
int to=e[i].to;
if(e[i].w&&dis[to]==dis[now]+1)
{
k=dfs(to,min(sum,e[i].w));
if(k==0) dis[to]=2e9;
e[i].w-=k;
e[i^1].w+=k;
sum-=k;
cnt+=k;
}
}
return cnt;
}
int Dinic()
{
int sum=0;
while(bfs()) sum+=dfs(s,2e9);
return sum;
}
int fa[N];
bool check(int k)
{
fill(head,head+1+t+1,0);
tot=2;
for(int i=1;i<=n;i++)
if(c[0][i]=='Y'&&!fa[i])
add(i,t,1),add(t,i,0);
for(int i=1;i<=n;i++)
add(s,i,1),add(i,s,0),
add(i+n,t,k),add(t,i+n,0);
for(int i=1;i<=n;i++)
{
if(fa[i])
{
add(i,fa[i],1);
add(fa[i],i,0);
continue;
}
for(int j=1;j<=n;j++)
if(c[i][j]=='Y') add(i,j+n,1),add(j+n,i,0);
}
return Dinic()==n;
}
int main()
{
scanf("%d",&n);
t=2*n+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cin>>c[i][j];
}
for(int i=1;i<=n;i++)
cin>>c[0][i];
int l=0,r=n+1;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)) r=mid-1;
else l=mid+1;
}
if(r>n)
{
printf("-1");
return 0;
}
for(int i=1;i<=n;i++)
{
bool p=0;
for(int j=1;j<=n;j++)
{
if(c[i][j]=='N') continue;
fa[i]=j+n;
if(check(r+1))
{
p=1;
break;
}
}
if(!p) fa[i]=t;
printf("%d ",fa[i]-n-1);
}
return 0;
}
T4 游戏设计
找不到原题(((
贴一下题目：
你是游戏设计师，你要设计所有长度为K的字符串，每个字符是‘A’或‘B’或‘C’或‘D’，显然共有4^K个不同的字符串，你要给每个字符串都分配一种颜色，不同的字符串可以分配相同的颜色，颜色分配过程是由你来决定的。
奶牛Bessie是这个游戏的玩家，首先Bessie会输入一个长度是K的字符串S（每个字符也是‘A’或‘B’或‘C’或‘D’），然后Bessie每一步操作是如下两种选择之一：
-
1、 交换当前字符串S的相邻的两个字符。注意，第一个字符和最后一个字符不算相邻，即S不能看成一个环。
-
2、如果当前字符串S含有子串b[i]，那么可以把该子串替换成字符串c[i]。其中b数组和c数组都是字符串数组，作为输入数据给出来的。
如果Bessie能够通过上面的操作，使得从字符串S出发，通过若干次操作之后，能够变成字符串T（T和S是不同的字符串），且字符串T和字符串S是相同颜色的，那么Bessie就会胜利了。
作为游戏设计师的你，你的目的是想让Bessie永远都不可能胜利，也就是说无论Bessie输入的字符串S是什么，都不可能胜利。
显然，这与你对4^K个不同的字符串如何分配颜色是非常重要的。现在的问题是，你至少需要多少种不同的颜色，才能使得Bessie永远不可能胜利。
简要题意：
有一个字符串 每次可以将这个字符串的一个子串变成另一个子串 然后每次变换后不能变成相同颜色 然后字符串可以随意排列 求最少的颜色方案数
思考：
注意到可以随便排列 因此原来的字符串已经不重要了 记一个数组 \(id_{a,b,c,d}\) 表示状态即可
因为 \(a+b+c+d=n\) 所以可以去掉一维 记\(id_{a,b,c}\) 即可
然后思考一下 什么是变成另一个子串？实际上不就是一个状态变换：
状态转移有什么用呢 如果是无环的直接 \(dp\) 即可 但是有可能有环
所以我们可以直接抽象出一个图 然后转移就是连边
那么这个图里面怎么跑出最少的颜色呢？总不可能每过一个点就染色吧？
实际上可以这样想：因为一个点到另一个点必须有不同颜色 但是到了访问过的点就无需再次染色
什么情况下会有访问过的点呢？一个点能经过另一条有向边回来
诶？这不就是强连通分量吗？
然后就可以缩点成一个 DAG
DAG 就能跑拓补啦！
答案就是经过点值最大的路径
好像遗漏了一个点：怎么求点值？
先求原点值 其实就是这个问题：
- 给你 \(a\) 个 \(A\), \(b\) 个 \(B\), \(c\) 个 \(C\), \(d\) 个 \(D\),有多少中不同的排列顺序？
那么也非常容易求，就是\(C(a+b+c+d,a)\times C(b+c+d,b)\times C(c+d,c)\times C(d,d)\)
很容易理解 因为 \(A\) 的排列顺序没有区别 所以只要想怎么放就行
一个强连通分量的价值就是它的点权和 然后就可以 dp 了
为什么卡了这么久没过？还不是因为初始化不彻底就 WA 的离谱
Code
#include<bits/stdc++.h>
#define ll long long
#define N 65
using namespace std;
int g;
int m,n,c;
ll C[N][N];
string s;
int s1[N][4],s2[N][4];
ll f[N*N*N],w[N*N*N],ans;
int head[N*N*N],tot=1;
int dfn[N*N*N],col[N*N*N],low[N*N*N],cnt,colcnt;
int q[N*N*N],l,r;
int in[N*N*N],ids,id[N][N][N];
pair<int,int> E[N*N*N*N];
struct edge{
int fr,to,next;
}e[N*N*N*N];
void add(int u,int v)
{
e[tot]=(edge){u,v,head[u]};
head[u]=tot++;
}
void tarjan(int x)
{
low[x]=dfn[x]=++cnt;
q[++r]=x;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(col[to]) continue;
if(!dfn[to]) tarjan(to);
low[x]=min(low[x],low[to]);
}
if(low[x]==dfn[x])
{
colcnt++;
while(q[r+1]!=x)
col[q[r--]]=colcnt;
}
}
void init()
{
ids=cnt=colcnt=ans=l=r=0;
tot=1;
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
memset(id,0,sizeof(id));
memset(f,0,sizeof(f));
memset(w,0,sizeof(w));
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(col,0,sizeof(col));
memset(q,0,sizeof(q));
memset(in,0,sizeof(in));
}
void Sort()
{
l=r=0;
for(int i=1;i<=colcnt;i++)
if(in[i]==0) q[++r]=i;
while(l<r)
{
int x=q[++l];
f[x]=max(w[x],f[x]);
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
in[to]--;
if(in[to]==0) q[++r]=to;
f[to]=max(f[to],f[x]+w[to]);
}
ans=max(ans,f[x]);
}
}
int main()
{
C[0][0]=1;
for(int i=1;i<=40;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
scanf("%d",&g);
while(g--)
{
scanf("%d%d",&n,&m);
c=(n+1)*(n+1)*(n+1)+5;
init();
for(int i=1;i<=m;i++)
{
cin>>s;
for(int j=0;j<s.size();j++)
s1[i][s[j]-'A']++;
}
for(int i=1;i<=m;i++)
{
cin>>s;
for(int j=0;j<s.size();j++)
s2[i][s[j]-'A']++;
}
for(int i=0;i<=n;i++)
for(int j=0;j<=n-i;j++)
for(int k=0;k<=n-i-j;k++)
{
id[i][j][k]=++ids;
f[ids]=C[n][i]*C[n-i][j]*C[n-i-j][k];
}
for(int i=0;i<=n;i++)
for(int j=0;j<=n-i;j++)
for(int k=0;k<=n-i-j;k++)
{
int now=id[i][j][k];
for(int l=1;l<=m;l++)
if(i>=s1[l][0]&&j>=s1[l][1]&&k>=s1[l][2]&&n-i-j-k>=s1[l][3])
{
int to=id[i-s1[l][0]+s2[l][0]][j-s1[l][1]+s2[l][1]][k-s1[l][2]+s2[l][2]];
E[tot]=make_pair(now,to);
add(now,to);
}
}
for(int i=1;i<=ids;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=ids;i++)
w[col[i]]+=f[i];
int tots=tot;
tot=1;
fill(head+1,head+1+ids+1,0);
fill(f+1,f+1+c+ids,-1);
for(int i=1;i<tots;i++)
{
int u=e[i].fr,v=e[i].to;
if(col[u]!=col[v])
add(col[u],col[v]),in[col[v]]++;
}
Sort();
printf("%lld\n",ans);
}
return 0;
}