提高组联考1
A. 字符交换
每个字母分开考虑，一定至少有一个字母不动，枚举不动的位置，向两侧扩展至最大，尝试更新答案
注意无穷大的选择
code
#include
#include
using namespace std;
int sum[27][4005],cnt[27];
char c[4005];
int main(){
freopen("swap.in","r",stdin);
freopen("swap.out","w",stdout);
int n,k;scanf("%d%d",&n,&k);
scanf("%s",c+1);
for(int i=1;i<=n;++i){
int ls=c[i]-'a'+1;++cnt[ls];
sum[ls][cnt[ls]]=i;
}
int ans=0;
for(int i=1;i<=26;++i){
if(cnt[i]<=ans)continue;
for(int j=1;j<=cnt[i];++j){
int p1=j-1,p2=j+1,l=1,r=1,res=k,ls=1;
while(1){
int net=-1,dis=2147483647;
if(p1>=1){net=p1;dis=sum[i][j]-l-sum[i][p1];}
if(p2<=cnt[i]&&dis>sum[i][p2]-sum[i][j]-r){net=p2;dis=sum[i][p2]-sum[i][j]-r;}
if(dis>res)break;
res-=dis;++ls;
if(netls?ans:ls;
}
}
printf("%d\n",ans);
return 0;
}
B. 平方数
\(a=p^2*x\)
\(b=q^2*y\)
（\(x,y\)不含平方因子）
若\(a*b\)为平方数，那么有
\(x*y\)为平方数，即\(x==y\)
将每个数的平方因子去掉，剩余部分判断有多少相等的，统计答案，可以使用排序
怎么去掉平方因子
-
暴力：直接枚举平方数->TLE
-
接近正解的优雅暴力: 筛质数，每次尝试去掉质数平方因子，大大减少枚举量，
像我一样写的优雅些会有90pts->TLE -
发现瓶颈在于枚举量上，考虑减少枚举的质数
我们只筛出来\(1-\sqrt[3]{max}\)的质数进行枚举，将只有一个的质因子也去掉，（记下来）
考虑一个数能写成\(p^2*x\)的形式，其中\(p>\sqrt[3]{max}\)，那么有\(x<\sqrt[3]{max}\)
所以最后再判断一下这个数是不是平方数，然后把去掉的单个因子乘回来
code
#include
#include
#include
#include
using namespace std;
const int maxn=300005;
int a[maxn];
bool flag[40005];
int prime[20005],cnt;
void prim(){
for(int i=2;i<=1000;++i){
if(!flag[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=1000;++j){
flag[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int main(){
freopen("square.in","r",stdin);
freopen("square.out","w",stdout);
int n;scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
prim();
for(int i=1;i<=n;++i){
int num=1;
for(int j=1;j<=cnt;++j){
int ls=prime[j]*prime[j];
if(ls>a[i])break;
while(a[i]%ls==0)a[i]/=ls;
if(a[i]%prime[j]==0){
num*=prime[j];
a[i]/=prime[j];
}
}
int p=round(sqrt(a[i]));
if(a[i]==p*p)a[i]=1;
a[i]*=num;
}
sort(a+1,a+n+1);
long long ans=0;
int las=a[1],num=1;
for(int p=2;p<=n+1;++p){
if(las!=a[p]){
las=a[p];
ans+=1ll*num*(num-1)/2;
num=0;
}
++num;
}
printf("%lld\n",ans);
return 0;
}
C. 多维网络
组合+容斥，组合结合DP可以水到75pts
考虑到了正解需要容斥，但是过于复杂，写不出来，题解的分步容斥真的是太妙了
不考虑坏点从A到B的路径数\(\Pi_{i=1}^{d} C_{sum}^{x_i}\)(\(sum\)为剩余的总距离差)
设\(path(x,y)\)表示\(x\)到\(y\)的路径数
一个坏点\(x\)，不合法的路径数为\(path(A,x)*path(x,B)\)
多个坏点，不合法路径数为单个坏点不合法路径+通过两个坏点的路径书-通过三个...................
发现这样很难写，而且复杂度极高
换一种思路，无论哪种不合法路径，一定经过一个坏点，如果我们知道到达坏点\(i\)，且不经过其他坏点的路径数，那么答案就好求了
设\(f[i]\)为到达坏点\(i\)的，不经过其他坏点的方案数
有\(f[i]=path(A,i)-\sum path(j,i)*f[j]\) \((j\)的所有坐标都小于\(i)\)
那么我们需要预先对点进行排序，以确定枚举顺序，我使用了所有坐标的和进行排序，（因为瞎调所以多写了几个没用的取模，请自动忽略）
最后答案为\(path(A,B)-\sum_{i=1}^{n} f[i]*path(i,B)\)
code
#include
#include
#include
using namespace std;
const int mod=1e9+7;
const int maxn=5000000;
struct zb{
int id[505];
long long sum;
}h[505];
bool cmp(zb x,zb y){return x.sum>=1;
}
return ans;
}
long long get_C(int n,int m){return jc[n]*inv[m]%mod*inv[n-m]%mod;}
void ycl(){
jc[0]=1;jc[1]=1;inv[0]=1;
for(int i=2;i<=maxn;++i)jc[i]=jc[i-1]*i%mod;
inv[maxn]=qpow(jc[maxn],mod-2);
for(int i=maxn-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%mod;
}
long long path(zb &x){
long long sum=0,ans=1;
for(int i=1;i<=d;++i)sum=(sum+x.id[i])%mod;
for(int i=1;i<=d;++i){
ans=ans*get_C(sum,x.id[i])%mod;
sum=(sum-x.id[i]+mod)%mod;
}
return ans%mod;
}
long long get_path(int x,int y){
zb z;
for(int i=1;i<=d;++i)z.id[i]=h[y].id[i]-h[x].id[i];
return path(z);
}
bool check(int x,int y){
for(int i=1;i<=d;++i)
if(h[x].id[i]>h[y].id[i])return false;
return true;
}
void ts(){printf("%lld\n",path(h[0]));}
void work(){
sort(h+1,h+n+1,cmp);
long long ans=path(h[0]);
for(int i=1;i<=n;++i){
f[i]=path(h[i]);
for(int j=1;j D. Lesson5!
暴力枚举删去的点+拓扑DP可以得到60pts
正反建图拓扑得到到达每个点的最远路径\(dl[],dr[]\)，一条连接\(u,v\)的边的权值为\(dl[u]+dr[v]+1\)，实际上是经过该边的最长路径的长度
正向拓扑，分层考虑所有点（按照拓扑序处理即可）
删除一个点，所有与它有关的边都不能贡献答案。
处理每个点时，删除所有入边的权值的贡献，此时出边的贡献还没有统计，相当于删掉了该点，然后查询当前的最大值，尝试更新答案
这个点考虑完之后就可以把它的出边都贡献答案，同一层的路径不会相互影响
进入下一层会有下一条边代表这条最长路，所以一定会不重不漏
code
#include
#include
#include
using namespace std;
const int maxn=100005;
const int maxm=500005;
const int inf=99999999;
queueq;
int max(int x,int y){return x>y?x:y;}
struct edge{int from,net,to,val;};
struct node{int l,r,val;};
struct G{
edge e[maxm];
int head[maxn],tot,rd[maxn];
void add(int u,int v){
e[++tot].net=head[u];
head[u]=tot;
e[tot].to=v;
e[tot].from=u;
++rd[v];
}
void pre_work(){
tot=0;
memset(head,0,sizeof(head));
memset(rd,0,sizeof(rd));
}
}G1,G2;
int rem[maxn],n,m,dl[maxn],dr[maxn],a[maxn];
void In(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int u,v;scanf("%d%d",&u,&v);
G1.add(u,v);G2.add(v,u);
}
}
void tp(){
a[0]=0;
for(int i=1;i<=n;++i)rem[i]=G1.rd[i];
for(int i=1;i<=n;++i)if(!rem[i])q.push(i),a[++a[0]]=i;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=G1.head[x];i;i=G1.e[i].net){
int v=G1.e[i].to;
--rem[v];if(!rem[v])q.push(v),a[++a[0]]=v;
dl[v]=max(dl[v],dl[x]+1);
}
}
for(int i=1;i<=n;++i)rem[i]=G2.rd[i];
for(int i=1;i<=n;++i)if(!rem[i])q.push(i);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=G2.head[x];i;i=G2.e[i].net){
int v=G2.e[i].to;
--rem[v];if(!rem[v])q.push(v);
dr[v]=max(dr[v],dr[x]+1);
}
}
for(int i=1;i<=G1.tot;++i)G1.e[i].val=dl[G1.e[i].from]+dr[G1.e[i].to]+1;
for(int i=1;i<=G2.tot;++i)G2.e[i].val=dr[G2.e[i].from]+dl[G2.e[i].to]+1;
}
struct tree{
int cnt;
node t[maxn<<2|1];
void pre_work(){
cnt=0;
memset(t,0,sizeof(t));
}
void add(int x,int l,int r,int k){
if(l==r){
++t[x].val;
return;
}
int mid=(l+r)>>1;
if(k<=mid){if(!t[x].l)t[x].l=++cnt;add(t[x].l,l,mid,k);}
if(k>mid){if(!t[x].r)t[x].r=++cnt;add(t[x].r,mid+1,r,k);}
++t[x].val;
}
void del(int x,int l,int r,int k){
if(l==r){
--t[x].val;
return;
}
int mid=(l+r)>>1;
if(k<=mid)del(t[x].l,l,mid,k);
if(k>mid)del(t[x].r,mid+1,r,k);
--t[x].val;
}
int query(int x,int l,int r){
if(l==r)return l;
int mid=(l+r)>>1;
if(t[x].r&&t[t[x].r].val)return query(t[x].r,mid+1,r);
if(t[x].l&&t[t[x].l].val)return query(t[x].l,l,mid);
return 0;
}
}T;
void ga(){
int root=++T.cnt;
for(int i=1;i<=n;++i)T.add(root,0,n,dr[i]);
int city,ans=inf;
for(int k=1;k<=n;++k){
int i=a[k];
for(int j=G2.head[i];j;j=G2.e[j].net)T.del(root,0,n,G2.e[j].val);
T.del(root,0,n,dr[i]);
int ls=T.query(root,0,n);
if(ls