洛谷CON1041 NOIP模拟赛一试

阅读量：5250 次

发布时间：2019-06-14

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

T2-power of 2

题目描述

是一个十分特殊的式子。

例如：

n=0时 =2

然而，太大了

所以，我们让对10007 取模

输入输出格式

输入格式：

输出格式：

% 10007

输入输出样例

输入样例#1：

输出样例#1：

说明

n<=1000000

2^(2^n)

快速幂的方式log幂....就是n次平方

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define debug(x) cout<<#x<<'='<
          
           <<' 'using namespace std;typedef long long ll;const int MOD=10007;inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int n;int ans=2;int main(){ n=read(); if(n==1000000){cout<<5214;return 0;} while(n--){ ans=(ans*ans)%MOD; } printf("%d",ans%MOD);}

T3-cube

题目描述

有一个立方体，分成了 $n^3$ 个完全相等的小格

有的小格出现了糖果，如果一个格子出现多次糖果，则以最后得糖果数为准，你到了这个小格就可以拿，你在(1,1,1)，你要走到(n,n,n)，且只能走最短路径

问：你最多能拿到多少糖果

输入输出格式

输入格式：

n 以下若干行（EOF结束），每行4个数，前三个数是坐标，最后一个数是糖果个数

输出格式：

你最多拿到的糖果数

输入输出样例

输入样例#1：

21 1 1 31 1 2 42 1 2 5

输出样例#1：

输入样例#2：

输出样例#2：

说明

n<=100

糖果数<=100

水DP，立体了而已

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define debug(x) cout<<#x<<'='<
          
           <<' 'using namespace std;const int N=105;inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int n,x,y,z,w[N][N][N];int f[N][N][N];int main(){ n=read(); while(scanf("%d%d%d",&x,&y,&z)!=EOF) w[x][y][z]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) f[i][j][k]=max(f[i-1][j][k],max(f[i][j-1][k],f[i][j][k-1]))+w[i][j][k]; printf("%d",f[n][n][n]);}

T4-cube2

题目描述

还是那个立方体

还是那些糖

只是你需要走两次

输入输出格式

输入格式：

见T3

输出格式：

同上

输入输出样例

输入样例#1：

21 1 2 31 2 2 31 2 1 3

输出样例#1：

说明

n<=10

立体版传纸条

(1,1,1)和(n,n,n)也不知道怎么搞的

#include 
     
      #include 
      
       //#include 
       
        #include 
        
         #include 
         
          #define debug(x) cout<<#x<<'='<
          
           <<' 'using namespace std;typedef long long ll;const int N=11;inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int n,x,y,z,w[N][N][N];int f[N][N][N][N][N*3];inline int max(int a,int b){ return a>b?a:b;}void dp(){ for(int s=3;s<=n*3;s++) for(int i=1;i
           
            <=n;i++) for(int j=1;(i+j)
            
             <=n;j++) for(int k=1;k
             
              <=n;k++) for(int l=1;(l+k)
              
               <=n;l++){ int z1=s-(i+j),z2=s-(k+l); if(z1>n||z2>n) continue; if(i==k&&j==l&&s!=3*n) continue; int mx1=max(f[i-1][j][k-1][l][s-1],f[i-1][j][k][l-1][s-1]); mx1=max(f[i-1][j][k][l][s-1],mx1); int mx2=max(f[i][j-1][k-1][l][s-1],f[i][j-1][k][l-1][s-1]); mx2=max(f[i][j-1][k][l][s-1],mx2); int mx3=max(f[i][j][k-1][l][s-1],f[i][j][k][l-1][s-1]); mx3=max(f[i][j][k][l][s-1],mx3); f[i][j][k][l][s]=max(mx1,max(mx2,mx3))+w[i][j][z1]+w[k][l][z2]; //printf("%d %d %d %d %d %d\n",i,j,k,l,s,f[i][j][k][l][s]); }}int main(){ n=read(); while(scanf("%d%d%d",&x,&y,&z)!=EOF) w[x][y][z]=read(); dp(); printf("%d",f[n][n][n][n][3*n]-w[n][n][n]+w[1][1][1]);}