2019 ACM-ICPC 西安邀请赛 A C D L M (/签到题 题解)

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 fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
const int maxn = 1e5 + 5 ;
int a[maxn];
signed main() {
fastio;
int n, m;
cin >> n >> m;
for(int i = 1 ; i <= n; i++) {
cin >> a[i];
}
int res = 0;
int ans = 0;
sort(a + 1, a + 1 + n);
for(int i = 1; i <=n; i++) {
if(res + a[i] <= m)
res += a[i], ans++;
else
break;
}
cout << ans << 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
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
const int maxn = 1e5 + 5 ;
const double pi = acos(-1.0);
double rdis(double x, double y, double a, double b) {
return sqrt((x - a) * (x - a) + (y - b) * (y - b));
}
signed main() {
//
fastio;
int T;
cin >> T;
while(T--) {
double rx, ry, r, x, y;
cin >> rx >> ry >> r >> x >> y;
if(x < rx - r || x > rx + r) {
if(x < rx - r) {
double ans = rdis(rx - r, ry, x, y);
ans += pi / 2 * r;
printf("%.4lfn", ans);
} else {
double ans = rdis(rx + r, ry, x, y);
ans += pi / 2 * r;
printf("%.4lfn", ans);
}
} else {
double d = rdis(x, y, rx, ry);
double qd = sqrt(d * d - r * r);
double a1 = atan(abs(x-rx) / abs(ry-y));
double a2 = atan(qd / r);
double j = pi / 2 - a1 - a2;
double xl = j * r;
//
cout<<qd<<"
"<<a1<<"
"<<a2<<"
"<<j<<"
"<<xl<<endl;
double ans = xl;
ans += qd;
ans += pi / 2 * r;
printf("%.4lfn", ans);
}
}
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
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
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
const int maxn = 1e6 + 5 ;
const double pi = acos(-1.0);
int n, m;
int dp[maxn];
int a[maxn];
int head[3005], cnt;
int nxt[10000], to[10000];
struct node {
int v, w;
} wu[205];
void ade(int a, int b) {
to[++cnt] = b;
nxt[cnt] = head[a];
head[a] = cnt;
}
int s1,s2;
int vis[maxn];
void dfs(int x) {
if(vis[x]==1) {
if(s1==-1) s1=0;
s1+=a[x];
} else {
if(s2==-1) s2=0;
s2+=a[x];
}
for(int i = head[x]; i; i = nxt[i]) {
if(vis[to[i]]) continue;
vis[to[i]] = (vis[x] == 1 ? 2 : 1);
dfs(to[i]);
}
}
signed main() {
//	fastio;
int T;
cin >> T;
while(T--) {
int sum=0;
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
cnt=0;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
a[i]/=50;
sum+=a[i];
}
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
ade(u,v),ade(v,u);
}
int wus=0;
for(int i=1; i<=n; i++) {
if(vis[i]) continue;
vis[i]=1;
s1=-1,s2=-1;
dfs(i);
wu[++wus]=node {s1,s2};
}
for(int i=1; i<=wus; i++) {
for(int j=sum/2; j>=0; j--) {
if(wu[i].w!=-1) {
if(j>=wu[i].w&&j>=wu[i].v) {
dp[j]=max(dp[j-wu[i].v]+wu[i].v,dp[j-wu[i].w]+wu[i].w);
} else if(j>=wu[i].w) {
dp[j]=dp[j-wu[i].w]+wu[i].w;
} else if(j>=wu[i].v) {
dp[j]=dp[j-wu[i].v]+wu[i].v;
}
} else {
if(j>=wu[i].v)
dp[j]=max(dp[j],dp[j-wu[i].v]+wu[i].v);
}
}
}
cout<<(sum-dp[sum/2])*50<<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
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
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
#define int long long
const int maxn = 1e5 + 5 ;
set<string> S;
string s;
int len;
void dfs(int d) {
if(d) {
if(len % 2 == 0) {
for(int i = 0; i < len / 2; i++) {
swap(s[i], s[i + len / 2 ]);
}
//
cout << s << endl;
if(S.find(s) != S.end())
return ;
S.insert(s);
dfs(!d);
}
else{
for(int i = 0; i < len / 2; i++) {
swap(s[i], s[i + len / 2 +1]);
}
//
cout << s << endl;
if(S.find(s) != S.end())
return ;
S.insert(s);
dfs(!d);
}
} else {
for(int i = 0; i < len - 1; i += 2) {
swap(s[i], s[i + 1]);
}
// cout << s << endl;
if(S.find(s) != S.end())
return ;
S.insert(s);
dfs(!d);
}
}
signed main() {
fastio;
int n=3;
// while(n<20){
cin>>n;
if(n==1) cout<<1<<endl;
else if(n==2) cout<<2<<endl;
else{
s="";
for(int i = 1; i <= n; i++)
s.push_back(i + 'a');
//
cout << s << endl;
len = n;
dfs(0);
//
cout<<n<<"
" << S.size()<<endl;
cout<<S.size()<<endl;
n++;
S.clear();
}
// }
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
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
struct node {
int to,dis;
};
bool vis[maxn];
vector<node>v[maxn];
int n,m,c,d,e;
bool check(int x) {
queue<pair<int,int> > que;
que.push(make_pair(1,x*e));
while(!que.empty()){
pair<int,int> p=que.front();
que.pop();
if(p.first==n) return 1;
if(vis[p.first]) continue ;
vis[p.first]=1;
for(int i=0;i<v[p.first].size();i++){
if(p.second>=1&&v[p.first][i].dis<=x*d){
que.push(make_pair(v[p.first][i].to,p.second-1));
}
}
}
return 0;
}
signed main() {
cin>>n>>m>>c>>d>>e;
memset(vis,0,sizeof(vis));
for(int i=0; i<m; i++) {
int x,y,z;
cin>>x>>y>>z;
v[x].push_back(node {y,z});
v[y].push_back(node {x,z});
}
int l=0,r=1e5,mid;
while(r-l>1) {
memset(vis,0,sizeof(vis));
mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
cout<<r*c<<endl;
return 0;
}