Camp第三天比赛部分题解。
小D面前有n个黑色的气球。
假设第i个黑色气球的高度是一个正整数h**i，现在小D知道了任意两个不同气球的高度之和，你能帮小D还原出每个黑色气球的具体高度嘛？
输入格式
第一行一个整数n
接下来n行，每行n个整数，其中第i行第j个整数表示第i个气球和第j个气球的高度之和。(当i=j时这个数为0)。
2≤n≤1000,输入的每个数不超过105。数据保证答案唯一。
输出格式
一行n个整数，表示答案。
保证答案唯一。
输入样例
1
2
3
4
5
6
| 5
0 3 4 5 6
3 0 5 6 7
4 5 0 7 8
5 6 7 0 9
6 7 8 9 0
|
输出样例
题解：显然，知道三个高度和，可解出这三个的值，因为给出的是三元一次方程组，但需要特判n==2，因为数据保证答案唯一，故当为n==2时，俩气球高度必为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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <ctime>
using namespace std;
typedef long long ll;
const int maxn=100050;
const int maxm=200050;
const int INF=1e9;
int a[1024][1024];
int main(){
int n;
scanf("%d", &n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) {
scanf("%d", &a[i][j]);
}
}
if(n == 2){
printf("%d %d\n", a[1][2]-1,1);
}
else {
int ans = (a[1][3]+a[1][2]-a[2][3])/2;
printf("%d",ans);
for(int i=2;i<=n;i++) printf(" %d", a[1][i]-ans);
}
return 0;
}
|
火山哥手里有一个n个点m条边的无向图。
现在，火山哥请你把无向图的每条边确定一个方向，使之成为一个DAG，并且最小化最长路的长度。
这里一条路径的长度指的是经过边的数量。
输入格式
第一行两个整数n,m，分别表示图的点数和边数。
接下来m行，每行两个正整数u,v，表示一条无向图。
输入数据保证无重边无自环，点编号从1开始。
1≤n≤17,1≤m≤136。
输出格式
一个整数，表示最短的最长路。
输入样例
输出样例
题解：经典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
| #include <cstdio>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5+5;
int n, m;
int d[20];
int dis[20];
int mp[20][20];
int dp[1<<18];
vector<int> a;
ll qpow(ll x, int k){
ll res = 1;
while(k){
if(k&1) res = res * x;
x = x * x;
k >>= 1;
}
return res;
}
bool check(int k){
ll res = 0;
for(auto s:a){
ll tmp = qpow(dp[s], k);
if(n-get_num(s) & 1) res -= tmp;
else res += tmp;
}
return res > 0;
}
int main(){
scanf("%d %d", &n, &m);
for(int i=1;i<=m;i++){
int u, v;
scanf("%d %d", &u, &v);
mp[u-1][v-1] = mp[v-1][u-1] = 1;
}
dp[0] = 0;
for(int i=1;i<(1<<n);i++) {
a.push_back(i);
}
for(auto s : a){
for(int j=0;j<n;j++){
if(s & (1<<j)){
int ss = s-(1<<j);
for(int h=0;h<n;h++)
if(mp[j][h] && (ss & (1<<h)))
ss -= (1<<h);
dp[s] = dp[s-(1<<j)] + dp[ss] + 1;
break;
}
}
}
for(int i=1;i<=n;i++){
if(check(i)){
printf("%d\n", i-1);
break;
}
}
return 0;
}
|