CONTEST – 缪永伟全校C语言程序设计作业十三

CONTEST – 缪永伟全校C语言程序设计作业十三

.php/2020/06/05/contest-%e7%bc%aa%e6%b0%b8%e4%bc%9f%e5%85%a8%e6%a0%a1c%e8%af%ad%e8%a8%80%e7%a8%8b%e5%ba%8f%e8%ae%be%e8%ae%a1%e4%bd%9c%e4%b8%9a%e5%8d%81%e4%b8%89/

---

 

感想：这个D没想出是个多重背包，然后利用存1判定.自己真菜。搞得我又想期末复习月写题了…

Problem A: 矩阵鞍点

Description

若矩阵Am´n中的某一元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍点存在时），并分析该函数的时间复杂度。该程序可以测试多个案例。

Input

第一行输入测试案例数T 以后T块输入每个测试案例，每个测试案例之间空一行 每个测试案例第一行输入m与n(m与n均小于100） 然后是m行数据 每行共n个数据（这些数据全为整数）

Output

对每个案例输出所有的鞍点，鞍点的顺序从上到下，从左到右,每个鞍点输出格式为：”A[i][j]”其中i,j是实际鞍点对应数字 每个鞍点之间空一个空格 如果没有鞍点，则输出“NO.”(注意NO后面有一个点’.’) 2个案例之间空一个空行

Sample Input

2
2 2
2 3
1 12 3
4 5 1
7 6 -1

Sample Output

A[1][1]A[1][3]

HINT

---

思路：以前的题是一个鞍点，现在多个。我们分别标记每列的最大和每行的最小，然后最后再输出。是一个模拟题

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=150;
typedef long long LL;
LL a[maxn][maxn];
LL vis1[maxn][maxn];
LL vis2[maxn][maxn];
int main(void)
{LL t;cin>>t;while(t--){memset(a,0,sizeof(a));memset(vis1,0,sizeof(vis1));memset(vis2,0,sizeof(vis2));int flag=1;LL n,m;cin>>n>>m;//n是行,m是列 for(LL i=1;i<=n;i++)for(LL j=1;j<=m;j++)cin>>a[i][j];//每一行的最小值 for(LL i=1;i<=n;i++){LL res=a[i][1];LL index1=i;LL index2=1;for(LL j=1;j<=m;j++){if(res>a[i][j]) {res=a[i][j];index1=i;index2=j;}}vis1[index1][index2]=1;}//每一列的最大值for(LL j=1;j<=m;j++){LL res=a[1][j];LL index1=1;LL index2=j;for(LL i=1;i<=n;i++){if(res<a[i][j]){res=a[i][j];index1=i;index2=j;	}	}	vis2[index1][index2]=3;} for(LL i=1;i<=n;i++)for(LL j=1;j<=m;j++){if(vis1[i][j]==1&&vis2[i][j]==3){flag=0;cout<<"A["<<i<<"]"<<"["<<j<<"]"<<endl;cout<<endl;}}if(flag) cout<<"NO."<<endl;	}return 0;
}

---

Problem B: 线性表逆置

Description

设有一个线性表 (e0, e1, …, en-2, en-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个程序将这个线性表原地逆置，即将数组的前n个原址内容置换为 (en-1, en-2, …, e1, e0)。 该程序可以对多个测试案例进行操作。

Input

第一行输入一个整数T,表示T个测试案例； 以后每行是一个测试案例，每行第一个数据是线性表中元素个数n（n不超过100）,然后是n个数字（浮点型）

Output

对于每一个测试案例，输出倒置后的线性表

Sample Input

1
5 2 3 4 5 6

Sample Output

6 5 4 3 2

HINT

---

思路：发现有好多同学来问的时候想多了…都在交换顺序啥的..其实倒序输出就行了

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5;
typedef long long LL;
double a[maxn];
int main(void)
{LL t;cin>>t;while(t--){LL n;cin>>n;for(LL i=1;i<=n;i++) cin>>a[i];for(LL i=n;i>=2;i--) cout<<a[i]<<" ";cout<<a[1]<<endl;}return 0;
}

---

Problem C: 直接插入排序

编一C程序，该程序可以测试多个测试组，每个测试组它能读入一串整数（以-9999为结束标记）并对它们进行从小到大直接插入排序，同时输出排序时对这些整数进行比较的总次数（输入整数时，相邻的两个用空格隔开，整数个数<2000）。

Input

第一行先输入测试组数T 然后是T个测试组， 每个测试组先输入整数个数N（2<=n<2000) 然后输入1行，包含N个整数，每2个整数之间用空格隔开，以-9999为结束标记

Output

对每个测试组输出2行， 第1行输出比较次数 第2行输出排序后的数，2个数之间用一个空格隔开

Sample Input

1
4
3 2 4 5 -9999

Sample Output

3
2 3 4 5

HINT

---

#include<iostream>
using namespace std;
int main()
{int t,n,a[3000],i,j,k,q,s,b;scanf("%d",&t);for(q=0;q<t;q++){s=0;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a[i]);}int k;cin>>k;for(i=1;i<n;i++){for(j=i-1;j>=0;j--){k=0;if(a[i]>=a[j]){k=j+1;s++;break;}else{s++;}}b=a[i];for(j=i;j>k;j--){a[j]=a[j-1];}a[k]=b;}				printf("%dn",s);printf("%d",a[0]);for(i=1;i<n;i++){printf(" %d",a[i]);}printf("n");}return 0;
}

---

Problem D: 欠债还钱

Description

llk经常和wy一起去yh小饭馆吃盖浇饭，一天他们吃完后llk把两个人的钱一起付了，但是wy不想欠llk的钱。现在wy手中有一些散钱，llk手中也有一些散钱，wy想知道能不能刚好使得两不相欠，但是wy很笨，你能帮助wy吗？

Input

多组测试数据，每组第一行输入3个非负整数，C，n，m。C代表wy欠llk的钱，n代表wy手中钱面值的种类，m代表llk手中钱面值的种类。接下来的n行，每行两个数v， c，分别代表wy手中面值为v的钱币有c个。再接下来的m行，每行两个数v，c，分别代表llk手中面值为v的钱币有c个。 （C <= 10000; 1<=n, m<50; 0<=v < =100; 0<=c<=10 ）

Output

每组数据输出一行，如果存在一种方案使得wy和llk两不相欠，输出YES，否则输出NO。

Sample Input

7 1 1
10 1
1 10

Sample Output

YES

HINT

wy给了llk一张10元的，llk又给了wy三个1元的

思路：刚开始想用dfs做的，但是太难写了。赛后讨论是个多重背包。考的是dp判定性。

状态定义：dp[i][j]表示前i个种类还钱数为j时候 的合法情况。

状态转移：dp[i][j]=dp[i-1][j-k*v[i]] (k:0~c[i])

和平时的dp有点不一样的是初始赋值1之后然后dp[i][j]为1的就不用转移了。并且要注意转移的条件是j-k*v[i]>=0（要还钱数为正)和j-k*v[i]<=C,我的输入这样做防止越界；

然后具体看代码注释，学校的oj容易Tle

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=150;
typedef int  LL;//要int，不然T 
LL dp[maxn][10010];
LL v[maxn];
LL c[maxn];
int main(void)
{std::ios::sync_with_stdio(false);cin.tie(0);LL C,n,m;while(cin>>C>>n>>m){memset(dp,0,sizeof(dp));for(LL i=1;i<=n;i++)cin>>v[i]>>c[i];for(LL i=n+1;i<=n+m;i++){cin>>v[i]>>c[i];v[i]=-v[i];	}	 dp[0][0]=1;for(LL i=1;i<=n+m;i++)for(LL j=0;j<=C;j++)//如果硬要j<=10000,把j和k的循环换一下，不然就T了 for(LL k=0;k<=c[i];k++)/// {if(dp[i][j]) continue;//已经是1的别更新了 if(j-k*v[i]>=0&&j-k*v[i]<=C)//v[i]会是个负数，<=C,不然可能超内存 dp[i][j]=dp[i-1][j-k*v[i]];}if(dp[n+m][C]) cout<<"YES"<<endl;else cout<<"NO"<<endl;	}
return 0;
}

 

上面的码有点问题..但是Oj的数据比较emmm居然过了.问了几个人说背包优化后T了没优化没有T，几个人交流了一下数据可能有问题.修正代码如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
typedef long long ll;
using namespace std;
const   int N=110;
int dp[N][50010];
int v[N];
int c[N];
int main()
{int C,n,m;while(scanf("%d%d%d",&C,&n,&m)!=EOF){for(int i=1;i<=n+m;i++)for(int j=0;j<50010;j++)dp[i][j]=0;int sum=C;for(int i=1;i<=n;i++){scanf("%d%d",&v[i],&c[i]);sum+=v[i]*c[i];}for(int i=n+1;i<=n+m;i++){scanf("%d%d",&v[i],&c[i]);v[i]=-v[i];}dp[0][0]=1;for(int i=1;i<=n+m;i++)for(int k=0;k<=sum;k++)for(int j=0;j<=c[i];j++){if(dp[i][k])	break;if(k-j*v[i]>=0&&dp[i-1][k-j*v[i]]){//		cout<<i<<' '<<k<<endl;dp[i][k]=dp[i-1][k-j*v[i]];}}if(dp[n+m][C])  printf("YESn");else        printf("NOn");}return 0;
}

---

Problem E: 输入3个字符串，按由小到大顺序输出

Description

输入3个字符串(长度都小于80)，按由小到大顺序输出。

Input

多组测试数据，每组输入三个字符串。

Output

按从小到大输出三个字符串。

Sample Input

oh
my
god
China
Beijing
Hangzhou

Sample Output

god
my
oh
Beijing
China
Hangzhou

HINT

---

上个学期的老题目了。贴上学期的代码：

当然现在c++更方便：

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e4;
typedef long long LL;
string str[maxn];
bool cmp(string a,string b)
{return a<b;
}
int main(void)
{while(cin>>str[0]>>str[1]>>str[2]){sort(str,str+3);cout<<str[0]<<endl;cout<<str[1]<<endl;cout<<str[2]<<endl;}return 0;
}

---

Problem F: 铺地砖

Description

元旦过去了，新年大酬宾活动也已经告一段落了。陈盖历望着堆在仓库的瓷砖，很无聊的他把这些瓷砖裁成很多1X1 1X2 1X3的小瓷砖，然后他把这些小瓷砖排在地上画的一个1*n的长方形里。问铺满这个长方形共有多少种方法？

Input

首先输入一个整数T,表示有T组测试数据 然后是T行，每行输入1个正整数n(n<=50)

Output

对于每个n输出铺的方法种数

Sample Input

3
1
2
3

Sample Output

1
2
4

HINT

---

思路：也是一个上学期被坑的老题了。这题数据有问题，别用longlong，据说long能过，int必过。

当前的转态由缺一个1×1,一个1×2,一个1×3的状态转移过来

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5;
typedef long long LL;
int a[maxn];//题目数据还是没修呀.. 
int main(void)
{LL t;cin>>t;a[1]=1;a[2]=2;a[3]=4;for(LL i=4;i<=60;i++)a[i]=a[i-1]+a[i-2]+a[i-3]; while(t--){LL n;cin>>n;cout<<a[n]<<endl;}return 0;
}