【蓝桥杯校选2】

【T1】出租

签到题，没什么考点，第二个数组找第一个数组的下标就好

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<vector>

#define ft first
#define sd second
#define js std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

//int d[N], e[N], ne[N], w[N], h[N], idx;
//int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
//priority_queue<int, vector<int>, greater<int>> r;

const int N = 100010;
const int INF = 0x3f3f3f3f;

int m, t, k;
int n, a[N], q[N];
int number[10], id[10];
int cntarr, cntindex = 11;

string s;

int main()
{
    js;
    cin >> s;
    int len = s.size();

    for(int i = 0; i < len; i++)
    {
        if(!number[s[i]-'0'])
        {
            number[s[i]-'0'] = 1;
            cntarr ++;
        }
    }
    int cnt = 1;
//    cout << "*" << cntarr << ' ';
    cout << "int[] arr = new int[]{";
    for(int i = 9; i >= 0; i--)
        if(number[i])
        {
            if(cntarr > 1)
                cout << i << ',';
            else cout << i << "};\n";
            cntarr --;
            id[cnt++] = i;
        }

    cout << "int[] index = new int[]{";
    for(int i = 0; i < len; i++)
    {
        for(int j = 1; j < cnt; j++)
        {
            if(id[j] == s[i]-'0')
            {
                if(i != len-1) cout << j-1 << ',';
                else cout << j-1 << "};";
            }
                
        }
    }

//    for(int i = 1; i < cnt; i++)
//        cout << id[i] << ' ';
    return 0;
}

【T2】最长连续递增子序列

【考点】没什么考点，顶多算是双指针吧

（第一眼以为DP存LIS（最长递增子序列），没敢开，写完一道之后发现不少人写，才发现题目让找的子序列是连续的）

双指针写，维护最长区间的开头结尾即可(注意输出格式！)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<vector>

#define ft first
#define sd second
#define js std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

//int d[N], e[N], ne[N], w[N], h[N], idx;
//int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
//priority_queue<int, vector<int>, greater<int>> r;

const int N = 100010;
const int INF = 0x3f3f3f3f;

int m, t, k;
int n, a[N], q[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    t = a[1];

    int ansl = 0, ansr = 0, maxlen = 0;
    for(int i = 2; i <= n; i++)
    {
        int cnt = 0, l = i, r = i;
        while(a[i] > t && i <= n)
        {
            cnt += 1;
            t = a[i];
            i++;
            r = i;

        }
//        cout << "**" << cnt << ' ';
//        cout << '\n';
        if(cnt > maxlen)
        {
            ansl = l, ansr = r;
            maxlen = cnt;
        }
        t = a[i];
    }
//    cout << ansl << ' ' << ansr << '\n';
    if(ansl == ansr) cout << a[1];
    else
    for(int i = ansl-1; i < ansr; i++)
        if(i != ansr-1)cout << a[i] << ' ';
        else cout << a[i];
    return 0;
}

【T3】那就别担心了

【考点】DFS或BFS，有向图

统计哪些点能走到结尾即可；考场上差一个bug，结束后5min修了一下，应该是没问题了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1010;

int n, m, a, b;
int e[N],v[N], flag;
vector<int> vec[N];
queue<int> r;

void bfs(int a)
{
    r.push(a);
    v[a]=1; e[a]=1;
    while(r.size())
    {
        int t = r.front(); r.pop();
        v[t] = 0;
        if(t == b) continue;
        for(int i = 0; i < vec[t].size(); i++) // 寻找该点的每一个儿子
        {
            int tt = vec[t][i];
            e[tt] += e[t];
            if(!v[tt]) r.push(tt), v[tt]=1;
        }
        e[t] = 0;
        if(!vec[t].size()) flag = 1;
    }
    return ;
}

int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&a,&b);
        vec[a].push_back(b);
    }
    scanf("%d%d",&a,&b);

    bfs(a);

    printf("%d ", e[b]);

    if(flag) printf("No\n");
    else printf("Yes\n");

    return 0;
}

【T4】推断学生所属学校的人数）

【考点】并查集（保存名字有些复杂，但是数据很小，O（n^2）查找就行）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<vector>

#define ft first
#define sd second
#define js std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long LL;
typedef pair<string, int> PII;

//int d[N], e[N], ne[N], w[N], h[N], idx;
//int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
//priority_queue<int, vector<int>, greater<int>> r;

const int N = 1010;
const int INF = 0x3f3f3f3f;

int n, m, t, k;
//int number[10], id[10];
//int cntarr, cntindex = 11;

int f[N];
string name[N];
int cnt1[N];

int findid(string nx)
{
    for(int i = 1; i <= n; i++)
        if(name[i] == nx) return i;
    return 0;
}

int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}

void merge(int fa, int fb)
{
    f[fa] = fb;
    return ;
}

int main()
{
    js;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> name[i];
        f[i] = i;
    }

    cin >> t;
    while(t--)
    {
        string na, nb;
        cin >> na >> nb;
        int ida = findid(na);
        int idb = findid(nb);

        int fa = find(ida), fb = find(idb);
        if(fa != fb) merge(fa, fb);  // 如果两个人不在同一个学校，把他们合并
    }

    for(int i = 1; i <= n; i++)
    {
        int sour = find(i);
        cnt1[sour] += 1;  // 看看每个人的祖宗结点，也就是看自己属于哪个学校集合
    }
    
    int ans = 0, cnt = 0;
    for(int i = 1; i <= n; i++)  // 统计连通块个数和维护连通块最大值
        if(cnt1[i])
        {
            cnt ++;
            ans = max(cnt1[i], ans);
        }
    cout << cnt << ' ' << ans << '\n';
    return 0;
}

【T5】包装机

【考点】栈

注意篮子里空的时候，按0是取不出物品的；同样如果传送带为空，是无法往篮子里加物品的

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>

#define ft first
#define sd second
#define js std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long LL;
typedef pair<string, int> PII;

//int d[N], e[N], ne[N], w[N], h[N], idx;
//int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
//priority_queue<int, vector<int>, greater<int>> r;

const int N = 1010;
const int INF = 0x3f3f3f3f;

int n, m, t, k;
stack<char> r;
string s[N];
int len[N];

int main()
{
    //js;
    cin >> n >> t >> m;
    for(int i = 1; i <= n; i++) cin >> s[i];

    int op;
    while(cin >> op)
    {
        if(op == -1) return 0;
        if(op == 0 && r.size())  // 篮子不空才能拿
        {
            cout << r.top();
            r.pop();
        }

        if(op == 0) continue;

        if(len[op] < s[op].size()) // 传送带上有东西才能往篮子里加
        {
            if(r.size() == m)
            {
                cout << r.top();
                r.pop();
            }
            r.push(s[op][len[op]]);
            len[op] ++;
        }
    }
    return 0;
}

【T6】求解最长递增子序列问题

【考点】LIS，但是题目没有给范围，就按照二分优化DP写了；后来发现数据很水，O(n^2)都能过

这里给出二分优化DP，不好讲，有兴趣自己百度吧

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<map>
#include<vector>

#define ft first
#define sd second
#define js std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

//int d[N], e[N], ne[N], w[N], h[N], idx;
//int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
//priority_queue<int, vector<int>, greater<int>> r;

const int N = 100010;
int n, a[N], q[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    q[1] = a[1];
    int cnt = 1;
    for(int i = 2; i <= n; i++)
    {
        if(a[i] > q[cnt])q[++cnt] = a[i];
        else
            *lower_bound(q + 1, q + cnt + 1, a[i])  = a[i]; // 二分优化
    }

    printf("%d", cnt);
    return 0;
}

【T7】正整数n不同分解式的个数

【考点】因数分解，分治（可以用DP优化）

（考场上没时间写了，先附上别人的代码吧，稍后学习）

1： 分治写法

#include <iostream>
using namespace std;

int solve(int n)
{
	int i;
	int count = 0;
	if (n == 1)
		return 1;
	else
		for (i = 2; i <= n; i++) {
			if (n%i == 0)
				count += solve(n / i);
		}
	return count;
}
int main()
{
	int n;
	cin >> n;
    cout << solve(n) << endl;
	return 0;
}

2：

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
 
 
int a[10000], dp[10000], k = 0;
 
void ul(int num)
{
	int i;
	for (i = 1; i < sqrt(num); i++)
	{
		if (num%i == 0)
		{
			a[k++] = i;
			a[k++] = num / i;
		}
	}
	if (i*i == num)
	{
		a[k++] = i;
	}
}
 
void solve(int n)
{
	int i, j;
	dp[0] = 1;
	for (i = 1; i < k; i++)
	{
		dp[i] = 0;
		for (j = 0; j < i; j++)
		{
			if (a[i] % a[j] == 0)
			{
				dp[i] += dp[j];
			}
		}
	}
}
 
int main()
{
	int n;
	cin >> n;
	ul(n);//求n的约数
	int t;
	
	sort(a, a + k);
	solve(n);
	cout << dp[k - 1] << endl;
	k = 0;
	
	
	return 0;
}