10.21基本功训练解题报告

题目:problem

今天终于AK了一次(虽然是【合作】的

因为都是SB题 直接发代码

1. 排列问题

// <1.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
const int maxn=1001;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int n,m,k,kk,a[maxn],f[maxn][maxn],i,j;
bool flag[maxn];
void work(int dep,int last){
int i;
if(dep==m){
kk++;
if(k==kk){
for(i=1; i<n; i++)cout<<a[i]-1<<” “;
cout<<a[n]-1;
exit(0);
}
return;
}
for(i=1;i<=n;i++){
if(f[last][i]&&!flag[i]){
a[dep]=i;
flag[i]=1;
work(dep+1,i);
flag[i]=0;
}
}
}
int main(){
freopen(“1.in”,”r”,stdin);
freopen(“1.out”,”w”,stdout);
n=getint();k=getint();
m=n+1;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=getint();
for(i=0;i<=n;i++)f[i][0]=1,f[0][i]=1;
memset(flag,false,sizeof(flag));
work(1,0);
return 0;
}

2.计算时间

// <2.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}

int main(){
freopen(“2.in”,”r”,stdin);
freopen(“2.out”,”w”,stdout);
int T=getint();
while(T–){
int t=getint();
int s=t%60;t/=60;
int m=t%60,h=t/60;
if(h<10)cout<<0;cout<<h<<“:”;
if(m<10)cout<<0;cout<<m<<“:”;
if(s<10)cout<<0;cout<<s<<endl;
}
return 0;
}

3.最小乘积

// <3.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
const int maxn=10010;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int a[maxn],b[maxn],i;
long long ans;
bool cmp(int a,int b){
return a>b;
}
int main(){
freopen(“3.in”,”r”,stdin);
freopen(“3.out”,”w”,stdout);
int T=getint();
while(T–){
int n=getint();
for(i=1;i<=n;i++)scanf(“%d”,&a[i]);
for(i=1;i<=n;i++)scanf(“%d”,&b[i]);
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1);
ans=0;
for(i=1;i<=n;i++)ans+=a[i]*b[i];
cout<<ans<<endl;
}
return 0;
}

4.最大乘积

// <4.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int a[20],ans,n,m;
bool k[20];
void src(int x,int ji){
if(x==m){ans=max(ans,ji);return;}
for(int i=0;i<n;i++)
if(!k[i]){
k[i]=1;
src(x+1,ji*a[i]);
k[i]=0;
}
}
int main(){
freopen(“4.in”,”r”,stdin);
freopen(“4.out”,”w”,stdout);
int T=getint();
while(T–){
cin>>n>>m;
for(int i=0;i<n;i++)k[i]=0;ans=-100000000;
for(int i=0;i<n;i++)scanf(“%d”,&a[i]);
src(0,1);
cout<<ans<<endl;
}
return 0;
}

5.和最大子序列

// <5.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int a[100002],f[100002],ans=-1000000001;
int main(){
freopen(“5.in”,”r”,stdin);
freopen(“5.out”,”w”,stdout);
int n=getint();
for(int i=1;i<=n;i++){
scanf(“%d”,&a[i]);
if(f[i-1]>0)f[i]=f[i-1]+a[i];
else f[i]=a[i];
ans=max(ans,f[i]);
}
cout<<ans;
return 0;
}

6.矩阵加法

// <6.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int a[102][102];
int main(){
freopen(“6.in”,”r”,stdin);
freopen(“6.out”,”w”,stdout);
int n=getint(),m=getint(),x;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf(“%d”,&x);
a[i][j]=x;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf(“%d”,&x);
a[i][j]+=x;
}
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++)
printf(“%d “,a[i][j]);
printf(“%d\n”,a[i][m]);
}
return 0;
}

7.螺旋数阵

// <7.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn=1002;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int a[maxn][maxn];
int qusi,i,j,m,x,y,k,flag;
int main(){
freopen(“7.in”,”r”,stdin);
freopen(“7.out”,”w”,stdout);
int n=getint();
for(i=1;i<=sqrt(n);i++)if(n%i==0)qusi=i;
m=n/qusi;n=qusi;
memset(a,0,sizeof(a));
for(i=0;i<=n;i++)a[i][0]=-1,a[i][m+1]=1;
for(i=0;i<=m;i++)a[0][i]=-1,a[n+1][i]=1;
x=1;y=1;k=0;flag=1;
while(1){
k++;a[x][y]=k;
if(a[x-1][y]&&a[x+1][y]&&a[x][y-1]&&a[x][y+1])break;
if(flag==1)
if(a[x+1][y]){
flag=2;
y++;
}else x++;
else{
if(flag==2)
if(a[x][y+1]){
flag=3;
x–;
}else y++;
else{
if(flag==3)
if(a[x-1][y]){
flag=4;
y–;
}else x–;
else if(a[x][y-1]){
flag=1;
x++;
}else y–;
}
}
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)cout<<a[i][j]<<” “;
cout<<endl;
}
return 0;
}

8.大数加法

// <8.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int sum[22];
int main(){
freopen(“8.in”,”r”,stdin);
freopen(“8.out”,”w”,stdout);
char s1[22],s2[22];
cin>>s1>>s2;
int l1=strlen(s1),l2=strlen(s2);
for(int i=21;i>21-l1;i–)s1[i]=s1[l1-21+i-1];
for(int i=0;i<=21-l1;i++)s1[i]=’0′;
for(int i=21;i>21-l2;i–)s2[i]=s2[l2-21+i-1];
for(int i=0;i<=21-l2;i++)s2[i]=’0′;
for(int i=21;i>=0;i–)sum[i]=s1[i]-‘0’+s2[i]-‘0’;
for(int i=21;i>=0;i–)if(sum[i]>=10){sum[i-1]+=sum[i]/10;sum[i]%=10;}
int i=0;
for(;!sum[i];i++);
for(;i<=21;i++)cout<<sum[i];
return 0;
}

9.统计单词数

// <9.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
struct WORD{
char s[20];
int len,count;
}w[102];
bool check(char s1[],char s2[],int l){
int i;
for(i=0;i<=l;i++)
if(s1[i]!=s2[i])return 0;
return 1;
}
int t;
int main(){
freopen(“9.in”,”r”,stdin);
freopen(“9.out”,”w”,stdout);
char s[20],c;
int l,maxl=0,i,j;
while(1){
memset(s,0,sizeof(s));
l=0;
do{
c=getchar();
if(!(‘a'<=c&&c<=’z’||’A'<=c&&c<=’Z’))break;
if(‘a'<=c&&c<=’z’)c=c-‘a’+’A’;
s[l++]=c;
}while(‘a'<=c&&c<=’z’||’A'<=c&&c<=’Z’);
if(c==EOF)break;
if(l==0)continue;
for(i=1;i<=t;i++){
if(l==w[i].len)
if(check(s,w[i].s,l)){w[i].count++;break;}
}
if(i==t+1){
t++;
w[t].len=l;
w[t].count=1;
maxl=max(l,maxl);
for(i=0;i<=l;i++)w[t].s[i]=s[i];
}
}
for (i=1;i<=t;i++){
for(j=1;j<=maxl-w[i].len;j++)printf(” “);
printf(“%s:”,w[i].s);
for(j=1;j<=w[i].count;j++)printf(“*”);
printf(“%d\n”,w[i].count);
}
return 0;
}

10.逆序对个数

// <10.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int q[201],yx[201],ans;
void merge(int l,int r)
{
if(l>=r)return;
int m=(l+r)>>1;
merge(l,m);
merge(m+1,r);
int i=l,j=m+1,k=l;
while(i<=m&&j<=r){
if(q[i]>q[j]){
yx[k++]=q[j++];
ans+=m-i+1;
ans%=99999997;
}
else yx[k++]=q[i++];
}
while(i<=m)yx[k++]=q[i++];
while(j<=r)yx[k++]=q[j++];
for(int w=l;w<=r;w++)q[w]=yx[w];
}
int main(){
freopen(“10.in”,”r”,stdin);
freopen(“10.out”,”w”,stdout);
int n=getint();
for(int i=0;i<n;i++)q[i]=getint();
merge(0,n-1);
cout<<ans;
return 0;
}

11.乘法表

// <11.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;

int main(){
freopen(“11.in”,”r”,stdin);
freopen(“11.out”,”w”,stdout);
for(int i=1;i<=9;i++){
for(int o=1;o<=i;o++)
cout<<i<<“*”<<o<<“=”<<i*o<<” “;
cout<<endl;
}
return 0;
}

12.日期距离

// <12.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
struct day{
int y,m,d;
};
int dpm[13]={0,31,28,31,30,31,30,31,31,30,31,30,31},ans;
bool run;
int main(){
freopen(“12.in”,”r”,stdin);
freopen(“12.out”,”w”,stdout);
int y1,m1,d1,y2,m2,d2;
cin>>y1>>m1>>d1>>y2>>m2>>d2;
if(y1>y2||(y1==y2&& (m1>m2||(m1==m2&&d1>d2) ) ) ){
swap(y1,y2);swap(m1,m2);swap(d1,d2);
}
day now={y1,m1,d1};
while(now.y!=y2||now.m!=m2||now.d!=d2){
if(now.y%400==0||(now.y%4==0&&now.y%100!=0))run=1;
else run=0;
now.d++;ans++;
if(now.m==2){
if(run){if(now.d==30){now.m++;now.d=1;}}
else if(now.d==29){now.m++;now.d=1;}
}else if(now.d==dpm[now.m]+1){
now.m++;now.d=1;
}
if(now.m==13){now.y++;now.m=1;}
}
cout<<ans;
return 0;
}

13.分数线划定

// <13.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
struct player
{
int k;
int s;
}p[5001];
bool cmp(player a,player b)
{
return a.s==b.s?a.k<b.k:a.s>b.s;
}
int main(){
freopen(“13.in”,”r”,stdin);
freopen(“13.out”,”w”,stdout);
int n=getint(),m=getint();
for(int i=0;i<n;i++)p[i].k=getint(),p[i].s=getint();
sort(p,p+n,cmp);
int rs=m*1.5;
int mins=p[int(m*1.5)-1].s;
while(p[rs].s==mins)rs++;
cout<<mins<<” “<<rs<<endl;
for(int i=0;i<rs;i++)
cout<<p[i].k<<” “<<p[i].s<<endl;
return 0;
}

14.线性运算

// <14.cpp> – 10/21/15 14:09:53
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int a[105][105],x[105],ax[105];
int main(){
freopen(“14.in”,”r”,stdin);
freopen(“14.out”,”w”,stdout);
int n=getint();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf(“%d”,&a[i][j]);
for(int i=1;i<=n;i++){
scanf(“%d”,&x[i]);
for(int j=1;j<=n;j++){
a[j][i]=a[j][i]*x[i];
ax[j]+=a[j][i];
}
}
for(int i=1;i<=n;i++)printf(“%d\n”,ax[i]);
return 0;
}

说点什么

您将是第一位评论人!

提醒
wpDiscuz