ARC165
A
猜的结论,质因数\(\ge2\)
感觉证明不难
#include<bits/stdc++.h>
using namespace std;
int t;
int n;
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int cnt_prime=0;
for(int i=2;i<=n/i;i++)
{
if(n%i==0)
{
++cnt_prime;
while(n%i==0)
{
n/=i;
}
}
}
if(n>1)
{
++cnt_prime;
}
if(cnt_prime>=2)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
B
对于两段操作区间,我们比较是否更有关键在于第一个变动的位置
这启示我们维护一段区间最长的不变位置,注意到相同的变动位置操作的左区间小的优
这玩意直接滑动窗口+双指针维护就行了(虽然我是直接二分的
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int a[MAXN];
int n,k;
int dq[MAXN];
int head;
int tail;
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
head=1;
tail=0;
int Maxi=0;
int Kt;
for(int i=1;i<=n;i++)
{
while(head<=tail&&i-dq[head]>=k)
{
head++;
}
while(head<=tail&&a[dq[tail]]>a[i])
{
tail--;
}
dq[++tail]=i;
if(i>=k)
{
int l=head;
int r=tail;
int Key=i-k;
while(l<=r)
{
int mid=(l+r)>>1;
if(dq[mid]-(i-k)==mid-head+1)
{
l=mid+1;
Key=dq[mid];
}
else
{
r=mid-1;
}
}
if(Key>Maxi)
{
Kt=i-k+1;
Maxi=Key;
}
if(Key==i)
{
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
}
}
sort(a+Kt,a+Kt+k);
//printf("%d\n",Kt);
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
}
C
有点抽象,建议和\(B\)换个位置
可以发现\(X\)的上界由最多由两条边决定
直接二分+二分图判定即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
struct Edge{
int v,val;
bool operator<(const Edge x)const{
return val<x.val;
}
};
int n,m;
int x,y,z;
vector<Edge>g[MAXN];
int col[MAXN];
bool found=0;
int Lit;
void dfs(int x,int c)
{
if(col[x])
{
if(col[x]!=c)
{
found=1;
}
return;
}
col[x]=c;
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i].v;
int w=g[x][i].val;
if(w<Lit)
{
dfs(v,(c==1)?2:1);
}
}
}
bool check(int mid)
{
for(int i=1;i<=n;i++)
{
col[i]=0;
}
found=0;
Lit=mid;
for(int i=1;i<=n;i++)
{
if(!col[i])
{
dfs(i,1);
}
}
if(found)
{
return 0;
}
else
{
return 1;
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&z);
g[x].push_back((Edge){y,z});
g[y].push_back((Edge){x,z});
}
int Mini=2e9+1;
for(int i=1;i<=n;i++)
{
sort(g[i].begin(),g[i].end());
if(g[i].size()==1)
{
}
else
{
Mini=min(Mini,g[i][0].val+g[i][1].val);
}
}
int l=0;
int r=Mini;
int Key;
//cerr<<"fuck"<<endl;
while(l<=r)
{
//cerr<<l<<' '<<r<<endl;
int mid=((long long)l+r)>>1;
if(check(mid))
{
Key=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
printf("%d\n",Key);
}
E
经典鞭尸题(虽然是搬运工
可以发现如果我们操作一些点数小于\(k\)的联通块实际上对最后的答案也没影响
然后还是经典的把贡献拆到每个点上,我们只需要计算\(u\)这个点产生有用断边的概率即可
然后接下来我们可以假装所有点都被操作一次,生成一个排列,依次操作,只有当\(u\)
操作时联通块\(\ge k\)时这个点可以产生贡献
根据这个我们可以设\(dp_{u,i,j}\)表示当前\(u\)及其子树内有\(i\)个点在\(u\)之前操作,当前有\(j\)个点与\(u\)联通的方案数
这玩意求得是子树内得贡献,多换几次根就行了
// LUOGU_RID: 125255492
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=105;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int fac[MAXN];
int inv_fac[MAXN];
int C(int n,int m)
{
if(n<m||m<0)
{
return 0;
}
if(n==m||m==0)
{
return 1;
}
return ((((long long)fac[n]*inv_fac[m])%MOD)*inv_fac[n-m])%MOD;
}
int n,k;
int x,y;
vector<int>g[MAXN];
int dp[MAXN][MAXN][MAXN];
int Siz[MAXN];
int Tmp[MAXN][MAXN];
void dfs(int x,int f)
{
Siz[x]=1;
dp[x][0][0]=1;
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
dfs(v,x);
for(int p=0;p<=Siz[x]+Siz[v];p++)
{
for(int q=0;q<=Siz[x]+Siz[v];q++)
{
Tmp[p][q]=dp[x][p][q];
dp[x][p][q]=0;
}
}
for(int p1=0;p1<=Siz[x];p1++)
{
for(int q1=0;q1<=Siz[x];q1++)
{
for(int p2=0;p2<=Siz[v];p2++)
{
for(int q2=0;q2<=Siz[v];q2++)
{
dp[x][p1+p2][q1+q2]=((long long)dp[x][p1+p2][q1+q2]+((long long)Tmp[p1][q1]*dp[v][p2][q2]))%MOD;
}
}
}
}
Siz[x]+=Siz[v];
}
for(int i=1;i<=Siz[x];i++)
{
dp[x][i][Siz[x]]=((long long)dp[x][i][Siz[x]]+C(Siz[x]-1,i-1))%MOD;//为啥要减1？？
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
fac[0]=1;
inv_fac[0]=1;
for(int i=1;i<=n;i++)
{
fac[i]=((long long)fac[i-1]*i)%MOD;
inv_fac[i]=((long long)inv_fac[i-1]*inv(i,MOD))%MOD;
}
int Res=0;
for(int rt=1;rt<=n;rt++)
{
memset(dp,0,sizeof(dp));
dfs(rt,0);
for(int p=0;p<n;p++)
{
for(int q=0;q<=n;q++)
{
if(q>=n-k)
{
break;
}
int Nt=((long long)dp[rt][p][q]*fac[p])%MOD;
Nt=((long long)Nt*fac[n-1-p])%MOD;
Nt=((long long)Nt*inv_fac[n])%MOD;
Res=((long long)Res+Nt)%MOD;
}
}
}
printf("%d\n",Res);
}
F
不难观察出形似\(AABB,ABAB\),\(A,B\)之间的顺序是固定的
如果我们把一个数的出现位置\((l,r)\)放在坐标系上,可以发现就是向它的右上所有点连边
直接主席树优化建图跑拓扑即可
#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
using namespace std;
const int MAXN=5e5+5;
int n;
int a[MAXN*2];
struct node{
int l,r,u;
bool operator<(const node x)const{
return l>x.l;
}
}b[MAXN];
int las[MAXN];
vector<int>g[MAXN*100];
int cnt_id;
int rt[MAXN];
struct Seg{
int id;
int lc,rc;
}Tree[MAXN*100];
int cnt_node;
int Rd[MAXN*100];
int copy(int p)
{
Tree[++cnt_node]=Tree[p];
return cnt_node;
}
void Insert(int &p,int o,int l,int r,int k,int v)
{
p=copy(o);
Tree[p].id=++cnt_id;
if(l==r)
{
g[Tree[p].id].push_back(v);
// printf("%d %d\n",Tree[p].id,v);
Rd[v]++;
return;
}
int mid=(l+r)>>1;
if(k<=mid)
{
Insert(ls,Tree[o].lc,l,mid,k,v);
}
else
{
Insert(rs,Tree[o].rc,mid+1,r,k,v);
}
if(ls)
{
g[Tree[p].id].push_back(Tree[ls].id);
// printf("%d %d\n",Tree[p].id,Tree[ls].id);
Rd[Tree[ls].id]++;
}
if(rs)
{
g[Tree[p].id].push_back(Tree[rs].id);
// printf("%d %d\n",Tree[p].id,Tree[rs].id);
Rd[Tree[rs].id]++;
}
}
void Update(int p,int l,int r,int ql,int qr,int u)
{
if(!p)
{
return;
}
if(ql>qr)
{
return;
}
//printf("%d??\n",p);
if(l>=ql&&r<=qr)
{
//printf("fuckfuckf\n");
g[u].push_back(Tree[p].id);
//printf("%d %d\n",u,Tree[p].id);
Rd[Tree[p].id]++;
return;
}
int mid=(l+r)>>1;
if(ql<=mid)
{
Update(ls,l,mid,ql,qr,u);
}
if(qr>mid)
{
Update(rs,mid+1,r,ql,qr,u);
}
}
struct Node{
int u,val;
bool operator<(const Node x)const{
return val>x.val;
}
};
int Cal(int x)
{
if(x<=n)
{
return x;
}
else
{
return 0;
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
int cnt=0;
for(int i=1;i<=(n<<1);i++)
{
scanf("%d",&a[i]);
if(las[a[i]])
{
b[++cnt]=(node){las[a[i]],i,a[i]};
}
else
{
las[a[i]]=i;
}
}
cnt_id=n;
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
{
//printf("%d???\n",b[i].u);
Insert(rt[i],rt[i-1],1,2*n,b[i].r,b[i].u);
Update(rt[i],1,2*n,b[i].r+1,2*n,b[i].u);
}
priority_queue<Node>Q;
for(int i=1;i<=cnt_id;i++)
{
if(!Rd[i])
{
Q.push((Node){i,Cal(i)});
//printf("%d----\n",i);
}
}
while(Q.size())
{
Node temp=Q.top();
Q.pop();
if(temp.u<=n)
{
printf("%d %d ",temp.u,temp.u);
}
for(int i=0;i<g[temp.u].size();i++)
{
int v=g[temp.u][i];
Rd[v]--;
if(!Rd[v])
{
Q.push((Node){v,Cal(v)});
}
}
}
}