2019 Multi-University Training Contest 7
2019-08-13 / Luo Jinrong   

进度

A B C D E F G H I J K
√ ∅ √

1001. A + B = C

题意

给定a，b，c，求x，y，z使得满足$a*10^x+b*10^y=c*10^z$且$0\leq x,y,z\leq 10^6$。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)

const int MAXN(1e6);
int T;
string a, b, c, tmpa, tmpb, tmpc;
ll znum[3];
int len1, len2, len3;

inline void Reduce(string &c, string &a, int& lenc, int& lena) {
    int pa=lena-1, pc=lenc-1;
    int flag=0;
    string ptr;
    while(pa>=0 && pc>=0) {
        flag = c[pc--]-'0'-(a[pa--]-'0')-flag;
        if(flag<0) {
            flag+=10;
            ptr+=flag+'0';
            flag = 1;
        } else {
            ptr+=flag+'0';
            flag = 0;
        }
    }
    while(pc>=0) {
        flag = c[pc--] - '0' - flag;
        if(flag<0) {
            flag+=10;
            ptr+=flag+'0';
            flag = 1;
        } else {
            ptr+=flag+'0';
            flag = 0;
        }
    }
    lenc = ptr.length();
    rep(i, 0, lenc) {if(ptr[i]!='0'){lenc=i+1;ptr=ptr.substr(0,lenc);break;}}
    c=string();
    per(i, 0, lenc) { c+=ptr[lenc-1-i]; }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--) {
        cin >> a >> b >> c;
        fill(znum, znum+3, 0);
        len1=a.length(); len2=b.length(); len3=c.length();
        rep(i, 0, len1) {if(a[i]=='0'){znum[0]++;} else {break;}}
        rep(i, 0, len2) {if(b[i]=='0'){znum[1]++;} else {break;}}
        rep(i, 0, len3) {if(c[i]=='0'){znum[2]++;} else {break;}}
        len1-=znum[0]; len2-=znum[1]; len3-=znum[2];
        a=a.substr(0,len1); b=b.substr(0,len2); c=c.substr(0,len3);
        //c-a
        {
            tmpa = a; tmpb = b; tmpc = c;
            int tmpl1=len1, tmpl2=len2, tmpl3=len3;
            int tmpznm[3];
            tmpznm[0]=znum[0]; tmpznm[1]=znum[1]; tmpznm[2]=znum[2];
            if (tmpl1 > tmpl3) {
                tmpc += string(tmpl1 - tmpl3, '0');
                tmpznm[2] -= (tmpl1-tmpl3);
                tmpl3=tmpl1;
            }
            if(tmpl1==tmpl3) {
                per(i, 0, tmpl1) {
                    if(tmpa[i]>tmpc[i]) {
                        tmpc+='0';
                        tmpl3++;
                        tmpznm[2]--;
                        break;
                    } else if(tmpa[i]<tmpc[i]) {
                        break;
                    }
                }
            }
            Reduce(tmpc, tmpa, tmpl3, tmpl1);
            rep(i, 0, tmpl3) {if(tmpc[i]=='0'){tmpznm[2]++;tmpznm[0]++;} else {tmpc=tmpc.substr(0, i+1);break;}}
            if(tmpc==tmpb) {
                int anso=max(tmpznm[0], tmpznm[1]);
                anso = max(anso, tmpznm[2]);
                tmpznm[0] = anso-tmpznm[0];
                tmpznm[1] = anso-tmpznm[1];
                tmpznm[2] = anso-tmpznm[2];
                if(tmpznm[0]<=MAXN && tmpznm[1]<=MAXN && tmpznm[2]<=MAXN) {
                    cout << tmpznm[0] << ' ' << tmpznm[1] << ' ' << tmpznm[2] << '\n';
                    continue;
                }
            }
        }
        //c-b
        {
            tmpa = b; tmpb = a; tmpc = c;
            int tmpl1=len2, tmpl2=len1, tmpl3=len3;
            int tmpznm[3];
            tmpznm[0]=znum[1]; tmpznm[1]=znum[0]; tmpznm[2]=znum[2];
            if (tmpl1 > tmpl3) {
                tmpc += string(tmpl1 - tmpl3, '0');
                tmpznm[2] -= (tmpl1-tmpl3);
                tmpl3=tmpl1;
            }
            if(tmpl1==tmpl3) {
                per(i, 0, tmpl1) {
                    if(tmpa[i]>tmpc[i]) {
                        tmpc+='0';
                        tmpl3++;
                        tmpznm[2]--;
                        break;
                    } else if(tmpa[i]<tmpc[i]) {
                        break;
                    }
                }
            }
            Reduce(tmpc, tmpa, tmpl3, tmpl1);
            rep(i, 0, tmpl3) {if(tmpc[i]=='0'){tmpznm[2]++;tmpznm[0]++;} else {tmpc=tmpc.substr(0, i+1);break;}}
            if(tmpc==tmpb) {
                int anso=max(tmpznm[0], tmpznm[1]);
                anso = max(anso, tmpznm[2]);
                tmpznm[0] = anso-tmpznm[0];
                tmpznm[1] = anso-tmpznm[1];
                tmpznm[2] = anso-tmpznm[2];
                if(tmpznm[0]<=MAXN && tmpznm[1]<=MAXN && tmpznm[2]<=MAXN) {
                    cout << tmpznm[1] << ' ' << tmpznm[0] << ' ' << tmpznm[2] << '\n';
                    continue;
                }
            }
        }
        cout << "-1\n";
    }

    return 0;
}

1011. Kejin Player

题意

一个氪金系统，可以从$1$级升到$n+1$级，升级规则：从$i$级升到$i+1$级需要花费$a_i$，成功率为$p_i$（通过$r_i/s_i$得到），升级失败会降级到$x_i$（$x_i\leq i$）。有$q$个询问，每次询问求从$l$级升到$r$级的花费期望。

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
#pragma warning(disable:4996)
#include<bits/stdc++.h>
#define upf(a,b,c) for(ll a=b;a<=c;++a)
#define drf(a,b,c) for(ll a=b;a>=c;--a)
#define mem(a,b) memset(a,b,sizeof(a))
#define Tcase(n) for(int _=1;_<=n;++_)
#define ll long long
#define int long long
#define mod MOD
const int MOD(1e9+7);
const int maxn(5e5+5);
const int INF(0x3fffffff);
const double esp(1e-6);
using namespace std;
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % mod; a = a * a % mod; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll t, n, q;
struct P {
    ll r, s, level, cost;
}node[maxn];
ll a[maxn], pre[maxn];

inline int niyuan(ll x) {
    return powmod(x, mod - 2);
}

void acm() {
    cin >> t;
    Tcase(t) {
        cin >> n >> q;
        upf(i, 1, n) {
            cin >> node[i].r >> node[i].s >> node[i].level >> node[i].cost;
        }
        upf(i, 0, n + 2) {
            a[i] = 0;
            pre[i] = 0;
        }
        
        upf(i, 1, n) {
            a[i] = (((node[i].s - node[i].r + mod) % mod) * niyuan(node[i].r)%mod) *((pre[i]-pre[node[i].level]+mod)%mod)%mod  + ((node[i].cost*node[i].s)%mod*niyuan(node[i].r))%mod;
            a[i] %= mod;
            pre[i + 1] = pre[i] + a[i];
            pre[i + 1] %= mod;
        }
        
        upf(i, 1, q) {
            int x, y;
            cin >> x >> y;
            cout << (pre[y] - pre[x] + mod) % mod << '\n';
        }
    }
}

signed main()
 {
#ifdef ACM_LOCAL
    freopen("./ACM.in", "r", stdin);
    freopen("./ACM.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //cout << 100 * powmod(9, mod - 2) % mod << endl << endl;
    acm();
}

Final Exam

题意

有$n$门考试，所有考试的总分和为$m$，但是不知道具体哪门占几分，想要最少过$k$门，问最少复习时间是多少，当一门考试有$a$分时，至少要花$a+1$的时间复习才能通过这门考试。

做法

对于出卷老师来说，在知道复习分配时间的情况下，最好的让我们过不了$k$门的方法是将总分分到复习时间最少的$n-k+1$门，只要这些过不了，我们最多只能过$k-1$门达不成目标。所以首先我们要保证$n-k+1$门里面至少过$1$门，即在这些课里面总共分配$m+1$的时间，这样不管怎么分配，总会有一门会过。接下来我们考虑剩下的$k-1$门，因为$n-k+1$门是分配最少的，所以剩下的$k-1$门不能比$n-k+1$门里面的最大值小，最好的分配就是$m+1$在$n-k+1$门里面平均分，即$m/{n-k+1}$，所以剩下$k-1$门里都分配$m/{n-k+1}+1$时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define FIN freopen("./1006.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e5+5);
const ll inf(0x3f3f3f3f3f3f3f3f);
ll T,n,m,k,ans,an1,ans_m,l,r;
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    for(int t=1;t<=T;t++){
        ans=inf;
        cin>>n>>m>>k;
        cout<<m+1+(k-1)*(m/(n-k+1)+1)<<"\n";
    }
}

return 0;

本文链接：
https://luojinrong.github.io/2019/08/13/2019-Multi-University-Training-Contest-7/