第三、第四、第五、第六届，软件院第一、第二、第三、第四程序设计大赛题目全集

备注: 右侧有目录(点击即可切换题目)，题目链接也可以点击, 部分题目暂时没写

7-1 诗歌交流

1
2
3
4
5
6
7
#include<iostream>
using namespace std;
int main()
{
    printf("Celi dada,mimi nunu!\nYe dada!\nMuhe ye!");
    return 0;
}

7-2 密码破译

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<string>
using namespace std;
const int N = 100;
string str[N];
int main()
{
    for(int i = 0; i < 5; i++)
        getline(cin, str[i]);
    cout << str[4] << endl;
    cout << str[0] << endl;
    cout << str[3] << endl;
    cout << str[1] << endl;
    printf("%s", str[2].c_str());
    return 0;
}

7-3 打印菱形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int main()
{
    int n; cin >> n;
    int cnt = 1, t = 1;
    while(cnt + 2 * (t + 1) <= n)
        cnt += 2 * (t + 1), t += 2;
    t /= 2;
    for(int i = -t; i <= t; i++)
    {
        for(int j = 0; j < abs(i); j++)
            cout << " ";
        for(int j = 0; j < 2 * (t-abs(i)) + 1; j++)
            cout << "*";
        cout << endl;
    }
    cout << n - cnt << endl;
    return 0;
}

7-4 比特串(Alter)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main()
{
    string s; cin >> s;
    int t = 0, cnt0 = 0, cnt1 = 0;
    int res = 0x3f3f3f3f;
    // t为总共0的个数
    for(int i = 0; i < s.size(); i++)
        if(s[i]=='0') t ++;
    for(int i = 0; i < s.size(); i++)
    {
        //cnt0动态维护前i个字符中0的个数(包括下标为i)，所以t-cnt0为i后有多少个0(不包括下标i)
        //cnt1动态维护前i个字符中0的个数(不包括下标为i)
        if(s[i]=='0') cnt0 ++;
        //将i前面1改为0, 后面0改为1的操作数取min
        res = min(cnt1 + t - cnt0, res);
        if(s[i]=='1') cnt1 ++;
    }
    cout << res << endl;
    return 0;
}

7-5 Keven的援助

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#define fr first
#define se second
using namespace std;
const int N = 100010;
pair<char, int> f[N];
int main()
{
    int n; cin >> n;
    while(n--)
    {
        string s; cin >> s;
        int idx = 0, cnt = 1;
        // 将s字符串转化计数, 例如: aaabbaccc -> {a,3} {b,2} {a,1} {c,3}
        for(int i = 1; i < s.size(); i++){
            if(s[i]!=s[i-1]) {
                f[idx++] = {s[i-1], cnt};
                cnt = 1;
            }
            else cnt ++;
        }
        f[idx++] = {s.back(), cnt};
        int res = 0;
        for(int i = 1; i < idx-1; i++)
            if(f[i].fr=='b' && f[i-1].fr=='a' && f[i+1].fr=='c')
                if(f[i].se<=f[i-1].se && f[i].se<=f[i+1].se)
                    res = max(res, f[i].se);
        cout << res << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
using namespace std;
string s;
bool judge(int idx, int cnt){
    if(s.size() - idx < 2 * cnt) 
        return false;
    for(int i = idx; i < idx+cnt; i++)
        if(s[i]!='b') return false;
    for(int i = idx+cnt; i < idx+2*cnt; i++)
        if(s[i]!='c') return false;
    return true;
}
int main()
{
    int n; cin >> n;
    while(n--)
    {
        cin >> s;
        int res = 0, a = 0, t = 0;
        for(int i = 0; i < s.size(); i++)
        {
            while(s[i]=='a') a++, i++, t = 1;
            if(t == 1)
            {
                while(a > 0)
                {
                    if(judge(i, a)) 
                    {
                        res = max(a, res);
                        i += 2 * a;
                        break;
                    }
                    a--;
                }
            }
            t = 0; 
        }
        cout << res << endl;
    }
    return 0;
}

7-6 音游

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int f[N];
map<int, int> mp;
int main()
{
    int n, w; cin >> n >> w;
    for(int i = 0; i < n; i++)
        cin >> f[i];
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int j = i;
        int Min = f[i], Max = f[i];
        while(j < n && Max - Min <= 2 * w){
            j++;
            Max = max(Max, f[j]);
            Min = min(Min, f[j]);
        }
        res = max(res, j - i);
    }
    cout << res << endl;
    return 0;
}

7-7 四心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

typedef pair<double, double> PII;

int T;
struct Point{
    double x, y;
    Point(){}
    Point(double xx, double yy)
    {
        x = xx;
        y = yy;
    }
};
Point a, b, c;
Point operator+(Point a, Point b)
{
    return Point(a.x + b.x, a.y + b.y);
}
Point operator-(Point a, Point b)
{
    return Point(a.x - b.x, a.y - b.y);
}
double sqr(double x)
{
    return x * x;
}
double dis(Point a, Point b)
{
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
Point gravity(Point a, Point b, Point c)//重心
{
    double x = (a.x + b.x + c.x) / 3;
    double y = (a.y + b.y + c.y) / 3;
    return Point(x, y);
}
Point Incenter(Point a, Point b, Point c)//内心
{
    double A = dis(b, c);
    double B = dis(a, c);
    double C = dis(a, b);
    double S = A + B + C;
    double x = (A * a.x + B * b.x + C * c.x) / S;
    double y = (A * a.y + B * b.y + C * c.y) / S;
    return Point(x, y);
}
Point Circum(Point a,Point b,Point c){ //三角形外心 
    double x1=a.x,y1=a.y;
    double x2=b.x,y2=b.y;
    double x3=c.x,y3=c.y;
    
    double a1=2*(x2-x1);
    double b1=2*(y2-y1);
    double c1=x2*x2+y2*y2-x1*x1-y1*y1;
    
    double a2=2*(x3-x2);
    double b2=2*(y3-y2);
    double c2=x3*x3+y3*y3-x2*x2-y2*y2;
    
    double x=(c1*b2-c2*b1)/(a1*b2-a2*b1);
    double y=(a1*c2-a2*c1)/(a1*b2-a2*b1);
    
    return Point(x,y);
}


Point Orthocenter(Point p0, Point p1 ,Point p2){
    double a1,b1,a2,b2,c1,c2;
    a1 = p2.x-p1.x , b1=p2.y-p1.y , c1 = 0 ;
    a2 = p2.x-p0.x , b2=p2.y-p0.y , c2 = (p1.x-p0.x)*a2+(p1.y-p0.y)*b2 ;
    double d = a1 * b2 - a2 * b1;
    return Point(p0.x+(c1*b2-c2*b1)/d , p0.y+(a1*c2-a2*c1)/d) ;
}

int main()
{
    while(cin >> T, T)
    {
        scanf("%lf%lf", &a.x, &a.y);
        scanf("%lf%lf", &b.x, &b.y);
        scanf("%lf%lf", &c.x, &c.y);
        if(T == 1)
        {
            Point res = Circum(a, b, c);
            if(res.x == -0) res.x = 0;
            printf("Point O : (%.2lf, %.2lf)\n", res.x, res.y);
        }
        else if(T == 2)
        {
            Point res = Incenter(a, b, c);
            if(res.x == -0) res.x = 0;
            printf("Point I : (%.2lf, %.2lf)\n", res.x, res.y);
        }
        else if(T == 3)
        {
            Point res = gravity(a, b, c);
            if(res.x == -0) res.x = 0;
            printf("Point G : (%.2lf, %.2lf)\n", res.x, res.y);
        }
        else
        {
            Point res = Orthocenter(a, b, c);
            if(res.x == -0) res.x = 0; 
            printf("Point H : (%.2lf, %.2lf)\n", res.x, res.y);
        }
    }
    return 0;
}

7-8 太空旅行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 20;
typedef pair<double, double> PII;
int st[N], d[N], g[N], n;
double res = 0x3f3f3f3f;
PII f[N];
double dd(PII a, PII b){
    double c =a.x - b.x, d = a.y - b.y;
    return sqrt(c*c + d*d);
}
void dfs(int u, PII a, double num, double Max)
{
    if(num - Max > res) return;
    if(u == n + 1){
        double t = dd(a, {0, 0});
        Max = max(Max, t);
        num += t - Max;
        if(round(num*100) < round(res*100)){
            res = num;
            memcpy(g, d, sizeof d);
        }
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!st[i])
        {
            st[i] = 1; d[u] = i;
            double t = dd(a, f[i]);
            dfs(u + 1, f[i], num + t, max(Max, t));
            st[i] = 0; 
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> f[i].x >> f[i].y;
    dfs(1, {0, 0}, 0, 0);
    for(int i = 0; i <= n; i++)
        cout << g[i] << " ";
    printf("0\n");
    printf("Total distance is %.2f.", res);
    return 0;
}

7-9 空间结构: 暂无

1

7-10 小马和电梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int res = 0, n = s.size();
    for(int i = 0; i < n; i++)
    {
        if(s[i]=='U') res += n - i - 1 + i * 2;
        else res += (n - i - 1) * 2 + i;
    }
    cout << res << endl;
    return 0;
}

7-11 小马和她的队友

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;
int cnt[19];
int main()
{
    int n, res = 0, idx = 0;
    cin >> n;
    while(n--)
    {
        int m, k; cin >> m >> k;
        int l = 1, r = 10000, t = 0;
        for(int i = 0; i < m; i++)
        {
            int a; cin >> a;
            if(a >= l && a <= r)
            {
                t++;
                if(a < k) l = a + 1, idx++;
                else if(a > k) r = a - 1, idx++;
            }
        }
        cnt[idx%3] += t;
    }
    for(int i = 0; i < 3; i++)
        res = max(res, cnt[i]);
    cout << res << endl;
    return 0;
}

7-12 小马和线性代数作业

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
int main()
{
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> f[i][j];
    int a = 0, b = 0, ch;
    while(m--)
    {
        cin >> ch;
        if(ch) a ++;
        else b ++;
    }
    // 列反转
    if(a%2)
    {
        for(int i = 1; i <= n; i++)
            reverse(f[i] + 1, f[i] + n + 1);
    }
    // 行反转
    if(b%2)
        for(int i = n; i >= 1; i--, puts(""))
            for(int j = 1; j <= n; j++)
                printf("%d ", f[i][j]);
    else 
        for(int i = 1; i <= n; i++, puts(""))
            for(int j = 1; j <= n; j++)
                printf("%d ", f[i][j]);
    return 0;
}

7-13 小马和Virtual participation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int f[N];
int main()
{
    int T; cin >> T;
    while(T--)
    {
        int n; cin >> n;
        memset(f, 0, sizeof f);
        map<string, int> mp;
        for(int i = 0; i < n; i++)
        {
            int x; char  p; string s;
            cin >> x >> p >> s;
            string t = to_string(x);
            if(s[0]!='A' || mp[t + p]) continue;
            mp[t + p] = 1;
            f[p-'A']++;
        }
        int res = 0, Max = 0;
        for(int i = 0; i < 28; i++)
        {
            if(f[i] > Max) 
            {
                Max = f[i];
                res = i;
            }
        }
        cout << (char)(res + 'A') << endl;
    }
}

7-14 小马和操作系统考试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<set>
using namespace std;
struct node
{
    int id, data;
    bool operator<(const node&x)const
    {
        if(data != x.data)return data<x.data;
        return id<x.id;
    }
};
multiset<node> s;
int n, m;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int a; cin >> a;
        s.insert({i, a});
    }
    for(int i = 0; i < m; i++)
    {
        int a; cin >> a;
        auto it = s.lower_bound({0, a});
        if(it->data >= a)
        {
            printf("%d ",it->id);
            int id = it->id, data = it->data - a;
            s.erase(it);
            s.insert({id, data});
        }
        else printf("-1 ");
    }
}

7-15 咕咕和三色珠串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int main()
{
    int T; cin >> T;
    while(T--)
    {
        string s; cin >> s;
        // 思路将三色球转换为双色，这里将b转化为rg
        // 考虑双色情况即可
        // 记录r和g的球的个数, t判断是否只有一种球
        int r = 0, g = 0, t = 1;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i]=='r') r++;
            else if(s[i]=='g') g++;
            else r ++, g++;
            if(i!=0 && s[i]!=s[i-1]) t = 0;
        }
        if(t) cout << s.size() << endl;
        else if(r%2==0 && g%2==0) cout << 2 << endl;
        else cout << 1 << endl;
    }
    return 0;
}

7-16 小马和数学题: 暂无

1

7-17 海祇岛的机关： 暂无

1

7-18 阶乘之和取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#define int long long
using namespace std;
const int mod = 1e6;
signed main()
{
    int n; cin >> n;
    int res = 0, t = 1;
    if(n > 100) n = 100;
    for(int i = 1; i <= n; i++)
    {
        t = t * i % mod;
        res = (res + t) % mod;
    }
    cout << res << endl;
}
1
2
3
4
5
6
7
8
9
n = int(input())
if n > 50: 
    n = 50
t = 1 
res = 0 
for i in range(1, n + 1):
    t = t * i % 1e6
    res = int((res + t) % 1e6)
print(res)

7-19 社交集群

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
vector<int> v[N];
int p[N];
int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    for(int i = 1; i < N; i++)
        p[i] = i;
    int n, k; cin >> n;
    for(int i = 1; i <= n; i++){
        scanf("%d: ", &k);
        while(k--){
            int a; cin >> a;
            v[a].push_back(i);
        }
    }
    for(int i = 1; i < N; i++)
        for(int j = 1; j < v[i].size(); j++)
            p[find(v[i][j])] = find(v[i][j-1]);
    unordered_map<int, int> mp;
    for(int i = 1; i <= n ; i++)
        mp[find(i)]++;
    vector<int> res;
    for(auto aa:mp)
        res.push_back(aa.second);
    sort(res.begin(), res.end(), greater<int>());
    cout << res.size() << endl;
    cout << res[0];
    for(int i = 1; i < res.size(); i++)
        cout << " " << res[i];
}

7-20 对称图形的面积：暂无

1

7-21 你究竟有几个好妹妹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
struct node{
    string name;
    int age;
    string date;
    bool operator < (const node &e){
        if(e.name != name) return name < e.name;
        if(e.age != age) return age < e.age;
        return date < e.date;
    }
};
string s, name, date;
int n, age;
char gender;
string check(string name)
{
    if(name.size() <= s.size()) return name;
    int m = s.size();
    string cp = name;
    transform(cp.begin(), cp.end(), cp.begin(), ::tolower);
    if(cp.compare(0, m, s)==0)
        return name.substr(m);
    if(cp.rfind(s)==name.size()-m)
        return name.substr(0, name.size()-m);
    return name;
}
vector<node> v;
int main()
{
    cin >> s >> n;
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    while(n--)
    {
        cin >> name >> gender >> age >> date;
        string temp = check(name);
        if(gender=='M' || temp == name) continue;
        v.push_back({temp, age, date});
    }
    sort(v.begin(), v.end());
    cout << v.size() << endl;
    for(int i = 0; i < v.size(); i++)
        cout << v[i].name << " " << v[i].age << " " << v[i].date << endl;
    return 0;
}

7-22 暴力小学(二年级篇)-求出4个数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
struct node{
    int a,b,c,d;
};
int main()
{
    int n; cin >> n;
    vector<node> v;
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < 10; j++)
            for(int k = 0; k < 10; k++)
                for(int t = 0; t < 10; t++)
                    {
                        if(i==j||i==k||i==t||j==k||j==t||k==t)
                            continue;
                        int a = i*1000+j*100+k*10+t;
                        int b = j*100+k*10+t;
                        int c = k*10+t;
                        int d = t;
                        if(a + b + c + d == n) 
                            v.push_back({i,j,k,t});
                    }
    cout << v.size() << endl;
    for(node aa:v)
        cout << aa.a << aa.b << aa.c << aa.d << endl;
    return 0;
}

7-23 还原二叉树： 暂无

1

7-24 白骑士的移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<queue>
#define x first
#define y second
using namespace std;
const int N = 120;
typedef pair<int, int> PII;
int st[N][N], x0, y0, d[N][N];
int nx[8] = {1, 1, 2, 2, -1, -1, -2, -2};
int ny[8] = {2, -2, 1, -1, 2, -2, 1, -1};
char mp[N][N];
void bfs(int xx, int yy){
    queue<PII> q;
    q.push({xx, yy});
    d[xx][yy] = 1;
    while(q.size()){
        PII t = q.front();
        q.pop();
        for(int i = 0; i < 8; i++){
            int x = nx[i]+t.x, y = ny[i]+t.y;
            if(x == x0 && y == y0) {
                cout << d[t.x][t.y] << endl;
                return;
            }
            if(x<1||y<1||x>8||y>8||st[x][y]||d[x][y]) 
                continue;
            d[x][y] = d[t.x][t.y] + 1;
            q.push({x, y});
        }
    }
    cout << "Checkmate" << endl;
}
int main()
{
    int a, b; char ch;
     for(int i = 1; i <= 8; i++)
        cin >> (mp[i] + 1);
    for(int i = 1; i <= 8; i++)
        for(int j = 1; j <= 8; j++)
        {
            ch = mp[i][j];
            if(ch == 'K') a = i, b = j;
            if(ch == 'R'){
                int x = i, y = j; 
                while(x<=8 && mp[x][j]!='B') st[x][j]=1, x++;
                while(y<=8 && mp[i][y]!='B') st[i][y]=1, y++;
                x = i; y = j;
                while(x>=1 && mp[x][j]!='B') st[x][j]=1, x--;
                while(y>=1 && mp[i][y]!='B') st[i][y]=1, y--;
            }
            if(ch == 'B'){
                int x = i, y = j; 
                while(x<=8&&y<=8&&mp[x][y]!='R') st[x][y]=1, x++,y++;
                x = i, y = j;
                while(x>=1&&y>=1&&mp[x][y]!='R') st[x][y]=1, x--,y--;
                x = i; y = j;
                while(x>=1&&y<=8&&mp[x][y]!='R') st[x][y]=1, x--,y++;
                x = i; y = j;
                while(x<=8&&y>=1&&mp[x][y]!='R') st[x][y]=1, x++,y--;
            }
            if(ch == 'Q') x0 = i, y0 = j;
        }
    bfs(a, b);
    return 0;
}

7-25 越大越好：暂无

1

7-26 欢迎来到JIT

1
print("Welcome To Jinling Institute of Technology!")

7-27 余数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n; cin >> n;
    while(n--)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1%y1 == x2%y2) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}

7-28 让yjj讨厌的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
bool judge(int x)
{
    while(x)
    {
        if(x%10==4) return true;
        x /= 10;
    }
    return false;
}
int main()
{
    int q, n;
    cin >> q;
    while(q--)
    {
        cin >> n;
        int res = 0;
        for(int i = 4; i <= n; i++)
            if(judge(i)) res++;
        cout << res << endl;
    }
    return 0;
}

7-29 666666

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s; cin >> s;
    int res = 0;
    for(int i = 0; i < s.size(); i++)
        res += abs(s[i]-'0'-6);
    res += 6 * (6-s.size());
    cout << res << endl;
    return 0;
}

7-30 字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int dp[N][N];
int main()
{
    int n, q;
    string s;
    cin >> n >> q >> s;
    s = " " + s;
    while(q--)
    {
        int x, y, cnt = 0; 
        cin >> x >> y;
        while(x <= n && y <= n && s[x]==s[y])
            x++, y++, cnt++;
        cout << cnt << endl; 
    }
    return 0;
}

7-31 yjj打怪兽

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int f[N];
void solve()
{
    int n, x;
    cin >> n >> x;
    for(int i = 0; i < n; i++)
        cin >> f[i];
    sort(f, f + n, greater<int>());
    if(n == 1 && f[0] < x) cout << -1 << endl;
    else if(n == 1) cout << 1 << endl;
    else
    {
        int cnt = x / (f[0]+f[1]);
        x -= cnt * (f[0] + f[1]);
        if(x == 0) cnt = cnt * 2;
        else if(x > f[0]) cnt = cnt * 2 + 2;
        else cnt = 2 * cnt + 1;
        cout << cnt << endl;
    }
}
int main()
{
    int T; cin >> T;
    while(T--)
        solve();
    return 0;
}

7-32 yjj的棋盘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
using namespace std;
int main()
{
    int T = 2;
    while(T--)
    {
        int n, m, a, b;
        cin >> n >> m >> a >> b;
        if(a+b<n*m||a<n*m/2||b<n*m/2) cout << "no" << endl;
        else 
        {
            int flag = a>b?1:0;
            cout << "yes" << endl;
            for(int i = flag; i < n+flag; i++)
            {
                int t = i%2;
                cout << t;
                for(int j = 1; j < m; j++)
                    cout << " " << (t+j)%2;
                cout << endl;
            }
        }
    }
    return 0;
}

7-33 二次函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a, b, c, l, r;
int f(int x)
{
    int y1 = b*x + c;
    int y2 = max(y1, a*x*x + b*x + c);
    int y3 = max(y2, -a*x*x + b*x + c);
    return y3;
}
signed main()
{
    int T; cin >> T;
    while(T--)
    {
        cin >> a >> b >> c >> l >> r;
        int res = max(f(l), f(r));
        if(a!=0)
        {
            int t1 = -b/(2*a), t2 = ceil(-b*1.0/(2*a));
            if(t1 > l && t1 < r) res = max(res, f(t1));
            if(t2 > l && t2 < r) res = max(res, f(t2));
        }
        cout << res << endl;
    }
}

7-34 遍历图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<vector>
using namespace std;
const int N = 1000010;
vector<int> v[N];
int d[N], st[N];
void dfs(int u, int t)
{
    if(d[u]) return;
    d[u] = t;
    for(int i = 0; i < v[u].size(); i++)
        dfs(v[u][i], t);
}
int main()
{
    int n, m;
    cin >> n >> m;
    while(m--)
    {
        int a, b; cin >> a >> b;
        v[b].push_back(a);
    }
    for(int i = n; i >= 1; i--)
        dfs(i, i);
    cout << d[1];
    for(int i = 2; i <= n; i++)
        cout << " " << d[i];
    return 0;
}

7-35 一尺之棰

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#define int long long
using namespace std;
signed main()
{
    int n;
    while(cin >> n)
    {
        int t = 0;
        while(n) n /= 2, t++;
        cout << t << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
while True:
    try:
        n = int(input())
        cnt = 0
        while n > 0:
            n //= 2
            cnt += 1
        print(cnt)
    except EOFError:
        break

7-36 一道非常有意思的题目

1
print("|       |\n| \     |\n|   \   |\n|     \ |")

7-37 统计数对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
const int N = 200010;
int mp[N], a[N];
int main()
{
    int n, c, res = 0;
    cin >> n >> c;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        mp[a[i]] ++;
    }
    for(int i = 1; i <= n; i++)
        res += mp[a[i]+c];
    cout << res << endl;
    return 0;
}

7-38 幸运数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define int long long 
using namespace std;
void solve()
{
    int a, b, l, r;
    cin >> a >> b >> l >> r;
    l--;
    int g = a * b / __gcd(a, b);
    int c1 = r/a - l/a, c2 = r/b - l/b, c3 = r/g - l/g;
    cout << c1 + c2 - c3 << endl;
}
signed main()
{
    int T; cin >> T;
    while(T--)
        solve();
}

7-39 Year-end prize of the algorithm Club

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N], dis = 0;
vector<int> v[N];
void dfs(int u, int fa, int d)
{
    dis += f[u] * d;
    for(int i = 0; i < v[u].size(); i++)
    {
        int j = v[u][i];
        if(j == fa) continue;
        dfs(j, u, d + 1);
    }
}
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int u1, u2;
        cin >> f[i] >> u1 >> u2;
        if(u1) v[i].push_back(u1), v[u1].push_back(i);
        if(u2) v[i].push_back(u2), v[u2].push_back(i);
    }
    int res = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
    {
        dis = 0;
        dfs(i, -1, 0);
        res = min(res, dis);
    }
    cout << res << endl;
    return 0;
}

7-40 幸运变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N], cnt[N], st[N];
int find(int x){
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x]; 
}
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        p[i] = i, cnt[i] = 1;
    int res = 0;
    while(m--)
    {
        int x, y;
        cin >> x >> y;
        int fa = find(x), fb = find(y);
        if(fa!=fb) 
        {
            if(st[fa]+st[fb]==1) 
            {
                if(st[fa]) res += cnt[fb];
                else res += cnt[fa];
                st[fb] = 1;
            }
            p[fa] = fb;
            cnt[fb] += cnt[fa];
            cnt[fa] = 1;
        }
        else 
        {
            if(!st[fa]) 
            {
                st[fa] = 1;
                res += cnt[fa];
            }
        }
        cout << res << endl;
    }
}

7-41 算法社の年终奖品（hard version）：暂无

1

7-42 高中の排列组合问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, mod = 1e9 + 7;
int f[N];
signed main()
{
    f[2] = 1; 
    for(int i = 3; i < N; i++)
        f[i] = (i - 1) * (f[i-1] + f[i-2]) % mod;
    int T, n; 
    cin >> T;
    while(T--)
    {
        cin >> n;
        cout << f[n] << endl;
    }
}

7-43 龙王lyj: 暂无

1

7-44 找8同：暂无

1

7-45 奖学金评选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
struct node{
    string s;
    int a, b, c;
};
bool cmp(node x, node y){
    int t1 = x.a+x.b+x.c;
    int t2 = y.a+y.b+y.c;
    if(t1 != t2) return t1 > t2;
    if(x.a != y.a) return x.a > y.a;
    if(x.b != y.b) return x.b > y.b;
    if(x.c != y.c) return x.c > y.c;
    return x.s < y.s;
}
vector<node> v[3];
int main()
{
    int n, x, y;
    cin >> n >> x >> y;
    string s;
    int a, b, c;
    while(n--)
    {
        cin >> s >> a >> b >> c;
        if(a < y || b < y || c < y) continue;
        if(a >= x && b >= x && c >= x)
            v[0].push_back({s, a, b, c});
        else if(a < x && b < x && c < x)
            v[2].push_back({s, a, b, c});
        else v[1].push_back({s, a, b, c});
    }
    for(int i = 0; i < 3; i++)
        sort(v[i].begin(), v[i].end(), cmp);
    for(int i = 0; i < 3; i++)
    {
        if(i==0) cout << "One" << endl;
        else if(i == 1) cout << "Two" << endl;
        else cout << "Three" << endl;
        for(int j = 0; j < v[i].size(); j++)
            cout << v[i][j].s << endl;
    }
}

7-46 简单的A+B问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
#include<string.h>
#define N 10010
char A[N], B[N], C[N];
int main(){
    scanf("%s\n%s", A, B);
	int t = 0, a = strlen(A)-1, b = strlen(B)-1, c = 0;
   	while(a >= 0 || b >= 0)
   	{
   		if(a >= 0) t += A[a]-'0', a--;
   		if(b >= 0) t += B[b]-'0', b--;
   		C[c] = t%10; c++;
   		t /= 10;
   	}
   	for(int i = c-1; i >= 0; i--)
   		printf("%d", C[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String a = input.next();
        String b = input.next();
        int lenA = a.length();
        int lenB = b.length();
        char[] arrA = a.toCharArray();
        char[] arrB = b.toCharArray();
        char[] result = new char[10010];
        int sum = 0, idx = 0;
        while(lenA > 0 || lenB > 0){
            if(lenA > 0){
                sum += arrA[lenA-1] - '0';
                lenA--;
            }
            if(lenB > 0){
                sum+= arrB[lenB-1] - '0';
                lenB--;
            }
            result[idx] = (char)(sum % 10 + '0');
            sum =sum / 10;
            idx++;
        }
        for (int i = idx-1; i >= 0; i--) {
            System.out.print(result[i]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
vector<int> add(vector<int> A, vector<int> B){
    int t = 0;
    vector<int> C;
    for(int i = 0; i<A.size()||i<B.size(); i++)
    {
        if(i < A.size()) t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t%10); 
        t /= 10;
    }
    return C;
}
int main()
{
    string a, b;
    vector<int> A, B, C;
    cin >> a >> b;
    for(int i = a.size()-1; i >= 0; i--)
        A.push_back(a[i]-'0');
    for(int i = b.size()-1; i >= 0; i--)
        B.push_back(b[i]-'0');
    C = add(A, B);
    for(int i = C.size()-1; i >= 0; i--)
        cout << C[i];
    return 0;
}
1
2
3
a = int(input())
b = int(input())
print(a + b)

7-47 最好的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
map<int, int> mp;
int main()
{
    int n; cin >> n;
    while(n--)
    {
        int l, r;
        cin >> l >> r;
        mp[l]++;
        mp[r+1]--;
    }
    int res = 0, sum = 0;
    for(auto aa:mp){
        sum += aa.second;
        res = max(sum, res);
    }
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input())
mp = {}
for _ in range(n):
    l, r = map(int, input().split())
    if l in mp:
        mp[l] += 1
    else:
        mp[l] = 1
    if r + 1 in mp:
        mp[r + 1] -= 1
    else:
        mp[r + 1] = -1
res = 0
total = 0
for key in sorted(mp.keys()):
    total += mp[key]
    res = max(res, total)
print(res)

7-48 鼓舞气势

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 10;
int f[N], g[N];
signed main()
{
    int n; cin >> n;
    int res = 0;
    for(int i = 0; i < n; i++)
        cin >> f[i];
    for(int i = 0; i < n; i++)
    {
        int l = f[i], r = f[i]+1e6, cnt = 0;
        for(int j = 0; j < n; j++)
        {
            g[j] = min(f[j], r);
            g[j] = max(g[j], l);
            if(j) cnt += abs(g[j] -g[j-1]);
        }
        res = max(cnt, res);
    }
    cout << res << endl;
}

7-49 粗心的同学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int tr[N];
void insert(int x, int c){
    for(int i = x; i ; i -= i & -i)
        tr[i] += c;
}
int query(int x)
{
    int res = 0;
    for(int i = x; i < N; i += i & -i)
        res += tr[i];
    return res;
}
signed main()
{
    int n; cin >> n;
    for(int i = 0; i < n; i++)
    {
        int a; cin >> a;
        cout << query(a) << " ";
        insert(a, 1);
    }
}

7-50 小李同学的努力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n, res = 0, a, last = 0; 
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a;
        if(a > last) res += a - last;  
        last = a;
    }
    cout << res << endl;
}

7-51 三倍进击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110;
int dp[N][N][N], f[N][N];
signed main()
{
    int n, K;
    cin >> n >> K;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin >> f[i][j];
    // 走到(i, j) 使用了k次乘3操作的 最大值
    memset(dp, -0x3f, sizeof dp);
    dp[1][1][0] = f[1][1]; dp[1][1][1] = 3*f[1][1];
    //dp[0][0][0] = 0;
    int res = -0x3f3f3f3f3f3f3f;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            for(int k = 0; k <= K; k++)
            {
                int& x = dp[i][j][k];
                if(k!=0)x = max(dp[i-1][j][k-1]+f[i][j]*3, dp[i-1][j-1][k-1]+f[i][j]*3);
                x = max({x, dp[i-1][j][k]+f[i][j], dp[i-1][j-1][k]+f[i][j]});
                res = max(res, x);
            }
    cout << res << endl;
}
算法刷题 > school
#算法竞赛
第三、第四、第五、第六届，软件院第一、第二、第三、第四程序设计大赛题目全集
https://leaf-domain.gitee.io/2023/11/21/schoolMatch/
作者
叶域
发布于
2023年11月21日
许可协议