a-b Problem

题目大意

分别给定n个数组，分别表示Alice拿第个石子获得的价值和Bob拿第j个石子获得的价值，Alice和Bob轮流拿，每个石子只能被拿一次。Alice先手。两人的目的都是是自己获得的价值减别人获得的价值最大。问最后Alice获得的价值。

解题思路

考虑贪心。

每个人要让自己获得的价值减别人获得的价值最多，假如Alice拿了，别人就损失了价值可以拿，相当于Alice赢得了的贡献。所以直接按照排序即可。

时间复杂度：

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
bool multi=1;
const int N=1e5+10;
int a[N],b[N];
PII c[N];
int n;
void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        c[i].first=a[i]+b[i];
        c[i].second=i;
    }
    
    sort(c,c+n,greater<PII>());
    int pos=0;
    int k=n;
    bool f=0;
    int res=0;
    while(k--){
        if(f==0){
            res+=a[c[pos++].second];
            f=1;
        }else{
            res-=b[c[pos++].second];
            f=0;
        }
    }
    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

PSO

题目大意

给定一个含有n个结点的菊花图，边长均为1，求任意两点的平均距离和最大距离。

解题思路

画图归纳即可。

两点间长度为2的数量有个，长度为1的数量有个，所有点对有

平均距离即所有长度之和除以点对数量。

当n=2时，最大距离为1，否则为2

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=1;

void solve(){
    int n;
    cin>>n;
    int cntedge=n*(n-1)/2;
    int totlength=(n-1)*(n-2)+n-1;
    cout<<fixed<<setprecision(9)<<(double)totlength/cntedge<<' ';
    cout<<(n==2?1.0:2.0)<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Simple Set Problem

题目大意

给定k个集合，让你在每个集合中选一个数，使得这些数的最大值减这些数的最小值最小。

解题思路

尺取法（双指针法）

先将每个数和它多在的集合编号放在一个整体进行排序，然后从小到大双指针遍历，当现在l到r内包含的集合数量小于k时，r指针往右走直到包含的集合数量为k，这是符合条件，由于遍历的数已经按照非降序排序，这一块区间的最大值减最小值就是r所在位置的数减l所在位置的数，与res取最小，接着左端点有右移每次维护res，直到包含集合数量小于k时向右移动r。

这样l和r分别只会从1移动到n，线性的时间复杂度，且能遍历到所有包含集合数量为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
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
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;

inline int read() { 
	char c = getchar();
	int x = 0, f = 1;
	while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
}
	while (c >= '0' && c <= '9') {
    	x = x * 10 + c - '0';
        c = getchar();
    }
	return x * f;
}

inline void out(int x){
	if(x>9) out(x/10);
	putchar(x%10+'0');
}
bool multi=1;

const int N=1e6+10;
PII v[N];
int cnt[N],cur;

void add(int x){
    if(cnt[x]==0) cur++;
    cnt[x]++;
}

void del(int x){
    cnt[x]--;
    if(cnt[x]==0) cur--;
}

void solve(){
    int n=0;
    int k=read();
    for(int i=1;i<=k;i++){
        int c=read();
        for(int j=0;j<c;j++){
            int x=read();
            v[n++]={x,i};
        }
    }
    memset(cnt,0,(k+1)*sizeof(int));
    sort(v,v+n);
    
    int cnt=0;
    int res=2e9;
    for(int l=0,r=-1;l<n;l++){
        while(r+1<n&&cur<k){
            add(v[r+1].second);
            r++;
        }
        if(cur==k){
            res=min(res,v[r].first-v[l].first);
        }
        del(v[l].second);
    }
    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) TTT=read();
    while(TTT--){
        solve();
    }

    return 0;
}

Kong Ming Qi

题目大意

给定一个的棋盘，棋盘中间的是棋子，每次可以选择一个棋子，跳过一个棋子到一个没有子的地方，中间那个棋子会消失。

解题思路

当只有一行或一列时，即，模拟可得到答案为

当行列可以被三整除时，可以发现当出现L形时，可以消掉L的竖着的三个棋子，最终剩下两个，否则剩下一个。

参考代码

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
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'

bool multi=1;

void solve(){
    int n, m;
    cin >> n >> m;
    if(n > m) swap(n, m);
    if(n == 1){
        cout << (m + 1) / 2 << '\n';
        return;
    }
    if(n % 3 == 0 || m % 3 == 0){
        cout << 2 << '\n';
        return;
    }
    cout << 1 << '\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

Circuit

题目大意

给定一个n个顶点m条边的有向图，保证没有重边和自环，计算最小环的长度和最小环的数量。

解题思路

这里是对于全图而言，n的范围每组又是最多500，且不超过10组。那么可以用的复杂度去做，想到用floyd去做。

这里需要用三个数组，一个记录两点之间的有向边权，一个记录两点之间最短距离，一个记录两点之间的最短距离的走法数量。

floyd算法是基于动态规划实现，每次在1~k-1的子图的基础上加入一个点k，不断更新子图中的点之间的距离。

当i走到j能被k更新时，有i走到k再走到j的总路程小于原来的最短路和等于原来的最短路两种情况。

①如果是小于的情况，那么路径被更新，然后两点间的最短距离的数量应该被重新记录，因为原来的数量是就最短路径而言。

②如果是等于的情况，那么两点间最短路径的数量累加。

子图中每加入一个点k（也就是外层循环），并更新完所有这个子图中的距离后，枚举每个点i与新加进来的k的关系，这里为了避免重复，所以只考虑从编号大的点k连向编号小的点i，如果有边，那么看k到i的距离加上i到k的最短距离是否小于当前答案，如果小于则更新答案，并重新计数；如果等于，则累加数量。

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
#define endl '\n'
const int mod = 998244353;
const int N = 510, INF = 1e18;
bool multi=1;
int n,m;
int w[N][N], cnt[N][N], d[N][N];

void solve(){
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            d[i][j] = (i == j ? 0 : INF);
            w[i][j] = 0;
        }
    }

    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        w[a][b] = d[a][b] = c;
        cnt[a][b] = 1;
    }

    int mn = INF, ans = 0;
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(d[i][j] > d[i][k] + d[k][j]){
                    d[i][j] = d[i][k] + d[k][j];
                    cnt[i][j] = cnt[i][k] * cnt[k][j] % mod;
                }else if(d[i][j] == d[i][k] + d[k][j]){
                    cnt[i][j] = (cnt[i][j] + cnt[i][k] * cnt[k][j]) % mod;
                }
            }
        }
        for(int i = 1; i < k; i++){
            if(w[k][i]){
                if(w[k][i] + d[i][k] < mn){
                    mn = w[k][i] + d[i][k];
                    ans = cnt[i][k];
                }else if(w[k][i] + d[i][k] == mn){
                    ans = (ans + cnt[i][k]) % mod;
                }
            }
        }
    }
    if(mn == INF) mn = ans = -1;
    cout << mn << ' ' << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}