[关闭]
@baobaobear 2020-04-19T10:54:17.000000Z 字数 40495 阅读 392

Contest 24

contest

A 1292224662

  1. #include<iostream>
  2. #include<set>
  3. #include<cstring>
  4. using namespace std;
  5. #define rep(i,a,n) for(int i=a;i<=n;i++)
  6. #define per(i,a,n) for(int i=n;i>=a;i--)
  7. #define pb push_back
  8. #define SZ(x) ((int)(x).size())
  9. typedef long long ll;
  10. typedef pair<int,int> pii;
  11. typedef double db;
  13. set<char> st[4];
  14. int cnt[4];
  15. char s[60];
  16. int main(){
  17.     int t;
  18.     cin>>t;
  19.     rep(i,0,25){
  20.         st[0].insert('a'+i);
  21.         st[1].insert('A'+i);
  22.     }
  23.     rep(i,0,9)  st[2].insert('0'+i);
  24.     st[3].insert('~');st[3].insert('%');
  25.     st[3].insert('!');st[3].insert('^');
  26.     st[3].insert('@');st[3].insert('$');
  27.     st[3].insert('#');
  28.     while(t--){
  29.         cin>>(s+1);
  30.         int len=strlen(s+1);
  31.         rep(i,0,3)  cnt[i]=0;
  32.         rep(i,1,len){
  33.             rep(j,0,3){
  34.                 if(st[j].find(s[i])!=st[j].end()){
  35.                     cnt[j]=1;
  36.                 }
  37.             }
  38.         }
  39.         if(len>=8&&len<=16&&(cnt[0]+cnt[1]+cnt[2]+cnt[3])>=3){
  40.             puts("YES");
  41.         }
  42.         else{
  43.             puts("NO");
  44.         }
  45.     }
  46.     return 0;
  47. }

B 1292224662

  1. #include<iostream>
  2. using namespace std;
  3. #define rep(i,a,n) for(int i=a;i<=n;i++)
  4. #define per(i,a,n) for(int i=n;i>=a;i--)
  5. #define pb push_back
  6. #define SZ(x) ((int)(x).size())
  7. typedef long long ll;
  8. typedef pair<int,int> pii;
  9. typedef double db;
  10. ll x,mod=10000;
  11. int main(){
  12.     while(~scanf("%lld",&x)){
  13.         x%=mod;
  14.         x=x*(x+1)/2;
  15.         x%=mod;
  16.         x=x*x%mod;
  17.         printf("%04lld\n",x);
  18.     }
  19.     return 0;
  20. }

C 1292224662

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for(int i=a;i<=n;i++)
  4. #define per(i,a,n) for(int i=n;i>=a;i--)
  5. #define pb push_back
  6. #define SZ(x) ((int)(x).size())
  7. typedef long long ll;
  8. typedef pair<int,int> pii;
  9. typedef double db;
  10. int n,k,x[100010];
  11. int solve(int l,int r){
  12.     if(l<0&&r<0)    return -l;
  13.     if(l>0&&r>0)    return r;
  14.     return r-l+min(-l,r);
  15. }
  16. int ans=1e9;
  17. int main(){
  18.     cin>>n>>k;k--;
  19.     rep(i,1,n)  scanf("%d",x+i);
  20.     rep(i,1,n-k){
  21.         ans=min(ans,solve(x[i],x[i+k]));    
  22.     }
  23.     cout<<ans<<endl;
  24.     return 0;
  25. }

D yingyingying777

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int INF=0x3f3f3f3f;
  5. const int N=1e6;
  6. int sum[N+5];
  7. bool check(int x)
  8. {
  9.     bool flag=false;
  10.     while(x)
  11.     {
  12.         int temp=x%10;
  13.         if(temp==6&&flag)
  14.             return false;
  15.         flag=false;
  16.         if(temp==4)
  17.             return false;
  18.         if(temp==2)
  19.             flag=true;
  20.         x/=10;
  21.     }
  22.     return true;
  23. }
  25. void maketable()
  26. {
  27.     for(int i=1;i<=N;++i)
  28.     {
  29.         if(check(i))
  30.             sum[i]=sum[i-1]+1;
  31.         else
  32.             sum[i]=sum[i-1];
  33.     }
  34. }
  35. int main()
  36. {
  37.     int n,m;
  38.     maketable();
  39.     while(scanf("%d%d",&n,&m)!=EOF)
  40.     {
  41.         if(!n&&!m)
  42.             break;
  43.         else
  44.             printf("%d\n",sum[m]-sum[n-1]);
  45.     }
  46.     return 0;
  47. }

E Kevin7Zz

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <queue> //priority_queue
  6. #include <map>
  7. #include <set> //multiset set<int,greater<int>>大到小
  8. #include <vector>// vector<int>().swap(v);清空释放内存
  9. #include <stack>
  10. #include <cmath> // auto &Name : STLName  Name.
  11. #include <utility>
  12. #include <sstream>
  13. #include <string>//__builtin_popcount(ans);//获取某个数二进制位1的个数
  14. #define mod 1000000007
  15. #define mod9 998244353
  16. typedef unsigned long long ull;
  17. typedef long long ll;
  18. typedef double db;
  19. typedef long double ld;
  20. const db eps=1e-10;
  21. const int INF = 0x3f3f3f3f;
  22. const ll inf=0x3f3f3f3f3f3f3f3f;
  23. #define rep(i,be,en) for (ll i=be;i<=en;i++)
  24. #define per(i,be,en) for (int i=en;i>=be;i--)
  25. //ll ksm(ll a,ll b,ll c){ll ans=1;a=a%c;while(b>0){if(b%2) ans=(ans*a)%c;b=b/2;a=(a*a)%c;}return ans;}
  26. using namespace std;
  28. const int N=2e5+7;
  29. int t,n,k,fl=0;
  30. char s[N]={0};
  32. bool check(int x){
  33.     int y=0;
  34.     for(int i=1;i<=n;i++){
  35.         if(s[i]=='1'){
  36.             i+=x-1;
  37.             y++;
  38.             if(i>n) break;
  39.         }
  40.     }
  41.     if(y<=k) return true;
  42.     else return false;
  43. }
  45. int main(){
  46.     scanf("%d",&t);
  47.     while(t--){
  48.         scanf("%d%d",&n,&k);
  49.         scanf("%s",s+1);
  50.         int l=1,r=n,m;
  51.         while(l<r){
  52.             m=(l+r)>>1;
  53.             if(check(m)) r=m;
  54.             else l=m+1;
  55.         }
  56.         m=(l+r)>>1;
  57.         printf("%d\n",m);
  58.     }
  61.     return 0;
  62. }

F 1292224662

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for(int i=a;i<=n;i++)
  4. #define per(i,a,n) for(int i=n;i>=a;i--)
  5. #define pb push_back
  6. #define SZ(x) ((int)(x).size())
  7. typedef long long ll;
  8. typedef pair<int,int> pii;
  9. typedef double db;
  10. map<ll,ll> mp;
  11. ll n,a[200010],dp[32][200010];
  12. int fa[32][200010],ans[200010],p;
  13. int main(){
  14.     cin>>n;
  15.     rep(i,1,n){
  16.         scanf("%lld",a+i);  
  17.     }sort(a+1,a+1+n);
  18.     rep(i,1,n){
  19.         mp[a[i]]=i;
  20.     }
  21.     ll del,to;
  22.     rep(i,0,30){
  23.         del=(1ll<<(ll)i);
  24.         rep(j,1,n){
  25.             to=(ll)a[j]-del;
  26.             if(mp.count(to)&&dp[i][mp[to]]+1>dp[i][j]){
  27.                 dp[i][j]=dp[i][mp[to]]+1;
  28.                 fa[i][j]=mp[to];
  29.             }
  30.             if(dp[i][j]==0){
  31.                 dp[i][j]=1;
  32.                 fa[i][j]=j;
  33.             }
  34.         }
  35.     }
  36.     int mx=0,nowi,nowj;
  37.     rep(i,0,30){
  38.         rep(j,1,n){
  39.             if(dp[i][j]>mx){
  40.                 mx=dp[i][j];
  41.                 nowi=i;nowj=j;
  42.             }
  43.         }
  44.     }
  45.     while(fa[nowi][nowj]!=nowj){
  46.         ans[++p]=a[nowj];
  47.         nowj=fa[nowi][nowj];
  48.     }ans[++p]=a[nowj];
  49.     mx=min(3,mx);
  50.     printf("%d\n",mx);
  51.     rep(i,1,mx){
  52.         printf("%d%c",ans[i],(i==p)?'\n':' ');
  53.     }
  54.     return 0;
  55. }

G yingyingying777

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int INF=0x3f3f3f3f;
  5. vector<int> vv;
  6. vector<int> v={10000000,10001880,10035200,10077696,10080000,10084200,10125000,10160640,10206000,10240000,10287648,10290000,10321920,10333575,10368000,10372320,10418625,10450944,10485760,10497600,10500000,10501974,10504375,10536960,10546875,10584000,10588410,10616832,10628820,10631250,10668672,10716300,10718750,10752000,10756480,10800000,10804500,10838016,10886400,10890936,10935000,10937500,10976000,11010048,11022480,11025000,11059200,11063808,11113200,11160261,11197440,11200000,11239424,11250000,11252115,11289600,11294304,11337408,11340000,11344725,11390625,11430720,11468800,11481750,11484375,11520000,11524800,11529602,11573604,11576250,11612160,11664000,11668860,11718750,11757312,11760000,11764900,11796480,11809800,11812500,11854080,11907000,11943936,12000000,12002256,12005000,12042240,12096000,12101040,12150000,12192768,12247200,12250000,12252303,12288000,12293120,12301875,12348000,12353145,12386304,12400290,12403125,12441600,12446784,12500000,12502350,12544000,12582912,12597120,12600000,12605250,12644352,12656250,12700800,12706092,12754584,12757500,12800000,12845056,12859560,12862500,12902400,12907776,12960000,12965400,13063680,13107200,13122000,13125000,13171200,13176688,13226976,13230000,13271040,13286025,13335840,13395375,13436928,13440000,13445600,13500000,13502538,13505625,13547520,13608000,13613670,13668750,13671875,13716864,13720000,13762560,13778100,13781250,13824000,13829760,13891500,13934592,13996800,14000000,14002632,14049280,14062500,14112000,14117880,14155776,14171760,14175000,14224896,14288400,14336000,14348907,14400000,14406000,14450688,14467005,14515200,14521248,14580000,14586075,14680064,14696640,14700000,14706125,14745600,14751744,14762250,14765625,14817600,14823774,14880348,14883750,14929920,15000000,15002820,15006250,15052800,15059072,15116544,15120000,15126300,15187500,15240960,15309000,15312500,15360000,15366400,15431472,15435000,15482880,15552000,15558480,15625000,15676416,15680000,15728640,15746400,15750000,15752961,15805440,15876000,15882615,15925248,15943230,15946875,16000000,16003008,16056320,16074450,16078125,16128000,16134720,16200000,16206750,16257024,16329600,16336404,16384000,16402500,16406250,16464000,16470860,16515072,16533720,16537500,16588800,16595712,16669800,16777216,16796160,16800000,16807000,16859136,16875000,16934400,16941456,17006112,17010000,17146080,17150000,17203200,17210368,17222625,17280000,17287200,17294403,17360406,17364375,17418240,17496000,17500000,17503290,17561600,17578125,17635968,17640000,17647350,17694720,17714700,17718750,17781120,17860500,17915904,17920000,18000000,18003384,18007500,18063360,18144000,18151560,18225000,18289152,18350080,18370800,18375000,18432000,18439680,18522000,18579456,18600435,18662400,18670176,18750000,18753525,18816000,18823840,18874368,18895680,18900000,18907875,18966528,18984375,19051200,19059138,19131876,19136250,19140625,19200000,19208000,19267584,19289340,19293750,19353600,19361664,19440000,19448100,19531250,19595520,19600000,19660800,19668992,19683000,19687500,19756800,19765032,19840464,19845000,19906560,20000000,20003760,20070400,20155392,20160000,20168400,20250000,20253807,20321280,20412000,20420505,20480000,20503125,20575296,20580000,20588575,20643840,20667150,20671875,20736000,20744640,20837250,20901888,20971520,20995200,21000000,21003948,21008750,21073920,21093750,21168000,21176820,21233664,21257640,21262500,21337344,21432600,21437500,21504000,21512960,21600000,21609000,21676032,21772800,21781872,21870000,21875000,21952000,22020096,22044960,22050000,22118400,22127616,22143375,22226400,22235661,22320522,22325625,22394880,22400000,22478848,22500000,22504230,22509375,22579200,22588608,22674816,22680000,22689450,22781250,22861440,22937600,22963500,22968750,23040000,23049600,23059204,23147208,23152500,23224320,23328000,23337720,23437500,23514624,23520000,23529800,23592960,23619600,23625000,23708160,23814000,23887872,23914845,24000000,24004512,24010000,24084480,24111675,24192000,24202080,24300000,24310125,24385536,24494400,24500000,24504606,24576000,24586240,24603750,24609375,24696000,24706290,24772608,24800580,24806250,24883200,24893568,25000000,25004700,25088000,25165824,25194240,25200000,25210500,25288704,25312500,25401600,25412184,25509168,25515000,25600000,25690112,25719120,25725000,25804800,25815552,25920000,25930800,26040609,26127360,26214400,26244000,26250000,26254935,26342400,26353376,26453952,26460000,26471025,26542080,26572050,26578125,26671680,26790750,26796875,26873856,26880000,26891200,27000000,27005076,27011250,27095040,27216000,27227340,27337500,27343750,27433728,27440000,27525120,27556200,27562500,27648000,27659520,27783000,27869184,27993600,28000000,28005264,28098560,28125000,28224000,28235760,28311552,28343520,28350000,28449792,28576800,28588707,28672000,28697814,28704375,28800000,28812000,28824005,28901376,28934010,28940625,29030400,29042496,29160000,29172150,29296875,29360128,29393280,29400000,29412250,29491200,29503488,29524500,29531250,29635200,29647548,29760696,29767500,29859840,30000000,30005640,30012500,30105600,30118144,30233088,30240000,30252600,30375000,30481920,30618000,30625000,30720000,30732800,30862944,30870000,30965760,31000725,31104000,31116960,31250000,31255875,31352832,31360000,31457280,31492800,31500000,31505922,31513125,31610880,31640625,31752000,31765230,31850496,31886460,31893750,32000000,32006016,32112640,32148900,32156250,32256000,32269440,32400000,32413500,32514048,32659200,32672808,32768000,32805000,32812500,32928000,32941720,33030144,33067440,33075000,33177600,33191424,33339600,33480783,33554432,33592320,33600000,33614000,33718272,33750000,33756345,33868800,33882912,34012224,34020000,34034175,34171875,34292160,34300000,34406400,34420736,34445250,34453125,34560000,34574400,34588806,34720812,34728750,34836480,34992000,35000000,35006580,35123200,35156250,35271936,35280000,35294700,35389440,35429400,35437500,35562240,35721000,35831808,35840000,36000000,36006768,36015000,36126720,36288000,36303120,36450000,36578304,36700160,36741600,36750000,36756909,36864000,36879360,36905625,37044000,37059435,37158912,37200870,37209375,37324800,37340352,37500000,37507050,37515625,37632000,37647680,37748736,37791360,37800000,37815750,37933056,37968750,38102400,38118276,38263752,38272500,38281250,38400000,38416000,38535168,38578680,38587500,38707200,38723328,38880000,38896200,39062500,39191040,39200000,39321600,39337984,39366000,39375000,39513600,39530064,39680928,39690000,39813120,39858075,40000000,40007520,40140800,40186125,40310784,40320000,40336800,40353607,40500000,40507614,40516875,40642560,40824000,40841010,40960000,41006250,41015625,41150592,41160000,41177150,41287680,41334300,41343750,41472000,41489280,41674500,41803776,41943040,41990400,42000000,42007896,42017500,42147840,42187500,42336000,42353640,42467328,42515280,42525000,42674688,42865200,42875000,43008000,43025920,43046721,43200000,43218000,43352064,43401015,43545600,43563744,43740000,43750000,43758225,43904000,44040192,44089920,44100000,44118375,44236800,44255232,44286750,44296875,44452800,44471322,44641044,44651250,44789760,44800000,44957696,45000000,45008460,45018750,45158400,45177216,45349632,45360000,45378900,45562500,45722880,45875200,45927000,45937500,46080000,46099200,46118408,46294416,46305000,46448640,46656000,46675440,46875000,47029248,47040000,47059600,47185920,47239200,47250000,47258883,47416320,47628000,47647845,47775744,47829690,47840625,48000000,48009024,48020000,48168960,48223350,48234375,48384000,48404160,48600000,48620250,48771072,48828125,48988800,49000000,49009212,49152000,49172480,49207500,49218750,49392000,49412580,49545216,49601160,49612500,49766400,49787136,50000000,50009400,50176000,50331648,50388480,50400000,50421000,50577408,50625000,50803200,50824368,51018336,51030000,51200000,51380224,51438240,51450000,51609600,51631104,51667875,51840000,51861600,51883209,52081218,52093125,52254720,52428800,52488000,52500000,52509870,52521875,52684800,52706752,52734375,52907904,52920000,52942050,53084160,53144100,53156250,53343360,53581500,53593750,53747712,53760000,53782400,54000000,54010152,54022500,54190080,54432000,54454680,54675000,54687500,54867456,54880000,55050240,55112400,55125000,55296000,55319040,55566000,55738368,55801305,55987200,56000000,56010528,56197120,56250000,56260575,56448000,56471520,56623104,56687040,56700000,56723625,56899584,56953125,57153600,57177414,57344000,57395628,57408750,57421875,57600000,57624000,57648010,57802752,57868020,57881250,58060800,58084992,58320000,58344300,58593750,58720256,58786560,58800000,58824500,58982400,59006976,59049000,59062500,59270400,59295096,59521392,59535000,59719680,60000000,60011280,60025000,60211200,60236288,60466176,60480000,60505200,60750000,60761421,60963840,61236000,61250000,61261515,61440000,61465600,61509375,61725888,61740000,61765725,61931520,62001450,62015625,62208000,62233920,62500000,62511750,62705664,62720000,62914560,62985600,63000000,63011844,63026250,63221760,63281250,63504000,63530460,63700992,63772920,63787500,64000000,64012032,64225280,64297800,64312500,64512000,64538880,64800000,64827000,65028096,65318400,65345616,65536000,65610000,65625000,65856000,65883440,66060288,66134880,66150000,66355200,66382848,66430125,66679200,66706983,66961566,66976875,67108864,67184640,67200000,67228000,67436544,67500000,67512690,67528125,67737600,67765824,68024448,68040000,68068350,68343750,68359375,68584320,68600000,68812800,68841472,68890500,68906250,69120000,69148800,69177612,69441624,69457500,69672960,69984000,70000000,70013160,70246400,70312500,70543872,70560000,70589400,70778880,70858800,70875000,71124480,71442000,71663616,71680000,71744535,72000000,72013536,72030000,72253440,72335025,72576000,72606240,72900000,72930375,73156608,73400320,73483200,73500000,73513818,73530625,73728000,73758720,73811250,73828125,74088000,74118870,74317824,74401740,74418750,74649600,74680704,75000000,75014100,75031250,75264000,75295360,75497472,75582720,75600000,75631500,75866112,75937500,76204800,76236552,76527504,76545000,76562500,76800000,76832000,77070336,77157360,77175000,77414400,77446656,77760000,77792400,78121827,78125000,78382080,78400000,78643200,78675968,78732000,78750000,78764805,79027200,79060128,79361856,79380000,79413075,79626240,79716150,79734375,80000000,80015040,80281600,80372250,80390625,80621568,80640000,80673600,80707214,81000000,81015228,81033750,81285120,81648000,81682020,81920000,82012500,82031250,82301184,82320000,82354300,82575360,82668600,82687500,82944000,82978560,83349000,83607552,83886080,83980800,84000000,84015792,84035000,84295680,84375000,84672000,84707280,84934656,85030560,85050000,85349376,85730400,85750000,85766121,86016000,86051840,86093442,86113125,86400000,86436000,86472015,86704128,86802030,86821875,87091200,87127488,87480000,87500000,87516450,87808000,87890625,88080384,88179840,88200000,88236750,88473600,88510464,88573500,88593750,88905600,88942644,89282088,89302500,89579520,89600000,89915392,90000000,90016920,90037500,90316800,90354432,90699264,90720000,90757800,91125000,91445760,91750400,91854000,91875000,92160000,92198400,92236816,92588832,92610000,92897280,93002175,93312000,93350880,93750000,93767625,94058496,94080000,94119200,94371840,94478400,94500000,94517766,94539375,94832640,94921875,95256000,95295690,95551488,95659380,95681250,95703125,96000000,96018048,96040000,96337920,96446700,96468750,96768000,96808320,97200000,97240500,97542144,97656250,97977600,98000000,98018424,98304000,98344960,98415000,98437500,98784000,98825160,99090432,99202320,99225000,99532800,99574272,100000000,100018800,100352000,100442349,100663296,100776960,100800000,100842000,101154816,101250000,101269035,101606400,101648736,102036672,102060000,102102525,102400000,102515625,102760448,102876480,102900000,102942875,103219200,103262208,103335750,103359375,103680000,103723200,103766418,104162436,104186250,104509440,104857600,104976000,105000000,105019740,105043750,105369600,105413504,105468750,105815808,105840000,105884100,106168320,106288200,106312500,106686720,107163000,107187500,107495424,107520000,107564800,108000000,108020304,108045000,108380160,108864000,108909360,109350000,109375000,109734912,109760000,110100480,110224800,110250000,110270727,110592000,110638080,110716875,111132000,111178305,111476736,111602610,111628125,111974400,112000000,112021056,112394240,112500000,112521150,112546875,112896000,112943040,113246208,113374080,113400000,113447250,113799168,113906250,114307200,114354828,114688000,114791256,114817500,114843750,115200000,115248000,115296020,115605504,115736040,115762500,116121600,116169984,116640000,116688600,117187500,117440512,117573120,117600000,117649000,117964800,118013952,118098000,118125000,118540800,118590192,119042784,119070000,119439360,119574225,120000000,120022560,120050000,120422400,120472576,120558375,120932352,120960000,121010400,121060821,121500000,121522842,121550625,121927680,122472000,122500000,122523030,122880000,122931200,123018750,123046875,123451776,123480000,123531450,123863040,124002900,124031250,124416000,124467840,125000000,125023500,125411328,125440000,125829120,125971200,126000000,126023688,126052500,126443520,126562500,127008000,127060920,127401984,127545840,127575000,128000000,128024064,128450560,128595600,128625000,129024000,129077760,129140163,129600000,129654000,130056192,130203045,130636800,130691232,131072000,131220000,131250000,131274675,131712000,131766880,132120576,132269760,132300000,132355125,132710400,132765696,132860250,132890625,133358400,133413966,133923132,133953750,133984375,134217728,134369280,134400000,134456000,134873088,135000000,135025380,135056250,135475200,135531648,136048896,136080000,136136700,136687500,136718750,137168640,137200000,137625600,137682944,137781000,137812500,138240000,138297600,138355224,138883248,138915000,139345920,139968000,140000000,140026320,140492800,140625000,141087744,141120000,141178800,141557760,141717600,141750000,141776649,142248960,142884000,142943535,143327232,143360000,143489070,143521875,144000000,144027072,144060000,144120025,144506880,144670050,144703125,145152000,145212480,145800000,145860750,146313216,146484375,146800640,146966400,147000000,147027636,147061250,147456000,147517440,147622500,147656250,148176000,148237740,148635648,148803480,148837500,149299200,149361408,150000000,150028200,150062500,150528000,150590720,150994944,151165440,151200000,151263000,151732224,151875000,152409600,152473104,153055008,153090000,153125000,153600000,153664000,154140672,154314720,154350000,154828800,154893312,155003625,155520000,155584800,155649627,156243654,156250000,156279375,156764160,156800000,157286400,157351936,157464000,157500000,157529610,157565625,158054400,158120256,158203125,158723712,158760000,158826150,159252480,159432300,159468750,160000000,160030080,160563200,160744500,160781250,161243136,161280000,161347200,161414428,162000000,162030456,162067500,162570240,163296000,163364040,163840000,164025000,164062500,164602368,164640000,164708600,165150720,165337200,165375000,165888000,165957120,166698000,167215104,167403915,167772160,167961600,168000000,168031584,168070000,168591360,168750000,168781725,169344000,169414560,169869312,170061120,170100000,170170875,170698752,170859375,171460800,171500000,171532242,172032000,172103680,172186884,172226250,172265625,172800000,172872000,172944030,173408256,173604060,173643750,174182400,174254976,174960000,175000000,175032900,175616000,175781250,176160768,176359680,176400000,176473500,176947200,177020928,177147000,177187500,177811200,177885288,178564176,178605000,179159040,179200000,179830784,180000000,180033840,180075000,180633600,180708864,181398528,181440000,181515600,182250000,182284263,182891520,183500800,183708000,183750000,183784545,184320000,184396800,184473632,184528125,185177664,185220000,185297175,185794560,186004350,186046875,186624000,186701760,187500000,187535250,187578125,188116992,188160000,188238400,188743680,188956800,189000000,189035532,189078750,189665280,189843750,190512000,190591380,191102976,191318760,191362500,191406250,192000000,192036096,192080000,192675840,192893400,192937500,193536000,193616640,194400000,194481000,195084288,195312500,195955200,196000000,196036848,196608000,196689920,196830000,196875000,197568000,197650320,198180864,198404640,198450000,199065600,199148544,199290375,200000000,200037600,200120949,200704000,200884698,200930625,201326592,201553920,201600000,201684000,201768035,202309632,202500000,202538070,202584375,203212800,203297472,204073344,204120000,204205050,204800000,205031250,205078125,205520896,205752960,205800000,205885750,206438400,206524416,206671500,206718750,207360000,207446400,207532836,208324872,208372500,209018880,209715200,209952000,210000000,210039480,210087500,210739200,210827008,210937500,211631616,211680000,211768200,212336640,212576400,212625000,213373440,214326000,214375000,214990848,215040000,215129600,215233605,216000000,216040608,216090000,216760320,217005075,217728000,217818720,218700000,218750000,218791125,219469824,219520000,220200960,220449600,220500000,220541454,220591875,221184000,221276160,221433750,221484375,222264000,222356610,222953472,223205220,223256250,223948800,224000000,224042112,224788480,225000000,225042300,225093750,225792000,225886080,226492416,226748160,226800000,226894500,227598336,227812500,228614400,228709656,229376000,229582512,229635000,229687500,230400000,230496000,230592040,231211008,231472080,231525000,232243200,232339968,233280000,233377200,234365481,234375000,234881024,235146240,235200000,235298000,235929600,236027904,236196000,236250000,236294415,237081600,237180384,238085568,238140000,238239225,238878720,239148450,239203125,240000000,240045120,240100000,240844800,240945152,241116750,241171875,241864704,241920000,242020800,242121642,243000000,243045684,243101250,243855360,244140625,244944000,245000000,245046060,245760000,245862400,246037500,246093750,246903552,246960000,247062900,247726080,248005800,248062500,248832000,248935680,250000000,250047000,250822656,250880000,251658240,251942400,252000000,252047376,252105000,252887040,253125000,254016000,254121840,254803968,255091680,255150000,256000000,256048128,256901120,257191200,257250000,257298363,258048000,258155520,258280326,258339375,259200000,259308000,259416045,260112384,260406090,260465625,261273600,261382464,262144000,262440000,262500000,262549350,262609375,263424000,263533760,263671875,264241152,264539520,264600000,264710250,265420800,265531392,265720500,265781250,266716800,266827932,267846264,267907500,267968750,268435456,268738560,268800000,268912000,269746176,270000000,270050760,270112500,270950400,271063296,272097792,272160000,272273400,273375000,273437500,274337280,274400000,275251200,275365888,275562000,275625000,276480000,276595200,276710448,277766496,277830000,278691840,279006525,279936000,280000000,280052640,280985600,281250000,281302875,282175488,282240000,282357600,282475249,283115520,283435200,283500000,283553298,283618125,284497920,284765625,285768000,285887070,286654464,286720000,286978140,287043750,287109375,288000000,288054144,288120000,288240050,289013760,289340100,289406250,290304000,290424960,291600000,291721500,292626432,292968750,293601280,293932800,294000000,294055272,294122500,294912000,295034880,295245000,295312500,296352000,296475480,297271296,297606960,297675000,298598400,298722816,300000000,300056400,300125000,301056000,301181440,301327047,301989888,302330880,302400000,302526000,303464448,303750000,303807105,304819200,304946208,306110016,306180000,306250000,306307575,307200000,307328000,307546875,308281344,308629440,308700000,308828625,309657600,309786624,310007250,310078125,311040000,311169600,311299254,312487308,312500000,312558750,313528320,313600000,314572800,314703872,314928000,315000000,315059220,315131250,316108800,316240512,316406250,317447424,317520000,317652300,318504960,318864600,318937500,320000000,320060160,321126400,321489000,321562500,322486272,322560000,322694400,322828856,324000000,324060912,324135000,325140480,326592000,326728080,327680000,328050000,328125000,329204736,329280000,329417200,330301440,330674400,330750000,330812181,331776000,331914240,332150625,333396000,333534915,334430208,334807830,334884375,335544320,335923200,336000000,336063168,336140000,337182720,337500000,337563450,337640625,338688000,338829120,339738624,340122240,340200000,340341750,341397504,341718750,341796875,342921600,343000000,343064484,344064000,344207360,344373768,344452500,344531250,345600000,345744000,345888060,346816512,347208120,347287500,348364800,348509952,349920000,350000000,350065800,351232000,351562500,352321536,352719360,352800000,352947000,353894400,354041856,354294000,354375000,355622400,355770576,357128352,357210000,358318080,358400000,358722675,359661568,360000000,360067680,360150000,361267200,361417728,361675125,362797056,362880000,363031200,363182463,364500000,364568526,364651875,365783040,367001600,367416000,367500000,367569090,367653125,368640000,368793600,368947264,369056250,369140625,370355328,370440000,370594350,371589120,372008700,372093750,373248000,373403520,375000000,375070500,375156250,376233984,376320000,376476800,377487360,377913600,378000000,378071064,378157500,379330560,379687500,381024000,381182760,382205952,382637520,382725000,382812500,384000000,384072192,384160000,385351680,385786800,385875000,387072000,387233280,387420489,388800000,388962000,390168576,390609135,390625000,391910400,392000000,392073696,393216000,393379840,393660000,393750000,393824025,395136000,395300640,396361728,396809280,396900000,397065375,398131200,398297088,398580750,398671875,400000000,400075200,400241898,401408000,401769396,401861250,401953125,402653184,403107840,403200000,403368000,403536070,404619264,405000000,405076140,405168750,406425600,406594944,408146688,408240000,408410100,409600000,410062500,410156250,411041792,411505920,411600000,411771500,412876800,413048832,413343000,413437500,414720000,414892800,415065672,416649744,416745000,418037760,419430400,419904000,420000000,420078960,420175000,421478400,421654016,421875000,423263232,423360000,423536400,424673280,425152800,425250000,425329947,426746880,428652000,428750000,428830605,429981696,430080000,430259200,430467210,430565625,432000000,432081216,432180000,432360075,433520640,434010150,434109375,435456000,435637440,437400000,437500000,437582250,438939648,439040000,439453125,440401920,440899200,441000000,441082908,441183750,442368000,442552320,442867500,442968750,444528000,444713220,445906944,446410440,446512500,447897600,448000000,448084224,449576960,450000000,450084600,450187500,451584000,451772160,452984832,453496320,453600000,453789000,455196672,455625000,457228800,457419312,458752000,459165024,459270000,459375000,460800000,460992000,461184080,462422016,462944160,463050000,464486400,464679936,465010875,466560000,466754400,466948881,468730962,468750000,468838125,469762048,470292480,470400000,470596000,471859200,472055808,472392000,472500000,472588830,472696875,474163200,474360768,474609375,476171136,476280000,476478450,477757440,478296900,478406250,478515625,480000000,480090240,480200000,481689600,481890304,482233500,482343750,483729408,483840000,484041600,484243284,486000000,486091368,486202500,487710720,488281250,489888000,490000000,490092120,491520000,491724800,492075000,492187500,493807104,493920000,494125800,495452160,496011600,496125000,497664000,497871360,500000000,500094000,501645312,501760000,502211745,503316480,503884800,504000000,504094752,504210000,505774080,506250000,506345175,508032000,508243680,509607936,510183360,510300000,510512625,512000000,512096256,512578125,513802240,514382400,514500000,514596726,514714375,516096000,516311040,516560652,516678750,516796875,518400000,518616000,518832090,520224768,520812180,520931250,522547200,522764928,524288000,524880000,525000000,525098700,525218750,526848000,527067520,527343750,528482304,529079040,529200000,529420500,530841600,531062784,531441000,531562500,533433600,533655864,535692528,535815000,535937500,536870912,537477120,537600000,537824000,539492352,540000000,540101520,540225000,541900800,542126592,544195584,544320000,544546800,546750000,546852789,546875000,548674560,548800000,550502400,550731776,551124000,551250000,551353635,552960000,553190400,553420896,553584375,555532992,555660000,555891525,557383680,558013050,558140625,559872000,560000000,560105280,561971200,562500000,562605750,562734375,564350976,564480000,564715200,564950498,566231040,566870400,567000000,567106596,567236250,568995840,569531250,571536000,571774140,573308928,573440000,573956280,574087500,574218750,576000000,576108288,576240000,576480100,578027520,578680200,578812500,580608000,580849920,583200000,583443000,585252864,585937500,587202560,587865600,588000000,588110544,588245000,589824000,590069760,590490000,590625000,592704000,592950960,594542592,595213920,595350000,597196800,597445632,597871125,600000000,600112800,600250000,600362847,602112000,602362880,602654094,602791875,603979776,604661760,604800000,605052000,605304105,606928896,607500000,607614210,607753125,609638400,609892416,612220032,612360000,612500000,612615150,614400000,614656000,615093750,615234375,616562688,617258880,617400000,617657250,619315200,619573248,620014500,620156250,622080000,622339200,622598508,624974616,625000000,625117500,627056640,627200000,629145600,629407744,629856000,630000000,630118440,630262500,632217600,632481024,632812500,634894848,635040000,635304600,637009920,637729200,637875000,640000000,640120320,642252800,642978000,643125000,644972544,645120000,645388800,645657712,645700815,648000000,648121824,648270000,650280960,651015225,653184000,653456160,655360000,656100000,656250000,656373375,658409472,658560000,658834400,660602880,661348800,661500000,661624362,661775625,663552000,663828480,664301250,664453125,666792000,667069830,668860416,669615660,669768750,669921875,671088640,671846400,672000000,672126336,672280000,674365440,675000000,675126900,675281250,677376000,677658240,679477248,680244480,680400000,680683500,682795008,683437500,683593750,685843200,686000000,686128968,688128000,688414720,688747536,688905000,689062500,691200000,691488000,691776120,693633024,694416240,694575000,696729600,697019904,699840000,700000000,700131600,702464000,703096443,703125000,704643072,705438720,705600000,705894000,707788800,708083712,708588000,708750000,708883245,711244800,711541152,714256704,714420000,714717675,716636160,716800000,717445350,717609375,719323136,720000000,720135360,720300000,720600125,722534400,722835456,723350250,723515625,725594112,725760000,726062400,726364926,729000000,729137052,729303750,731566080,732421875,734003200,734832000,735000000,735138180,735306250,737280000,737587200,737894528,738112500,738281250,740710656,740880000,741188700,743178240,744017400,744187500,746496000,746807040,750000000,750141000,750312500,752467968,752640000,752953600,754974720,755827200,756000000,756142128,756315000,758661120,759375000,762048000,762365520,764411904,765275040,765450000,765625000,768000000,768144384,768320000,770703360,771573600,771750000,771895089,774144000,774466560,774840978,775018125,777600000,777924000,778248135,780337152,781218270,781250000,781396875,783820800,784000000,784147392,786432000,786759680,787320000,787500000,787648050,787828125,790272000,790601280,791015625,792723456,793618560,793800000,794130750,796262400,796594176,797161500,797343750,800000000,800150400,800483796,802816000,803538792,803722500,803906250,805306368,806215680,806400000,806736000,807072140,809238528,810000000,810152280,810337500,812851200,813189888,816293376,816480000,816820200,819200000,820125000,820312500,822083584,823011840,823200000,823543000,825753600,826097664,826686000,826875000,829440000,829785600,830131344,833299488,833490000,836075520,837019575,838860800,839808000,840000000,840157920,840350000,842956800,843308032,843750000,843908625,846526464,846720000,847072800,847425747,849346560,850305600,850500000,850659894,850854375,853493760,854296875,857304000,857500000,857661210,859963392,860160000,860518400,860934420,861131250,861328125,864000000,864162432,864360000,864720150,867041280,868020300,868218750,870912000,871274880,874800000,875000000,875164500,877879296,878080000,878906250,880803840,881798400,882000000,882165816,882367500,884736000,885104640,885735000,885937500,889056000,889426440,891813888,892820880,893025000,895795200,896000000,896168448,899153920,900000000,900169200,900375000,903168000,903544320,903981141,905969664,906992640,907200000,907578000,910393344,911250000,911421315,914457600,914838624,917504000,918330048,918540000,918750000,918922725,921600000,921984000,922368160,922640625,924844032,925888320,926100000,926485875,928972800,929359872,930021750,930234375,933120000,933508800,933897762,937461924,937500000,937676250,937890625,939524096,940584960,940800000,941192000,943718400,944111616,944784000,945000000,945177660,945393750,948326400,948721536,949218750,952342272,952560000,952956900,955514880,956593800,956812500,957031250,960000000,960180480,960400000,963379200,963780608,964467000,964687500,967458816,967680000,968083200,968486568,972000000,972182736,972405000,975421440,976562500,979776000,980000000,980184240,983040000,983449600,984150000,984375000,987614208,987840000,988251600,990904320,992023200,992250000,992436543,995328000,995742720,996451875,1000000000};
  8. void pre()
  9. {
  10.     for(int i=1;i<10000000;i++)
  11.     {
  12.         int tmp=i;
  13.         while(tmp%2==0)
  14.             tmp/=2;
  15.         while(tmp%3==0)
  16.             tmp/=3;
  17.         while(tmp%5==0)
  18.             tmp/=5;
  19.         while(tmp%7==0)
  20.             tmp/=7;
  21.         if(tmp==1)
  22.             vv.push_back(i);
  23.     }
  24.     vv.push_back(10000000);
  25. }
  27. int main()
  28. {
  29.     pre();
  30.     int t;
  31.     scanf("%d",&t);
  32.     while(t--)
  33.     {
  34.         int n;
  35.         int ans;
  36.         scanf("%d",&n);
  37.         auto it=lower_bound(vv.begin(),vv.end(),n);
  38.         if(it==vv.end())
  39.             it=lower_bound(v.begin(),v.end(),n);
  40.         printf("%d\n",*it);
  41.     }
  42.     return 0;
  43. }

H yingyingying777

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int INF=0x3f3f3f3f;
  5. const int N=5005;
  6. char s[N];
  7. ll dp[N];
  9. struct pam
  10. {
  11.     int nxt[N][256];
  12.     int fail[N];
  13.     int len[N];
  14.     int cnt[N];
  15.     int sed[N];
  16.     int record[N];
  17.     char s[N];
  18.     int tot;
  19.     int last;
  20.     int n;
  21.     void init()
  22.     {
  23.         for(int i=0;i<=tot;i++)
  24.         {
  25.             fail[i]=cnt[i]=sed[i]=len[i]=0;
  26.             for(int j=0;j<256;j++)
  27.                 nxt[i][j]=0;
  28.         }
  29.         tot=n=0;
  30. //      memset(fail,0,sizeof(fail));
  31. //      memset(cnt,0,sizeof(cnt));
  32. //      memset(sed,0,sizeof(sed));
  33. //      memset(len,0,sizeof(len));
  34. //      memset(nxt,0,sizeof(nxt));
  35.     }
  36.     void build()
  37.     {
  38.         len[0]=0;
  39.         len[1]=-1;
  40.         tot=1;
  41.         last=0;
  42.         fail[0]=1;
  43.     }
  44.     int getfail(int x,int n)
  45.     {
  46.         while(s[n-len[x]-1]!=s[n]||n-len[x]-1<0)
  47.             x=fail[x];
  48.         return x;
  49.     }
  50.     void insert(char ch)
  51.     {
  52.         int c=ch;
  53.         s[++n]=ch;
  54.         int p=getfail(last,n);
  55.         if(!nxt[p][c])
  56.         {
  57.             tot++;
  58.             len[tot]=len[p]+2;
  59.             fail[tot]=nxt[getfail(fail[p],n)][c];
  60.             sed[tot]=sed[fail[tot]]+1;
  61.             nxt[p][c]=tot;
  62.         }
  63.         last=nxt[p][c];
  64.         cnt[last]++;
  65.         record[last]=n;
  66.     }
  67.     void get_cnt()
  68.     {
  69.         for(int i=tot;i>0;i--)
  70.             cnt[fail[i]]+=cnt[i];
  71.     }
  72. }tree;
  74. int main()
  75. {
  76.     ios::sync_with_stdio(false);
  77.     memset(dp,0x3f,sizeof(dp));
  78.     dp[0]=0;
  79.     cin>>(s+1);
  80.     int n=strlen(s+1);
  81.     for(int i=1;i<=n;i++)
  82.     {
  83.         tree.init();
  84.         tree.build();
  85.         for(int j=i;j>0;j--)
  86.         {
  87.             tree.insert(s[j]);
  88.             int tmp=tree.len[tree.last];
  89.             if(tmp==i-j+1)
  90.                 dp[i]=min(dp[i],dp[i-tmp]+1);
  91.         }
  94.     }
  95.     cout<<dp[n]<<endl;
  96.     return 0;
  97. }

I wang639026

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=8000;
  4. int n,num[maxn<<1],a[maxn<<1];
  5. int main()
  6. {
  7.     while(scanf("%d",&n)!=EOF)
  8.     {
  9.         for(int i=1;i<=n;++i) scanf("%d",&a[i]);
  10.         for(int i=1;i<=n;++i)
  11.         {
  12.             memset(num,0,sizeof(num));
  13.             int cnt=0,ans=0;
  14.             num[maxn]++;
  15.             for(int j=i+1;j<=n;++j)
  16.             cnt+=a[j]>a[i]?1:-1,num[maxn+cnt]++;
  17.             ans+=num[maxn];
  18.             cnt=0;
  19.             for(int j=i-1;j>=1;--j)
  20.             cnt+=a[j]<a[i]?1:-1,ans+=num[maxn+cnt];
  21.             printf("%d%s",ans,i==n?"\n":" ");
  22.         }
  23.     }
  24. }

J _Wallace_

  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  5. const int N = 5e4 + 5;
  6. stack<int> st;
  7. int lower[N], upper[N], A[N];
  8. int n;
  10. void calcBound() {
  11.     while (!st.empty()) st.pop();
  12.     for (register int i = n; i; i --) {
  13.         while (!st.empty() && A[st.top()] > A[i]) st.pop();
  14.         lower[i] = st.empty() ? n + 1 : st.top();
  15.         st.push(i);
  16.     }
  18.     while (!st.empty()) st.pop();
  19.     for (register int i = n; i; i --) {
  20.         while (!st.empty() && A[st.top()] < A[i]) st.pop();
  21.         upper[i] = st.empty() ? n + 1 : st.top();
  22.         st.push(i);
  23.     }
  24. }
  26. int calcPairs() {
  27.     int ret = n;
  28.     for (register int i = 1; i <= n; i ++)
  29.         for (register int j = upper[i]; j < lower[i]; j = upper[j]) ret ++;
  30.     return ret;
  31. }
  33. signed main() {
  34.     cin >> n;
  35.     for (register int i = 1; i <= n; i ++)
  36.         cin >> A[i];
  37.     calcBound();
  38.     cout << calcPairs() << endl;
  39.     return 0;
  40. }

J baobaobear

前一份代码会被有序数据卡掉，这里另提供一份解答

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <string>
  5. #include <vector>
  6. #include <stack>
  7. #include <deque>
  8. #include <queue>
  9. #include <list>
  10. #include <limits>
  11. #include <set>
  12. #include <map>
  13. #include <functional>
  15. #include <inttypes.h>
  16. #include <stdint.h>
  17. #include <limits.h>
  18. #include <stdio.h>
  19. #include <stdlib.h>
  20. #include <string.h>
  21. #include <math.h>
  22. #include <time.h>
  24. using namespace std;
  25. typedef long long ll;
  27. #ifndef PRId64
  28. #define PRId64 "lld"
  29. #endif
  30. #ifndef SCNd64
  31. #define SCNd64 "lld"
  32. #endif
  33. #define SC sc()
  34. #define PT pr()
  35. #define NL pt_nl()
  36. #define FORi(i,b,e) for (int i = (b), _ = (e); i < _; ++i)
  37. #define FORe(i,b,e) for (int i = (b), _ = (e); i <= _; ++i)
  38. #define FORre(i,b,e) for (int i = (b), _ = (e); i >= _; --i)
  40. static int sc_ret = 0;
  41. struct pt_nl {};
  42. struct sc
  43. {
  44.     sc& operator>>(char& v) { sc_ret = scanf(" %c", &v); return *this; }
  45.     sc& operator>>(int& v) { /*sc_ret = read(v);*/ sc_ret = scanf("%d", &v); return *this; }
  46.     sc& operator>>(unsigned& v) { sc_ret = scanf("%u", &v); return *this; }
  47.     sc& operator>>(double& v) { sc_ret = scanf("%lf", &v); return *this; }
  48.     sc& operator>>(char* v) { sc_ret = scanf("%s", v); return *this; }
  49.     sc& operator>>(string& v) { sc_ret = (bool)(cin >> v); return *this; }
  50.     sc& operator>>(ll& v) { sc_ret = read(v); return *this; }
  51.     sc& ch(char& v) { v = sc_ret = getchar(); return *this; }
  52.     sc& gets(char* v) { sc_ret = fgets(v, INT_MAX, stdin) != 0; v[strlen(v) - 1] = 0; return *this; }
  53.     operator bool() const { return sc_ret > 0; }
  54.     template <typename T>
  55.     int read(T& v)
  56.     {
  57.         T x = 0, k = 1;
  58.         int c = getchar();
  59.         while (c < '0' || c > '9')
  60.         {
  61.             if (c == '-') k = -1;
  62.             c = getchar();
  63.         }
  64.         while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c - 48), c = getchar();
  65.         v = x * k;
  66.         return c;
  67.     }
  68. };
  69. struct pr
  70. {
  71.     pr& ln() { putchar('\n'); return *this; }
  72.     pr& operator<<(const pt_nl& nl) { putchar('\n'); return *this; }
  73.     pr& operator<<(char v) { putchar(v); return *this; }
  74.     pr& operator<<(int v) { write(v); return *this; }
  75.     pr& operator<<(double v) { printf("%.2f", v); return *this; }
  76.     pr& operator()(const char* fmt, double v) { printf(fmt, v); return *this; }
  77.     pr& operator<<(const char* v) { printf("%s", v); return *this; }
  78.     pr& operator<<(string v) { printf("%s", v.c_str()); return *this; }
  79.     pr& operator<<(ll v) { write(v); return *this; }
  80.     template <typename T>
  81.     void write(T v)
  82.     {
  83.         int cnt = 0; char c[23];
  84.         if (v == 0)
  85.         {
  86.             putchar('0');
  87.             return;
  88.         }
  89.         if (v < 0) putchar('-'), v = -v;
  90.         while (v) c[++cnt] = (v % 10) + 48, v /= 10;
  91.         while (cnt > 0) putchar(c[cnt--]);
  92.     }
  93.     template <typename T>
  94.     void ln(T* arr, int size)
  95.     {
  96.         if (size > 0)
  97.         {
  98.             (*this) << arr[0];
  99.             for (int i = 1; i < size; ++i)
  100.             {
  101.                 putchar(' ');
  102.                 (*this) << arr[i];
  103.             }
  104.             putchar('\n');
  105.         }
  106.     }
  108.     template <typename T>
  109.     void muln(T* arr, int size)
  110.     {
  111.         for (int i = 0; i < size; ++i)
  112.         {
  113.             (*this) << arr[i];
  114.             putchar('\n');
  115.         }
  116.     }
  117. };
  119. const int inf = 0x3f3f3f3f;
  120. const int mod1e9 = 1000000007;
  121. const int mod998 = 998244353;
  122. const int mod = mod998;
  123. const int maxn = 2000000 + 10;
  125. vector<int> v;
  127. void Main()
  128. {
  129.     ll cnt = 0;
  130.     int n;
  131.     vector<int> u, d;
  132.     SC >> n;
  133.     v.resize(n + 2);
  134.     u.reserve(n + 1); d.reserve(n + 1);
  135.     v[0] = INT_MIN;
  136.     v[1] = INT_MAX;
  137.     u.push_back(0);
  138.     d.push_back(1);
  139.     FORe(i, 2, n + 1)
  140.     {
  141.         SC >> v[i];
  142.         int j = upper_bound(d.begin(), d.end(), i, [](int a, int b){return v[a] > v[b];}) - d.begin();
  143.         while (v[u.back()] > v[i]) u.pop_back();
  144.         u.push_back(i);
  145.         int k = lower_bound(u.begin(), u.end(), d[j - 1]) - u.begin();
  146.         cnt += u.size() - k;
  147.         while (v[d.back()] < v[i]) d.pop_back();
  148.         d.push_back(i);
  149.     }
  150.     PT << cnt << NL;
  151. }
  153. int main()
  154. {
  155.     Main();
  156.     //scanf("%*s");
  157.     return 0;
  158. }

K

L wang639026

  1. #include<cstdio>
  2. #include<algorithm>
  3. const int N=100000,inf=0x3f3f3f3f;
  4. int es[N],enx[N],ev[N],e0[N],ep;
  5. int h[N],q[N],S,T;
  6. inline void adde(int a,int b,int c){
  7.     es[ep]=b;enx[ep]=e0[a];ev[ep]=c;e0[a]=ep++;
  8.     es[ep]=a;enx[ep]=e0[b];ev[ep]=0;e0[b]=ep++;
  9. }
  10. bool bfs(){
  11.     int ql=0,qr=0;
  12.     for(int i=0;i<=T;i++)h[i]=0;
  13.     h[S]=1;q[qr++]=S;
  14.     while(ql!=qr){
  15.         int w=q[ql++];
  16.         for(int i=e0[w];i;i=enx[i]){
  17.             int u=es[i];
  18.             if(!h[u]&&ev[i]){
  19.                 h[u]=h[w]+1;
  20.                 q[qr++]=u;
  21.             }
  22.         }
  23.     }
  24.     return h[T];
  25. }
  26. int dfs(int w,int f){
  27.     if(w==T)return f;
  28.     int c,u,used=0;
  29.     for(int i=e0[w];i;i=enx[i]){
  30.         u=es[i];
  31.         if(h[u]!=h[w]+1||!ev[i])continue;
  32.         c=f-used;
  33.         if(c>ev[i])c=ev[i];
  34.         c=dfs(u,c);
  35.         used+=c;
  36.         ev[i]-=c;
  37.         ev[i^1]+=c;
  38.         if(used==f)return f;
  39.     }
  40.     if(!used)h[w]=0;
  41.     return used;
  42. }
  43. int qs[53][3],xs[107],ps[107],xp,pp;
  44. bool d[107][107];
  45. int main(){
  46.     int _T,n,q;
  47.     for(scanf("%d",&_T);_T;_T--){
  48.         scanf("%d%d",&n,&q);
  49.         for(int i=0;i<q;i++)scanf("%d%d%d",qs[i],qs[i]+1,qs[i]+2);
  50.         xp=pp=0;
  51.         xs[xp++]=1;
  52.         xs[xp++]=n+1;
  53.         ps[pp++]=1;
  54.         ps[pp++]=n+1;
  55.         for(int i=0;i<q;i++){
  56.             xs[xp++]=qs[i][2];
  57.             xs[xp++]=qs[i][2]+1;
  58.             ps[pp++]=qs[i][0];
  59.             ps[pp++]=qs[i][1]+1;
  60.         }
  61.         std::sort(xs,xs+xp);
  62.         xp=std::unique(xs,xs+xp)-xs;
  63.         std::sort(ps,ps+pp);
  64.         pp=std::unique(ps,ps+pp)-ps;
  65.         for(int i=0;i<xp;i++)for(int j=0;j<pp;j++)d[i][j]=1;
  66.         for(int i=0;i<q;i++){
  67.             for(int j=0;j<xp-1;j++){
  68.                 if(xs[j]>qs[i][2]){
  69.                     for(int k=0;k<pp-1;k++)if(qs[i][0]<=ps[k]&&ps[k]<=qs[i][1]){
  70.                         d[j][k]=0;
  71.                     }
  72.                 }else if(xs[j]==qs[i][2]){
  73.                     for(int k=0;k<pp-1;k++)if(qs[i][0]>ps[k]||ps[k]>qs[i][1]){
  74.                         d[j][k]=0;
  75.                     }
  76.                 }
  77.             }
  78.         }
  79.         S=xp+pp+1;T=S+1;
  80.         for(int i=1;i<=T;i++)e0[i]=0;
  81.         ep=2;
  82.         for(int i=0;i<xp-1;i++)adde(S,i+1,xs[i+1]-xs[i]);
  83.         for(int i=0;i<pp-1;i++)adde(xp+i+1,T,ps[i+1]-ps[i]);
  84.         for(int i=0;i<xp-1;i++)for(int j=0;j<pp-1;j++)if(d[i][j])adde(i+1,xp+j+1,n);
  85.         int ans=0;
  86.         while(bfs())ans+=dfs(S,inf);
  87.         puts(ans==n?"Possible":"Impossible");
  88.     }
  89.     return 0;
  90. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注