2018 CCPC吉林赛区

我队写了九题,Rank4,状态还可以


The Fool

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

The Fool is numbered 0 – the number of unlimited potential –and therefore does not have a specific place in the sequence of the Tarot cards. The Fool can be placed either at the beginning of the Major Arcana or at the end. The Major Arcana is often considered as the Fool’s journey through life and as such, he is
ever present and therefore needs no number.

Given n ∈ N+, print the parity of
∑i=1N [ni],
where [x] = max a (a∈Z,a≤x) 
InputThe first line of the input contains one integer T ≤ 100, denoting the number of testcases. Then T testcases follow.
In each of the T testcases, there is a positive number n ≤ 109. 
OutputFor each testcase, print a single line starting with “Case i : ”(i indicates the case number) and then “even” or “odd”, separated with a single space. 

Sample Input

3
1
10000
100000000

Sample Output

Case 1: odd
Case 2: even
Case 3: even

整数分块,签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n;
void solve(int ca){
    printf("Case %d: ",ca);
    scanf("%d",&n); int res=0;
    for(int i=3,ans=1;;i+=2,ans^=1){
        res+=i;
        if(res>=n){
            printf(ans?"odd\n":"even\n");
            break;
        }
    }
}
int main(){
    int T;cin>>T;
    rep(i,1,T) solve(i);
}

 


The World

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

The World can indicate world travel, particularly on a large scale. You may be lucky enough to be embarking on a six-month overseas trip, or are working, studying or living overseas for an extended period of time. Similarly, this card reinforces Universal understanding and global awareness, and you will have a new appreciation for people and cultures from across the world.

Across the world there are various time zones, leading to time differences. Here you are informed of several famous capitals and their corresponding time zones.

Beijing – China – UTC + 8 (China Standard Time)
Washington – United States – UTC – 5 (Eastern Standard Time)
London – United Kingdom – UTC (Greenwich Mean Time)
Moscow – Russia – UTC + 3 (Moscow Time)
Given the local time of a city, you are expected to calculate the date and local time of another specific city among the above capitals. 
InputThe first line of input contains a single integer T ≤ 1000 indicating the number of testcases.
Each testcase consists of three lines. The first line is in the form of “hour:minute AM/PM” (1 ≤ hour ≤ 12, 00 ≤ minute ≤ 59) indicating the local time. Next two lines contain two strings s1, s2. s1 is the name of city corresponding to the given time, while s2 indicates the city you are expected to calculate the local time. 
OutputFor each testcase, begin with “Case i:”, where i indicate the case number, and then output a single line in the following format“Yesterday/Today/Tomorrow hour:minute AM/PM”, separated by spaces. The first word describes the corresponding date. 

Sample Input

2
12:00 AM
London
Moscow
4:00 PM
London
Beijing

Sample Output

Case 1: Today 3:00 AM
Case 2: Tomorrow 12:00 AM

直接模拟,注意小细节,签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int md=720;
int cal(int a,int b){return a*60+b;}
map<char,int> mp;
void solve(int ca){
    printf("Case %d: ",ca);
    int h,m;scanf("%d:%d",&h,&m);
    if(h==12) h=0;
    char s[10]; scanf("%s",s);
    if(s[0]=='P') h+=12;
    char t1[20],t2[20];scanf("%s%s",t1,t2);
    int delt=mp[t2[0]]-mp[t1[0]];
    h+=delt;
    if(h>=24){
        printf("Tomorrow ");
        h-=24;
    }
    else if(h<0){
        h+=24;
        printf("Yesterday ");
    }
    else printf("Today ");
    int tmp=h;
    if(h==0) tmp=12;
    else if(h==12) tmp=12;
    else if(h>12) tmp=h-12;
    printf("%d:%02d ",tmp,m);
    if(h>=12) printf("PM\n");
    else printf("AM\n");
}
int main(){        
    mp['B']=8; mp['W']=-5; mp['L']=0; mp['M']=3;
    int T;cin>>T;
    rep(i,1,T) solve(i);
}

 


Justice

Time Limit: 7000/4000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

Put simply, the Justice card represents justice, fairness, truth and the law. You are being called to account for your actions and will be judged accordingly. If you have acted in a way that is in alignment with your Higher Self and for the greater good of others, you have nothing to worry about. However, if you have
acted in a way that is out of alignment, you will be called out and required to own up to your actions. If this has you shaking in your boots, know that the Justice card isn’t as black and white as you may think.

On the table there are n weights. On the body of the i-th weight carved a positive integer ki , indicating that its weight is 12ki gram. Is it possible to divide the n weights into two groups and make sure that the sum of the weights in each group is greater or equal to 12 gram? That’s on your call. And please tell us how if possible. 
InputIn the first line of the input there is a positive integer T (1 ≤ T ≤ 2000), indicating there are T testcases.
In the first line of each of the T testcases, there is a positive integer n (1 ≤ n ≤ 105, ∑n ≤ 7 × 105), indicating there are n weights on the table.
In the next line, there are n integers ki (1 ≤ ki ≤ 109), indicating the number carved on each weight. 
OutputFor each testcase, first print Case i: ANSWER in one line, i indicating the case number starting from 1 and ANSWER should be either YES or NO, indicating whether or not it is possible to divide the weights. Pay attention to the space between : and ANSWER.
If it’s possible, you should continue to output the dividing solution by print a 0/1 string of length n in the next line. The i-th character in the string indicating whether you choose to put the i-th weight in group 0 or group 1. 

Sample Input

3
3
2 2 2
3
2 2 1
2
1 1

Sample Output

Case 1: NO
Case 2: YES
001
Case 3: YES
10

判一下全部的和是否大于1就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
int z,x,n,m,w,h,k,l[100010];
struct tt{int t,id,p;}a[maxn];
bool cmp1(tt a,tt b){return a.t<b.t;}
bool cmp2(tt a,tt b){return a.id<b.id;}
void solve(int ca){
    printf("Case %d: ",ca);
    scanf("%d",&n);
    rep(i,1,n){
        scanf("%d",&a[i].t);a[i].p=0;a[i].id=i;
    } sort(a+1,a+n+1,cmp1);
    m=0;k=1;
    rep(i,1,n){
        l[++m]=a[i].t;
        while (m!=1&&l[m]==l[m-1]){
            l[m-1]=l[m-1]-1;
            m--;
        }
        if (k) a[i].p=1;
        if (l[1]==1) k=0;
        if (l[1]==0) break;
    }
    sort(a+1,a+n+1,cmp2);
    if (l[1]>0) printf("NO\n");
    else{
        printf("YES\n");
        for (int i=1;i<=n;i++) printf("%d",a[i].p);
        printf("\n");  
    }
}
int main(){        
    int T;cin>>T;
    rep(i,1,T) solve(i);
}

 


The Moon

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

The Moon card shows a large, full moon in the night’s sky, positioned between two large towers. The Moon is a symbol of intuition, dreams, and the unconscious. The light of the moon is dim, compared to the sun, and only vaguely illuminates the path to higher consciousness which winds between the two towers.

Random Six is a FPS game made by VBI(Various Bug Institution). There is a gift named “Beta Pack”. Mr. K wants to get a beta pack. Here is the rule.
Step 0. Let initial chance rate q = 2%.
Step 1. Player plays a round of the game with winning rate p.
Step 2. If the player wins, then will go to Step 3 else go to Step 4.
Step 3. Player gets a beta pack with probability q. If he doesn’t get it, let q = min(100%, q + 2%) and he will go to Step 1.
Step 4. Let q = min(100%, q + 1.5%) and goto Step 1.
Mr. K has winning rate p% , he wants to know what’s the expected number of rounds before he needs to play. 
InputThe first line contains testcase number T (T ≤ 100). For each testcase the first line contains an integer p (1 ≤ p ≤ 100). 
OutputFor each testcase print Case i : and then print the answer in one line, with absolute or relative error not exceeding 106. 

Sample Input

2
50
100

Sample Output

Case 1: 12.9933758002
Case 2: 8.5431270393

dp[i]表示p=i时的答案,然后从后往前维护就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const double eps=1e-10;
double p,q,dp[1030];
void solve(int ca){
    printf("Case %d: ",ca);
    scanf("%lf",&p); p/=100.0;
    rep(i,0,1010) dp[i]=0.0;
    dp[1000]=1.0/p;
    dep(i,1000-5,20){ //100%~2%
        dp[i]+=p*(i/1000.0+(1.0-i/1000.0)*(dp[min(1000,i+20)]+1.0));
        dp[i]+=(1.0-p)*(dp[min(1000,i+15)]+1.0);
    }
    printf("%.10lf\n",dp[20]);
}
int main(){
    int T;cin>>T;
    rep(i,1,T) solve(i);
}

 


The Tower

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

The Tower shows a tall tower perched on the top of a rocky mountain. Lightning strikes, setting the building alight, and two people leap from the windows, head first and arms outstretched. It is a scene of chaos and destruction.

There is a cone tower with base center at (0, 0, 0), base radius r and apex (0, 0, h). At time 0 , a point located at (x0, y0, z0) with velocity (vx, vy, vz). What time will they collide? Here is the cone tower.

InputThe first line contains testcase number T (T ≤ 1000), For each testcase the first line contains spaceseparated real numbers r and h (1 ≤ r, h ≤ 1000) — the base radius and the cone height correspondingly.
For each testcase the second line contains three real numbers x0, y0, z0 (0 ≤ |x0|, |y0|, z0 ≤ 1000). For each testcase the third line contains three real numbers vx, vy, vz(1 ≤ v2x + v2y + v2z ≤ 3 × 106). It is guaranteed that at time 0 the point is outside the cone and they will always collide. 
OutputFor each testcase print Case i : and then print the answer in one line, with absolute or relative error not exceeding 10−6 

Sample Input

2
1 2
1 1 1
-1.5 -1.5 -0.5
1 1
1 1 1
-1 -1 -1

Sample Output

Case 1: 0.3855293381
Case 2: 0.5857864376

解析几何简单题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const double eps=1e-7; 
double a,b,c;
void solve(int ca){
    printf("Case %d: ",ca);
    double r,h; scanf("%lf%lf",&r,&h);
    double x,y,z; scanf("%lf%lf%lf",&x,&y,&z);
    double vx,vy,vz; scanf("%lf%lf%lf",&vx,&vy,&vz);
    double a,b,c,ro;
    ro=r*r/h/h;
    a=vx*vx+vy*vy-vz*vz*ro;
    b=2*x*vx+2*y*vy-2*ro*z*vz+2*ro*h*vz;
    c=x*x+y*y-(h*h+z*z-2*h*z)*ro;
    double delt=b*b-4*a*c;
    delt=sqrt(delt);
    double t1=(-b+delt)/(2*a),t2=(-b-delt)/(2*a);
    double z1=t1*vz+z,z2=t2*vz+z;
    double ans;
    if(z1+eps>h){
        ans=t2;
        printf("%.10lf\n",ans);
    }
    else if(z2+eps>h){
        ans=t1;
        printf("%.10lf\n",ans);
    }
    else{
        ans=min(max(0.0,t1),max(0.0,t2));
        printf("%.10lf\n",ans);
    }
}
int main(){        
    int T;cin>>T;
    rep(i,1,T) solve(i);
}

 


The Hermit

Time Limit: 25000/15000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

The Hermit stands alone on the top of a mountain with a lantern in his hand. The snow-capped mountain range symbolises the Hermit’s spiritual achievement, growth and accomplishment. He has chosen this path of self-discovery and, as a result, has reached a heighted state of awareness

dhh loves to listen to radio. There are N radio stations on a number axis, and the i-th station is located at xi = i. The broadcasting scope of the i-th station is radi , which means stations in the interval [i – radi + 1, i + radi – 1] can receive the signal from the i-th station. For some unknown reason, the left boundary that can receive the i-th station’s signal is non-descending, which meansi i – radi + 1 ≤ i + 1 – radi+1 + 1.
Now dhh wants to listen to the radio from station i, and he finds that the station k, satisfying both of the following conditions, can receive perfect signal from the station i:

k < i and station k can receive station i’s signal.
There exists another station j(k ≤ j < i) such that station k and i can both receive the signal from station j and the distance between station k and j is greater than or equal to the distance between station j and i.
Now dhh wonders for each station i, how many stations can receive the perfect signal from station i. 
InputThe first line of the input contains one integer T ≤ 20, denoting the number of testcases. Then T testcases follow. For each testcase:
The first line contains one positve integer N.
The second line contains N positive integers rad1, rad2, … , radN .
It’s guaranteed that 1 ≤ N ≤ 106 ,i – radi + 1 ≥ 1 and i + radi – 1 ≤ N 
OutputFor the k-th testcase, output “Case k: ans” in one line, where ans represents the xor result of answer for each radio station i.
xor is a bitwise operation, which takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison
of two bits, being 1 if the two bits are different, and 0 if they are the same. 

Sample Input

2
7
1 2 3 4 3 2 1
10
1 1 2 3 4 4 3 2 2 1

Sample Output

Case 1: 2
Case 2: 0
Hint
In the first testcase of the example, the number of stations that can receive the perfect signal from each station $i$ is respectively 0, 0, 1, 2, 1, 0, 0 in order, so the answer must be 

0 xor 0 xor 1 xor 2 xor 1 xor 0 xor 0 = 2

签到题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const double eps=1e-10;
int n;
void solve(int ca){
    printf("Case %d: ",ca);
    scanf("%d",&n);
    int ans=0;
    rep(i,1,n){
        int x;scanf("%d",&x);
        ans^=(max(0,x-2));
    }
    printf("%d\n",ans);
}
int main(){
    int T;cin>>T;
    rep(i,1,T) solve(i);
}

 


Lovers

Time Limit: 25000/15000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

The Fool comes to a cross-road, filled with energy, confidence and purpose, knowing exactly where he wants to go and what he wants to do. But he comes to a dead stop. A flowering tree marks the path he wants to take, the one he’s been planning on taking. But standing before a fruit tree marking the other path is a woman. The Fool has met and had relationships with women before, some far more beautiful and alluring. But she is different. Seeing her, he feels as though he’s just been shot in the heart with cupid’s arrow.

There are n empty strings:
s1, s2, . . . , sn.
You are required to perform two kinds of operations:

wrap l r d: change si to dsid for all l ≤ i ≤ r, where d is a digit character.
query l r: query ∑i=lr value(si) (mod 109 + 7), where value(s) is the number that string s represents.

Note that the value of an empty string is 0. 
InputThe first line contains one integer T, which denote the number of cases.
For each case, the first line contains two integer n and m where n is the number of strings and m is the number of operations.
Each line of the following m lines contains an operation with format
wrap l r d
or
query l r. 
OutputFor each case, you should output “Case i:”in a line, where i is the case number starting from 1.
Then for each query operation in that case, output a line that contains a single integer that representing the answer for that query operation. 

Sample Input

2
3 2
wrap 1 3 1
query 1 2
4 4
wrap 1 3 0
wrap 2 4 3
query 1 4
query 2 3

Sample Output

Case 1:
22
Case 2:
6039
6006
Hint
1 ≤ T ≤ 5, 1 ≤ n, m ≤ 1e5, 1 ≤ l ≤ r ≤ n.

维护两颗线段树,一颗维护答案,查询时就是普通线段树查询,另一颗维护10的长度次的和,用于更新第一颗线段树

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const double eps=1e-10;
const int mod=(int)1e9+7;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define delf int mid=(l+r)>>1
struct node{
    int l,r,len;
    ll s1,s2,lazy1,lazy2,lazylen;
}s[maxn<<2];
void build(int l,int r,int rt){
    s[rt].l=l; s[rt].r=r;
    s[rt].len=s[rt].s1=r-l+1;
    s[rt].lazy1=0; s[rt].lazy2=0;
    s[rt].lazylen=1;
    s[rt].s2=0;
    if(l==r)return;
    delf;
    build(lson); build(rson);
}
int n,m;
char op[10];
void pushup(int rt){
    s[rt].s1=(s[rt<<1].s1+s[rt<<1|1].s1)%mod;
    s[rt].s2=(s[rt<<1].s2+s[rt<<1|1].s2)%mod;
}
void pushdown(int rt){
    if(s[rt].lazylen>1){   
        s[rt<<1].s2=(s[rt].lazy1*s[rt<<1].s1%mod*s[rt].lazylen%mod+s[rt<<1].s2*s[rt].lazylen%mod+s[rt].lazy2*s[rt<<1].len%mod)%mod;
        s[rt<<1|1].s2=(s[rt].lazy1*s[rt<<1|1].s1%mod*s[rt].lazylen%mod+s[rt<<1|1].s2*s[rt].lazylen%mod+s[rt].lazy2*s[rt<<1|1].len%mod)%mod;
        s[rt<<1].s1=(s[rt<<1].s1*s[rt].lazylen%mod*s[rt].lazylen)%mod;
        s[rt<<1|1].s1=(s[rt<<1|1].s1*s[rt].lazylen%mod*s[rt].lazylen)%mod;
        s[rt<<1].lazy1=(s[rt].lazy1*s[rt<<1].lazylen%mod+s[rt<<1].lazy1)%mod;
        s[rt<<1|1].lazy1=(s[rt].lazy1*s[rt<<1|1].lazylen%mod+s[rt<<1|1].lazy1)%mod;
        s[rt<<1].lazy2=(s[rt<<1].lazy2*s[rt].lazylen%mod+s[rt].lazy2)%mod;
        s[rt<<1|1].lazy2=(s[rt<<1|1].lazy2*s[rt].lazylen%mod+s[rt].lazy2)%mod;
        s[rt<<1].lazylen=(s[rt<<1].lazylen*s[rt].lazylen)%mod;
        s[rt<<1|1].lazylen=(s[rt<<1|1].lazylen*s[rt].lazylen)%mod;
        s[rt].lazylen=1; s[rt].lazy1=0; s[rt].lazy2=0;
    }
}
void update(int l,int r,int rt,int d){
    if(l<=s[rt].l && s[rt].r<=r){
        s[rt].s2=(s[rt].s2*10%mod+d*s[rt].s1*10%mod+s[rt].len*d%mod)%mod;
        s[rt].s1=s[rt].s1*100%mod;
        s[rt].lazy1=(s[rt].lazylen*d%mod+s[rt].lazy1)%mod;
        s[rt].lazy2=(s[rt].lazy2*10+d)%mod;
        s[rt].lazylen=(s[rt].lazylen*10)%mod;
        return;
    }
    pushdown(rt);
    if(l<=s[rt<<1].r) update(l,r,rt<<1,d);
    if(r>=s[rt<<1|1].l) update(l,r,rt<<1|1,d);
    pushup(rt);
}
ll query(int l,int r,int rt){
    if(l<=s[rt].l&&s[rt].r<=r) return s[rt].s2;
    pushdown(rt);
    ll res=0;
    if(l<=s[rt<<1].r) res=(res+query(l,r,rt<<1))%mod;
    if(r>=s[rt<<1|1].l) res=(res+query(l,r,rt<<1|1))%mod;
    return res%mod;
}
void solve(int ca){
    printf("Case %d:\n",ca);
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while(m--){
        scanf("%s",op);
        if(op[0]=='w'){
            int l,r,k;scanf("%d%d%d",&l,&r,&k);
            update(l,r,1,k);
        }
        else{
            int l,r;scanf("%d%d",&l,&r);
            printf("%lld\n",query(l,r,1));
        }
    }
}
int main(){
    int T;cin>>T;
    rep(i,1,T) solve(i);
}

 


Strength

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

Strength gives you the confidence within yourself to overcome any fears, challenges or doubts. Feel the fear and do it anyway! If you have been going through a rough time and feel burnt out or stressed, the Strength card encourages you to find the strength within yourself and keep going. You have got what it takes to see this situation through to its eventual end. You might also feel compelled to hold space for someone else who is going through a difficult period and needs your strength and support.

Alice and Bob are playing “Yu-Gi-Oh!”, a famous turn-based trading card game, in which two players perform their turns alternatively. After several turns, Alice and Bob have many monsters respectively.
Alice has n and Bob has m monsters under their own control. Each monster’s strength is measured by a non-negative integer si . To be specific, the larger si is, the more power the monster has.
During each turn, for every single monster under control, the player can give a command to it at most once, driving it to battle with an enemy monster (given that opposite player has no monsters as a shield, the monster can directly attack him).
Additionally, the process of the battle is also quite simple. When two monsters battle with each other, the stronger one (i.e. the one with larger si) will overwhelm the other and destroy it and the winner’s strength will remain unchanged. Meanwhile, the difference of their strength will produce equivalent damage to the player who loses the battle. If the player is directly attacked by a monster, he will suffer from the damage equal to the monster’s strength. Notice that when two monsters have the same strength, both of them will vanish and no damage will be dealt.
Right now it is Alice’s turn to play, having known the strength of all monsters, she wants to calculate the maximal damage she can deal towards Bob in one turn. Unfortunately, Bob has great foresight and is well-prepared for the upcoming attack. Bob has converted several of his monsters into defense position,
in which even if the monster is destroyed, he wouldn’t get any damage.
Now you are informed of the strength of all the monsters and whether it is in defense position for each Bob’s monster, you are expected to figure out the maximal damage that could be dealt in this turn. 
InputThe first line contains a single integer T ≤ 20 indicating the number of test cases.
For each test case, the first line includes two integer 0 ≤ n, m ≤ 100000, representing the number of monsters owned by Alice and Bob.
In next three lines, the first two lines include n and m integers 0 ≤ si ≤ 109 indicating the strength of the i-th monster, separated by spaces. The last line contains m integers 0 or 1 indicating the position of Bob’s i-th monsters.In other words, 0 represents the normal position and 1 represents the defense position. 
OutputFor the ith test, output a single line in beginning of “Case i:”, followed by an integer indicating the answer, separated by a single space. 

Sample Input

2
4 2
10 10 10 20
5 15
0 1
4 2
10 10 10 20
5 25
0 1

Sample Output

Case 1: 25
Case 2: 15

队友写的,直接贪心乱搞

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    int p,sta;
    bool operator < (const node& y){
        return p<y.p;
    }
};
node b[100100];
int a[100100];
int main(){
    int T;
    int th=0;
    scanf("%d",&T);
    while(T--){
        int n,m;
        th++;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%d",&b[i].p);
        }
        for(int i=1;i<=m;i++){
            scanf("%d",&b[i].sta);
        }
        sort(a+1,a+n+1);
        sort(b+1,b+1+m);
        int pt=n;
        int fg=1;
        printf("Case %d: ",th);
        if(n>=m)for(int i=m;i>0;i--){
            if(b[i].p>a[pt]){
                fg=0;
                break;
            }
            pt--;
        }
        else fg=0;
        if(fg){
            int pt=1;
            ll cnt=0;
            for(int i=1;i<=m;i++){
                if(b[i].sta){
                    while(a[pt]<b[i].p){
                        pt++;
                    }
                    cnt+=a[pt]*1ll;
                    pt++;
                }
            }
            ll ans=0;
            for(int i=1;i<=n;i++){
                ans+=a[i];
            }
            for(int i=1;i<=m;i++){
                if(b[i].sta==0){
                    ans-=b[i].p;
                }
            }
            ans-=cnt;
            printf("%lld\n",ans);
        }
        else{
            int pt=n;
            ll ans=0;
            for(int i=1;i<=m;i++){
                if(!b[i].sta){
                    if(b[i].p>a[pt]){
                        break;
                    }
                    else{
                        ans+=a[pt]-b[i].p;
                        pt--;
                    }
                }
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

 

发表评论,支持MarkDown语法