源题目 2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)
</br>
写一篇博客表示自己把题补了.
</br>
A.Altruistic Amphibians
简单DP，每个青蛙的重量总和不会超过 1e8，每一次影响的状态最多只有 1e8复杂度最高只有1e8
dp[j]表示能支撑重量j最大高度是多少。
dp[j-w[i]]=max(dp[j-w[i]],dp[j]);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
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> P;
const long long mod=1e9+7;
const int maxn=1e8+5;
const int INF=0x7fffffff;
const LL inf=0x3f3f3f3f;
const double eps=1e-8;
int a[maxn/10];
struct node {
int l,w,h;
bool operator<(const node & t) {
return w>t.w;
}
} dat[maxn/10];
int dp[maxn*2];
int main() {
int n,d;
scanf("%d%d",&n,&d);
int mx=0;
for(int i=0; i<n; i++) {
scanf("%d%d%d",&dat[i].l,&dat[i].w,&dat[i].h);
mx=max(mx,dat[i].w);
}
sort(dat,dat+n);
int ans=0;
for(int i=0; i<n; i++) {
if(dp[dat[i].w]+dat[i].l>d)ans++;
for(int j=dat[i].w+1; j<min(2*dat[i].w,maxn); j++) {
dp[j-dat[i].w]=max(dp[j-dat[i].w],dp[j]+dat[i].h);
}
}
printf("%d\n",ans);
return 0;
}
B. Baby Bites
水题都不解释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
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
int n;
string s;
int main()
{
FIN;
while(cin>>n)
{
int falg= 1;
for(int i = 1; i<=n; i++)
{
cin>>s;
if(s=="mumble") continue;
else
{
int tmp = stoi(s);
if(tmp!=i)
{
falg = 0;
}
}
}
if(falg){
cout<<"makes sense"<<endl;
}
else{
cout<<"something is fishy"<<endl;
}
}
return 0;
}
C. Code Cleanups
1 |
|
D. Delivery Delays
这题也挺简单的，不过出了不少bug记录一下。
首先预处理出所有点直接的最近距离，然后再预处理出送完第j个回到1点然后一直等到 i 第i个订单的需要的时间，和用户最大等待时间。
然后dp[i]保存送完第 i 个订单回到 1 的最小时间，然后再二分最大等待时间。
最后写二分出了点问题，二分的范围 ，l 初值应该是-1而不是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
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL, int> P;
const long long mod = 1e9 + 7;
const int maxn = 1e3 + 5;
const LL INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
void f() {
freopen("../data.in", "r", stdin);
return;
}
int n, m;
struct edge {
int to, next;
LL w;
} eg[maxn * 10];
int head[maxn], tot;
LL cost[maxn];
void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
void add(int u, int v, LL w) {
eg[tot].to = v;
eg[tot].w = w;
eg[tot].next = head[u];
head[u] = tot++;
}
LL dis[maxn][maxn];
void dij(int u) {
memset(cost, inf, sizeof(cost));
priority_queue<P, vector<P>, greater<P> > q;
cost[u] = 0;
q.push(P(cost[u], u));
while (q.size()) {
int v = q.top().second;
LL w = q.top().first;
q.pop();
if (cost[v] < w)continue;
else {
for (int i = head[v]; i != -1; i = eg[i].next) {
edge &e = eg[i];
if (cost[e.to] > w + e.w) {
cost[e.to] = w + e.w;
q.push(P(cost[e.to], e.to));
}
}
}
}
for (int i = 1; i <= n; i++) {
dis[u][i] = cost[i];
}
}
int q;
LL s[maxn], to[maxn], t[maxn];
LL dp[maxn];
LL k[maxn][maxn];
LL mx[maxn][maxn];
int solve(LL m) {
memset(dp, inf, sizeof(dp));
dp[0] = 0;
for (int i = 1; i <= q; i++) {
for (int j = 0; j < i; j++) {
LL ti = dp[j], flag = 1;
ti = max(ti, t[i]);
if(mx[j][i]+ti>m)flag=0;
ti+=k[j][i];
if (flag == 0)continue;
else {
dp[i] = min(dp[i], ti + dis[to[i]][1]);
}
}
}
for(int i=1;i<=q;i++){
if(dp[i]==dp[maxn-1])return 0;
}
return 1;
}
int main() {
f();
scanf("%d%d", &n, &m);
init();
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
for (int i = 1; i <= n; i++) {
dij(i);
}
scanf("%d", &q);
to[0] = 1;
for (int i = 1; i <= q; i++) {
scanf("%lld%lld%lld", &s[i], &to[i], &t[i]);
}
for (int i = 1; i <= q; i++) {
for (int j = 0; j < i; j++) {
LL ti,m=-inf;
ti=0;
int pos = j + 1, lat = 1;
while (pos <= i) {
ti += dis[lat][to[pos]];
if (ti - s[pos] > m ) {
m=ti - s[pos];
}
lat = to[pos];
pos++;
}
k[j][i]=ti;
mx[j][i]=m;
}
}
LL l = -1, r =inf;
while (r > l + 1) {
if (solve(mid))r = mid;
else l = mid;
}
printf("%lld\n", r);
return 0;
}
E. Explosion Exploit
这题竟然没想到用 类似状压DP了，还一直想怎么十维数组了，唉。
直接用一个long long 整数，前5位保存自己小兵的值，后5位保存对面小兵的值。后来发现这样写复杂度过不去。就算是记忆化搜索还是错的。应该用6位来保存还剩多少点血的小兵的个数。因为 前面一种搜索，31300和 13300不是同一种状态，除非排一下序。而后面这一种保存方式，全部都是102。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
113
114
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> P;
const long long mod=1e9+7;
const int INF=0x7fffffff;
const LL inf=0x3f3f3f3f;
const double eps=1e-8;
map<LL,double>mp;
int n,m,k;
double dfs(LL a,int u) {
if(mp.count(a)) {
return mp[a];
}
LL b=a;
LL ans=0,a1=0,a2=0;
for(int i=0; i<12; i++) {
if(i>=6) {
if(b%10!=0)a2+=b%10;
b/=10;
continue;
}
ans+=(b%10)*(6-i);
if(b%10!=0)a1+=b%10;
b/=10;
}
// debug(ans<<"a="<<a2);
if(ans==0) {
mp[a]=1;
return 1;
}
if(ans>u) {
mp[a]=0;
return 0;
}
double tp=0;
if(a2==0) {
mp[a]=1;
return 1;
} else {
LL tk=1;
b=a;
for(int i=0; i<12; i++) {
if(b%10!=0) {
if(i==11||i==5){
tp+=dfs(a-tk,u-1)*(b%10)*1.0/(a1+a2);
}
else if(i<6){
tp+=dfs(a-tk+tk*10,u-1)*(b%10)*1.0/(a1+a2);
}
else tp+=dfs(a-tk+tk*10,u-1)*(b%10)*1.0/(a1+a2);
}
b/=10;
tk*=10;
}
}
mp[a]=tp;
return tp;
}
LL a;
int b[2][10];
int main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=0 ; i<n; i++) {
int p;
scanf("%d",&p);
b[0][p]++;
}
for(int i=0; i<m; i++) {
int p;
scanf("%d",&p);
b[1][p]++;
}
for(int i=1; i<=6; i++) {
a=a*10+b[0][i];
}
for(int i=1; i<=6; i++) {
a=a*10+b[1][i];
}
printf("%.10f\n",dfs(a,k));
return 0;
}
/*
2 2 3
1 1
1 2
*/
F * G 这两题有点难，没写出来。。。
空着。。
H. House Lawn
队友写的。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
using namespace std;
typedef long long LL;
typedef long double lb;
typedef pair<int, int> P;
const LL mod = 1e9+7;
const int inf=0x3f3f3f3f;
const int INF=0x7fffffff;
const double eps = 1e-7;
const double pi = acos(-1);
const int maxn=1e6+5;
int n, sum;
string s, name[106];
int stak[106], top = 0;
int minp;
struct node {
int id;
LL p, c, t, r;
} lawn[107];
LL solve(LL tm, LL tp, LL c, LL t, LL r) {
return (c*t*(tp/(t+r)))/sum;
}
int main() {
//scanf("%d%d", &sum, &n);
cin >> sum >> n;
int ans = inf;
int p, c, t, r;
minp = INF;
getchar();
for(int i = 1, len; i <= n; ++i) {
getline(cin, s);
len = s.length();
int tmp = 0;
for(; s[tmp] != ',';++tmp) ;
name[i] = s.substr(0, tmp);
//cout << name[i] << endl;
p = c = t = r = 0;
for(++tmp; s[tmp] != ',';++tmp) p = p*10+s[tmp]-'0';
for(++tmp; s[tmp] != ',';++tmp) c = c*10+s[tmp]-'0';
for(++tmp; s[tmp] != ',';++tmp) t = t*10+s[tmp]-'0';
for(++tmp; tmp < len;++tmp) r = r*10+s[tmp]-'0';
//cout << p <<" "<< c <<" "<< t <<" "<< r << endl;
//cin >> p >> c >> t >> r;
//scanf("%d%d%d%d", &p, &c, &t, &r);
lawn[i].id = i;
lawn[i].p = p;
lawn[i].c = c;
lawn[i].t = t;
lawn[i].r = r;
}
for(int i = 1; i <= n; ++i) {
LL tp = 10080LL * (lawn[i].t+lawn[i].r) / __gcd(10080LL , 1LL*(lawn[i].t+lawn[i].r));
LL T = tp / 10080;
LL tot = sum * T;
LL tt = solve(tot, tp, lawn[i].c, lawn[i].t, lawn[i].r);
//printf("i: %d, T: %lld, tp: %lld, tt: %lld\n", i, T, tp, tt);
if(tt >= T) {
//printf("OK\n");
if(minp > lawn[i].p) {
minp = lawn[i].p;
top = 1;
stak[top] = lawn[i].id;
} else if(minp == lawn[i].p) {
top ++;
stak[top] = lawn[i].id;
}
}
}
for(int i = 1; i <= top; ++i) {
cout << name[stak[i]] << "\n";
}
if(top == 0) cout << "no such mower\n";
//printf("%d\n", ans);
return 0;
}
/*
7000 4
9999 10 120 120
999 1 120 240
5499 2 25 35
5499 3 25 35
10000 3
aaa,1,1,1,1
bbb,1,10000,10080,1
ccc,1,10000,10079,1
*/
I. Intergalactic Bidding
大数，排序,没了。。
因为保证 一个值等于另一个值的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
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
using namespace std;
typedef long long LL;
typedef long double lb;
typedef pair<int, int> P;
const LL mod = 1e9+7;
const int inf=0x3f3f3f3f;
const int INF=0x7fffffff;
const double eps = 1e-7;
const double pi = acos(-1);
const int maxn=1e6+5;
const int MAXL = 6e3+5;
const int MAXN = 9999;
const int DLEN = 4 ;
class big {
public:
int a[MAXN],len;
big (const char *s) {
int t,k,index=0,L=strlen(s);
memset(a,0,sizeof(a));
len=L/DLEN;
if(L%DLEN)
len++;
for(int i = L-1; i>=0; i-=DLEN) {
t=0;
k=i-DLEN + 1;
if(k<0)
k=0;
for(int j = k; j <=i ; j++)
t=t*10+s[j]-'0';
a[index++]=t;
}
}
bool operator<(const big &t) const {
int ln;
if(len>t.len)
return false;
else if(len==t.len) {
ln=len-1;
while(a[ln]==t.a[ln]&&ln>=0)
ln--;
if(ln>=0&&a[ln]>t.a[ln])
return false;
else
return true;
} else
return true;
}
big operator-(const big &T)const {
bool flag;
big t1=*this,t2=T;
flag=0;
int b=t1.len;
for(int i=0,j; i<b; i++) {
if(t1.a[i]<t2.a[i]) {
if(j=i+1);
while(t1.a[j]==0)
j++;
t1.a[j--]--;
while(j>i)
t1.a[j--]+=MAXN;
t1.a[i]+=MAXN+1-t2.a[i];
} else
t1.a[i]-=t2.a[i];
}
t1.len=b;
while(t1.a[t1.len-1]==0&&t1.len>1)
t1.len--,b--;
return t1;
}
void print() {
printf("%d",a[len-1]);
for(int i=len-2; i>=0; i--) {
printf("%04d",a[i]);
}
}
};
typedef pair<big,string> PS;
vector<PS> v;
int main() {
int n;
char s[1005];
scanf("%d%s",&n,s);
big mx(s);
// debug((mx<big("0")&&big("0")<mx));
// mx.print();
char nam[100];
for(int i=0; i<n; i++) {
scanf("%s%s",nam,s);
v.push_back(PS(s,nam));
}
sort(v.begin(),v.end());
int l=v.size();
vector<string> ans;
while(l-->0) {
big b=v[l].first;
if(b<mx) {
ans.pb(v[l].se);
mx=mx-b;
}
}
big temp("0");
if(!(temp<mx&&mx<temp)) {
printf("0\n");
return 0;
}
printf("%d\n",ans.size());
for(auto i:ans) {
cout<<i<<"\n";
}
return 0;
}
J. Jumbled String
首先更具a,d算出有多少个0 和 1 特判一下只有一个1的情况。更具这个可以判断出 01 10 这两种字符串就是 0 在1前面和1在0前面又多少个，还可以发现0在1前面和1在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
using namespace std;
typedef long long LL;
typedef long double lb;
typedef pair<int, int> P;
const LL mod = 1e9+7;
const int inf=0x3f3f3f3f;
const int INF=0x7fffffff;
const double eps = 1e-7;
const double pi = acos(-1);
const int maxn=1e6+5;
LL a,b,c,d;
LL zn=-1,on=-1;
int main() {
while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d)) {
for(LL i=0; i<1e5; i++) {
if(i*(i-1)>2*a) {
break;
} else if(i*(i-1)==2*a) {
zn=i;
}
}
for(LL i=0; i<1e5; i++) {
if(i*(i-1)>2*d) {
break;
} else if(i*(i-1)==2*d) {
on=i;
}
}
if(a==0) {
if(b!=0||c!=0) {
zn=1;
} else
zn=0;
}
if(d==0) {
if(b!=0||c!=0) {
on=1;
} else
on=0;
}
// debug(zn);
// debug(on);
if(((b+c)!=on*zn)||zn==-1||on==-1) {
puts("impossible");
} else {
LL k=(on==0)?0:((on*zn)-b)/on,num=(on==0)?0:((on*zn)-b)%on;
// debug(k);
// debug(num);
for(int i=0; i<zn+on; i++) {
if(i<zn-k-1) {
printf("0");
} else if(i>zn+on-k-1) {
printf("0");
} else if(i==zn-k+num-1) {
printf("0");
} else
printf("1");
}
puts("");
}
}
return 0;
}
K. King’s Colors
队友写的。。。不过这题就是一个容斥，是一颗树，所以能够保证一个节点的染色只合一个节点有关。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
using namespace std;
typedef long long LL;
typedef long double lb;
typedef pair<int, int> P;
const LL mod = 1e9+7;
const int inf=0x3f3f3f3f;
const int INF=0x7fffffff;
const double eps = 1e-7;
const double pi = acos(-1);
const int maxn=1e6+5;
char s[10];
int rint(char* t) {
int l=strlen(t);
if(t[0]<'0'||t[0]>'9') {
return -1;
}
else {
int i=0,ans=0;
while(i<l){
ans=ans*10+t[i]-'0';
i++;
}
return ans;
}
}
//int a[maxn];
LL ksm(LL a, int b) {
LL res = 1;
for(;b;b>>=1,a=a*a%mod) {
if(b&1) res = res*a%mod;
}
return res;
}
LL C[3005][3005];
int main() {
C[1][1] = 1;
for(int i = 2; i < 3000; ++i) {
for(int j = 1; j <= i; ++j) {
C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
}
}
LL n, k;
scanf("%lld%lld",&n, &k);
for(int i = 1, x; i < n; ++i) {
scanf("%d", &x);
}
LL ans = 0, tmp;
for(LL i = k, j = 0; i >= 2; --i, j = !j) {
tmp = C[k+1][i+1] * i % mod * ksm(i-1, n-1) % mod;
if(j == 0) ans = (ans+tmp)%mod;
else ans = (ans - tmp)%mod;
}
printf("%lld\n", (ans+mod)%mod);
return 0;
}