题目描述

用来打卡的

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<queue>
using namespace std;
const int N=1010;
int n,m;
bool st[N];//判断x是不是在队列内
int main()
{
    queue<int>q;
    cin>>m>>n;
    int res=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        if(!st[x])//如果当前输入的数不在队列内且如果输入的数和队列的数不相同
        {
            if(q.size() == m)
            {
                int t=q.front();
                st[t]=false;
                q.pop();
            }
            q.push(x);//把输入的数入队并标记 
            st[x]=true;
            res++;
        }
    }
    cout<<res<<endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=360;
int res=0;
int cnt=0;
int a[N];
int main()
{
    for(int i=1;i<=12;i++)
    {
        cin>>a[i];
        if(cnt+300-a[i]>=0)
        {
            cnt+=300-a[i];
        }else
        {
            res=-i;
            break;
        }
      if(cnt/100)
      {
          res+=cnt/100*120;
          cnt=cnt%100;
      }
    }
    if(res>0) res+=cnt;//最后存的钱是妈妈的钱加上手中剩余的钱
    printf("%d",res);
    return 0; 
}
blablabla

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
int c;
long long miin=9999999999;
int main()
{
    scanf("%d",&n);
   for(int i=0;i<3;i++)
   {
       int x,y;
       scanf("%d %d",&x,&y);
       if(n%x) c=n/x+1;
       else c=n/x;
       if(c*y<miin) miin=c*y;
   }
   printf("%lld",miin);
   return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

//这里填你的代码^^
/*
dp分析
状态表示 选前i个物品且数量总和取余k为j的所有方案数量最大值
状态计算 划分为两类选 1.选第i个物品 2.不选第i个物品
1.选第i个物品可以表示为 从1-i-1个物品选,且总和余数为j f[i-1][j]
2.假设最后一个选的是第i个物品 所以可以划成两个部分 前面部分为不包含i的物品 和选i的最后一个位置
假设前面部分总和为S 故(S+wi)%k=j 因为(S+a[i])%k=j就说明 S+a[i]=nk+j (n是某个整数)
变换一下就是 S=nk+j-a[i] ------> S%k=(j-a[i])%k (nk%k=0)
从定义出发选i个物品就可以表示为 从1-i个物品选,且总和余数为j f[i-1][(j-wi)%k] +wi因为已经选了所以要加上
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=110;
int n,k;
int f[N][N];
int main()
{
    cin>>n>>k;
    memset(f,-0x3f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        int w;
        cin>>w;
         for(int j=0;j<k;j++)//因为j表示余数所以j一定小于k
          f[i][j]=max(f[i-1][j],f[i-1][(j+k-w%k)%k]+w);//因为(j-w)%k可能为负数 为了保证是正数 w%k的绝对值肯定是0-k-1之间,所以k-w%k一定是正数
          //根据同余定理x%mod=(x+mod)%mod 设x=(j-w)%k 则(j+k-w%k)%k=(j-w)%k
    }
    cout<<f[n][0]<<endl;
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
/*
dp套路  状态表示和状态计算
状态表示 属性 集合 
集合可以表述表示为总和为i 个数为j的所有方案个数和的数量 f[i][j]

状态计算可以划分为两个集合 划分的依据是能量值最小为0和不为0

因为不考虑顺序 当把0放在最后一个位置 能量值最小为0就可以表示为 f[i][j-1]

当最小值不为0时 故每个位置都是大于等于1的  假设当前状态全部减去1 则此时状态可以表示为 f[i-j][j] 
因为当前状态减去1 和当前状态最小值不为0是相互转换来的 所以减去1的状态为最小值不为0状态的一类 故可以表示
f[i-j][j]表示 总和为i-j(每个位置减去1 有个数相当于减去 j个1 所以减去的是j) 总和为j的方案数量(最小能量值不为0)
f[i][j-1]表示 总和为i(因为最小是0不影响)个数为j-1因为有位置选了0(最小能力值为0)
故状态计算可以表示为 f[i][j]=f[i][j-1]+f[i-j][j]
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=20;
int f[N][N];
int t;
int n,m;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;

        f[0][0]=1;// 表示总和为0 个数为0的数的方案数量为1 f[0][1]=1也有意义 表示总和为0个数为1的方案数量为1
        for(int i=0;i<=n;i++)
         for(int j=1;j<=m;j++)
         {
             f[i][j]=f[i][j-1];
             //防止越界
             if(i>=j) f[i][j]+=f[i-j][j];
         }
           cout<<f[n][m]<<endl;
    }
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
/*
等差数列的项数的个数 =(尾项-首项)/d+1
为了使项数最少 则d要越大项数越少 所以可以用最大公约数求d
每一项与第一项的差一定是d的倍数 要使d最大 就是求每一项与第一项差的所有最大公约数
*/
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100010;
int a[N];
int n;
int gcd(int a,int b)
{
   return b?gcd(b,a%b):a; 
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);

    int d=0;//一个数与0的公约数都是本身
    for(int i=1;i<n;i++)
    {
        d=gcd(d,a[i]-a[0]);
    }

    if(!d) printf("%d\n",n);
    else printf("%d",(a[n-1]-a[0])/d+1);
    return 0;
}

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=500010;
int a[N];
int n;
int main()
{
    long double s;
    cin>>n>>s;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n);

    long double avg=s/n,res=0;
    for(int i=0;i<n;i++)
    {
     double cur=s/(n-i);
     if(cur>a[i]) cur=a[i];
     res+=(cur-avg)*(cur-avg);
     s-=cur;
    }
    printf("%.4Lf\n",sqrt(res/n));
    return 0;
}


//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=20;
int n;
bool col[N];//判断当前列有没有放皇后
bool dgs[N];//判断正对角线有没有放皇后 y=-x+b b=x+y 
bool rgs[N];//判断反对角线有没有放皇后 y=x+b  b=y-x 因为y可能会小于x 所以要加上n保证是正数
char g[N][N];
void dfs(int u)
{
    if( u==n )
    {
        for(int i=0;i<n;i++) puts(g[i]);
        puts(" ");
        return ;
    }
    else
    {
     for(int i=0;i<n;i++)
     {
         if(!col[i]&&!dgs[u+i]&&!rgs[i-u+n])
         {
             g[u][i]='Q';
             col[i]=dgs[u+i]=rgs[i-u+n]=true;
             dfs(u+1);
             col[i]=dgs[u+i]=rgs[i-u+n]=false;
             g[u][i]='.';
         }
     }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
      g[i][j]='.';
      dfs(0);
     return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int N=110;
int L,R,C;
int dist[N][N][N];//判断每个点是不是走过和存储起点到终点的距离 宽搜求最短只能求权值为1的图 
char g[N][N][N];
struct Point{
    int x,y,z;
};//存储每个点的下标
Point q[N*N*N];
int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
int bfs(Point start,Point end)
{
    int hh=0,tt=0;
    q[0]=start;
    memset(dist,-1,sizeof dist);
    dist[start.x][start.y][start.z]=0;
    while(hh<=tt)
    {
        auto t=q[hh++];
        for(int i=0;i<6;i++)
        {
            int x=t.x+dx[i],y=t.y+dy[i],z=t.z+dz[i];
            if(x<0||x>=L||y<0||y>=R||z<0||z>=C) continue;
            if(g[x][y][z]=='#') continue;
            if(dist[x][y][z]!=-1) continue;//之前走过

            dist[x][y][z]=dist[t.x][t.y][t.z]+1;
            if(x==end.x&&y==end.y&&z==end.z) return dist[x][y][z];
            q[++tt]={x,y,z};
        }
    }
    return -1;
}
int main()
{
    while(scanf("%d %d %d",&L,&R,&C),L||R||C)//逗号表达式返回的是逗号后面的值 这里如果lrc不为0就继续做
    {
        Point start,end;
    for(int i=0;i<L;i++)
     for(int j=0;j<R;j++)
      {
      scanf("%s",g[i][j]);//输入每一层的地牢
       for(int k=0;k<C;k++)//枚举每层每行每列
       {
           if(g[i][j][k]=='S')   start={i,j,k};
           else if(g[i][j][k]=='E')  end={i,j,k};
       }
      }
      int distance=bfs(start,end);
      if(distance==-1)   cout<<"Trapped!"<<endl;
      else printf("Escaped in %d minute(s).\n",distance);
    }
    return 0;
}

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

//这里填你的代码^^
/*
哈希表存储每一种数字
枚举地图的起点

递归可以画出对应的递归搜索树
从起点出发一共有k层 每层都有最多 4个点 所以从起点出发 到叶节点的路径就是起点到终点不一样路径就是答案
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<unordered_set>

const int N=20;
using namespace std;
int n,m,k;
int a[N][N];
bool st[N];
unordered_set <int> S;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int dfs(int x,int y,int u,int num)
{
    if(u==k)  S.insert(num);//如果加入两个数字一样相当于只有1个数
    else
    {
        for(int i=0;i<4;i++)
        {
            int sx=x+dx[i],sy=y+dy[i];
            if(sx>=0&&sx<n&&sy>=0&&sy<m)
             dfs(sx,sy,u+1,num*10+a[sx][sy]);

        }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
     for(int j=0;j<m;j++)
        cin>>a[i][j];


    for(int i=0;i<n;i++)
     for(int j=0;j<m;j++)
       dfs(i,j,0,a[i][j]); 
      printf("%d\n",S.size());
      return 0; 
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~