题目链接https://codeforces.com/contest/1487

A- Arena

题目：有n个有等级英雄，和同等级的英雄打会平局，和比自己等级低的打可以使自己等级上升1，两个英雄可以打很多次。称可以达到$100^{500}$的英雄可以成为冠军，问有多少个可能的冠军

思路：比最小值大就可以。

代码：

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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6; 
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;

int a[N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    IOS
    
    int T; cin>>T;
    while(T--)
    {
        int minn = inf;
        int n; cin>>n;
        for(int i = 0; i < n; i++) cin>>a[i], minn = min(a[i], minn);
        int cnt = 0;
        for(int i = 0; i < n; i++) 
        {
            if(a[i] > minn) cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

B- Cat Cycle

题意：A的移动顺序是1 2 3 … n 1 2…；B的移动顺序是n n-1 n-2 … 3 2 1 n n-1 …如果某一时刻B的值与A相等，那么A再移动一次。问在第k小时，A在哪。

思路：枚举找规律可以发现：
n是偶数的时候，B不会对A的移动产生影响，所以答案是k%n

n是奇数的时候，在经过n/2秒之后，A和B猫会在中间相遇，此时A要多走一格。此时某种意义上又和初始状态一样了，只不过间隔着n-2个格子。也就是说每n/2秒，A会多走一格。所以答案是(k+(k-1)/(n/2))%n即可。

代码：

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 <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6; 
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;

int a[N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    IOS
    
    int T; cin>>T;
    while(T--)
    {
        int n, k; cin>>n>>k;
        int ans;
        if(n&1) ans = (k+(k-1)/(n/2))%n;
        else ans = k%n;
        cout<<(ans == 0 ? n:ans)<<endl;
    }
    return 0;
}

C- Minimum Ties

题意：n个队打比赛，每队和其他队各交手一次。赢的队得三分，输的队得0分；平局各得一分。要求最后每队得到的分数一样多且平局得数量尽可能地小。胜局结果为1，负局为结果-1，平局结果为0。最后输出格式为:以n为5为例：1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5队之间的结果。

思路：基本思路为，每个队赢一半输一半，如果多出来一局就平局。
（1）n=5（奇数）
一队：1 1 -1 -1
二队：-1 1 1 -1
三队：-1 -1 1 1
四队：1 -1 -1 1
五队：1 1 -1 -1
(2) n=4（偶数）
一队：1 0 -1
二队：-1 1 0
三队：0 -1 1
四队：1 0 -1
没错，最后按顺序输出一队的结果就是答案。

代码：

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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;

typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios::sync_with_stdio(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6; 
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 3e3 + 100;

int ans[N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T; cin>>T;
    while(T--)
    {
        int n; cin>>n;
        n--;
        if(n&1)
        {
            for(int i = 1; i <= n; i++) 
            {
                if(i <= n/2) ans[i] = 1;
                else if(i == n/2+1) ans[i] = 0;
                else ans[i] = -1;
            }
        }
        else
        {
            for(int i = 1; i <= n; i++)
            {
                if(i <= n/2) ans[i] = 1;
                else ans[i] = -1;
            }
        }
        for(int i = n; i >= 1; i--) 
            for(int j = 1; j <= i; j++)
                cout<<ans[j]<<" ";
        cout<<endl;
    }
    return 0;
}

D- Pythagorean Triples

题意: 求在1<=a<=b<=c<=n的范围内，同时满足$a^{2}+b^{2} = c^{2}$ 和$a^{2}-b=c^{2}$的（a,b,c）有多少组。

思路：用数学推一下，可以得到a, b, c之间的关系。暴力枚举a的取值，满足b,c小于等于n且b,c是整数答案加1。
推导过程如下：
在这里插入图片描述
代码：

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 <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;

typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios::sync_with_stdio(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6; 
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 3e3 + 100;


int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T; cin>>T;
    while(T--)
    {
        int n; cin>>n;
        int cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            if((i*i+1)/2 > n) break;
            if((i*i+1)%2 == 0 && (i*i+1)/2-1 >= 1) cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

E- Cheap Dinner

题意：有$n_{1}$种主食，$n_{2}$种副食，$n_{3}$种饮料，$n_{4}$种甜点，有$m_{1}$，$m_{2}$，$m_{3}$对关系，$m_{1}$的每对关系代表一些主食与副食不能搭配，$m_{2}$代表一些副食与饮料不能搭配，$m_{3}$代表一些饮料和甜点不能搭配。每个食物都有价格，问怎么选才能使得价格最少，并且这4类要有，输出最少的花费。

思路：整体就像暴力模拟，把每一组中各个食物能选的最小花费的搭配存进cost里面，因为是set，所以最优的结果就是第四组中的第一个值（cost[3].begin()->first）。具体看代码吧，有疑惑请留言。
(网络流时间过不了，题解给的是数据结构的写法，看其他博主还用了线段树优化的dp也可以过)

代码:

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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6; 
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 150000 + 10;


int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    IOS
    int a[4];  
    for(int i = 0; i < 4; i++) cin>>a[i];

    int b[4][N];
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < a[i]; j++)
            cin>>b[i][j];

    vector<set<int> > edge[3];
    for(int i = 0; i < 3; i++)
    {
        edge[i] = vector<set<int> >(a[i+1]);
        int x; cin>>x;
        for(int j = 0; j < x; j++)
        {
            int u, v; cin>>u>>v;
            u--; v--;
            edge[i][v].insert(u);
        }
    }
    set<pair<int, int> > cost[4];
    for(int i = 0; i < a[0]; i++) cost[0].insert({b[0][i], i});
    for(int i = 1; i < 4; i++)
    {
        for(int j = 0; j < a[i]; j++)
        {
            auto it = cost[i-1].begin();
            while(it != cost[i-1].end() && edge[i-1][j].count(it->second))
                it++;
            if(it != cost[i-1].end())
                cost[i].insert({it->first+b[i][j], j});
        }
    }
    if(cost[3].size() == 0) cout<<-1<<endl;
    else cout<<cost[3].begin()->first<<endl;
    return 0;
}

F- Ones

( 整理ing)
题意：

思路： dp

代码：