Kyooma's Blog

2022-10-14周赛

  • ~10.53K 字

题目来自: 2015 ACM-ICPC Asia EC-Final Contest

A - Boxes and Balls

签到, 不过要注意精度

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(int T){
    ll n, m;
    scanf("%lld", &n);
    n *= 2;
    m = (ll)sqrtl(n);
    ll ans;
    if(m * (m + 1) <= n){
        ans = (m + 1) * m / 2;
    }else{
        ans = (m - 1) * m / 2;
    }
    printf("Case #%d: %lld\n", T, ans);
}

int main() {
    int T=1;
    cin >> T;
    for(int i = 1; i <= T; i++) {
        solve(i);
    }
}

M - November 11th

签到, 有$n$行座位, 要求每个人的左右都没有人坐, 而且给了$k$个位置不能坐人, 问最多和最少能坐几个人

SOLUTION

对一段连续的来讲,

最多就是 $\lceil \frac{n}{2} \rceil$ , 最少就是 $\lceil \frac{n}{3} \rceil$

CODE
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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10, Log = 20, inf = 0x3f3f3f3f;

vector<int> e[N];

void solve() {
    int r, s, b;
    scanf("%d%d%d", &r, &s, &b);
    int mn = 0, mx = 0;
    for(int i = 0, x, y; i < b; i++){
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
    }
    for(int i = 0; i < r; i++){
        e[i].push_back(s);
        sort(e[i].begin(), e[i].end());
        int pre = 0;
        for(int j : e[i]){
            int len = j - pre;
            mn += (len + 2) / 3;
            mx += (len + 1) / 2;
            pre = j + 1;
        }
        e[i].clear();
    }
    printf("%d %d\n", mx, mn);
}

int main() {
    int T = 1;
    scanf("%d", &T);
    for(int i = 1; i <= T; i++){
        printf("Case #%d: ", i);
        solve();
    }
    return 0;
}

D - Change

你有价值$A$的整钱, 现在需要凑出价值为$B$的钱, 可以多次使用一个自动售货机, 每次使用消耗任意数量的钱$x$, 但是找零的钱是随机的(只保证总和相等), 问最少花多少钱能刚好凑出$B$

SOLUTION

You have as much time as you want to use the vending machine.

原来这句话的意思是可以使用多次售货机

感觉是整场比赛最烂的题, 一开始看成了只用一次, 写了个背包但是怎么都过不了, 后来过了几个小时才发现是可以多次使用, 于是和2取了个min

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N=1e3+10;
const int INF=2e9;

map<string, int> mp;

void init(){
    mp["0.01"] = 1;
    mp["0.02"] = 2;
    mp["0.05"] = 5;
    mp["0.1"] = 10;
    mp["0.2"] = 20;
    mp["0.5"] = 50;
    mp["1"] = 100;
    mp["2"] = 200;
    mp["5"] = 500;
    mp["10"] = 1000;
    mp["20"] = 2000;
    mp["50"] = 5000;
    mp["100"] = 10000;
}

int v[10010];

void solve(){
    int n,i,j,m,x,y,k,l,r;
    string a, b;
    cin >> a >> b;
    int A = mp[a], B = mp[b];
    v[0] = v[A] = 1;
    for(auto i : mp){
        if(i.second > B && i.second < A){
            for(j = 0; j <= A - i.second; j++){
                if(v[j]) v[j + i.second] = 1;
            }
        }
    }
    int ans = A - B;
    for(i = A; i >= 0; i--){
        if(!v[i]){
            int ok = 1;
            for(j = i - 1; j > i - B; j--){
                if(v[j]) ok = 0;
            }
            if(ok){
                ans = A - i;
                break;
            }
        }
    }
    ans = min(ans, 2);
    int d1 = ans % 100;
    ans /= 100;
    printf("%d.%.02d\n", ans, d1);
    for(int i = 0; i <= A; i++) v[i] = 0;
}

int main() {
    int T=1;
    cin>>T;
    init();
    for(int i=1;i<=T;i++) {
        printf("Case #%d: ", i);
        solve();
    }
}

L - Multiplication Table

咕

SOLUTION

咕

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N=1e3+10;
const int INF=2e9;
int a[N][N];
vector<int>v;
int check(int x,int y){
//    printf("%d %d\n",x,y);
    int l,r;
    for(auto i:v){
        l=i/2000;
        r=i%2000;
        if(1ll*(x+l)*(y+r)!=a[l][r]) return 0;
    }
    return 1;
}
void solve(){
    int n,i,j,m,x,y,k,l,r;
    cin>>n>>m;
    v.clear();
    l=1,r=1;
    int cnt=0;
    x=0;
    while(cnt<n*m){
        char c=getchar();
        if(c=='?') cnt++,x=0,r++;
        else if(c>='0'&&c<='9') x=x*10+c-'0';
        else if(x>0) a[l][r]=x,v.push_back(l*2000+r),x=0,cnt++,r++;
        if(r==m+1) r=1,l++;
    }
    if(v.size()==0){
        puts("Yes");
        return;
    }
    int x1,x2,y1,y2;
    if(v.size()==1){
        x1=v[0]/2000;
        y1=v[0]%2000;
        l=a[x1][y1];
        for(i=1;i*i<=l;i++){
            if(l%i) continue;
            x=i,y=l/i;
            if(x>=x1&&y>=y1){
                puts("Yes");
                return;
            }
            x=l/i,y=i;
            if(x>=x1&&y>=y1){
                puts("Yes");
                return;
            }
        }
        puts("No");
        return;
    }
    x1=v[0]/2000;
    y1=v[0]%2000;
    x2=v[1]/2000;
    y2=v[1]%2000;
    l=a[x1][y1];
    r=a[x2][y2];
    //printf("%d %d\n",l,r);
    for(i=1;i*i<=l;i++){
        if(l%i) continue;
        x=i,y=l/i;
        x-=x1,y-=y1;
        if(1ll*(x+x2)*(y+y2)==r){
            if(x<0||y<0);
            else if(check(x,y)){
                puts("Yes");
                return;
            }
        }
        x=l/i,y=i;
        x-=x1,y-=y1;
        if(1ll*(x+x2)*(y+y2)==r){
            if(x<0||y<0);
            else if(check(x,y)){
                puts("Yes");
                return;
            }
        }
    }
    puts("No");
}

int main() {
    int T=1;
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    cin>>T;
    //init();
    for(int i=1;i<=T;i++) {
        printf("Case #%d: ", i);
        solve();
    }
}

B - Business Cycle

咕

SOLUTION

咕

CODE
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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N = 2e5 + 10;
const int INF = 2e9;

ll a[N];

void solve() {
    ll n, i, k, m;
    __int128 mx, x, y, ans;
    cin >> n >> m >> k;
    ans = m;
    for (i = 1; i <= n; i++) scanf("%lld", a + i), a[i + n] = a[i];
    x = 0;
    n *= 2;
    for (i = 1; i <= min(n, k); i++) {
        x += a[i];
        ans = min(ans, m - x);
    }
    x = 0;
    mx = 0;
    for (i = 1; i <= min(n, k); i++) {
        x += a[i];
        if (x < 0) x = 0;
        mx = max(mx, x);
    }
    if (mx >= m) ans = 0;
    n /= 2;
    __int128 s = 0;
    for (int j = 1; j <= n; ++j) {
        s += a[j];
    }
    if (k / n >= 1) {
        mx = s * (k / n - 1);
        __int128 sum = 0;
        for (int j = 1; j <= n + k % n; ++j) {
            sum += a[j];
            mx = max(mx, s * (k / n - 1) + sum);
        }
        ans = min(ans, m - mx);
    }
    if (k / n >= 2) {
        __int128 mxx = 0;
        __int128 suf = 0;
        for (int j = n; j >= 1; --j) {
            suf += a[j];
            mxx = max(mxx, suf);
        }
        __int128 mxxx = 0;
        __int128 pre = 0;
        for (int j = 1; j <= n + k % n; ++j) {
            pre += a[j];
            mxxx = max(mxxx, pre);
        }
        if ((k / n - 2) * s + mxx + mxxx >= m) ans = 0;
    }
    ll ANS = max((__int128) 0, ans);
    printf("%lld\n", ANS);
}

int main() {
    int T = 1;
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    cin >> T;
    //init();
    for (int i = 1; i <= T; i++) {
        printf("Case #%d: ", i);
        solve();
    }
}

F - Hungry Game of Ants

咕

SOLUTION

咕

CODE
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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N=1e6+10;
const int INF=2e9;
ll dp[N],c[N];
ll p=1e9+7;
ll po(ll x,ll y){
    ll b=1;
    while(y){
        if(y&1) b=b*x%p;
        y>>=1;
        x=x*x%p;
    }
    return b;
}
void init(){
    ll i,I=po(2,p-2);
    c[0]=1;
    for(i=1;i<=1e6;i++) c[i]=c[i-1]*I%p;
}
void solve(){
    ll n,i,k,m,sum;
    cin>>n>>k;
    queue<pll>q;
    int f=1;
    sum=1;
    ll tot=0;
    for(i=n;i;i--){
        while(tot>i*(i+1)/2){
            sum=(sum-q.front().first*c[q.size()-f]%p+p)%p;
            tot-=q.front().second;
            q.pop();
            f=0;
        }
        dp[i]=sum;
        q.push({sum,i});
        tot+=i;
    }
    ll ans=1;
    dp[1]=0;
    ll l,r;
    l=0,r=1;
    m=1;
    //for(i=1;i<=n;i++) printf("%lld\n",dp[i]);
    for(i=2;i<n;i++){
        r+=i;
        while(r-m>l+m){
            r-=m;
            l+=m;
            m++;
        }
        dp[i]=dp[i]*c[i-m+1]%p;
        ans=(ans-dp[i]+p)%p;
    }
    dp[n]=ans;
    printf("%lld\n",dp[k]*po(2,n)%p);
}

int main() {
    int T=1;
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    cin>>T;
    init();
    for(int i=1;i<=T;i++) {
        printf("Case #%d: ", i);
        solve();
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可