华东交通大学2017年ACM双基程序设计大赛题解

简单题

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 19 Accepted Submission(s) : 14

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

大吉大利今晚吃鸡

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 1379 Accepted Submission(s) : 501

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

最近流行吃鸡,那就直接输出一行"Winner winner ,chicken dinner!"(没有双引号)
模板代码：
#include <stdio.h>
int main(){
printf("hello world ");
return 0;
}

Input

没有输入

Output

输出一行"Winner winner ,chicken dinner!"注意要换行

Sample Output

Winner winner ,chicken dinner!

解题报告：

签到题

#include <stdio.h>
int main(){
printf("Winner winner ,chicken dinner! ");
return 0;
}

1002

跳舞

Time Limit : 3000/1500ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 354 Accepted Submission(s) : 38

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

一天YZW参加了学校组织交际舞活动，活动的开始活动方分别给男生和女生从1-n进行编号，按照从小到大顺时针的方式进行男女搭档分配，相同编号的男女组合成一对，例如一号男生与一号女生配对，以此类推。可是YZW对其中一个小姐姐一见钟情，于是机智的他向管理员提出了两种操作
1.在这种情况下，管理员会给出移动的方向和大小，然后所有的男生向着这个方向移动x个位置。2.管理员会把相邻的奇数和偶数位置上的男生互换。
在其中女生的位置是不会变的。可是YZW不知道经过这些Q次操作后，他自己身在何方，能否到达自己喜欢的小姐姐身边。

Input

输入一个T代表T组数据(T<=10)，每组输入一个n和q(2≤n≤200000,1≤q≤1000000,其中n为偶数),分别代表有n对男女和有q次操作。
接下来是q行，每一行输入：
1.x代表所有男生移动的位置的大小。同时x>0表示顺时针移动，x<0表示逆时针移动。
2.代表管理员会把相邻的奇数和偶数位置上的男生互换。

Output

输出1号到n号小姐姐配对的分别是几号男生。

Sample Input

6 3

1 2

Sample Output

4 3 6 5 2 1

解题报告：记录第一个和第二个男生的位置n1和n2，将所有的操作的影响加在这个两位置上，其中第一种操作相当于n1和n2加上或者减去x,第二种操作相当于奇数位置上的数+1,偶数位上的数-1.然后通过这样两个位置推导出所有的其他的位置即可

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<bitset>

#include<set>

#include<map>

using namespace std;

#define LL long long

#define pi (4*atan(1.0))

#define eps 1e-8

#define bug(x) cout<<"bug"<<x<<endl;

const int N=1e6+10,M=7e6+10,inf=1e9+10,MOD=10;

const LL INF=1e18+10;

int a[N];

int main()

{

int T;

scanf("%d",&T);

while(T--)

{

int n,q;

scanf("%d%d",&n,&q);

int s=1,e=2;

while(q--)

{

int t;

scanf("%d",&t);

if(t==1)

{

LL x;

scanf("%lld",&x);

x%=n;

s+=x;

e+=x;

if(s>n)s-=n;

if(s<=0)s+=n;

if(e>n)e-=n;

if(e<=0)e+=n;

}

else

{

if(s%2)s++;

else s--;

if(e%2)e++;

else e--;

}

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

{

a[s]=i*2-1;

a[e]=i*2;

s+=2;

e+=2;

if(s>n)s-=n;

if(e>n)e-=n;

}

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

printf("%d%c",a[i],(i==n?' ':' '));

}

return 0;

}

1003

这是道水题

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 827 Accepted Submission(s) : 179

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

有两个球在长度为L的直线跑道上运动，两端为墙。0时刻小球a以1m/s的速度从起点向终点运动，t时刻小球b以相同的速度从终点向起点运动。问T时刻两球的距离。这里小球与小球、小球与墙的碰撞均为弹性碰撞，所有过程没有能量损失。

Input

先输入一个q，代表q组数据，然后每组3个整数 L，t，T。
1<=L<=1000;0<=t<=1000;t<=T<=1000;

Output

一个整数，代表答案。

Sample Input

10 4 7

8 3 9

Sample Output

解题报告：单独考虑每个小球，分别求出最后小球的位置pos1，pos2。答案即为abs(pos1-pos2)。

代码:

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
    int L,t,T;
    int cas;
    scanf("%d",&cas);
    while(cas--&&scanf("%d %d %d",&L,&t,&T)){
        int n=T%(2*L);
        int l;
        if(n>=L){
            l=L-(n-L);
        }else{
            l=n;
        }
        int r;
        int n2=(T-t)%(2*L);
        if(n2>=L){
            r=L-(n2-L);
        }else{
            r=n2;
        }
        r=L-r;
        int ans=r-l;
        if(ans>=0){
            printf("%d ",ans);
        }else{
            printf("%d ",-1*ans);
        }
    }
    return 0;
}

1004

小廖的美丽子串

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 7 Accepted Submission(s) : 0

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

小廖最近沉迷于字符串，发现了一个问题，不能解决，非常懊恼。你能帮助他吗？
对于一个长度为n的字符串，可以从大小为m的字母表里选取构成。
定义一个字符串是美丽的就满足：如果它的所有字符适当改变顺序后能够组成一个回文串并且长度为奇数。
那么问题来了，大小为m的字母表组成的所有大小为n的串有m^n个，其包含美丽的子串的总和是多少？

Input

首先输入一个t，代表t组数据t<=100
每组数据输入n，m，n代表字符串的长度，m代表字母表的大小。
1<=n,m<=2000

Output

输出结果mod1000000007。（mod表示取余）

Sample Input

2 2

3 2

10 3

Sample Output

1490526

解题报告：

设dp[i][j]表示长度为i的串有j种字符出现奇数次的个数。

dp[i][j]只能由dp[i-1][j-1]和dp[i-1][j+1]转化来。

假如长度为i-1的串有j-1种字符出现奇数次，可以在剩余的（m-j+1）种字符选取一个；

假如长度为i-1的串有j+1种字符出现奇数次，可以在（j+1）种字符里任选一个；

所以状态转移方程为： dp[i][j]=(dp[i-1][j-1]*(m-j+1)+dp[i-1][j+1]*(j+1))

注意若能组成回文串，当长度为奇数时j=1，否则j=0.

枚举奇数长度i的串，其位置可以有（n-i+1）种，其它n-i位任意补齐，所以对于长度为i有

dp[i][1]*p[n-i]*（n-i+1）个，p[n-i]表示m的n-i次方。累加求和得到

ans=(ans+dp[i][i&1]*po[n-i]%mod*(n-i+1)%mod)%mod;

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<time.h>
#define F(x) (3*x*x-x)/2
using namespace std;
typedef long long ll;
const int maxn=2000+10;
const int mod=1e9+7;
int n,m;
ll dp[maxn][maxn],po[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        dp[0][0]=1;dp[0][1]=0;
        for(int i=1;i<=n;i++)
        {
            dp[i][0]=dp[i-1][1];
            dp[i][i]=(dp[i-1][i-1]*(m-i+1))%mod;
            int j;
            if(i&1)j=1;
            else j=2;
            for(;j<i;j+=2)
            {
                dp[i][j]=(dp[i-1][j-1]*(m-j+1)+dp[i-1][j+1]*(j+1))%mod;
            }
        }
        po[0]=1;
        for(int i=1;i<=n;i++)
        po[i]=(po[i-1]*m)%mod;
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
                    if(i%2)
            ans=(ans+dp[i][i&1]*po[n-i]%mod*(n-i+1)%mod)%mod;
        }
        printf("%lld ",ans);
    }
    return 0;
}

1005

矩阵

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 168 Accepted Submission(s) : 52

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

假设你有一个矩阵，有这样的运算A^(n+1) = A^(n)*A (*代表矩阵乘法)
现在已知一个n*n矩阵A,S = A+A^2+A^3+...+A^k,输出S，因为每一个元素太大了，输出的每个元素模10

Input

先输入一个T(T<=10)，每组一个n,k(1<=n<=30, k<=1000000)

Output

输出一个矩阵,每个元素模10(行末尾没有多余空格)

Sample Input

3 2

0 2 0

0 0 2

0 0 0

Sample Output

0 2 4

0 0 2

0 0 0

解题报告：

倍增，复杂度log(k)*n*n

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<bitset>

#include<set>

#include<map>

using namespace std;

#define LL long long

#define pi (4*atan(1.0))

#define eps 1e-8

#define bug(x) cout<<"bug"<<x<<endl;

const int N=1e6+10,M=7e6+10,inf=1e9+10,MOD=10;

const LL INF=1e18+10;

int n;

struct Matrix

{

short a[31][31];

Matrix()

{

memset(a,0,sizeof(a));

}

void init()

{

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

for(int j=0;j<n;j++)

a[i][j]=(i==j);

}

Matrix operator + (const Matrix &B)const

{

Matrix C;

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

for(int j=0;j<n;j++)

C.a[i][j]=(a[i][j]+B.a[i][j])%MOD;

return C;

}

Matrix operator * (const Matrix &B)const

{

Matrix C;

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

for(int k=0;k<n;k++)

for(int j=0;j<n;j++)

C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%MOD;

return C;

}

Matrix operator ^ (const int &t)const

{

Matrix A=(*this),res;

res.init();

int p=t;

while(p)

{

if(p&1)res=res*A;

A=A*A;

p>>=1;

}

return res;

}

}a[100],base;

int main()

{

int T;

scanf("%d",&T);

while(T--)

{

int k;

scanf("%d%d",&n,&k);

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

for(int j=0;j<n;j++)

scanf("%d",&a[1].a[i][j]);

base=a[1];

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

{

a[i]=a[i-1]+(a[i-1])*base;

base=base*base;

}

base=a[1];

Matrix now,ans;

now.init();

for(int i=19;i>=0;i--)

{

if((1<<i)&k)

{

ans=ans+a[i+1]*now;

now=now*(base^(1<<i));

}

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

{

for(int j=0;j<n;j++)

printf("%d%c",ans.a[i][j],(j==n-1?' ':' '));

}

return 0;

}

1006

大厦

Time Limit : 4000/2000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 41 Accepted Submission(s) : 2

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

给你一个n(1<=n<=1000)层楼的大厦，每一楼里面有m(1<=m<=1000)房间，
每个房间一定的金钱X(1<=x<=1000)，假设不同楼层的房间是互通的，相同楼层的房间是不互通的。也就是说每层只能取一个，现在给你一个捡钱的机会。捡钱的方式不同，会导致你得到的钱的不同，求可能捡到的钱的前k大的和

Input

输入一个T，表示T组样例；
每组数据第一行输入n，m，k
接下来输入n行，每行m个数，代表这个房间拥有的金钱

Output

输出可能捡到的钱的前k大的和

Sample Input

3 4 5

1 2 3 4

5 6 7 8

1 2 3 4

Sample Output

解题报告：

假设任意两层为集合A B(从大到小排序）对于B集合的元素B[i]，显然它和A[1]组合值最大，

如果B[i]+A[j]是前K大值中的一个，那么B[i]+A[k](1<=k < j)必然也是前K大的，

所以B[i]+A[j]被选则B[i]+A[j-1]之前就被选了，

所以优先队列中只需维护Size(B)个元素，首先把A[1]+B[i]全部进队，

每次从队首拿出一个组合(i,j)(表示A[i]+B[j])，把A[i+1]+B[j]进队，

直到拿出K个元素为止，即为这两个集合合并的前K大

n层的话只要把每次得到的结果和其他层按照这样处理就可以了

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<bitset>

#include<set>

#include<map>

using namespace std;

#define LL long long

#define pi (4*atan(1.0))

#define eps 1e-8

#define bug(x) cout<<"bug"<<x<<endl;

const int N=1e3+10,M=7e6+10,inf=1e9+10,MOD=10;

const LL INF=1e18+10;

int a[N],k,n,m;

vector<int>v;

struct is

{

int x,pos;

is(){}

is(int _x,int _pos):x(_x),pos(_pos){}

bool operator <(const is &c)const

{

return x<c.x;

}

};

int cmp(int x,int y)

{

return x>y;

}

vector<int> update(vector<int>v)

{

vector<int>ans;

if(v.size()*m<=k)

{

for(int i=0;i<v.size();i++)

for(int j=1;j<=m;j++)

ans.push_back(v[i]+a[j]);

sort(ans.begin(),ans.end(),cmp);

}

else

{

priority_queue<is>q;

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

{

q.push(is(a[i]+v[0],0));

}

int tmp=k;

while(tmp--)

{

is x=q.top();

ans.push_back(x.x);

q.pop();

if(x.pos+1<v.size())

q.push(is(x.x-v[x.pos]+v[x.pos+1],x.pos+1));

}

return ans;

}

int main()

{

int T;

scanf("%d",&T);

while(T--)

{

scanf("%d%d%d",&n,&m,&k);

v.clear();

v.push_back(0);

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

{

for(int j=1;j<=m;j++)

scanf("%d",&a[j]);

v=update(v);

}

LL ans=0;

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

ans+=v[i];

printf("%lld ",ans);

}

return 0;

}

1007

超级牛奶

Time Limit : 6000/3000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 52 Accepted Submission(s) : 6

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

超市有 n 种牛奶，每种牛奶的浓度为 ai/1000 。
Alice 想合成出一种浓度为 k/1000 的超级牛奶，每种牛奶可以买任意杯，她最少需要买多少杯牛奶呢？

Input

多组输入，每组数据第一行输入 k、n ，第二行输入 n 个数ai，表示 n 种牛奶的浓度。
0<=k<=1000 , 1<=n<=1000000, 0<=ai<=1000 。所给数据都是整数。

Output

每组数据输出一个数，表示最少要买多少杯牛奶。如果无法合成浓度为 k/1000 的牛奶，就输出 -1 。

Sample Input

50 2

100 25

Sample Output

解题报告：要注意到浓度绝不会超过1000/1000。

假设选取m杯牛奶，则 (a1+a2+......+am) / m = n，变换一下为(a1-n)+(a2-n)+......+(am-n) = 0。即要选 m杯牛奶，其浓度减 n之和为0。而浓度不超过1000，故(a1-n)+(a2-n)+....+(as-n)的和肯定在 -1000~1000之间，所以可以 bfs解，相当于找一条浓度0 到浓度0 的路径，边长为(ai-n)，这样到每个可能浓度点的距离一定是最近的。

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<bitset>

#include<set>

#include<map>

using namespace std;

#define LL long long

#define pi (4*atan(1.0))

#define eps 1e-8

#define bug(x) cout<<"bug"<<x<<endl;

const int N=1e3+10,M=7e6+10,inf=1e9+10,MOD=10;

const LL INF=1e18+10;

vector<int>v[5];

int flag[N][2];

int dp[N][2];

int main()

{

int k,n;

while(~scanf("%d%d",&k,&n))

{

v[0].clear();

v[1].clear();

memset(flag,0,sizeof(flag));

memset(dp,-1,sizeof(dp));

int fuck=0;

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

{

int x;

scanf("%d",&x);

if(x==k)fuck=1;

if(x<k&&!flag[k-x][0])v[0].push_back(k-x),flag[k-x][0]=1;

if(x>k&&!flag[x-k][1])v[1].push_back(x-k),flag[x-k][1]=1;

}

if(fuck)

{

printf("1 ");

continue;

}

dp[0][0]=0;

dp[0][1]=0;

for(int kk=0;kk<=1;kk++)

for(int i=0;i<v[kk].size();i++)

{

for(int j=v[kk][i];j<=1000;j++)

{

if(dp[j-v[kk][i]][kk]!=-1)

{

if(dp[j][kk]==-1)dp[j][kk]=dp[j-v[kk][i]][kk]+1;

else dp[j][kk]=min(dp[j][kk],dp[j-v[kk][i]][kk]+1);

}

int ans=inf;

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

if(dp[i][0]!=-1&&dp[i][1]!=-1)

{

ans=min(ans,dp[i][0]+dp[i][1]);

}

if(ans==inf)printf("-1 ");

else printf("%d ",ans);

}

return 0;

}

1008

子序列

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 499 Accepted Submission(s) : 270

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

长度为 n 的序列，把它划分成两段非空的子序列，定义权值为：两段子序列的最大值的差的绝对值。求可能的最大的权值。
数据范围：
2 <= n <= 10^6 ， 0 < 序列内的数 <= 10^6 。

Input

第一行输入一个 T，表示有　T　组数据。
接下来有 T 组数据，每组数据的第一行输入一个数 n ，第二行输入 n 个数。

Output

每组数据输出可能的最大的权值。

Sample Input

1 2 3

Sample Output

解题报告：

签到题，代码：

#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int a[1000010];
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
   int maxn=0;int k,n;
   memset(a,0,sizeof(a));
   cin>>n;
   for(int i=1;i<=n;i++){

   cin>>a[i];
   if(a[i]>maxn)
   {
   maxn=a[i];
   k=i;
  }


                        }
    int k2;
    if(k!=1&&k!=n)
    k2=min(a[1],a[n]);
    else if(k==a[1])
    {

     k2=a[n];

}
else
k2=a[1];
cout<<maxn-k2<<endl;
  }
return 0;
}

1009

MDD的随机数

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 61 Accepted Submission(s) : 28

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

MDD随机生成了n(n<le5)个随机数x(x<=1e9),
这n个随机数排成一个序列，MDD有q(q<=le5)个询问，
每个询问给你一个a，问你这个序列中有多少个区间的最大公约数不为a

Input

第一行输入一个T,表示T组测试样例
每组样例包含一个n,表示n个随机数
再输入一个Q，表示Q个询问
每个询问输入一个a

Output

每个询问输出有多少个区间的gcd不为a

Sample Input

1 2 4 4 1

Sample Output

题解：考虑到如果固定区间左端点L，那么右端点从L+1变化到n的过程中gcd最多变化logn次（因为每次变化至少除以2）,那么我们就可以枚举左端点，然后每次二分值连续的区间，然后都存到map里,只需要将所有的区间个数减去区间gcd=x的个数就是本题的答案

代码：#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<bitset>

#include<set>

#include<map>

using namespace std;

#define LL long long

#define pi (4*atan(1.0))

#define eps 1e-8

#define bug(x) cout<<"bug"<<x<<endl;

const int N=1e3+10,M=7e6+10,inf=1e9+10,MOD=10;

const LL INF=1e18+10;

int a[N];

map<int,LL>dp[N],ans;

map<int,LL>::iterator it;

int main()

{

int n,T;

scanf("%d",&T);

while(T--)

{

scanf("%d",&n);

ans.clear();

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

dp[i].clear();

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

scanf("%d",&a[i]);

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

{

dp[i][a[i]]++;

ans[a[i]]++;

for(it=dp[i-1].begin();it!=dp[i-1].end();it++)

{

int x=it->first;

LL z=it->second;

int now=__gcd(x,a[i]);

dp[i][now]+=z;

ans[now]+=z;

}

LL sum=1LL*n*(n+1)/2;

int q;

scanf("%d",&q);

while(q--)

{

int x;

scanf("%d",&x);

printf("%lld ",sum-ans[x]);

}

return 0;

}

1010

QAQ

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 1082 Accepted Submission(s) : 223

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

定义操作：将数 n 变为 f(n) = floor(sqrt(n))。即对一个数开平方后，再向下取整。
如对 2 进行一次操作，开平方再向下取整, 1.414213562..... = 1 , 即变为了 1 。
现在给出一个数 n，如果能在 5 次操作内把 n 变为 1，则输出操作次数；如果则超过5次输出"QAQ"。
数据范围：
1<= n <= 10^100

Input

多组输入，每行输入一个数　ｎ。

Output

每组数据输出要多少次操作，或者输出"QAQ"

Sample Input

233

233333333333333333333333333333333333333333333333333333333

Sample Output

QAQ

解题报告：签到题，大数

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include<string.h>
using namespace std;

int main()
{
char str[1000005];
long long n;
while(cin>>str)
{
    double ant=0;

int len=strlen(str);
if(len>10)
cout<<"QAQ"<<endl;
else
{
for(int i=0;i<len;i++)
{
ant=ant*10+str[i]-'0';
}
int flag=0;
while(ant!=1)
{
ant= floor(sqrt(ant));
flag++;
}
if(flag>5)
cout<<"QAQ"<<endl;
else
cout<<flag<<endl;
}
}

    return 0;
}