Contest3047 - 计科2101~2104算法设计与分析上机作业04
目录
问题 A: 繁衍
问题 B: 平面分割
问题 C: 二分查找(binary)
问题 D: 求逆序对(deseq)
问题 E: 任务安排问题
问题 F: 最长单调递增子序列的长度
问题 A: 繁衍
题目描述
有一种生物A，一天就能长大，长大的A每过一天就能生一个小A（刚长大的A会从下一天开始生小A），小A过一天后也会长大。。。以此往复。现在，我们有一个刚出生的小A，问n天后共有多少个长大的生物A
输入
输入仅一行，包含一个自然数 n,0<=n<=46.
输出
长大的A的个数
样例输入
5样例输出
5提示
sample 2
0
0
模拟一下就好啦
#include<bits/stdc++.h>
#define int long long
using namespace std;
void fun(int n){
int all=0;
int young=1;
int old=0;
for(int i=1;i<=n;i++){
all=young+old;
int temp=old;
old+=young;
young=temp;
}
cout<<all<<endl;
}
signed main(){
int n;
cin>>n;
fun(n);
}问题 B: 平面分割
题目描述
同一平面内有 n（n≤500）条直线，已知其中 p（p≥2）条直线相交于同一点，则这 n 条直线最多能将 平面分割成多少个不同的区域？
输入
两个整数 n（n≤500）和 p（2≤p≤n）。
输出
一个正整数，代表最多分割成的区域数目。
样例输入
12 5样例输出
73画个图，不难看出，要使分割的区域最大，必然相交的线要最多，
不难看出，当五条线交与一点时，再新增一条线，与之相交的线最多有五条，最多增加5+1块区域
#include<bits/stdc++.h>
#define int long long
using namespace std;
void fun(int n,int k){
int ans=k*2;
for(int i=k+1;i<=n;i++){
ans+=i;
}
cout<<ans<<endl;
}
signed main(){
int n,k;
cin>>n>>k;
fun(n,k);
}问题 C: 二分查找(binary)
题目描述
给出有 n 个元素的由小到大的序列，请你编程找出某元素第一次出现的位置。(n<=10^6)
输入
第一行：一个整数，表示由小到大序列元素个数；下面 n 行，每行一个整数；最后一行 一个整数 x，表示待查找的元素；
输出
如果 x 在序列中，则输出 x 第一次出现的位置，否则输出-1。
样例输入
5
3
5
6
6
7
6样例输出
3这里不是非得用二分，方法很多，像二维数组，map，甚至遍历，既然它叫我们用二分，那我们就用二分吧
注意判别不存在的情况
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>a;
void fun(int n,int t){
int l=0,r=n-1;
int mid=(l+r)/2;
int ans=0;
int flag=0;
while(r-l>1){
if(a[mid]>t){
r=mid;
mid=(l+r)/2;
}
else if(a[mid]<t){
l=mid;
mid=(l+r)/2;
}
else{
ans=mid;
flag=1;
break;
}
}
if(a[r]==t){
ans=r;
}
else if(a[l]==t){
ans=l;
}
else{
if(!flag){
cout<<-1<<endl;
return ;
}
}
while(a[ans]==t){
ans--;
}
cout<<ans+2<<endl;
}
signed main(){
int n;
cin>>n;
int temp;
for(int i=0;i<n;i++){
cin>>temp;
a.push_back(temp);
}
int t;
cin>>t;
fun(n,t);
}问题 D: 求逆序对(deseq)
题目描述
给定一个序列 a1,a2,…,an，如果存在 i<j 并且 ai>aj，那么我们称之为逆序对，求逆序对 的数目。
输入
第一行为 n,表示序列长度，接下来的 n 行，第 i+1 行表示序列中的第 i 个数。
输出
所有逆序对总数。
样例输入
4
3
2
3
2样例输出
3提示
N<=10^5，Ai<=10^5
分治？？？太难了，不会，我用set试试
#include<bits/stdc++.h>
#define int long long
using namespace std;
class Mycompare{
public:
bool operator()(int v1, int v2){
return v1 > v2;
}
};
multiset<int,Mycompare>a;
signed main(){
int n;
cin>>n;
int temp;
int ans=0;
for(int i=0;i<n;i++){
cin>>temp;
a.insert(temp);
ans+=distance(a.begin(),a.find(temp));
}
cout<<ans<<endl;
}我擦，时间超了，没道理呀，On*logn鸭。（可能是distance函数太慢了，我去，它的时间复杂度是On，你太baby了）
吐了，老老实实分治吧
有种归并排序的意思
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int b[100005];
int fun(int l,int r){
if(l==r){
return 0;
}
int mid=(l+r)/2;
int ans=fun(l,mid)+fun(mid+1,r);
for(int i=l,j=l,k=mid+1;i<=r;i++){
if(j>mid){
b[i]=a[k++];
continue;
}
if(k>r){
b[i]=a[j++];
continue;
}
if(a[j]>a[k]){
b[i]=a[k++];
ans+=mid-j+1;
}
else{
b[i]=a[j++];
continue;
}
}
for(int i=l;i<=r;i++){
a[i]=b[i];
}
return ans;
}
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cout<<fun(1,n)<<endl;
}问题 E: 任务安排问题
题目描述
某个系统中有一个设备，该设备每次只能分配给一个任务使用，且只有当任务结束后才能再分配给另一个任务使用。 假设系统启动时间计为时间0点，预先有一份任务计划表，预定了每个任务的开始时间点和持续时间。 要求设计算法统计出该设备最多能够满足任务计划表中的多少个任务的使用请求。
输入
输入的第一行为一个整数m，表示要计算的用例的个数。 从第二行开始是m个测试用例的输入数据。 每个测试用例的第一行为一个整数n，表示任务计划表中的任务个数，n≤1000。 每个测试用例的第二行为2*n个整数，分别为每个任务的开始时间点和持续时间，整数之间用空格隔开。
输出
要求对每个测试用例输出一行结果，输出结果为该测试用例下，能够满足的最大任务数。
样例输入
1
11
12 2 2 11 8 4 8 3 6 4 5 4 3 5 5 2 0 6 3 2 1 3样例输出
4结束时间早的优先
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct info{
int s;
int e;
};
bool mysort(info a,info b){
return a.e<b.e;
}
signed main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<info>all(n);
int temp;
for(int i=0;i<n;i++){
cin>>all[i].s>>temp;
all[i].e=all[i].s+temp;
}
sort(all.begin(),all.end(),mysort);
int ti=-1;
int ans=0;
for(int i=0;i<n;i++){
if(ti<=all[i].s){
ans++;
ti=all[i].e;
}
}
cout<<ans<<endl;
}
}问题 F: 最长单调递增子序列的长度
题目描述
请设计算法找出一个整数序列中最长单调递增子序列的长度。
输入
第一行为测试用例个数n，0＜n≤1000。 第二行开始，每行为一个测试用例。每个测试用例由一组空格间隔的整数组成，第一个整数m为序列的长度，后面m个整数为序列内容，0＜m≤1000。0≤ai≤1000
输出
对每个测试用例，输出其最长单调递增子序列的长度，每个输出占一行。
样例输入
2
5 1 3 2 4 5
6 3 2 4 5 3 2
样例输出
4
3动态规划嘛。。。
注意：dp[i]是表示i之前的最大递增子序列，我们如何求dp[i]呢？
当然是遍历i之前的dp数组，如果a[i]>a[j]，那么dp[i]=max(dp[j]+1,dp[i])
dp数组初始化为1嗷
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1005];
signed main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
int dp[1005];
for(int i=0;i<1005;i++){
dp[i]=1;
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(a[i]>a[j]){
dp[i]=max(dp[j]+1,dp[i]);
}
}
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}
}