2019 HDU多校第七场

A + B = C

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

Hi everyone! Welcome to the Stage 7 of this series of training contests. Cuber QQ is the problem settler of this contest; he has prepared 11 problems for you and wishes you to enjoy it. Good luck!

As the first problem of this contest, Cuber QQ thought that it’s reasonable to start with an easy one, so he modified the famous A + B problem by a little bit, so that it’s easy enough but not that trivial.

Given a,b,c , find an arbitrary set of x,y,z such that a⋅10x+b⋅10y=c⋅10z and 0≤x,y,z≤106. 
InputThe input consists of multiple test cases, starting with an integer t (1≤t≤100), denoting the number of test cases.

For each test case, there are three space-separated integers, a,b,c respectively (1≤a,b,c≤10100000). 
OutputFor each test case, please output three space-separated integers x,y,z. If there are multiple solutions, print any of them.

In case there are no solutions, please output −1 as a single line. 

Sample Input

3
23 39 62
2 31 51
1 1 1

Sample Output

0 0 0
1 0 0
-1

首先把 a, b, c 末尾的 0 都去掉得到 A, B, C, 方便处理.去掉的 0, 显然是可以通过调整相对大小补回来的.考虑 C · 10k, k > 0 的情况只存在于 A + B, 因为如果是 A · 10n + B = C · 10k(n > 0, k > 0)的情况, 显然 B 的末尾是存在 0 的, 这和我们上面已经去掉了末尾的 0 矛盾.那么接下来, 显然就是 k = 0 的情况, 这样的话, 显然 n = 0 或者 m = 0, 因为 C 的最后以为是非 0 的.确定一个数和 C 末尾对齐以后, 另一个要么是和 C 首位对齐, 要么就是和 C 第二位对齐(发生了进位).

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
char a[maxn],b[maxn],c[maxn];
int l1,l2,l3;
struct bign{
    int d[maxn],len;
    void clean(){while(len>1&&!d[len-1]) len--;}
    bign(){ memset(d, 0, sizeof(d)); len = 1;}
    bign(int num){ *this = num;} 
    bign(char* num) { *this = num; }
    bign operator = (const char* num){
        memset(d, 0, sizeof(d)); len = strlen(num);
        for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';
        clean();
        return *this;
    }
    bign operator = (int num){
        char s[20]; sprintf(s, "%d", num);
        *this = s;
        return *this;
    }
    bign operator + (const bign& b){
        bign c = *this; int i;
        for (i = 0; i < b.len; i++){
            c.d[i] += b.d[i];
            if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;
        }
        while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;
        c.len = max(len, b.len);
        if (c.d[i] && c.len <= i) c.len = i+1;
        return c;
    }
    bign operator - (const bign& b){
        bign c = *this; int i;
        for (i = 0; i < b.len; i++){
            c.d[i] -= b.d[i];
            if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;
        }
        while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;
        c.clean();
        return c;
    }
    bign operator * (const bign& b)const{
        int i, j; bign c; c.len = len + b.len; 
        for(j = 0; j < b.len; j++) for(i = 0; i < len; i++) 
            c.d[i+j] += d[i] * b.d[j];
        for(i = 0; i < c.len-1; i++)
            c.d[i+1] += c.d[i]/10, c.d[i] %= 10;
        c.clean();
        return c;
    }
    bign operator / (const bign& b){
        int i, j;
        bign c = *this, a = 0;
        for (i = len - 1; i >= 0; i--)
        {
            a = a*10 + d[i];
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
            c.d[i] = j;
            a = a - b*j;
        }
        c.clean();
        return c;
    }
    bign operator % (const bign& b){
        int i, j;
        bign a = 0;
        for (i = len - 1; i >= 0; i--)
        {
            a = a*10 + d[i];
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
            a = a - b*j;
        }
        return a;
    }
    bign operator += (const bign& b){
        *this = *this + b;
        return *this;
    }
    bool operator <(const bign& b) const{
        if(len != b.len) return len < b.len;
        for(int i = len-1; i >= 0; i--)
            if(d[i] != b.d[i]) return d[i] < b.d[i];
        return false;
    }
    bool operator >(const bign& b) const{return b < *this;}
    bool operator<=(const bign& b) const{return !(b < *this);}
    bool operator>=(const bign& b) const{return !(*this < b);}
    bool operator!=(const bign& b) const{return b < *this || *this < b;}
    bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}
    string str() const{
        char s[maxn]={};
        for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';
        return s;
    }
    void print(){
        dep(i,len-1,0) printf("%d",d[i]);
    }
};
bign aa,bb,cc;
int check(bign x,int l,char c[]){
    x.clean();
    int len=x.len;
    rep(i,1,l) if(x.d[len-i]!=c[i]-'0') return -1;
    rep(i,0,len-1-l) if(x.d[i]!=0) return -1;
    return len-l;
}
void solve(){
    scanf("%s%s%s",a+1,b+1,c+1);
    l1=strlen(a+1),l2=strlen(b+1),l3=strlen(c+1);
    int t1=0,t2=0,t3=0;
    while(a[l1]=='0') l1--,t1++;
    while(b[l2]=='0') l2--,t2++;
    while(c[l3]=='0') l3--,t3++;
    a[l1+1]='\0';b[l2+1]='\0';c[l3+1]='\0';
    aa=(a+1);bb=(b+1);cc=(c+1);
    int ans1,ans2,ans3;
    if((ans3=check(aa+bb,l3,c))>=0){
        ans1=-t1,ans2=-t2,ans3-=t3;
        int g=min({ans1,ans2,ans3});
        printf("%d %d %d\n",ans1-g,ans2-g,ans3-g);
        return;
    }
    else if((ans2=check(cc-aa,l2,b))>=0){
        ans1=-t1,ans2-=t2,ans3=-t3;
        int g=min({ans1,ans2,ans3});
        printf("%d %d %d\n",ans1-g,ans2-g,ans3-g);
        return;
    }
    else if((ans1=check(cc-bb,l1,a))>=0){
        ans1-=t1,ans2=-t2,ans3=-t3;
        int g=min({ans1,ans2,ans3});
        printf("%d %d %d\n",ans1-g,ans2-g,ans3-g);
        return;
    }
    puts("-1");
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}


Final Exam

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

Final Exam is coming! Cuber QQ has now one night to prepare for tomorrow’s exam.

The exam will be a exam of problems sharing altogether m points. Cuber QQ doesn’t know about the exact distribution. Of course, different problems might have different points; in some extreme cases, some problems might worth 0 points, or all m points. Points must be integers; a problem cannot have 0.5 point.

What he knows, is that, these n problems will be about n totally different topics. For example, one could be testing your understanding of Dynamic Programming, another might be about history of China in 19th century. So he has to divide your night to prepare each of these topics separately. Also, if one problem is worth x points in tomorrow’s exam, it takes at least x+1 hours to prepare everything you need for examination. If he spends less than x+1 hours preparing, he shall fail at this problem.

Cuber QQ’s goal, strangely, is not to take as much points as possible, but to solve at least k problems no matter how the examination paper looks like, to get away from his parents’ scoldings. So he wonders how many hours at least he needs to achieve this goal.

InputThe first line of the input is an integer t (1≤t≤20 000), denoting the number of test cases.

Each test case are three space-separated integers n,m,k (0≤m≤109, 1≤k≤n≤109). 

OutputFor each test case, output the number of hours Cuber QQ needs.

Sample Input

2
1 10 1
10 109 10

Sample Output

11
1100
Hint
Cuber QQ should solve one problem in sample 1, so he at least prepares 11 hours when the problem one is 10 point. 
Cuber QQ should solve all the ten problems in sample 2, so he at least prepares 110 hours for each problem because there may be one problem is 109 point.

换位思考, 考虑如果我们是出题人会怎么让学生做不出 k 题, 即最坏情况.显然, 我们会挑出学生复习得最少的 n − k + 1 道题, 让每道题的难度都等于他复习的时间.(田忌赛马的策略)因此, 回到学生视角, 我们要让自己复习的最少的 n − k + 1 题复习时间总和 > m, 构造方式显然.

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
ll n,m,k;
void solve(){
    scanf("%lld%lld%lld",&n,&m,&k);
    ll kk=m/(n-k+1);
    printf("%lld\n",(kk+1)*k+kk*(n-k)+m%(n-k+1));
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}


Halt Hater

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

Cuber QQ has recently won a million dollars and bought a new car. He is now driving in the Infinite City and he doesn’t want his car to stop, ever!

The Infinite City, looks like an infinite grid, with infinite streets built at all possible x’s and y’s when they are integers. The following picture, looks like part of this city. (The picture is downloaded from a webpage, which is certainly not describing the Infinite City.)

There are traffic lights installed on every crossings. Just like what Chinese people usually do, the traffic lights only show signals for left and straight and you can always turn right regardless of the traffic light. The estimate time of waiting for a left turn is a, at all crossings; and the time of waiting for a straight is b.

Cuber QQ is now driving from (0,−1) to (0,0), about to entering the crossing at (0,0). At a crossing, he can choose to go straight, turn left or turn right. He wishes to go to (x,y), but here is a weird request: he wants to have the least estimated traffic light waiting time. In other words, he doesn’t care whether he has to drive a long way, or he has to burn a lot of gas, all he wants is to wait as little as possible.

Note that Cuber QQ doesn’t have to wait for the traffic light at (x,y); he also doesn’t care from which direction he enters (x,y).

InputThe first line of the input contains an integer t (1≤t≤100 000).

Then follows t test cases, each containing a, b, x, y (1≤a,b≤109, −109≤x,y≤109, |x|+|y|>0), space separated. 

OutputFor each test case, output one integer as the answer. 

Sample Input

4
9 1 0 2
2 1 8 0
2 3 3 3
1 1 -1 -1

Sample Output

2
7
6
1

首先配合左转和右转, 一个左转完全可以替代直走, 因此我们可以准确求出笔直向前走 x 步的最小代价.之后是考虑在坐标轴上, 方法是枚举开局走的几步.很容易推出只有很少的走法是有意义的.比如在 x 正半轴上, 显然应该直接右转然后笔直走.之后再考虑第一象限.要么笔直走, 再右转 (尽量直走), 要么右转再左转 (尽量直走), 要么是先右转或先直走的不停左转右转走锯齿 (尽量右转).注意这里的直走指的是我们刚刚求得的子问题.因为线性规划问题就是尽量选性价比最高的方案, 不会证明这样搞是否严格是对的.之后考虑其他象限, 当然也是枚举开始的有效走法, 比如第二象限可以左转或者直走再右转三次.然后把他转成第一象限.写法上把它们写成子问题就很容易实现.

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
typedef long long ll;
ll a,b,x,y,ans=-1;
void gao(ll lx,ll ly,ll tx,ll ty){
        if(ans==-1) ans=max(abs(tx),abs(ty))*a+((abs(tx)+abs(ty)))%2*b;
        else ans=min(ans,max(abs(tx),abs(ty))*a+((abs(tx)+abs(ty))%2)*b);
        if(ans==-1) ans=(abs(tx)+abs(ty))*b;
        else ans=min(ans,(abs(tx)+abs(ty))*b);
        if(ans==-1) ans=min(abs(tx),abs(ty))*a+(max(abs(tx),abs(ty))-min(abs(tx),abs(ty)))*b;
        else ans=min(ans,min(abs(tx),abs(ty))*a+(max(abs(tx),abs(ty))-min(abs(tx),abs(ty)))*b);
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ans=-1;
        scanf("%lld%lld%lld%lld",&a,&b,&x,&y);
        gao(0,0,x,y);gao(0,0,x-1,y);gao(0,0,x,y+1);gao(0,0,x-1,y+1);
        printf("%lld\n",ans);
    }
    return 0;
}


Kejin Player

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

Cuber QQ always envies those Kejin players, who pay a lot of RMB to get a higher level in the game. So he worked so hard that you are now the game designer of this game. He decided to annoy these Kejin players a little bit, and give them the lesson that RMB does not always work.

This game follows a traditional Kejin rule of “when you are level i, you have to pay ai RMB to get to level i+1”. Cuber QQ now changed it a little bit: “when you are level i, you pay ai RMB, are you get to level i+1 with probability pi; otherwise you will turn into level xi (xi≤i)”.

Cuber QQ still needs to know how much money expected the Kejin players needs to “ke” so that they can upgrade from level l to level r, because you worry if this is too high, these players might just quit and never return again.

InputThe first line of the input is an integer t, denoting the number of test cases.

For each test case, there is two space-separated integers n (1≤n≤500 000) and q (1≤q≤500 000) in the first line, meaning the total number of levels and the number of queries.

Then follows n lines, each containing integers ri, si, xi, ai (1≤ri≤si≤109, 1≤xi≤i, 0≤ai≤109), space separated. Note that pi is given in the form of a fraction risi.

The next q lines are q queries. Each of these queries are two space-separated integers l and r (1≤l<r≤n+1).

The sum of n and sum of q from all t test cases both does not exceed 106. 
OutputFor each query, output answer in the fraction form modulo 109+7, that is, if the answer is PQ, you should output P⋅Q−1 modulo 109+7, where Q−1 denotes the multiplicative inverse of Q modulo 109+7.

Sample Input

1
3 2
1 1 1 2
1 2 1 3
1 3 3 4
1 4
3 4

Sample Output

22
12

签到题,设从 l 到 r 的期望为 g(l, r), 这种期望满足减法 g(l, r) = g(1, r) − g(1, l).因为升级只能一级一级升, 所以要从 1 升级到 r, 必然要经过 l.因此用期望方程推导一下 g(1, x) 就好了.

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(ll)5e5+10;
const int mod=(ll)1e9+7;
ll n,q,L,R;
ll ans[maxn],pre[maxn],r,s,x,a;
inline ll read(){
    ll x = 0;
    char c = getchar();
    bool flag = 0;
    while(!isdigit(c)) {
        if(c == '-') flag = 1;
        c = getchar();
    }
    while(isdigit(c)) {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return flag ? -x : x;
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
ll qpow(ll base, ll n){
    ll res = 1;
    while (n > 0){
        if (n & 1)  
            res = (res * base) % mod;
        base = (base * base) % mod;
        n >>= 1;
    }
    return res;
}
ll inv(ll b){return qpow(b,mod-2)%mod;}
void solve(){
    n=read();q=read();
    rep(i,1,n){
        r=read();s=read();x=read();a=read();
        ans[i]=(inv(r)*(a*s%mod+((s-r)*(pre[i]-pre[x]+mod)%mod))%mod)%mod;
        pre[i+1]=(pre[i]+ans[i])%mod;
    }
    while(q--){
        L=read();R=read();
        write((pre[R]-pre[L]+mod)%mod);
        puts("");
    }
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

发表评论,支持MarkDown语法