拼多多-技术类笔试-20190728

找到数组A中的逆序对（相等也算），有两个位置，数组B中的元素替换时，这两个位置都可以替换

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<sstream>
#include<vector>
#include<cmath>
using namespace std;
vector<int> shua,shub;
int main(){
	string line;
	getline(cin,line);
	stringstream ss1(line);
	int s,lena=0,lenb=0;
	while(ss1 >> s){
		shua.push_back(s);
	}
	getline(cin,line);
	stringstream ss2(line);
	while(ss2>>s){
		shub.push_back(s);
	}
	int pa=shua.size()-1;
	for(int i=0;i<shua.size()-1;i++){
		if(shua[i]>=shua[i+1]){
			pa=i;
			break;
		}
	}
	sort(shub.begin(),shub.end());
	int x;
	bool find=false;
	for(x=shub.size()-1;x>=0;x--){
		//printf("%d\n",x);
		for(int j=1;j>=0;j--){
			if(pa+j==shua.size()-1){
				if(shub[x]>shua[pa+j-1]){
					shua[pa+j]=shub[x];
					find=true;
					break;
				}
			}
			else{
				if(pa+j==0){
					if(shub[x]<shua[pa+j+1]){
						shua[pa+j]=shub[x];
						find=true;
						break;
					}
				}
				else{
					if(shub[x]>shua[pa+j-1]&&shub[x]<shua[pa+j+1]){
						shua[pa+j]=shub[x];
						find=true;
						break;
					}
				}
			}
		}
		if(find)
		break;		
	}
	if(find==false){
		printf("NO\n");
	}
	else{
		for(int i=0;i<shua.size();i++){
			printf("%d ",shua[i]);
		}
	}
	return 0; 
}

测试用例比较弱，忽略乱序就能过90%。统计头尾次数是否为偶数就能A。

真正的解法是：任取一个字符串，记录头尾字符串S，在剩余的字符串中找一个S尾开头的，更新头和尾，直到最后一个满足条件返回true，期间如果找不到开头的，返回false。

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<sstream>
using namespace std;

const int maxn=1030;
string str[maxn];

int main(){
	string s;
	string line;
	getline(cin,line);
	stringstream ss1(line);
	int i=0;
	while(ss1>>s){
	  str[i++]=s;
	}
	bool flag=true;
	string s1=str[0];
	string s2=str[i-1];
	int len2=s2.length();
	if(s1[0]!=s2[len2-1]){
		flag=false;
	}
	if(flag==true){
		for(int j=0;j<i-1;j++){
			s1 = str[j];
			s2 = str[j+1];
			int len1=s1.length();
			if(s1[len1-1]!=s2[0]){
			  flag=false;
			  break;
			}
		}
	}
	if(flag==false){
		printf("false\n");
	}else{
		printf("true\n");
	}
	return 0;
}

拓扑排序

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct Edge
{
	int to,next;
}e[110000];

int n,m,in[11000];
int cnt,p[11000];

pair<int,int> a[11000];

typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > Q;

void insert(const int &x,const int &y)
{
	in[y]++;
	e[++cnt].to=y;
	e[cnt].next=p[x];
	p[x]=cnt;
}

void Topo()
{
	while(!Q.empty())
	{
		int t=Q.top().second; Q.pop();
		cout << t << ' ';
		for(int i=p[t];i;i=e[i].next)
			if(--in[e[i].to]==0) Q.push(a[e[i].to]);
	}
	cout << endl;
	return ;
}

int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;++i)
	{
		cin >> a[i].first;
		a[i].second=i;
	}
	for(int i=1;i<=m;++i)
	{
		int x,y;
		cin >> x >> y;
		insert(x,y);
	}

	for(int i=1;i<=n;++i)
		if(in[i]==0) Q.push(a[i]);

	Topo();
	return 0;
}

dp，待改进

#include <iostream>
#include <algorithm>

using namespace std;

int f[110][8100];
pair<int,int> a[1100];

int getLast(int i)
{
	int temp=a[i].first;
	while(a[i].first==temp)i--;
	return i;
}

int main()
{
	int n,Max=0,Ans=0;
	cin >> n;
	for(int i=1;i<=n;++i)
		cin >> a[i].first;
	for(int i=1;i<=n;++i)
	{
		cin >> a[i].second;
		Max=max(Max,a[i].second);
	}

	sort(a+1,a+n+1);

	for(int i=1;i<=n;++i)
		for(int j=1;j<=Max<<3;++j)
		{
			if(a[i].second<=j && j<=a[i].second<<3)
				f[i][j]=max(f[i-1][j],f[getLast(i)][j-a[i].second]+1);
			else f[i][j]=f[i-1][j];
			Ans=max(Ans,f[i][j]);
		}

	cout << Ans << endl;

	return 0;
}