2018.8.15提高B组模拟考试-白红宇

2018.8.15提高B组模拟考试

阅读量：5880 次

发布时间：2019-06-19

本文共 2418 字，大约阅读时间需要 8 分钟。

emmm...所以为什么出狱了还要做监狱的考试啊？

T1 题意简述：

Description

Input

Output

Data Constraint

解题思路：dp。设dp[i][j]为用了i个弹珠，放进j个抽屉中的方案数。

一开始我想到的dp转移方程是dp[i][j]=∑(k=1~i/j)dp[i-k][j-1]。

然后我就兴致勃勃地交了上去，只拿了10分。凉凉。

看题解说是和第二类斯特林数相似，好像没毛病。

转移方程为dp{i}[j]=dp[i-1][j-1]+dp[i-j][j]。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MOD 998244353#define ll long longusing namespace std;ll n,m,ans,dp[5001][5001];int main(){ scanf("%lld%lld",&n,&m); dp[0][0]=1; for(ll i=1;i<=n;i++) for(ll j=1;j<=min(i,m);j++) dp[i][j]=(dp[i-1][j-1]+dp[i-j][j])%MOD; printf("%lld\n",dp[n][m]%MOD); return 0;}

T2 题意简述：

Description

Input

Output

Data Constraint

解题思路：结论题。

通过打表可以发现，当gcd(a,b)=a xor b时，a-b=gcd(a,b)=a xor b。

因此只需枚举a-b的取值并计数即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,cnt[10000001];int main(){ scanf("%d",&n); for(int i=1;i<=10000000;i++) for(int j=i+i;j<=10000000;j+=i) if((j^(j-i))==i) cnt[j]++; for(int i=1;i<=10000000;i++) cnt[i]+=cnt[i-1]; printf("%d\n",cnt[n]); return 0;}

T3 题意简述：

Description

Input

Output

Data Constraint

解题思路：点分治。

一遍点分治计算出所有(S,E)取值范围内的路径，计算时更新答案即可。

注意dis数组不必memset，也不必sort，否则会T得很惨。

#pragma GCC optimize(3)#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define INF 0x3f3f3f3fusing namespace std;set
            
              st;int n,ans=INF,sta,end,cnt,head[100001];int mn,root,siz[100001],vis[100001],dis[100001],tot;struct uio{ int nxt,to,val;}edge[200001];void add(int x,int y,int z){ edge[++cnt].nxt=head[x]; edge[cnt].to=y; edge[cnt].val=z; head[x]=cnt;}void getroot(int x,int fa,int size){ siz[x]=1; int tmp=0; for(int i=head[x];i;i=edge[i].nxt) { int y=edge[i].to; if(y==fa||vis[y]) continue; getroot(y,x,size); siz[x]+=siz[y]; tmp=max(tmp,siz[y]); } tmp=max(tmp,size-siz[x]); if(tmp
             
              =sta&&tmp<=end) ans=tmp; } for(int j=tot;j;j--) { if(dis[j]
              
               =sta&&dis[j]<=end) ans=dis[j]; st.insert(dis[j]); } } for(int i=head[x];i;i=edge[i].nxt) { int y=edge[i].to; if(vis[y]) continue; mn=INF,getroot(y,0,siz[y]); dfs(root); }}int main(){ scanf("%d%d%d",&n,&sta,&end); for(int i=1;i