【noip 2016】普及组

时间：2022-08-11 09:52:20

T1.买铅笔

题目链接

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int n,p,w,ans=0x3f3f3f3f;

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 int main()

 {

     n=read();

     for(int i=;i<=;i++)

     {

         w=read(),p=read();

         if(n%w)w=n/w+;

         else w=n/w;

         ans=min(ans,w*p);

     }

     printf("%d",ans);

     return ;

 }

T2.回文日期

题目链接

直接枚举年份，再判断日期是否合法就好了……然而我居然还WA了一发（好菜啊

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int d1,d2,ans;

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 int rev(int x)

 {

     int s[],ans=;

     for(int i=;i<=;i++)s[i]=x%,x/=;

     for(int i=;i<=;i++)ans=ans*+s[i];

     return ans;

 }

 bool pan(int y,int m,int d)

 {

     int day=;

     if(m==||m==||m==||m==)day=;

     if(m==)

     {

         if((y%==&&y%!=)||y%==)day=;

         else day=;

     }

     if(m<||m>||d<||d>day)return false;

     return true;

 }

 int main()

 {

     d1=read();d2=read();

     for(int i=d1/;i<=d2/;i++)

     {

         int t=i*+rev(i);

         if(pan(i,(t/)%,t%)&&t>=d1&&t<=d2)ans++;

     }

     printf("%d",ans);

     return ;

 }

T3.海港

题目链接

因为保证输入的ti是递增的，所以开一个队列瞎搞就好了✔

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,k,t,ans,nat[];

 struct node{int t,nat;}q[];

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 int main()

 {

     n=read();

     int head=,tail=;

     while(n--)

     {

         t=read();k=read();

         while(k--)

         {

             q[++tail].nat=read();

             if(!nat[q[tail].nat])ans++;

             nat[q[tail].nat]++;

             q[tail].t=t;

         }

         while(q[head].t<=t-)

         {

             nat[q[head].nat]--;

             if(!nat[q[head].nat])ans--;

             head++;

         }

         printf("%d\n",ans);

     }

     return ;

 }

T4.魔法阵

题目链接

据题意得，x​b​​−x​a​​=2(x​d​​−x​c​​)，x​c​​−x​b​​>6(x​d​​−x​c​​)，即总距离s>9(x​d​​−x​c​​)；

另，魔法值相同的物品所需要输出的答案是一样的；

所以可以先枚举(x​d​​−x​c​​)，再倒序枚举a的位置并推算出b及最小的合法c、d的位置并进行计算（倒序是为了使前面枚举过的c、d位置合法，方便累加）；同理，正序枚举d的位置并推算出c及最大的合法a、b的位置并进行计算。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int n,m,num,xa,xb,xc,xd;

 int w[N],a[N],b[N],c[N],d[N],id[];

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 int main()

 {

     n=read();m=read();

     for(int i=;i<=m;i++)

     {

         id[i]=read();

         w[id[i]]++;

     }

     for(int i=;i<=n/;i++)

     {

         num=;

         for(xa=n-*i-;xa>=;xa--)

         {

             xb=xa+*i;xc=xb+*i+;xd=xc+i;

             num+=w[xc]*w[xd];

             a[xa]+=w[xb]*num;

             b[xb]+=w[xa]*num;

         }

         num=;

         for(xd=*i+;xd<=n;xd++)

         {

             xc=xd-i;xb=xc-*i-;xa=xb-*i;

             num+=w[xa]*w[xb];

             c[xc]+=w[xd]*num;

             d[xd]+=w[xc]*num;

         }

     }

     for(int i=;i<=m;i++)

         printf("%d %d %d %d\n",a[id[i]],b[id[i]],c[id[i]],d[id[i]]);

     return ;

 }

相关文章