团体程序设计天梯赛练习集

L1-042 日期格式化

思路或重点

格式化输入输出

#include<iostream>
using namespace std;
int main()
{
    int a,b,c;
    scanf("%d-%d-%d",&a,&b,&c);
    printf("%04d-%02d-%02d",c,a,b);	
}

L1-025 正整数A+B

思路或重点

如何正确读取一行中两个值(第二个可能是包含空格的值)，如何将字符串转化为值

#include <iostream>
using namespace std;
string s[2];  // 存放读取的两个值
int f[2];	  // 将两个值转化为数字后的值	
int main()
{
    // cin读取第一个单词，getchar读取单词后的空格
    cin >> s[0];  getchar();
    // 整行读入，即读取第二个单词(因为第二个单词可能含有空格)
    getline(cin, s[1]);
    for(int k = 0; k < 2; k++) 	// 遍历读取的两个值
        for(int i = 0; i < (int)s[k].size(); i++)
        {
            if(s[k][i] >= '0' && s[k][i] <='9')
                f[k] = f[k] * 10 + s[k][i] - '0';
            else 
            {
                f[k] = -1; // 如果含有不是数字的值就使其等于负数，方便后续统一判断
                break;
            }
        }
    // 如果转化后的值在1~1000区间内才合法
    if(f[0] >= 1 && f[0] <= 1000 && f[1] >= 1 && f[1] <= 1000) 
        printf("%d + %d = %d", f[0], f[1], f[0] + f[1]);
    else if(f[0] >= 1 && f[0] <= 1000) 
        printf("%d + ? = ?", f[0]);
    else if(f[1] >= 1 && f[1] <= 1000)
        printf("? + %d = ?", f[1]);
    else printf("? + ? = ?");
}

L1-033 出生年

思路或重点

暴力判断n后的日期是否满足题意即可

#include <iostream>
#include <set>
using namespace std;
// 获取x中含有0~9数字种类的个数
int get(int x)
{
    set<int> st; // 集合自动去重
    // 如果x不是4位数要补0，即: x中含0
    if(x < 1000) st.insert(0);
    while(x)
    {
        st.insert(x % 10);
        x /= 10;
    }
    return st.size();
}
int main()
{
    int n, m;
    cin >> n >> m;
    int i = n;
    while(get(i) != m) i++;
    printf("%d %04d", i - n, i);
}

L1-050 倒数第N个字符串

思路或重点

将az看作025，就会发现这题是个十进制数到二十六进制数的转换。倒序就用最后一个数减 转化为正序即可。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    // 最后一个数为26^n，类比：十进制数000~999间共有10^9个数
    int t = pow(26, n);
    m = t - m; 
    string s = "";
    // 将十进制的m转化为26进制，注意是个n位数字空位记得补0(a)
    for(int i = 0; i < n; i++)
    {
        char ch = 'a' + m % 26;
        s = ch + s;
        m /= 26;
    }
    cout << s << endl;
}

L1-095 分寝室

思路或重点

枚举一个性别寝室数量另外一个可以通过计算的出，找到两种性别每间寝室入住的人数差最小的即可

时间复杂度O(n)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n0, n1, n;
    cin >> n0 >> n1 >> n;
    // t存女生寝室数量，res两种性别每间寝室入住的人数差
    int t = -1, res = 0x3f3f3f3f; 
    // 枚举女生寝室数量i
    for(int i = 1; i < n; i++)
    {
        // 计算男生寝室数量(总数n减女生寝室数量i)
        int j = n - i;
        // 不能一人一间
        if(i==n0||j==n1) continue;
        // 如果能平分，取两种性别每间寝室入住的人数差小的
        if(n0%i==0&&n1%j==0&&abs(n1/j-n0/i)<=res)
                t = i, res = abs(n1 / j - n0 / i);
    }
    if(res == 0x3f3f3f3f) cout << "No Solution" << endl;
    else cout << t << " " << n - t << endl;
    return 0;
}

L1-046 整除光棍

思路或重点

高精度除法。即：实现小学手写除法的计算过程hh

#include <iostream>
using namespace std;
signed main()
{
    int n; cin >> n;
    int t = 1, cnt = 0;
    while(t < n) t = t * 10 + 1, cnt ++;
    while(true) 
    {
        cout << t / n;	
        cnt ++;
        if(t % n == 0) break; //如果没有余数了，停止
        t = t % n * 10 + 1;	
    }
    cout << " " << cnt << endl;
    return 0;
}

L2-003 月饼

思路或重点

贪心选取单价最高的月饼即可

注意：题目中只说饼的库存量，月饼的总售价为正数。所有不一定是整数

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct node{
    double x, y;
    //重载小于号，排序会用小于号作为比较大小的符号
    //比较 a.x / a.y 和 b.x / b.y，这里防止除法有精度损失，所以移项了(如下代码)
    bool operator <(const node &b)const {
        return x * b.y < b.x * y;
    }
}f[N];
signed main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> f[i].x;
    for(int i = 0; i < n; i++)
        cin >> f[i].y;
    sort(f, f + n);
    double res = 0;
    int l = 0;
    while(l < n && m >= f[l].x)
        res += f[l].y, m -= f[l++].x;
    if(l < n) res += m * f[l].y / f[l].x;
    printf("%.2lf", res);
}

运算符重载：运算符重载函数operator的简单用法与常用案例_重载符排序-CSDN博客

L2-008 最长对称子串

思路或重点

这题暴力能过！！！

枚举每个区间判断是否为回文子串即可，按照时间复杂度来说这样其实过不了，这题只是测试点没卡而已。

#include <iostream>
using namespace std;
string s;
bool check(int l, int r)
{
    while(l < r)
    {
        if(s[l] != s[r])
            return false;
        l++, r--;
    }
    return true;
}
int main()
{
    getline(cin, s);
    int n = s.size(), res = 1;
    for(int i = 0; i < n; i++)
        for(int j = i; j < n; j++)
            if(check(i, j))
                res = max(res, j - i + 1);
    cout << res << endl;
}

L2-001 紧急救援

思路或重点

Dijkstra求最短路，即单源路径最短路。只是的记录如下信息、最短路径条数、最大队伍人数、最短且最大人数的路径

#include <bits/stdc++.h>
#define fr first
#define se second
using namespace std;
const int N = 1000010;
typedef pair<int, int> PII;
int e[N], ne[N], w[N], h[N], st[N];
int d[N], cnt[N], num[N], f[N], path[N];
int n, m, S, D, idx;
void add(int a, int b, int c){
    e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx ++;
}
void Dijkstra()
{
    memset(d, 0x3f, sizeof d);
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, S}); d[S] = 0; cnt[S] = 1; num[S] = f[S];
    while(q.size())
    {
        PII t = q.top();
        q.pop();
        if(st[t.se]) continue;
        st[t.se] = 1;
        for(int i = h[t.se]; ~i; i = ne[i]){
            int j = e[i];
            if(d[t.se] + w[i] < d[j]){
                d[j] = d[t.se] + w[i];
                q.push({d[j], j});
                path[j] = t.se;  // 储存路径
                cnt[j] = cnt[t.se]; 
                num[j] = num[t.se] + f[j];
            }
            else if(d[t.se] + w[i] == d[j]){
                cnt[j] += cnt[t.se]; // 最短路径条数增加
                if(num[t.se] + f[j] > num[j]){
                    path[j] = t.se;	// 在最短路径的情况下找最大人数的路径
                    num[j] = num[t.se] + f[j];//在最短路径的情况下求最大人数
                }
            }
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m >> S >> D;
    S ++, D ++; // 为了防止0出问题，给所有点值+1
    for(int i = 1; i <= n; i++)
        cin >> f[i];
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a++, b++;
        add(a, b, c);
        add(b, a, c);
    }
    Dijkstra();
    cout << cnt[D] << " " << num[D] << endl;
    vector<int> v;
    int t = D;
    while(t != S){
        v.push_back(t);
        t = path[t];
    }
    cout << S - 1;
    for(int i = v.size() - 1; i >= 0; i--)
        cout << " " << v[i] - 1;
    return 0;
}

L2-014 列车调度

思路或重点

例如样例：8 4 2 5 3 9 1 6 7 –> 拆分为(8 7) (4 2) (5 3 1) (9 6) 进入四个车道即可

将原数组拆分为几个递减序列，最小化递减序列的个数就是答案

这里有一个Dilworth 定理，本题可参考拦截导弹问题

这题其实就是求最长上升子序列的长度，具体见拦截导弹问题的题解

考虑到数据范围为1e5 dp复杂度O(n^2)会超时，换种做法：单调栈优化，代码如下

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n; cin >> n;
    vector<int> st;
    for(int i = 0; i < n; i++)
    {
        int a; cin >> a;
        if(st.empty() || st.back() < a)
            st.push_back(a);
        *lower_bound(st.begin(), st.end(), a) = a;
    }
    cout << st.size() << endl;
    return 0;
}