2019 HDU多校第八场

Acesrc and Good Numbers

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

Problem Description

Acesrc is a famous mathematician at Nanjing University second to none. Playing with interesting numbers is his favorite. Today, he finds a manuscript when cleaning his room, which reads

… Let f(d,n) denote the number of occurrences of digit d in decimal representations of integers 1,2,3,⋯,n. The function has some fantastic properties …

… Obviously, there exist some nonnegative integers k, such that f(d,k)=k, and I decide to call them d-good numbers …

… I have found all d-good numbers not exceeding 101000, but the paper is too small to write all these numbers …

Acesrc quickly recollects all d-good numbers he found, and he tells Redsun a question about d-good numbers: what is the maximum d-good number no greater than x? However, Redsun is not good at mathematics, so he wants you to help him solve this problem. 
InputThe first line of input consists of a single integer q (1≤q≤1500), denoting the number of test cases. Each test case is a single line of two integers d (1≤d≤9) and x(0≤x≤1018).

OutputFor each test case, print the answer as a single integer in one line. Note that 0 is trivially a d-good number for arbitrary d. 

Sample Input

3
1 1
1 199999
3 0

Sample Output

1
199990
0

OEIS打表

#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 a[10][400];
int num[12];
void solve(){
    int d;
    ll x;
    scanf("%d%lld",&d,&x);
    rep(i,1,num[d]+1) if(i>num[d]||a[d][i]>x){
        printf("%lld\n",a[d][i-1]);return;
    }
}
int main(){
    a[1][1]=0;a[1][2]=1;a[1][3]=199981;a[1][4]=199982;a[1][5]=199983;a[1][6]=199984;a[1][7]=199985;a[1][8]=199986;a[1][9]=199987;a[1][10]=199988;a[1][11]=199989;a[1][12]=199990;a[1][13]=200000;a[1][14]=200001;a[1][15]=1599981;a[1][16]=1599982;a[1][17]=1599983;a[1][18]=1599984;a[1][19]=1599985;a[1][20]=1599986;a[1][21]=1599987;a[1][22]=1599988;a[1][23]=1599989;a[1][24]=1599990;a[1][25]=2600000;a[1][26]=2600001;a[1][27]=13199998;a[1][28]=35000000;a[1][29]=35000001;a[1][30]=35199981;a[1][31]=35199982;a[1][32]=35199983;a[1][33]=35199984;a[1][34]=35199985;a[1][35]=35199986;a[1][36]=35199987;a[1][37]=35199988;a[1][38]=35199989;a[1][39]=35199990;a[1][40]=35200000;a[1][41]=35200001;a[1][42]=117463825;a[1][43]=500000000;a[1][44]=500000001;a[1][45]=500199981;a[1][46]=500199982;a[1][47]=500199983;a[1][48]=500199984;a[1][49]=500199985;a[1][50]=500199986;a[1][51]=500199987;a[1][52]=500199988;a[1][53]=500199989;a[1][54]=500199990;a[1][55]=500200000;a[1][56]=500200001;a[1][57]=501599981;a[1][58]=501599982;a[1][59]=501599983;a[1][60]=501599984;a[1][61]=501599985;a[1][62]=501599986;a[1][63]=501599987;a[1][64]=501599988;a[1][65]=501599989;a[1][66]=501599990;a[1][67]=502600000;a[1][68]=502600001;a[1][69]=513199998;a[1][70]=535000000;a[1][71]=535000001;a[1][72]=535199981;a[1][73]=535199982;a[1][74]=535199983;a[1][75]=535199984;a[1][76]=535199985;a[1][77]=535199986;a[1][78]=535199987;a[1][79]=535199988;a[1][80]=535199989;a[1][81]=535199990;a[1][82]=535200000;a[1][83]=535200001;a[1][84]=1111111110;
    a[2][1]=28263827;a[2][2]=35000000;a[2][3]=242463827;a[2][4]=500000000;a[2][5]=528263827;a[2][6]=535000000;a[2][7]=10000000000;a[2][8]=10028263827;a[2][9]=10035000000;a[2][10]=10242463827;a[2][11]=10500000000;a[2][12]=10528263827;a[2][13]=10535000000;
    a[3][1]=371599983;a[3][2]=371599984;a[3][3]=371599985;a[3][4]=371599986;a[3][5]=371599987;a[3][6]=371599988;a[3][7]=371599989;a[3][8]=371599990;a[3][9]=371599991;a[3][10]=371599992;a[3][11]=500000000;a[3][12]=10000000000;a[3][13]=10371599983;a[3][14]=10371599984;a[3][15]=10371599985;a[3][16]=10371599986;a[3][17]=10371599987;a[3][18]=10371599988;a[3][19]=10371599989;a[3][20]=10371599990;a[3][21]=10371599991;a[3][22]=10371599992;a[3][23]=10500000000;a[3][24]=20000000000;a[3][25]=20371599983;a[3][26]=20371599984;a[3][27]=20371599985;a[3][28]=20371599986;a[3][29]=20371599987;a[3][30]=20371599988;a[3][31]=20371599989;a[3][32]=20371599990;a[3][33]=20371599991;a[3][34]=20371599992;a[3][35]=20500000000;
    a[4][1]=499999984;a[4][2]=499999985;a[4][3]=499999986;a[4][4]=499999987;a[4][5]=499999988;a[4][6]=499999989;a[4][7]=499999990;a[4][8]=499999991;a[4][9]=499999992;a[4][10]=499999993;a[4][11]=500000000;a[4][12]=10000000000;a[4][13]=10499999984;a[4][14]=10499999985;a[4][15]=10499999986;a[4][16]=10499999987;a[4][17]=10499999988;a[4][18]=10499999989;a[4][19]=10499999990;a[4][20]=10499999991;a[4][21]=10499999992;a[4][22]=10499999993;a[4][23]=10500000000;a[4][24]=20000000000;a[4][25]=20499999984;a[4][26]=20499999985;a[4][27]=20499999986;a[4][28]=20499999987;a[4][29]=20499999988;a[4][30]=20499999989;a[4][31]=20499999990;a[4][32]=20499999991;a[4][33]=20499999992;a[4][34]=20499999993;a[4][35]=20500000000;a[4][36]=30000000000;a[4][37]=30499999984;a[4][38]=30499999985;a[4][39]=30499999986;a[4][40]=30499999987;a[4][41]=30499999988;a[4][42]=30499999989;a[4][43]=30499999990;a[4][44]=30499999991;a[4][45]=30499999992;a[4][46]=30499999993;a[4][47]=30500000000;
    a[5][1]=0;a[5][2]=10000000000;a[5][3]=20000000000;a[5][4]=30000000000;a[5][5]=40000000000;
    a[6][1]=0;a[6][2]=9500000000;a[6][3]=9628399986;a[6][4]=9628399987;a[6][5]=9628399988;a[6][6]=9628399989;a[6][7]=9628399990;a[6][8]=9628399991;a[6][9]=9628399992;a[6][10]=9628399993;a[6][11]=9628399994;a[6][12]=9628399995;a[6][13]=10000000000;a[6][14]=19500000000;a[6][15]=19628399986;a[6][16]=19628399987;a[6][17]=19628399988;a[6][18]=19628399989;a[6][19]=19628399990;a[6][20]=19628399991;a[6][21]=19628399992;a[6][22]=19628399993;a[6][23]=19628399994;a[6][24]=19628399995;a[6][25]=20000000000;a[6][26]=29500000000;a[6][27]=29628399986;a[6][28]=29628399987;a[6][29]=29628399988;a[6][30]=29628399989;a[6][31]=29628399990;a[6][32]=29628399991;a[6][33]=29628399992;a[6][34]=29628399993;a[6][35]=29628399994;a[6][36]=29628399995;a[6][37]=30000000000;a[6][38]=39500000000;a[6][39]=39628399986;a[6][40]=39628399987;a[6][41]=39628399988;a[6][42]=39628399989;a[6][43]=39628399990;a[6][44]=39628399991;a[6][45]=39628399992;a[6][46]=39628399993;a[6][47]=39628399994;a[6][48]=39628399995;a[6][49]=40000000000;a[6][50]=49500000000;a[6][51]=49628399986;a[6][52]=49628399987;a[6][53]=49628399988;a[6][54]=49628399989;a[6][55]=49628399990;a[6][56]=49628399991;a[6][57]=49628399992;a[6][58]=49628399993;a[6][59]=49628399994;a[6][60]=49628399995;a[6][61]=50000000000;a[6][62]=59500000000;a[6][63]=59628399986;a[6][64]=59628399987;a[6][65]=59628399988;a[6][66]=59628399989;a[6][67]=59628399990;a[6][68]=59628399991;a[6][69]=59628399992;a[6][70]=59628399993;a[6][71]=59628399994;a[6][72]=59628399995;
    a[7][1]=0;a[7][2]=9465000000;a[7][3]=9471736170;a[7][4]=9500000000;a[7][5]=9757536170;a[7][6]=9965000000;a[7][7]=9971736170;a[7][8]=10000000000;a[7][9]=19465000000;a[7][10]=19471736170;a[7][11]=19500000000;a[7][12]=19757536170;a[7][13]=19965000000;a[7][14]=19971736170;a[7][15]=20000000000;a[7][16]=29465000000;a[7][17]=29471736170;a[7][18]=29500000000;a[7][19]=29757536170;a[7][20]=29965000000;a[7][21]=29971736170;a[7][22]=30000000000;a[7][23]=39465000000;a[7][24]=39471736170;a[7][25]=39500000000;a[7][26]=39757536170;a[7][27]=39965000000;a[7][28]=39971736170;a[7][29]=40000000000;a[7][30]=49465000000;a[7][31]=49471736170;a[7][32]=49500000000;a[7][33]=49757536170;a[7][34]=49965000000;a[7][35]=49971736170;a[7][36]=50000000000;a[7][37]=59465000000;a[7][38]=59471736170;a[7][39]=59500000000;a[7][40]=59757536170;a[7][41]=59965000000;a[7][42]=59971736170;a[7][43]=60000000000;a[7][44]=69465000000;a[7][45]=69471736170;a[7][46]=69500000000;a[7][47]=69757536170;a[7][48]=69965000000;a[7][49]=69971736170;
    a[8][1]=0;a[8][2]=9465000000;a[8][3]=9486799989;a[8][4]=9486799990;a[8][5]=9486799991;a[8][6]=9486799992;a[8][7]=9486799993;a[8][8]=9486799994;a[8][9]=9486799995;a[8][10]=9486799996;a[8][11]=9486799997;a[8][12]=9497400000;a[8][13]=9498399989;a[8][14]=9498399990;a[8][15]=9498399991;a[8][16]=9498399992;a[8][17]=9498399993;a[8][18]=9498399994;a[8][19]=9498399995;a[8][20]=9498399996;a[8][21]=9498399997;a[8][22]=9500000000;a[8][23]=9882536171;a[8][24]=9965000000;a[8][25]=9986799989;a[8][26]=9986799990;a[8][27]=9986799991;a[8][28]=9986799992;a[8][29]=9986799993;a[8][30]=9986799994;a[8][31]=9986799995;a[8][32]=9986799996;a[8][33]=9986799997;a[8][34]=9997400000;a[8][35]=9998399989;a[8][36]=9998399990;a[8][37]=9998399991;a[8][38]=9998399992;a[8][39]=9998399993;a[8][40]=9998399994;a[8][41]=9998399995;a[8][42]=9998399996;a[8][43]=9998399997;a[8][44]=10000000000;a[8][45]=19465000000;a[8][46]=19486799989;a[8][47]=19486799990;a[8][48]=19486799991;a[8][49]=19486799992;a[8][50]=19486799993;a[8][51]=19486799994;a[8][52]=19486799995;a[8][53]=19486799996;a[8][54]=19486799997;a[8][55]=19497400000;a[8][56]=19498399989;a[8][57]=19498399990;a[8][58]=19498399991;a[8][59]=19498399992;a[8][60]=19498399993;a[8][61]=19498399994;a[8][62]=19498399995;a[8][63]=19498399996;a[8][64]=19498399997;a[8][65]=19500000000;a[8][66]=19882536171;a[8][67]=19965000000;a[8][68]=19986799989;a[8][69]=19986799990;a[8][70]=19986799991;a[8][71]=19986799992;a[8][72]=19986799993;a[8][73]=19986799994;a[8][74]=19986799995;a[8][75]=19986799996;a[8][76]=19986799997;a[8][77]=19997400000;a[8][78]=19998399989;a[8][79]=19998399990;a[8][80]=19998399991;a[8][81]=19998399992;a[8][82]=19998399993;a[8][83]=19998399994;a[8][84]=19998399995;a[8][85]=19998399996;a[8][86]=19998399997;a[8][87]=20000000000;a[8][88]=29465000000;a[8][89]=29486799989;a[8][90]=29486799990;a[8][91]=29486799991;a[8][92]=29486799992;a[8][93]=29486799993;a[8][94]=29486799994;a[8][95]=29486799995;a[8][96]=29486799996;a[8][97]=29486799997;a[8][98]=29497400000;a[8][99]=29498399989;a[8][100]=29498399990;a[8][101]=29498399991;a[8][102]=29498399992;a[8][103]=29498399993;a[8][104]=29498399994;a[8][105]=29498399995;a[8][106]=29498399996;a[8][107]=29498399997;a[8][108]=29500000000;a[8][109]=29882536171;a[8][110]=29965000000;a[8][111]=29986799989;a[8][112]=29986799990;a[8][113]=29986799991;a[8][114]=29986799992;a[8][115]=29986799993;a[8][116]=29986799994;a[8][117]=29986799995;a[8][118]=29986799996;a[8][119]=29986799997;a[8][120]=29997400000;a[8][121]=29998399989;a[8][122]=29998399990;a[8][123]=29998399991;a[8][124]=29998399992;a[8][125]=29998399993;a[8][126]=29998399994;a[8][127]=29998399995;a[8][128]=29998399996;a[8][129]=29998399997;a[8][130]=30000000000;a[8][131]=39465000000;a[8][132]=39486799989;a[8][133]=39486799990;a[8][134]=39486799991;a[8][135]=39486799992;a[8][136]=39486799993;a[8][137]=39486799994;a[8][138]=39486799995;a[8][139]=39486799996;a[8][140]=39486799997;a[8][141]=39497400000;a[8][142]=39498399989;a[8][143]=39498399990;a[8][144]=39498399991;a[8][145]=39498399992;a[8][146]=39498399993;a[8][147]=39498399994;a[8][148]=39498399995;a[8][149]=39498399996;a[8][150]=39498399997;a[8][151]=39500000000;a[8][152]=39882536171;a[8][153]=39965000000;a[8][154]=39986799989;a[8][155]=39986799990;a[8][156]=39986799991;a[8][157]=39986799992;a[8][158]=39986799993;a[8][159]=39986799994;a[8][160]=39986799995;a[8][161]=39986799996;a[8][162]=39986799997;a[8][163]=39997400000;a[8][164]=39998399989;a[8][165]=39998399990;a[8][166]=39998399991;a[8][167]=39998399992;a[8][168]=39998399993;a[8][169]=39998399994;a[8][170]=39998399995;a[8][171]=39998399996;a[8][172]=39998399997;a[8][173]=40000000000;a[8][174]=49465000000;a[8][175]=49486799989;a[8][176]=49486799990;a[8][177]=49486799991;a[8][178]=49486799992;a[8][179]=49486799993;a[8][180]=49486799994;a[8][181]=49486799995;a[8][182]=49486799996;a[8][183]=49486799997;a[8][184]=49497400000;a[8][185]=49498399989;a[8][186]=49498399990;a[8][187]=49498399991;a[8][188]=49498399992;a[8][189]=49498399993;a[8][190]=49498399994;a[8][191]=49498399995;a[8][192]=49498399996;a[8][193]=49498399997;a[8][194]=49500000000;a[8][195]=49882536171;a[8][196]=49965000000;a[8][197]=49986799989;a[8][198]=49986799990;a[8][199]=49986799991;a[8][200]=49986799992;a[8][201]=49986799993;a[8][202]=49986799994;a[8][203]=49986799995;a[8][204]=49986799996;a[8][205]=49986799997;a[8][206]=49997400000;a[8][207]=49998399989;a[8][208]=49998399990;a[8][209]=49998399991;a[8][210]=49998399992;a[8][211]=49998399993;a[8][212]=49998399994;a[8][213]=49998399995;a[8][214]=49998399996;a[8][215]=49998399997;a[8][216]=50000000000;a[8][217]=59465000000;a[8][218]=59486799989;a[8][219]=59486799990;a[8][220]=59486799991;a[8][221]=59486799992;a[8][222]=59486799993;a[8][223]=59486799994;a[8][224]=59486799995;a[8][225]=59486799996;a[8][226]=59486799997;a[8][227]=59497400000;a[8][228]=59498399989;a[8][229]=59498399990;a[8][230]=59498399991;a[8][231]=59498399992;a[8][232]=59498399993;a[8][233]=59498399994;a[8][234]=59498399995;a[8][235]=59498399996;a[8][236]=59498399997;a[8][237]=59500000000;a[8][238]=59882536171;a[8][239]=59965000000;a[8][240]=59986799989;a[8][241]=59986799990;a[8][242]=59986799991;a[8][243]=59986799992;a[8][244]=59986799993;a[8][245]=59986799994;a[8][246]=59986799995;a[8][247]=59986799996;a[8][248]=59986799997;a[8][249]=59997400000;a[8][250]=59998399989;a[8][251]=59998399990;a[8][252]=59998399991;a[8][253]=59998399992;a[8][254]=59998399993;a[8][255]=59998399994;a[8][256]=59998399995;a[8][257]=59998399996;a[8][258]=59998399997;a[8][259]=60000000000;a[8][260]=69465000000;a[8][261]=69486799989;a[8][262]=69486799990;a[8][263]=69486799991;a[8][264]=69486799992;a[8][265]=69486799993;a[8][266]=69486799994;a[8][267]=69486799995;a[8][268]=69486799996;a[8][269]=69486799997;a[8][270]=69497400000;a[8][271]=69498399989;a[8][272]=69498399990;a[8][273]=69498399991;a[8][274]=69498399992;a[8][275]=69498399993;a[8][276]=69498399994;a[8][277]=69498399995;a[8][278]=69498399996;a[8][279]=69498399997;a[8][280]=69500000000;a[8][281]=69882536171;a[8][282]=69965000000;a[8][283]=69986799989;a[8][284]=69986799990;a[8][285]=69986799991;a[8][286]=69986799992;a[8][287]=69986799993;a[8][288]=69986799994;a[8][289]=69986799995;a[8][290]=69986799996;a[8][291]=69986799997;a[8][292]=69997400000;a[8][293]=69998399989;a[8][294]=69998399990;a[8][295]=69998399991;a[8][296]=69998399992;a[8][297]=69998399993;a[8][298]=69998399994;a[8][299]=69998399995;a[8][300]=69998399996;a[8][301]=69998399997;a[8][302]=70000000000;a[8][303]=79465000000;a[8][304]=79486799989;a[8][305]=79486799990;a[8][306]=79486799991;a[8][307]=79486799992;a[8][308]=79486799993;a[8][309]=79486799994;a[8][310]=79486799995;a[8][311]=79486799996;a[8][312]=79486799997;a[8][313]=79497400000;a[8][314]=79498399989;a[8][315]=79498399990;a[8][316]=79498399991;a[8][317]=79498399992;a[8][318]=79498399993;a[8][319]=79498399994;a[8][320]=79498399995;a[8][321]=79498399996;a[8][322]=79498399997;a[8][323]=79500000000;a[8][324]=79882536171;a[8][325]=79965000000;a[8][326]=79986799989;a[8][327]=79986799990;a[8][328]=79986799991;a[8][329]=79986799992;a[8][330]=79986799993;a[8][331]=79986799994;a[8][332]=79986799995;a[8][333]=79986799996;a[8][334]=79986799997;a[8][335]=79997400000;a[8][336]=79998399989;a[8][337]=79998399990;a[8][338]=79998399991;a[8][339]=79998399992;a[8][340]=79998399993;a[8][341]=79998399994;a[8][342]=79998399995;a[8][343]=79998399996;a[8][344]=79998399997;
    a[9][1]=0;a[9][2]=10000000000;a[9][3]=20000000000;a[9][4]=30000000000;a[9][5]=40000000000;a[9][6]=50000000000;a[9][7]=60000000000;a[9][8]=70000000000;a[9][9]=80000000000;
    num[1]=84;num[2]=13;num[3]=35;num[4]=47;num[5]=5;num[6]=72;num[7]=49;num[8]=344;num[9]=9;
    int T;cin>>T;
    while(T--) solve();
}


Calabash and Landlord

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

Problem Description
Calabash is the servant of a landlord. The landlord owns a piece of land, which can be regarded as an infinite 2D plane.

One day the landlord set up two orthogonal rectangular-shaped fences on his land. He asked Calabash a simple problem: how many nonempty connected components is my land divided into by these two fences, both finite and infinite? Calabash couldn’t answer this simple question. Please help him! 

Recall that a connected component is a maximal set of points not occupied by the fences, and every two points in the set are reachable without crossing the fence.

InputThe first line of input consists of a single integer T (1≤T≤10000), the number of test cases. 

Each test case contains two lines, specifying the two rectangles. Each line contains four integers x1,y1,x2,y2 (0≤x1,y1,x2,y2≤109,x1<x2,y1<y2), where (x1,y1),(x2,y2) are the Cartesian coordinates of two opposite vertices of the rectangular fence. The edges of the rectangles are parallel to the coordinate axes. The edges of the two rectangles may intersect, overlap, or even coincide.

OutputFor each test case, print the answer as an integer in one line. 


Sample Input

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

Sample Output

3
4
2

将边延伸成无限长的直线,并删除重复的直线。因此,平面被划分为最多5×5个连接区域。对于两个相邻的区域,如果它们之间原本没有边缘,则合并这两个区域(可以使用并查集查找)。答案是联合查找中的集合数。

当然也可以暴力

#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;
int A,B,C,D,aa,bb,cc,dd;
struct node{
    int x1,y1,x2,y2;
}a,b;
void solve(){
    scanf("%d%d%d%d%d%d%d%d",&a.x1,&a.y1,&a.x2,&a.y2,&b.x1,&b.y1,&b.x2,&b.y2);
    if((a.x1==b.x1)&&(a.x2==b.x2)&&(a.y1==b.y1)&&(a.y2==b.y2)){puts("2");return;}
    if((a.x1>=b.x2)||(b.x1>=a.x2)||(b.y1>=a.y2)||(a.y1>=b.y2)){
        puts("3");return;
    }
    if((b.x1>=a.x1)&&(b.x2<=a.x2)&&(b.y1>=a.y1)&&(b.y2<=a.y2)){
        int f1=0,f2=0,f3=0,f4=0;
        if(a.x1==b.x1) f1=1;
        if(a.x2==b.x2) f2=1;
        if(a.y1==b.y1) f3=1;
        if(a.y2==b.y2) f4=1;
        if(f1&&f2&&f3==0&&f4==0){
            puts("4");return;
        }
        if(f3&&f4&&f1==0&&f2==0){
            puts("4");return;
        }
        puts("3");return;
    }
    if((a.x1>=b.x1)&&(a.x2<=b.x2)&&(a.y1>=b.y1)&&(a.y2<=b.y2)){
        int f1=0,f2=0,f3=0,f4=0;
        if(a.x1==b.x1) f1=1;
        if(a.x2==b.x2) f2=1;
        if(a.y1==b.y1) f3=1;
        if(a.y2==b.y2) f4=1;
        if(f1&&f2&&f3==0&&f4==0){
            puts("4");return;
        }
        if(f3&&f4&&f1==0&&f2==0){
            puts("4");return;
        }
        puts("3");return;
    }
    if((a.x1>=b.x1)&&(a.x2<=b.x2)&&(a.y1<=b.y1)&&(a.y2>=b.y2)){
        int f1=0,f2=0,f3=0,f4=0;
        if(a.x1==b.x1) f1=1;
        if(a.x2==b.x2) f2=1;
        if(a.y1==b.y1) f3=1;
        if(a.y2==b.y2) f4=1;
        int num=f1+f2+f3+f4;
        if(num==1){
            puts("5");return;
        }
        if(num==2){
            if((f1&&f3)||(f1&&f4)||(f2&&f3)||(f2&&f4)){
                puts("4");return;
            }
        }
        puts("6");return;
    }
    if((b.x1>=a.x1)&&(b.x2<=a.x2)&&(b.y1<=a.y1)&&(b.y2>=a.y2)){
        int f1=0,f2=0,f3=0,f4=0;
        if(a.x1==b.x1) f1=1;
        if(a.x2==b.x2) f2=1;
        if(a.y1==b.y1) f3=1;
        if(a.y2==b.y2) f4=1;
        int num=f1+f2+f3+f4;
        if(num==1){
            puts("5");return;
        }
        if(num==2){
            if((f1&&f3)||(f1&&f4)||(f2&&f3)||(f2&&f4)){
                puts("4");return;
            }
        }
        puts("6");return;
    }
    puts("4");
}
int main(){
    // freopen("/Users/edwin/Desktop/debug/in.txt","r",stdin);
    // freopen("/Users/edwin/Desktop/debug/out.txt","w",stdout);
    int T;cin>>T;
    while(T--) solve();
    // fclose(stdin); fclose(stdout);
}


Quailty and CCPC

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

Problem Description
Considering the overall difficulty of other problems, we invite Quailty to propose an easy problem for this contest.

Quailty accidentally won both gold medal and silver medal in 2017 CCPC final. The reason is explained as follows. According to the official rule, the number of gold medals was 10\% of the number of participating teams, rounded to the nearest integer. This is ambiguous when the fractional part of the result is exactly 0.5. There were 115 participating teams, and the rank of Quailty’s team was 12. The organizer originally decided to round down the number, so there were only 11 gold medals, and Quailty’s team could only win the silver medal. Many people defended him against the organizer, saying that his team deserved a gold medal. Later, the organizer changed to round up the number, and Quailty’s team finally won a gold medal.

Now, give you the scoreboard of a contest and the proportion of gold medal teams, could you determine whether there exists a team, such that they would win a gold medal were the number of gold medals rounded up when the fractional part is exactly 0.5, and silver medal if rounded down?

A team ranks before another if they solved more problems or both teams solved an equal number of problems but they had less penalty time.

(Disclaimer: the background is fictitious and the problem is prepared by Nanjing University ICPC Training Team, not Quailty.)

InputThe first line of input consists of a single integer T (1≤T≤120), denoting the number of test cases.

Each test case starts with a line of two integers n (1≤n≤105), denoting the number of participating teams, and d (0≤d≤9), denoting that the proportion of gold medal teams is 10d%. For the next n lines, each containing a string s and two integers p,t (0≤p,t≤109), denoting the name of the team, the number of problems solved and the penalty time of the team, respectively. The name of the each team contains at least 1 and at most 10 latin letters. The names are case sensitive. No two teams have the same name. No two teams have the same penalty time. The sum of n over all test cases does not exceed 106. 
OutputFor each test case, print the team name if there exists such team, or print 𝚀𝚞𝚊𝚒𝚕𝚝𝚢 𝚒𝚜 𝚟𝚎𝚛𝚢 𝚐𝚛𝚎𝚊𝚝 otherwise. It can be proved that there is at most one such team.


Sample Input

2
5 1
Ace 1000 0
Luffy 999 1
Sabo 998 2
Roronoa 997 3
Sanji 996 4
2 3
You 0 0
I 10 1

Sample Output

Ace
Quailty is very great

签到

#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;
int n,d;
struct node{
    char name[22];
    int a,b;
}p[maxn];
int cmp(node a,node b){
    if(a.a==b.a) return a.b<b.b;
    return a.a>b.a;
}
void solve(){
    scanf("%d%d",&n,&d);
    rep(i,1,n) scanf("%s%d%d",p[i].name+1,&p[i].a,&p[i].b);
    if((n*d)%10!=5){
        puts("Quailty is very great");
        return;
    }
    sort(p+1,p+1+n,cmp);
    printf("%s\n",p[(n*d+5)/10].name+1);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}


Roundgod and Milk Tea

Time Limit: 6000/6000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description
Roundgod is a famous milk tea lover at Nanjing University second to none. This year, he plans to conduct a milk tea festival. There will be n classes participating in this festival, where the ith class has ai students and will make bi cups of milk tea.

Roundgod wants more students to savor milk tea, so he stipulates that every student can taste at most one cup of milk tea. Moreover, a student can’t drink a cup of milk tea made by his class. The problem is, what is the maximum number of students who can drink milk tea? 
InputThe first line of input consists of a single integer T (1≤T≤25), denoting the number of test cases.

Each test case starts with a line of a single integer n (1≤n≤106), the number of classes. For the next n lines, each containing two integers a,b (0≤a,b≤109), denoting the number of students of the class and the number of cups of milk tea made by this class, respectively.

It is guaranteed that the sum of n over all test cases does not exceed 6×106. 
OutputFor each test case, print the answer as a single integer in one line. 

Sample Input

1
2
3 4
2 1

Sample Output

3

也是签到题呀

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
typedef long long ll;
int T;
struct node{
    ll a,b;
};
node nd[1000100];
int main(){
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        ll r=0,m=0,cnt=0;ll sr=0,sn=0;
        for(int i=1;i<=n;i++){
            scanf("%lld%lld",&nd[i].a,&nd[i].b);
            sr+=nd[i].a;
            sn+=nd[i].b;
        }
        ll ans=-1;
        for(int i=1;i<=n;i++){
            if(sr-nd[i].a<nd[i].b && sn-nd[i].b<nd[i].a){
                ans=max(ans,(sr-nd[i].a)+sn-nd[i].b);
            }
        }
        printf("%lld\n",ans==-1?min(sr,sn):ans);
    }
    return 0;
}

发表评论,支持MarkDown语法