ARC164
A
考虑先给\(N\)按三进制分解一下
然后对于\(3^m\rightarrow3^{m-1}\),实际上可以加\(2\)的贡献,我们先计算\(N\)最小需要\(S\)
然后可以发现只要\(K-S\)是偶数即可
#include<bits/stdc++.h>
using namespace std;
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
int T;
long long N,K;
scanf("%d",&T);
while(T--)
{
scanf("%lld %lld",&N,&K);
if((N-K)&1)
{
printf("No\n");
continue;
}
long long Now=N;
long long S=0;
while(Now)
{
S+=(Now%3);
Now/=3;
// cerr<<Now<<endl;
}
if((S<=K)&&(K-S)%2==0)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
B
就是找\(01\)交替然后只有一条相同边的奇环
好像不能直接找环,因为环套环会出问题
直接由并查集维护即可,颜色不同的连边
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
int n,m;
int x,y;
struct Edge{
int u,v;
}edge[MAXN];
int fa[MAXN];
int c[MAXN];
int find(int x)
{
if(fa[x]==x)
{
return fa[x];
}
fa[x]=find(fa[x]);
return fa[x];
}
void unionn(int i,int j)
{
fa[find(i)]=find(j);
}
bool found=0;
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",&x,&y);
edge[i].u=x;
edge[i].v=y;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
fa[i]=i;
}
for(int i=1;i<=m;i++)
{
if(c[edge[i].u]!=c[edge[i].v])
{
unionn(edge[i].u,edge[i].v);
}
}
for(int i=1;i<=m;i++)
{
if(c[edge[i].u]==c[edge[i].v])
{
if(find(edge[i].u)==find(edge[i].v))
{
found=1;
}
}
}
if(found)
{
printf("Yes");
}
else
{
printf("No");
}
}
C
先假设全部是\(A\)朝上
对于\(A\)来说,翻肯定选\(B_i-A_i\)最大的
对于\(B\),同样也要这样选
由于\(A\)一定会翻\(n\)次,这里我们可以用堆模拟这个过程
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3e5+5;
int n;
struct node{
int A,B;
}s[MAXN];
signed main(){
// freopen("date.in","r",stdin);
//freopen("date.out","w",stdout);
scanf("%lld",&n);
int Sum=0;
priority_queue<int>Q;
for(int i=1;i<=n;i++)
{
scanf("%lld %lld",&s[i].A,&s[i].B);
Sum+=s[i].A;
Q.push((s[i].B-s[i].A));
}
int Op=0;
while(n--)
{
int temp=Q.top();
Q.pop();
Sum+=temp;
Q.push(-temp);
Op^=1;
}
printf("%lld",Sum);
}
D
如果能确定每个点的走的朝向,那其实可以直接抽象为括号匹配,答案就是每对匹配括号的距离之和
一个经典的套路,我们可以把左括号的贡献定义为\(-i\),这样我们就只需要算其合法序列的个数
考虑枚举位置\(i\)前面的\(?\)是\(+\)的数量,然后\(i\)的朝向就确定了,直接组合数算贡献即可
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=3005;
int n;
char s[MAXN*2];
int dp[MAXN*2][MAXN*2];
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*2];
int inv_fac[MAXN*2];
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 Prel[MAXN*2];
int Prer[MAXN*2];
int Surl[MAXN*2];
int Surr[MAXN*2];
int Prep[MAXN*2];
int Surp[MAXN*2];
signed main(){
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
scanf("%s",s+1);
fac[0]=1;
for(int i=1;i<=2*n;i++)
{
fac[i]=((long long)fac[i-1]*i)%MOD;
}
inv_fac[2*n]=inv(fac[2*n],MOD);
for(int i=2*n-1;i>=1;i--)
{
inv_fac[i]=((long long)inv_fac[i+1]*(i+1))%MOD;
}
int Res=0;
int Tot=0;
int Totl=0;
int Totr=0;
for(int i=1;i<=2*n;i++)
{
Prel[i]=Prel[i-1];
Prer[i]=Prer[i-1];
Prep[i]=Prep[i-1];
if(s[i]=='+')
{
Prel[i]++;
Totl++;
}
else if(s[i]=='-')
{
Prer[i]++;
Totr++;
}
else
{
Prep[i]++;
Tot++;
}
}
for(int i=2*n;i>=1;i--)
{
Surl[i]=Surl[i+1];
Surr[i]=Surr[i+1];
Surp[i]=Surp[i+1];
if(s[i]=='+')
{
Surl[i]++;
}
else if(s[i]=='-')
{
Surr[i]++;
}
else
{
Surp[i]++;
}
}
for(int i=1;i<=2*n;i++)
{
if(s[i]!='+')
{
int O1=Prel[i-1];
int O2=Prer[i-1];
int O3=Surl[i+1];
int O4=Surr[i+1];
int O5=Prep[i-1];
int O6=Surp[i+1];
int O=O4-O3+O1-O2;
for(int j=0;j<=O5;j++)
{
int Tp=(Totl+j);
int Np=(n-Tp);
if(Np>=0)
{
if(O+j-(O5-j)-Np+(O6-Np)<0)
{
int Tx=((long long)C(O5,j)*C(O6,Np))%MOD;
Tx=((long long)Tx*(MOD-i))%MOD;
// printf("%d -%d %d %d %d %d??\n",i,(MOD-Tx)%MOD,O5,O6,j,Np);
Res=((long long)Res+Tx)%MOD;
}
else
{
int Tx=((long long)C(O5,j)*C(O6,Np))%MOD;
Tx=((long long)Tx*(i))%MOD;
// printf("%d %d>??\n",i,Tx);
Res=((long long)Res+Tx)%MOD;
}
}
}
}
if(s[i]!='-')
{
int O1=Prel[i-1];
int O2=Prer[i-1];
int O3=Surl[i+1];
int O4=Surr[i+1];
int O5=Prep[i-1];
int O6=Surp[i+1];
int O=O4-O3+O1-O2;
for(int j=0;j<=O5;j++)
{
int Tp=(Totl+j);
if(s[i]=='?')
{
Tp++;
}
int Np=(n-Tp);
if(Np>=0)
{
if(O+j-(O5-j)-Np+(O6-Np)>0)
{
int Tx=((long long)C(O5,j)*C(O6,Np))%MOD;
Tx=((long long)Tx*(MOD-i))%MOD;
// printf("%d -%d??\n",i,(MOD-Tx)%MOD);
Res=((long long)Res+Tx)%MOD;
}
else
{
int Tx=((long long)C(O5,j)*C(O6,Np))%MOD;
Tx=((long long)Tx*(i))%MOD;
// printf("%d %d>??\n",i,Tx);
Res=((long long)Res+Tx)%MOD;
}
}
}
}
}
printf("%d\n",Res);
}
E
对于每个线段树的结点\(i\),我们记录分割点\(P_i\)
可以发现,对于区间\([l,r]\),它询问到的最大深度就是\(l-1,r\)分割点对应的节点的最大深度,因为对于中间的那段区间实际上一定是在其上面覆盖的
对于第一问,我们可以计算需要哪些分割点,然后在二叉树上一层一层铺即可
对于第二问,可以发现如果如果我们的分割点在\(d-1\),那访问次数实际上为在\(d-1\)深度分割点的数量\(\times2\)
于是我们要让位于\(d-1\)的分割点尽量少
对于\(d-1\)的一颗满二叉树,我们可以发现如果以\(dfs\)序标号,\(d-1\)的点都是奇数
据此我们可以\(dp\),设\(dp_{i,j}\)为前\(i\)需要的分割点走了\(j\)个点的最小次数,奇数位置放要记录贡献,偶数不用
#include<bits/stdc++.h>
using namespace std;
int n,Q;
int l,r;
int C[5005];
vector<int>V;
int dp[5005][5005];
signed main(){
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&Q);
for(int i=1;i<=Q;i++)
{
scanf("%d %d",&l,&r);
C[l-1]++;
C[r]++;
}
int d=0;
V.clear();
for(int i=1;i<n;i++)
{
if(C[i])
{
V.push_back(C[i]);
}
}
for(int i=0;i<=20;i++)
{
if(((1<<i)-1)>=((int)V.size()))
{
d=i;
break;
}
}
if(d==0)
{
printf("%d %d\n",0,Q);
return 0;
}
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=0;i<V.size();i++)
{
for(int j=0;j<(1<<d);j++)
{
if((j%2==0))
{
dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+V[i]);
dp[i][j+1]=min(dp[i][j+1],dp[i][j]);
}
else
{
dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);
}
}
}
int Res=0x3f3f3f3f;
for(int i=0;i<(1<<d);i++)
{
Res=min(Res,dp[V.size()][i]);
}
//printf("%d %d???\n",V.size(),(1<<d)-1);
printf("%d %d\n",d,2*Res);
}