Winter Petrozavodsk Camp(7题)

2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus)

Winter Petrozavodsk Camp(7题)
C. Brave Seekers of Unicorns(dp+二进制推导)
D - Bank Security Unification（二进制dp)
G - Biological Software Utilities(找规律+矩阵树定理)
I - Binary Supersonic Utahraptors(签到题)
J - Burnished Security Updates(判二分图)
M - Brilliant Sequence of Umbrellas
N - Best Solution Unknown(记忆化迭代)

C. Brave Seekers of Unicorns(dp+二进制推导)

\[dp[i]$$表示以i结束的方案数数量 $$dp[i]=\sum_{1}^{i-1}(dp[j]-dp[i\oplus j])\]
记$$k=i\oplus j$$,则$$k
变形后，dp[i]=\sum_{1}^{i-1}dp[j]-\sum_{k
我们来讨论后半段，以i=1011001，-表示无所谓
i: 1 0 1 1 0 0 1

j: 1 0 0 - - - -

k: 0 0 1 - - - -

注意：

1.j第一位一定是1，不然j
2.因为后面k取什么都可以，所以：对于i每一位为1的数，以当前为例就是第5位是1，前面是0的数都是合法的k，这就是dp[x*2-1]-dp[x-1]的由来

#include
 
using namespace std;
#define debug( x) cout<<#x<<':'<


D - Bank Security Unification（二进制dp)
/*
 位运算dp：
 有一个dp性质是：
 到当前位置，有若干个位数为j的数组成的子序列：a1,a2,a3,...,ax;
 只需要用ax来更新当前位置就可以了,因为前面的dp[ai]
using namespace std;
typedef long long ll;
void Ios(){
 ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
}
const int maxn=5e6;
const int qwq=60;
ll a[maxn],dp[qwq],sum[maxn],pos[qwq];
int main(){
   Ios();
    ll n;cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    } 
    ll ans=0;a[0]=0;memset(pos,0,sizeof(pos));memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        ll top=0,imax=0,temp=a[i];
        for(int j=0;j>=1;
        }
        
        dp[top]=imax;
        pos[top]=i;
        ans=max(ans,imax);
    }
    cout<

G - Biological Software Utilities(找规律+矩阵树定理)

简述一下题意：
这道题就是1-n顶点的树，我们要找到有多少棵树，删除一些边后是由两两连通块组成的。
非常正确的想法是：
把两两分堆然后拼起来。
1.首先要知道label tree有n^(n-2)个
?	具体见https://www.cnblogs.com/zx0710/p/14475040.html
?	建议还是当结论记下来，毕竟赛场上推矩阵树定理未免有点难顶
2.![img](file:///C:\Users\zx200\Documents\Tencent Files\2505986089\Image\C2C\IRXK5XAYC@H__}CO%W0APB.png)
每个连通块间有4中连接方式

#include
using namespace std;
typedef long long ll;
#define debug(x) cout<>=1;
    }
    return ans;
}
int main(){

    ll n,ans;scanf("%lld",&n);
    if(n%2==1)ans=0;
    else if(n==2)ans=1;
    else{
        ans=qpow(n/2,n/2-2)*qpow(2,n/2-2)%mod;
        for(int i=n/2+1;i<=n;i++)ans=ans*i%mod;
    }
    printf("%lld\n",ans);
}


I - Binary Supersonic Utahraptors(签到题)
#include
using namespace std;
typedef long long ll;
const int maxn=1e6+50;
const int mod=998244353;
int a[100];
int main(){
    ll n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    ll temp;
    for(int i=1;i<=n+m;i++){
        scanf("%lld",&temp);a[temp]++;
    }
    printf("%lld",abs(a[0]-m));
    //system("pause");
}

J - Burnished Security Updates(判二分图)
/*
读懂题意胜过一切。
读懂之后发现：要判一下是不是二分图。
是二分图的话，输出一下两边最少点的数量。
因为可能是森林，所以每dfs一次判一下。
*/
 
#include
 
using namespace std;
#define debug( x) cout<<#x<<':'<

M - Brilliant Sequence of Umbrellas
/*
一开始一直在想要怎么构造，然后枚举了一下，过了
*/
#include
using namespace std;
typedef long long ll;
const ll N =2e7+10;//
bool notp[N];
int prime[N], pnum;
void sieve()
{
    //[0,N]的素数表
    memset(notp, 0, sizeof(notp));//0为素数；
    notp[0] = notp[1] = 1;
    pnum = 0;
    for (int i = 2; i <= N; i++)
    {
        if (!notp[i])  prime[++pnum] = i;
        for (int j = 1; j <= pnum && prime[j] * i <= N; j++)
        {
            notp[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}
ll a[1000005];
int main(){
    ll n;
    sieve();
    
    scanf("%lld",&n);
    ll k=ceil(2.0/3.0*sqrt(n));
    printf("%lld\n",k);
    a[1]=1;a[2]=2;
   
    for(ll i=3;i<=k;i++) a[i]=1ll*prime[i-2]*prime[i-1];
    a[k]=prime[k-2];
    for(ll i=1;i<=k;i++){
        printf("%lld ",a[i]);
    }
}


N - Best Solution Unknown(记忆化迭代)
#include
using namespace std;
typedef long long ll;
const int maxn=2e6+10;
#define debug(x) cout<<#x<<':'<=a[lx]){//打败左边缘的数
        flag=true;
        l[x]=min(lx,l[lx]);
        r[x]=max(r[x],r[lx]);
    }
    int rx=r[x]+1;
    if(a[x]+r[x]-l[x]>=a[rx]){//打败右边缘的数
        flag=true;
        r[x]=max(rx,r[rx]);
        l[x]=min(l[x],l[rx]);
    }
    if(flag) judge(x);
}
int main(){
    int n;scanf("%d",&n);
    vector>vc;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        vc.push_back({a[i],i});
        l[i]=i;r[i]=i;
    }
    a[0]=a[n+1]=0x3f3f3f3f;//一定要足够大
    sort(vc.begin(),vc.end());
    vectorans;
    for(int i=0;i


					
					
					
						相关
						
				
						
			
																
								
										1.13训练赛
									
									
								 

        
								
							
							

																
								
										CDZSC_2022寒假个人训练赛21级(3)题解
									
									
								 

        
								
							
							

																
								
										【2022 省选训练赛 Contest 17 A】字符串游戏（结论）
									
									
								 

        
								
							
							

																
								
										新生个人训练赛第6场题解