算法竞赛

复习用

练习用多case解题

这道题注意要开long long。。

#include<iostream>

using namespace std;

typedef  long long ll;

ll god(ll x,ll y)
{ ll s=x*y;

while(x%y)
{ ll tmp=x%y;

x=y;

y=tmp;

}

return s/y;

}



int main()
{

 int n;

cin>>n;

while(n--)
{

ll x,y;

cin>>x>>y;

cout<<god(x,y)<<endl;

}

cout<<"group 1 done"<<endl;

ll x,y;

cin>>x>>y;

while(x&&y)
{

cout<<god(x,y)<<endl;

cin>>x>>y;

}

cout<<"group 2 done"<<endl;



while(cin>>x>>y)
{

cout<<god(x,y)<<endl;

}

cout<<"group 3 done"<<endl;

return 0;

} 

有序数组元素安插

这题是真的屎啊。。题目也没说要double，搞得我怎么都过不了，还有排序记得用lower_bound(折半插入排序)，不然好像会超时。。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

double god(vector<int>nums)
{
	if (nums.size() % 2)
	{
		return nums[nums.size() / 2];
	}

	else return (nums[nums.size() / 2] + nums[nums.size() / 2 - 1]) / 2.0;
}

int main()
{	

	vector<int>nums;
	vector<int>operation;
	int n;
	cin >> n;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	int m;
	cin >> m;
	for (int i=0;i<m;i++)
	{
		int x;
		cin >> x;
		operation.push_back(x);
	}
	vector<int>current=nums;
	for (int num:operation)
	{
		auto it = lower_bound(current.begin(),current.end(),num);
		current.insert(it,num);
		int len = current.size();
		double ans=god(current);
		if (ans == (int)ans)
		{
			cout << (int)ans << endl;
		}
		else cout << ans << endl;
	}


	return 0;
}

丑数

动态规划做法。

#include<iostream>
#include<vector>
#include<algorithm>
typedef long long ll;
using namespace std;

int dp[1000001],n;

void god()
{	
	dp[1] = 1;
	int p2 = 1, p3 = 1, p5 = 1;
	for (int i=2;i<=n;i++)
	{
		dp[i] = min(min(dp[p3]*3,dp[p5]*5),dp[p2]*2);
		if (dp[i]==dp[p2]*2)
		{
			p2++;
		}

		if (dp[i]==dp[p3]*3)
		{
			p3++;
		}
		if (dp[i]==dp[p5]*5)
		{
			p5++;
		}
	}
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		god();
		cout << dp[n]<<endl;
	}
	return 0;
}

勇者斗恶龙

贪心算法，先将两个数组排好序，然后用双指针，

#include<iostream>
#include<algorithm>
using namespace std;
const long long N = 1e7;
int r[N],p[N]; 


int main()
{
	int n, m;
	cin >> n >> m;
	while (n&&m)
	{
		int ans=0;
	
		for (int i = 0; i < n; i++)
		{
			cin >> r[i];
		}
		for (int j = 0; j < m; j++)
		{
			cin >> p[j];
		}
		if (m < n)
		{
			cout << "Loowater is doomed!" << endl;
			cin >> n >> m;
			continue;
		}
		sort(r, r + n);
		sort(p, p + m);
		int i = 0, j = 0;
		while (i < n && j < m)
		{
			if (r[i] <= p[j])
			{
				ans += p[j];
				i++;
			}

			j++;
		}
		if (j == m && i != n)
		{
			cout << "Loowater is doomed!" << endl;
			cin >> n >> m;
			continue;
		}
		cout << ans << endl;
		cin >> n >> m;
	}
	return 0;
}

校赛排名

这题考查的是用stable_sort，不改变原来的输入序列的情况下排序，其实就是要用稳定的排序算法

#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct str {
	char name[20];
	int num;
	int t;
}stu;
bool cmp(stu a,stu b)
{
	if (a.num != b.num) {
		return a.num > b.num;
	}

	else if (a.t != b.t)
	{
		return a.t < b.t;
	}

     return false;

}

stu student[500010];
int main()
{	
	
	int n;
	scanf("%d",&n);
	for (int i=0;i<n;i++)
	{
		scanf("%d%d%s",&student[i].num,&student[i].t,&student[i].name);
	}
	stable_sort(student,student+n,cmp);
	for (int i=0;i<n;i++)
	{
		printf("%s\n",student[i].name);
	}
	return 0;
}

简单迷宫

考察dfs，深度优先搜索的基础题

#include <stdio.h>
#include <queue>
using namespace std;
typedef struct {
    int r; // row
    int c; // column
    int s; // step
}LOC;
int sr, sc, dr, dc;
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
char d[100][100];
void solve() {
    int m, n, i, nr, nc;
    queue<LOC> q;
    scanf("%d%d", &m, &n);
    for (i = 0; i < m; i++) scanf("%s", d[i]);
    scanf("%d%d%d%d", &sr, &sc, &dr, &dc);
    LOC first = { sr,sc,0 };
    q.push(first);
    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        d[current.r][current.c] = '1';
        if (current.c==dc&&current.r==dr)
        {
            printf("%d\n",current.s);
            return;
        }
        for (int i=0;i<4;i++)
        {
            int tc = current.c + dir[i][0], tr = current.r + dir[i][1];
            if (d[tr][tc]=='0'&& tr >= 0 && tc >= 0 && tr<m && tc<n)
            {
                LOC tmp = {tr,tc,current.s+1};
                q.push(tmp);
            }
        }

    }
    printf("die\n");

}
int main() {
    int n;
    scanf("%d", &n);
    while (n--) solve();
}

巡逻的士兵

本体只使用递归会超时，要开一个数组进行记忆化存储

#include<iostream>
using namespace std;
int dp[100010];

int f(int n)
{		
	if (n<100000&&dp[n])
	{
		return dp[n];
	}
	if (n<3)
	{
		return 0;
	}

	else if (n==3)
	{
		return 1;
	}

	int t=f(n / 2) + f((n+1)/2);
	if (n < 100000)
	{
		dp[n] = t;
	}
	return t;
}

int main()
{
	int n;
	cin >> n;
	while (n)
	{
		cout<<f(n)<<endl;
		cin >> n;
	}
	return 0;
}

不巡逻的士兵

没什么好说的。。就是把输出改成n-3*f(n)就可以了。。（因为上一题得出的结果是用多少种不同的解，而这题求的是有多少个位置不会被选中，所以将解的个数乘以3再用总数减掉就可以了）

#include<iostream>
using namespace std;
int dp[100010];

int f(int n)
{		
	if (n<100000&&dp[n])
	{
		return dp[n];
	}
	if (n<3)
	{
		return 0;
	}

	else if (n==3)
	{
		return 1;
	}

	int t=f(n / 2) + f((n+1)/2);
	if (n < 100000)
	{
		dp[n] = t;
	}
	return t;
}

int main()
{
	int n;
	cin >> n;
	while (n)
	{
		cout<<n-3*f(n)<<endl;
		cin >> n;
	}
	return 0;
}

不被选中去巡逻的士兵的最小编号

简单说一下思路：每次去奇和偶，去奇数的话总数除以2，去偶数的话总数+1除以2，start表示每次操作得到的序列的第一个编号，step表示数与数之间的间隔，去奇数的话要将第一个数加上间隔，去偶数的话的一个编号不发生改变，每次操作比较最小值就可以了。。

#include<iostream>
using namespace std;
const int N = 1011;
int f(int n,int start,int step)
{	
	if (n==3)
	{
		return 0;
	}

	if (n<3)
	{
		return start;
	}
	int odd = f(n/2,start+step,step*2);
	int even = f((n+1)/2,start,step*2);
	if (odd&&even)
	{
		return min(odd,even);
	}

	 if (odd)
	{
		return odd;
	}

	 if (even)
	{
		return even;
	}
}


int main()
{
	int n;
	cin >> n;
	while (n)
	{
		cout << f(n,1,1)<<endl;
		cin >> n;
	}

	return 0;
}

判断士兵是否会被选中去巡逻

本来这道题是想要从上面那道题改一下交上去的，结果发现超时了，这道题重点在于找到原序列与子序列，原位置与子序列中的位置中的换算关系。

#include<iostream>
using namespace std;

bool f(int n,int m)
{
	if (n==3)
	{
		return true;
	}

	 if (n<3)
	{
		return false;
	}

	if (m % 2)
	{
		return f((n + 1) / 2, (m + 1) / 2);
	}

	else return f(n/2,m/2);
}


int main()
{
	int t,m;
	cin >> t >> m;
	while (t&&m)
	{
		if (f(t, m))
		{
			cout << 'Y' << endl;
		}

		else cout << 'N' << endl;

		cin >> t >> m;
	}


	return 0;
}

除法等式

本题枚举的时候注意是按照n的倍数去枚举的，然后是判断函数开一个数组存储出现过的数字，然后0的话是不做处理的。。。

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;

bool f(int n,int m)
{
	vector<bool>a(10,false);
	int i = 0;
	while (n)
	{	

		if (n%10&&!a[n%10])
		{
			a[n % 10] = true;
		}
		else if(n%10&&a[n%10])
		{
			return false;
		}
		n /= 10;
	}



	while (m)
	{	

		if (m%10&&!a[m % 10])
		{
			a[m % 10] = true;
		}
		else if (m%10&&a[m % 10])
		{
			return false;
		}
		m /= 10;
	}
	return true;
}

int main()
{
	int n;
	cin >> n;
	while (n)
	{
		for (int i = 1; n * i < 100000; i++)
		{
			if (f(i * n, i))
			{
				printf("%05d/%05d=%d\n", i * n, i, n);
			}
		}
		cout << endl;
		cin >> n;
	}

	return 0;
}

分数拆分

非常简单的代码，通过数学推导得到。。。

#include<iostream>
#include<vector>
using namespace std;
int main()
{	
	long long k;
	cin >> k;
	for (long long y=k+1;y<=2*k;y++)
	{
		if (y*k%(y-k)==0)
		{
			long long x = y * k / (y - k);
			printf("1/%lld=1/%lld+1/%lld\n",k,x,y);
		}
	}
	return 0;
}

N各不同整数全排列

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;
vector<int>nums;
int mark[1011];
vector<vector<int>>ans;
vector<int>tmp;
void dfs(int x)
{
	if (x==n)
	{
		ans.push_back(tmp);
	}

	for (int i=0;i<n;i++)
	{
		if (!mark[i])
		{
			mark[i] = 1;
			tmp.push_back(nums[i]);
			dfs(x+1);
			mark[i] = 0;
			tmp.pop_back();
		}
	}



}


int main()
{
	cin >> n;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	dfs(0);
	sort(ans.begin(),ans.end());
	for (int i=0;i<ans.size();i++)
	{
		for (int j=0;j<n;j++)
		{
			cout << ans[i][j]<<' ';
		}
		cout << endl;
	}

	return 0;
}

这个有点太长了。。。

改进版：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int>nums;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	sort(nums.begin(),nums.end());
	do {
		for (int k:nums)
		{
			cout << k << ' ';
		}
		cout << endl;
	} while (next_permutation(nums.begin(), nums.end()));

	return 0;
}

有重复元素的全排列

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

map<vector<int>,bool>mp;

bool issafe(const vector<int>&nums)
{
	for (int i = 1; i < nums.size();i++) {
		if (nums[i-1]%2&&nums[i]%2)
		{
			return false;
		}
	}
	return  true;
}

void load(const vector<int>&nums)
{
	for (int k:nums)
	{
		cout << k << ' ';
	}
	cout << endl;
}

vector<vector<int>>ans;

int main()
{
	int n;
	cin >> n;
	vector<int>nums;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}
	sort(nums.begin(),nums.end());
	do {
		if (issafe(nums))
		{
			
			if (!mp[nums])
			{	
				mp[nums] = true;
				ans.push_back(nums);
			}
			}
	} while (next_permutation(nums.begin(), nums.end()));
	for (int i=0;i<ans.size();i++)
	{
		load(ans[i]);
	}
	return 0;
}

N皇后

先写一个判断函数，再利用回溯

#include<iostream>
#include<algorithm>

using namespace std;

int queen[1011] = {0};

int ans;

bool is_Safe(int queen[], int row, int col,int n)
{
	for (int i=1;i<row;i++)//检查列方向是否会被攻击
	{
		if (queen[i]==col)
		{
			return false;
		}
	}

	for (int i = row - 1, j=col-1; i > 0&&j>=1;i--,j--)//检查左上方是否会被攻击
	{
		if (queen[i]==j)
		{
			return false;
		}
	}

	for (int i = row - 1, j=col+1; i >=1&&j<=n;i--,j++)//检查右上方是否会被攻击
	{
		if (queen[i]==j)
		{
			return false;
		}

	}

	return true;
}


void Queen(int queen[],int row,int n)
{
	if (row==n+1)
	{	
		ans++;
		return;
	}

	for (int i=1;i<=n;i++)
	{
		if (is_Safe(queen,row,i,n))
		{
			queen[row] = i;
			Queen(queen,row+1,n);
			queen[row] = 0;
		}
	}


}




int main()
{
	int t;
	cin >> t;
	int n;
	while (t--)
	{
		cin >> n;
		Queen(queen,1,n);
		cout << ans << endl;
		ans = 0;
	}
	return 0;
}

01背包问题

经典的动态算法问题

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1011;
int dp[N];
int w[N];
int v[N];
int main()
{
	int m,n;
	cin >> m>>n;
	for (int i = 1; i <= n; i++)
	{
		cin >> w[i]>>v[i];
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=m;j>=w[i];j--)
		{
			dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout << dp[m];
	return 0;
}

最长公共子序列

注意状态转移方程

#include<iostream>
#include<string>
using namespace std;
const int N = 1011;

string text1, text2;

int dp[N][N];

int main()
{
	getline(cin,text1);
	getchar();
	getline(cin,text2);
	int n = text1.size();
	int m = text2.size();
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			if (text1[i] == text2[j])
			{
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
		}
	}
	cout << dp[n][m]+1;
	return 0;
}

铁棍焊接

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;

void f(vector<int>&nums,int index,int current_sum,set<int>&sum)
{
	if (index==nums.size())
	{
		if (current_sum)
		{
			sum.insert(current_sum);
		}
		return;
	}
	if (current_sum)
	{
		sum.insert(current_sum);
	}

	f(nums,index+1,current_sum,sum);
	f(nums,index+1,current_sum+nums[index],sum);
}


int main()
{
	int n;
	cin >> n;
	vector<int>nums(n);
	for (int &i:nums)
	{
		cin >> i;
	}
	set<int>sum;
	f(nums,0,0,sum);
	for (int i:sum)
	{
		cout << i << ' ';
	}
	return 0;
}

王教授的密码

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;



int main()
{
	vector<int>nums(3);
	for (int &i:nums)
	{
		cin >> i;
	}
	int s1 = nums[1] - nums[0];
	int s2 = nums[2] - nums[1];
	if (s1<s2)
	{
		cout << nums[1] + s1;
	}

	if (s2<s1)
	{
		cout << nums[0] + s2;
	}

	if (s2==s1)
	{
		if (s1 < 0)
		{
			cout << nums[2] + s1;
		}

		else cout << nums[0] - s1;
	}
	return 0;
}

to be continue…