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

没有验证过答案,不保证正确性(但是我觉得都是对的hhh)

试题 A: 求余

1

试题 B: 双阶乘

59375

试题 C: 格点

15698

试题 D: 整数分解

691677274345

记忆化搜索，注意开$longlong$

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define int long longint f[2222][6];int dfs(int x,int k){ if( f[x][k]!=-1 ) return f[x][k]; if( k==0 ) return x==0; int ans = 0; for(int i=1;i<=x;i++) ans += dfs(x-i,k-1); return f[x][k] = ans;}signed main(){ memset( f,-1,sizeof f ); cout << dfs(2021,5) << endl;}
        
       
      
     
    
   

试题 E: 城邦

4046

裸的最小生成树

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 2022*2022;struct p{ int l,r,w; bool operator < ( const p&tmp ) const { return w
        
       
      
     
    
   

试题 F: 特殊年份

按照题意模拟即可

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int main(){ int x,ans = 0; for(int i=1;i<=5;i++) { cin >> x; int ge = x%10; x/=10; int shi = x%10; x/=10; int bai = x%10; x/=10; int qian = x%10; if( qian==shi && ge==bai+1 ) ans++; } cout << ans;}
        
       
      
     
    
   

试题 G: 小平方

这里需要特别注意小于$n$的一半,需要分$n$的奇偶性讨论一下

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int main(){ int ans = 0,n; cin >> n; for(int i=1;i
        
       
      
     
    
   

试题 H: 完全平方数

先欧拉筛得到$10^7$以内的所有质数

然后对$n$进行质因子分解,若存在一个质因子只有奇数次幂,那么不是平方数

所以我们添加上一个质因子补齐

又注意到$n<=10^{11}$,所以不会有两个或以上的质因子超过$10^7$

那么最后分解剩下来的$n$就是一个质数,乘上去即可

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 1e7;int prime[maxn+10],top;bool vis[maxn+10]; void make_prime(){ for(int i=2;i<=maxn;i++) { if( !vis[i] ) prime[++top] = i; for(int j=1;j<=top && prime[j]*i<=maxn;j++) { vis[i*prime[j]] = 1; if( i%prime[j]==0 ) break; } } }long long ans = 1,n;int main(){ //对n进行质因子分解 //大于等于 make_prime(); cin >> n; for(int i=1;i<=top;i++) { int temp = 0; while( n%prime[i]==0 ) n /= prime[i], temp++; if( temp&1 ) ans = ans*prime[i]; } //这样一来,n只会包含大于1e7的质数,那么最多只有一个 ans *= n; cout << ans;}
        
       
      
     
    
   

试题 I: 负载均衡

开一个优先队列,队列内装的是现在在执行的作业

越早结束的作业优先级越大,在堆顶最早被弹出来

每次加入一个$a$时刻的作业时

我们从优先队列回收掉所有$<=a$时候结束的作业即可

这样一直模拟

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 1e6+10;int n,m,v[maxn];struct p{ int id,suan,ed;//分别是占用的计算机,占用算力,结束时间 bool operator < ( const p&tmp ) const { return ed>tmp.ed;//优先级大的是终止时间小的 } };priority_queue
         
q;int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&v[i] ); for(int i=1;i<=m;i++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); while( !q.empty() ) { p now = q.top(); if( now.ed>a ) break; q.pop(); v[now.id] += now.suan; } if( d>v[b] ) printf("-1\n"); else { p r; r.id = b, r.suan = d, r.ed = a+c; q.push( r ); v[b] -= d; printf("%d\n",v[b] ); } }}
        
       
      
     
    
   

试题 J: 国际象棋

容易发现$n$很小,考虑对$n$进行状态压缩

也就压缩第$i$行是否放了马

然后我们考虑第$i$列的马,只可能和第$i-1,i-2$列放置的马产生冲突

你可能会说还可能和$i+1,i+2$列产生冲突啊,那是后面的状态了,第$i+1$列转移的时候再考虑吧

所以定义$f[i][j][k][l]$表示当前枚举到第$i$列

第$i$列放马的状态为$k$,第$i-1$列放马的状态为$j$,一共放了$l$匹马

然后暴力枚举状态转移即可

提前预处理哪些状态冲突会比较好写

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int mod = 1e9+7;int n,m,K,b[1009];int f[102][65][65][22]; vector
         
          v1[65],v2[65];//v1[i]存的是当第k列状态为i时,第k-1列可行的状态//v2[i]存的是当第k列状态为i时,第k-2列可行的状态bool ok[65][65];//ok[i][j]表示当前列为i时,前一列不能是j int mx;int fx[10] = { 1,1,-1,-1,2,2,-2,-2};int fy[10] = { 2,-2,2,-2,1,-1,1,-1};bool isok(int x,int y,int ex,int ey){ for(int i=0;i<=7;i++) { int nx = x+fx[i], ny = y+fy[i]; if( nx==ex && ny==ey ) return false;//能吃掉 } return true;}void init(){ for(int i=0;i
          
           >=1,x=1ll*x*x%mod ) if( n&1 ) ans = 1ll*ans*x%mod; return ans;}int C(int n,int m){ if( m
           
            >1]+(i&1); fac[0] = 1; for(int i=1;i<=1000;i++) fac[i] = 1ll*fac[i-1]*i%mod; cin >> n >> m >> K; if( m==1 ) { cout << C(n,K); return 0; } mx = (1<
           
          
         
        
       
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116562370 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！