HPU2016级暑期集训选拔赛 【题解】

时间：2022-12-20 22:44:37

A .水题 

int main()
{
int a,b,c,x;
    scanf("%d%d%d",&a,&b,&c);
    scanf("%d",&x);
printf("%d\n",a*x*x+b*x+c);
return 0;
}

B 水题 控制好什么时候到了对角线，该加了就行了

int arr[MAXN][MAXN]; 
int main()
{
int n;
scanf("%d",&n);
int sum1=0;int sum2=0;
int a;
for(int i=1;i<=n;i++)
    {
for(int j=1;j<=n;j++)
        {
scanf("%d",&a);
if(i==j){ sum1+=a; } // 正对角线
if(i+j==n+1) sum2+=a;  //反对角线
         } 
    } 
printf("%d\n",abs(sum1-sum2));
return 0;
}

C 模拟 找好规律就行

int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
    {
for(int j=1;j<=n;j++)
        {
if(j>n-i) printf("#"); // 关键
else putchar(' ');
         }
if(i!=n) putchar('\n');
     }
return 0;
}

D 水题模版 

LL gcd(LL a,LL b)
{
return b==0?a:gcd(b,a%b);
}
LL lcm(LL a,LL b)
{
return a/gcd(a,b)*b;
}
int main()
{
    LL a,b;
while(~scanf("%lld%lld",&a,&b))
    {
printf("%lld\n",lcm(a,b));
    }
return 0;
}

E 水题

int main()
{
     LL t;
     scanf("%lld",&t);
while(t--)
     {
        LL r;
        scanf("%lld",&r);
printf("%lld\n",r*2);
       } 
return 0;
}

F 同余定理的简单应用

int main()
{
    LL n,p;
while(~scanf("%lld%lld",&n,&p))
    {
        LL ans=1;
for(LL i=1;i<=n;i++)
        {
            ans=ans*i%p;
        }
printf("%lld\n",ans);
    }
return 0;
}

G 打表找规律
注意 大于等于1000的时候 判定是不是水仙花数的条件是 a*a*a*a*+b*b*b*b+c*c*c*c*+d*d*d*d == i 

int check(int i)
{
int a=i%10;
int b=i/10%10;
int c=i/100%10;
return (a*a*a+b*b*b+c*c*c)==i;
}
int main()
{
int m;
while(~scanf("%d",&m))
    {
int i;
if(m>407) printf("%d\n",1634);//自己打个表就可以知道当大于407时候最近的水仙花数就是1634 
else {
for(i=m;i<500;i++)
      {
if(i<100) continue;
if(check(i)) break;
       }
printf("%d\n",i);
         } 
    }
return 0;
}

H 打表前缀和，（当时脑梗，只想到了暴力，幸亏后来又想到了）

LL arr[MAXN];
LL ss[MAXN];
LL n;
void dabiao()
{
    ss[0]=0;
    ss[1]=arr[1];
for(int i=2;i<=n;i++)
    ss[i]=arr[i]+ss[i-1]; //s[i]表示 从第一个数到第n个数的总和为多少
}
int main()
{   
        scanf("%lld",&n);
for(LL i=1;i<=n;i++)
        scanf("%lld",&arr[i]);
        dabiao();
        LL q;
        scanf("%lld",&q);
while(q--)
        {
            LL l,r;
            scanf("%lld%lld",&l,&r); 
printf("%lld\n",ss[l+r-1]-ss[l-1]);
         }
return 0;
}

I 水题

int xx[MAXN];
int yy[MAXN];
int main()
{
int n;
while(~scanf("%d",&n))
     {
for(int i=1;i<=n;i++)
        {
scanf("%d%d",&xx[i],&yy[i]);       
           }
int flag=1;
for(int i=2;i<=n;i++) if(xx[i]!=xx[i-1]) flag=0;
if(flag) puts("YES");
else 
         {
            flag=1;
for(int i=2;i<=n;i++) if(yy[i]!=yy[i-1]) flag=0;
if(flag) puts("YES");
else puts("NO");
         }  
       }
return 0;
}

J 之前做过超级台阶这道题，就改动了过了（简单dp）
超级台阶题目链接

const LL mod=14062008;
LL arr[MAXN]; // 是不是坏了楼梯，0表示没有坏，1表示坏了
LL dp[MAXN];
int main()
{
    LL n,k;
    scanf("%lld%lld",&n,&k);
    memset(arr,0,sizeof(arr));
int flag=1;
for(LL i=1;i<=k;i++) 
    {
        LL a;
        scanf("%lld",&a);
        arr[a]=1;
    }
if(n==1) printf("0\n");
else{
for(int i=2;i<=n;i++) 
if(arr[i]&&arr[i-1])
    {
        flag=0;
break;
      }  

if(!flag) printf("0\n");
else 
    {
        LL ans=0;
        dp[1]=1;dp[0]=0;
for(LL i=2;i<=n;i++)
        {
if(!arr[i]) dp[i]=(dp[i-1]%mod+dp[i-2]%mod)%mod;
else { dp[i]=0;} // 坏了的话到不了 这里，方法数就是0 ；
        }
printf("%lld\n",dp[n]%mod);
    }
    }
return 0;
}

K 找规律。
当n 的阶乘小于mod的时候，就是1+2+3+…n 。用前n项和公式求。
当n>=mod的时候，会发现每mod个数都是 一个循环，找到有几个循环，和每个循环的值。
自己可以找组数据 枚举算一下，就能够发现规律；

int arr[MAXN];
int main()
{
    LL t;
    scanf("%lld",&t);
while(t--)
    {
        LL n,mod;
        scanf("%lld%lld",&n,&mod);
if(n<mod)   printf("%lld\n",(1+n)*n/2) ；
else 
        {
        LL ans=(1+mod-1)*(mod-1)/2;
        LL m=n/mod;
        LL k=n%mod; 
        LL s=(1+k)*k/2;
printf("%lld\n",s+ans*m);
        }
    }
return 0;
}

L 不断覆盖矩形区域，找到覆盖最多的 格子数就可以；

LL arr[MAXN][5];
int main()
{
    LL n;
    scanf("%lld",&n);
for(LL i=n;i>=1;i--) 
    scanf("%lld%lld",&arr[i][1],&arr[i][2]);

    LL le=inf; LL ri=inf;// 找到最小的覆盖区域
for(LL i=1;i<=n;i++) 
    {
        le=min(le,arr[i][1]);
        ri=min(ri,arr[i][2]);
    }
printf("%lld\n",le*ri);
return 0;
}

M 其实能够被8整除 得数是有规律，只是这次的数据有点水，我就暴力过了，本想构造一个dfs，但是构造了半天，没有构造出来，然后就看书现学的一个函数next_permutation(ss,ss+len) 输出全排列。
卡过的代码 

```
char ss[MAXN];
int len;
int main()
{
int t;
int n;
scanf("%d",&t);
    getchar();
while(t--)
    {
scanf("%s",&ss);len=strlen(ss);
        flag=0;
        sort(ss,ss+len);//这里一定要有，当时因为现学的，怎么都搞不定，最后才发觉，必须要从 字典序最小的出发，这个函数才可以弄所有的排列情况。
do{

int sum=0;
for(int i=0;i<len;i++)
    sum=sum*10+ss[i]-'0';
if(sum%8==0) 
    {
        flag=1;
break;
    }

    }while(next_permutation(ss,ss+len));
if(flag) printf("YES\n");
else printf("NO\n");
    }
return 0;
｝

这道题的标准答案
链接

N 算是一道找规律的。当时没时间找了，回寝室瞎搞 搞出来。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#define LL long long
#define inf 0x3f3f3f3f
using namespace std;
const int MAXN = 100000;
const double PI= acos(-1.0);
const double eps = 1e-8;
const double e = exp(1.0);
/****************************************/
struct Edge {
int from,to,next;
}edge[MAXN];
int head[MAXN],top;
int root=1;
int n,m;
void init()
{
memset(head,-1,sizeof(head));
    top=0;
}
void addedge(int a,int b)
{
    Edge e={a,b,head[a]};
    edge[top]=e;head[a]=top++;
}
void getmap()
{
int a,b;
while(m--)
    {
scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
}
int depth[MAXN];
int ge[MAXN];
void dfs(int now,int de)
{
    depth[now]=de;
for(int i=head[now];i!=-1;i=edge[i].next)
    {
        Edge e=edge[i];
if(depth[e.to]==-1) 
        {
            dfs(e.to,de+1);
            ge[e.to]++;
            ge[now]+=ge[e.to];
        }
    }
}
int main()
{
scanf("%d%d",&n,&m);
memset(depth,-1,sizeof(depth));
memset(ge,0,sizeof(ge));
    init();
    getmap();
    dfs(1,0);int ans=0;
for(int i=1;i<=n;i++)
if(ge[i]%2==0) ans++;
printf("%d\n",ans);
return 0;
}
标签：

相关文章