2020牛客NOIP赛前集训营-普及组（第三场）

Powered by:AB_IN 局外人

A 牛半仙的妹子串

预处理，将每个字符串最后的字母转化为数组下标，往数组里$push\_back$对应的结构体。最后$O(1)$查询即可。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int N=1e6+10;
struct sa
{
    string s;
    int f;
    int id;
}a[N];
int n,m,k;
char x;
int cmp(const struct sa a , const struct sa b)
{
    if(a.f!=b.f) return a.f>b.f;
    else return a.id<b.id;
}
vector< sa > ans[27] ;// 结构体vector, ans[27]存26个英文字母的下标
int main()
{
    IOS;
    //freopen("data10.in","r",stdin);
    //freopen("w.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].s>>a[i].f;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        ans[a[i].s[a[i].s.size()-1]-'a'].push_back(a[i]);
    }
    for(int i=1;i<=m;i++){
        cin>>x>>k;
        if(ans[x-'a'].size()<k) cout<<"Orz YYR tql"<<endl;
        else cout<<ans[x-'a'][k-1].s<<endl;
    }
    return 0;
}

另一种写法

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int N=1e6+10;
struct sa
{
    string s;
    int f;
    int id;
    bool operator <(const sa &a) const {//这里符号都是相反的
        if(a.f!=f) return a.f<f;
        else return a.id>id;
    }
}a[N];
int n,m,k;
char x;
vector< sa > ans[27];
int main()
{
    IOS;
    //freopen("data10.in","r",stdin);
    //freopen("w.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].s>>a[i].f;
        a[i].id=i;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        ans[a[i].s[a[i].s.size()-1]-'a'].push_back(a[i]);
    }
    for(int i=1;i<=m;i++){
        cin>>x>>k;
        if(ans[x-'a'].size()<k) cout<<"Orz YYR tql"<<endl;
        else cout<<ans[x-'a'][k-1].s<<endl;
    }
    return 0;
}

还是习惯$friend$这么写。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int N=1e6+10;
struct sa
{
    string s;
    int f;
    int id;
    friend bool operator < (sa a, sa b){
        if(a.f!=b.f) return a.f>b.f;
        else return a.id<b.id;
    }
}a[N];
int n,m,k;
char x;
vector< sa > ans[27];
int main()
{
    IOS;
    //freopen("data10.in","r",stdin);
    //freopen("w.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].s>>a[i].f;
        a[i].id=i;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        ans[a[i].s[a[i].s.size()-1]-'a'].push_back(a[i]);
    }
    for(int i=1;i<=m;i++){
        cin>>x>>k;
        if(ans[x-'a'].size()<k) cout<<"Orz YYR tql"<<endl;
        else cout<<ans[x-'a'][k-1].s<<endl;
    }
    return 0;
}

B 牛半仙的妹子gcd

强推无脑打表法，用最普通的$70$分做法打上个$10mins$足够了。

$50$分
嵌套$gcd$是真的慢。

#include <bits/stdc++.h>

using namespace std;
int n,ans;
int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}
int main()
{
    //freopen("pjT2","r",stdin);
    //freopen("w.txt","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                ans+=gcd(k,gcd(i,j));
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

$70$分

#include <bits/stdc++.h>

using namespace std;
int n,ans;
int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}
int main()
{
    //freopen("pjT2","r",stdin);
    //freopen("w.txt","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x=gcd(i,j);//要早定义！！！不然只有50分
            for(int k=1;k<=n;k++){
                ans+=gcd(k,x);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

$100$分

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005]={0,1,9,30,76,141,267,400,624,885,1249,1590,2208,2689,3411,4248,5248,6081,7485,8530,10248,11889,13687,15228,17988,20053,22569,25242,28588,31053,35463,38284,42540,46581,50893,55362,61824,65857,71247,76884,84388,89349,97881,103342,111528,120141,128047,134580,146316,154177,164817,174438,185836,194157,207927,218812,233268,245277,257857,268182,288216,299257,313635,330204,347836,362973,383709,397042,416448,434025,456967,471948,499740,515581,536073,559758,583960,604833,633651,652216,683712,709065,734233,754734,793188,818917,846603,874512,909496,933081,977145,1006126,1041504,1073385,1106467,1138536,1187112,1215145,1255101,1295142,1342852,1373253,1422195,1453816,1502376,1553361,1595437,1629570,1691292,1726717,1782111,1827492,1887772,1925853,1986837,2033674,2089776,2145333,2197483,2246640,2332104,2379085,2434833,2490534,2554600,2609625,2693919,2742052,2813988,2875245,2952085,3003306,3096024,3157249,3224511,3306240,3388576,3444609,3533637,3591322,3693924,3767085,3842623,3912324,4027884,4102093,4181949,4270422,4361548,4427853,4548003,4616104,4718640,4812789,4918561,5003286,5131848,5205481,5299011,5392008,5521384,5610705,5739009,5818390,5930196,6052893,6156139,6239472,6402720,6493681,6623853,6741078,6864016,6953457,7094451,7215016,7359936,7475145,7593865,7689630,7886244,7984165,8130747,8253888,8403448,8523897,8684853,8802826,8949612,9105537,9267595,9376656,9574704,9686065,9827097,9997134,10174780,10290813,10493367,10611772,10813692,10962213,11115121,11256486,11474160,11621905,11780931,11951868,12152644,12299469,12557589,12690730,12877248,13044009,13215631,13378068,13639212,13800565,13978665,14154942,14401360,14564721,14793483,14942224,15188880,15419685,15611101,15765234,16036176,16193041,16429311,16663212,16899868,17062269,17342853,17536762,17767764,17974173,18222175,18393060,18746652,18920413,19157001,19390038,19636924,19871697,20152263,20355532,20625636,20853453,21130753,21319254,21694104,21908065,22149867,22437552,22728496,22926129,23234577,23463814,23805108,24075513,24332791,24539772,24931452,25177789,25486401,25748310,26046016,26262561,26675175,26894956,27234516,27558429,27839821,28128786,28523688,28753321,29042991,29351592,29785072,30021393,30389565,30629266,30963492,31321485,31672711,31953804,32425836,32688877,33062565,33373626,33726904,33983865,34429779,34734808,35118504,35492157,35825017,36121134,36654504,36963505,37305363,37642584,38065072,38391057,38865501,39147634,39616920,39967617,40394071,40683612,41225940,41519221,41888793,42384162,42797764,43098597,43566255,43904500,44429652,44808093,45257725,45601170,46169952,46569937,46968303,47361012,47831476,48200253,48818913,49146934,49603392,50041701,50459863,50852892,51526308,51866341,52323525,52745562,53322544,53708505,54298779,54698668,55215828,55737405,56186161,56546694,57171096,57535801,58143171,58660356,59251012,59624133,60203157,60644362,61169064,61716561,62196991,62582916,63412356,63821065,64312293,64834254,65483848,65950185,66568971,66972304,67587720,68125101,68730733,69199074,69911592,70328233,70921695,71533620,72150796,72618765,73404141,73834306,74552100,75085101,75632119,76071420,76872060,77491909,78050445,78641142,79264228,79717413,80573763,81073864,81821688,82388769,82970701,83516610,84414252,84886285,85480095,86161164,86992564,87474165,88220157,88754098,89429544,90180657,90891319,91439292,92355780,92856805,93599289,94219470,94921888,95501673,96361407,96963844,97781220,98419629,99157789,99683634,100827984,101358865,102026463,102731352,103515112,104190777,105028173,105647746,106405692,107180709,107996839,108553260,109628292,110189893,111000765,111825138,112611640,113233569,114118647,114695932,115733556,116587773,117408865,117996726,119008440,119700889,120446595,121180104,122179048,122782953,123944493,124616194,125461392,126214713,126987415,127845180,128985180,129610813,130397193,131270778,132316132,132952773,134129775,134771956,135744444,136685061,137499157,138152490,139394688,140141545,141115407,141929748,142899964,143638245,144674289,145514614,146611944,147507021,148363591,149050956,150490956,151248877,152119845,153111618,154157344,154979553,156150327,156860860,157897644,158775381,159955693,160677954,161918172,162708157,163729311,164914584,166024144,166862457,168005745,168751750,169977900,170899221,171843979,172602000,174180024,175071289,176146005,177153882,178221148,178997373,180443943,181329964,182500908,183587361,184577833,185504670,186867852,187748725,188899827,189888504,191324248,192137529,193495953,194315494,195450960,196790985,197828251,198729504,200340360,201212221,202448781,203556726,204921484,205850445,207164499,208164568,209414304,210472713,211557853,212625654,214451880,215328841,216430179,217512360,218892616,219930345,221558841,222455374,223697100,224881041,226333231,227315508,228975396,230012461,231163113,232498398,233776600,234706233,236256087,237277084,239059956,240368637,241552765,242502546,244129080,245244217,246445263,247873212,249275956,250246101,252045201,253022182,254575080,255780081,257191003,258414288,260324016,261321649,262640985,263871342,265522876,266667237,268227459,269345800,270828360,272468205,273755641,274788174,276759864,277880449,279411027,280692888,282267808,283321569,285199149,286647586,288116088,289424097,290910535,291985740,294228660,295311061,296861793,298288842,299796988,301176993,302868219,303972352,305688768,307255497,308891041,310109142,312206772,313332853,314746275,316382952,318355768,319496601,321255309,322403554,324287772,325869297,327319795,328635000,330863472,332262097,333731313,335358702,336988948,338267925,340758567,341951788,343687044,345157485,346664497,348072486,350137608,351614461,353311911,354913632,357031264,358262625,360160257,361399318,363386052,365184909,366908491,368163024,370552848,371936953,373945653,375733074,377490172,378768093,380737167,382235092,384165372,385858209,387708361,389009886,391745940,393055381,394698459,396508512,398423272,400224465,402424209,403853638,405697944,407340321,409311643,410790624,413528256,414885697,416588889,418726074,420744376,422118009,424233927,425795404,428219484,429921285,431857753,433255854,435864360,437502409,439508175,441240084,443361580,444907917,447526917,448957978,450937056,453190125,454995907,456682056,459303936,460871329,462697989,464490906,467175676,468648477,471245499,472835584,475222176,477368361,479237137,480929670,483485652,484992277,487204851,489186156,491386732,493017333,495766617,497816014,499934616,501821025,503753875,505303320,508711584,510471625,512520357,514438458,516604624,518536449,521155395,522739528,525468336,527583165,529921585,531644166,534375384,535985785,538005747,540607836,543106012,544888485,547584489,549221374,551895516,554146149,556494931,558149592,561140712,563077801,565164357,567350574,569971720,571870737,574941987,576632488,579163488,581244009,583591273,585580638,589051812,590769445,592923675,595292232,598306528,600042369,602713821,604684306,607096212,609864441,612064387,613978056,617199432,618971977,622084809,624265950,626728588,628519629,631482663,633686428,636299004,638835621,641105041,643053606,646838160,648838681,651346923,653844396,656913364,659063733,661905789,663762322,666328008,668612145,671348983,673466364,677237076,679281877,681645609,684370206,686988208,688892241,692310819,694365736,697741896,700254381,702665989,704780250,708072024,710693569,713371215,715760724,718592548,720554373,724324761,726296302,729433800,731858961,734606803,736924440,740685936,742827385,745336185,748452354,751729672,753750153,756858015,758888356,761833116,765034101,767940913,769991046,773787624,775847689,778867539,781401240,784701688,787193709,790392813,792825442,796084464,798933477,801566467,803676552,808484712,810673081,813331269,815938650,818881636,821544309,825079203,827700316,830913252,833557869,836947789,839261250,842955768,845136889,848242911,851684952,854862208,857063841,860953389,863165314,866767188,869875869,872661847,874894428,879259356,881869693,884681589,887587722,891166888,893641233,897777183,900241444,903538260,906521049,909639373,912713298,916617900,918923533,921813903,924648660,928907596,931234317,935520837,937858138,941482752,944854665,947797951,950156484,954401052,957074149,960544617,963954150,967241128,969795633,973470747,976265056,980287968,983563113,986586673,989160678,994291668,996899989,1000267347,1003683840,1007226400,1010083425,1013857701,1016323834,1019729700,1022962761,1027267771,1029755712,1034432616,1037162737,1040295009,1043898006,1047364108,1050207861,1054590447,1057122292,1061509116,1064621157,1067808505,1070574126,1075773120,1078899985,1082115051,1085477028,1089421444,1092008709,1096726869,1099825006,1103413164,1106606805,1109877667,1113335976,1118550792,1121182825,1124926077,1128160914,1132457836,1135112397,1139192079,1142026900,1146002988,1150583457,1154284153,1156972686,1161542388,1164465205,1168679835,1171997856,1176602968,1179325689,1183812873,1186993918,1190769120,1194508809,1197949939,1201059576,1206875160,1209727501,1213526613,1217153982,1220992588,1224240525,1229215491,1232018824,1236404568,1240201857,1244321869,1247148450,1252315116,1255516021,1259073063,1263499548,1267748068,1270609701,1275006669,1278144034,1283354904,1287118749,1290734467,1293631368,1298833008,1302216817,1306176549,1310252226,1314758548,1317873885,1323822579,1326766840,1331266296,1334883777,1339084849,1342537638,1347579780,1350559813,1354294323,1358336628,1363480228};
int main()
{
    cin>>n;
    cout<<a[n]<<endl;
}

另
$$gcd(i,j,k)=gcd(gcd(i,j),k)$$第一个循环，先枚举$i,j$，算出每个$gcd(i,j)$的出现次数。
第二个循环，枚举的$i$实际上就是上一个循环的$gcd(i,j)$，然后枚举$k$，让$i$和$k$再$gcd$，再乘上贡献，加和即可。

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[1010];
int main()
{
    cin>>n;
    for(int i = 1; i <= n; i++ ){
        for(int j = 1;j <= n; j++){
            a[__gcd(i,j)]++;
        }
    }
    for(int i = 1; i <= n; i++ ){
        for(int k = 1;k <= n; k++){
            ans+= a[i]* __gcd(i,k); 
        }
    }
    cout<<ans<<endl;
}

完结。