AT1483 1 题解 (危)

Otomachi_Una_ · 2021-05-23 07:30:49 · 题解

区间打表能过

考虑到输入比较单一，考虑打表。

但因为 n 比较大，不能打出全部的表，考虑区间打表。

先暴力求解，然后每隔一段就输出一次结果，这就是区间打表。

总的来说，区间打表可以骗分，AC，甚至拿到最优解。

打表程序：

#include<iostream>
#include<cstdio> 
using namespace std;
int ans=0;
void check(int x){
    while(x){
        if(x%10==1)
            ans++;
        x/=10;
    }
}
int main(){
    freopen("dabiao.out","w",stdout);
    for(int i=1;i<=1e9;i++){
        check(i);
        if(i%1000000==0)
            cout<<ans<<",";
    }
    return 0;
}

打表结果：

600001,2200000,2800000,3400000,4000000,4600000,5200000,5800000,6400000,7000001,8600002,11200001,12800001,14400001,16000001,17600001,19200001,20800001,22400001,24000000,24600001,26200000,26800000,27400000,28000000,28600000,29200000,29800000,30400000,31000000,31600001,33200000,33800000,34400000,35000000,35600000,36200000,36800000,37400000,38000000,38600001,40200000,40800000,41400000,42000000,42600000,43200000,43800000,44400000,45000000,45600001,47200000,47800000,48400000,49000000,49600000,50200000,50800000,51400000,52000000,52600001,54200000,54800000,55400000,56000000,56600000,57200000,57800000,58400000,59000000,59600001,61200000,61800000,62400000,63000000,63600000,64200000,64800000,65400000,66000000,66600001,68200000,68800000,69400000,70000000,70600000,71200000,71800000,72400000,73000000,73600001,75200000,75800000,76400000,77000000,77600000,78200000,78800000,79400000,80000001,81600002,84200001,85800001,87400001,89000001,90600001,92200001,93800001,95400001,97000002,99600003,103200002,105800002,108400002,111000002,113600002,116200002,118800002,121400002,124000001,125600002,128200001,129800001,131400001,133000001,134600001,136200001,137800001,139400001,141000001,142600002,145200001,146800001,148400001,150000001,151600001,153200001,154800001,156400001,158000001,159600002,162200001,163800001,165400001,167000001,168600001,170200001,171800001,173400001,175000001,176600002,179200001,180800001,182400001,184000001,185600001,187200001,188800001,190400001,192000001,193600002,196200001,197800001,199400001,201000001,202600001,204200001,205800001,207400001,209000001,210600002,213200001,214800001,216400001,218000001,219600001,221200001,222800001,224400001,226000001,227600002,230200001,231800001,233400001,235000001,236600001,238200001,239800001,241400001,243000001,244600002,247200001,248800001,250400001,252000001,253600001,255200001,256800001,258400001,260000000,260600001,262200000,262800000,263400000,264000000,264600000,265200000,265800000,266400000,267000001,268600002,271200001,272800001,274400001,276000001,277600001,279200001,280800001,282400001,284000000,284600001,286200000,286800000,287400000,288000000,288600000,289200000,289800000,290400000,291000000,291600001,293200000,293800000,294400000,295000000,295600000,296200000,296800000,297400000,298000000,298600001,300200000,300800000,301400000,302000000,302600000,303200000,303800000,304400000,305000000,305600001,307200000,307800000,308400000,309000000,309600000,310200000,310800000,311400000,312000000,312600001,314200000,314800000,315400000,316000000,316600000,317200000,317800000,318400000,319000000,319600001,321200000,321800000,322400000,323000000,323600000,324200000,324800000,325400000,326000000,326600001,328200000,328800000,329400000,330000000,330600000,331200000,331800000,332400000,333000000,333600001,335200000,335800000,336400000,337000000,337600000,338200000,338800000,339400000,340000000,340600001,342200000,342800000,343400000,344000000,344600000,345200000,345800000,346400000,347000001,348600002,351200001,352800001,354400001,356000001,357600001,359200001,360800001,362400001,364000000,364600001,366200000,366800000,367400000,368000000,368600000,369200000,369800000,370400000,371000000,371600001,373200000,373800000,374400000,375000000,375600000,376200000,376800000,377400000,378000000,378600001,380200000,380800000,381400000,382000000,382600000,383200000,383800000,384400000,385000000,385600001,387200000,387800000,388400000,389000000,389600000,390200000,390800000,391400000,392000000,392600001,394200000,394800000,395400000,396000000,396600000,397200000,397800000,398400000,399000000,399600001,401200000,401800000,402400000,403000000,403600000,404200000,404800000,405400000,406000000,406600001,408200000,408800000,409400000,410000000,410600000,411200000,411800000,412400000,413000000,413600001,415200000,415800000,416400000,417000000,417600000,418200000,418800000,419400000,420000000,420600001,422200000,422800000,423400000,424000000,424600000,425200000,425800000,426400000,427000001,428600002,431200001,432800001,434400001,436000001,437600001,439200001,440800001,442400001,444000000,444600001,446200000,446800000,447400000,448000000,448600000,449200000,449800000,450400000,451000000,451600001,453200000,453800000,454400000,455000000,455600000,456200000,456800000,457400000,458000000,458600001,460200000,460800000,461400000,462000000,462600000,463200000,463800000,464400000,465000000,465600001,467200000,467800000,468400000,469000000,469600000,470200000,470800000,471400000,472000000,472600001,474200000,474800000,475400000,476000000,476600000,477200000,477800000,478400000,479000000,479600001,481200000,481800000,482400000,483000000,483600000,484200000,484800000,485400000,486000000,486600001,488200000,488800000,489400000,490000000,490600000,491200000,491800000,492400000,493000000,493600001,495200000,495800000,496400000,497000000,497600000,498200000,498800000,499400000,500000000,500600001,502200000,502800000,503400000,504000000,504600000,505200000,505800000,506400000,507000001,508600002,511200001,512800001,514400001,516000001,517600001,519200001,520800001,522400001,524000000,524600001,526200000,526800000,527400000,528000000,528600000,529200000,529800000,530400000,531000000,531600001,533200000,533800000,534400000,535000000,535600000,536200000,536800000,537400000,538000000,538600001,540200000,540800000,541400000,542000000,542600000,543200000,543800000,544400000,545000000,545600001,547200000,547800000,548400000,549000000,549600000,550200000,550800000,551400000,552000000,552600001,554200000,554800000,555400000,556000000,556600000,557200000,557800000,558400000,559000000,559600001,561200000,561800000,562400000,563000000,563600000,564200000,564800000,565400000,566000000,566600001,568200000,568800000,569400000,570000000,570600000,571200000,571800000,572400000,573000000,573600001,575200000,575800000,576400000,577000000,577600000,578200000,578800000,579400000,580000000,580600001,582200000,582800000,583400000,584000000,584600000,585200000,585800000,586400000,587000001,588600002,591200001,592800001,594400001,596000001,597600001,599200001,600800001,602400001,604000000,604600001,606200000,606800000,607400000,608000000,608600000,609200000,609800000,610400000,611000000,611600001,613200000,613800000,614400000,615000000,615600000,616200000,616800000,617400000,618000000,618600001,620200000,620800000,621400000,622000000,622600000,623200000,623800000,624400000,625000000,625600001,627200000,627800000,628400000,629000000,629600000,630200000,630800000,631400000,632000000,632600001,634200000,634800000,635400000,636000000,636600000,637200000,637800000,638400000,639000000,639600001,641200000,641800000,642400000,643000000,643600000,644200000,644800000,645400000,646000000,646600001,648200000,648800000,649400000,650000000,650600000,651200000,651800000,652400000,653000000,653600001,655200000,655800000,656400000,657000000,657600000,658200000,658800000,659400000,660000000,660600001,662200000,662800000,663400000,664000000,664600000,665200000,665800000,666400000,667000001,668600002,671200001,672800001,674400001,676000001,677600001,679200001,680800001,682400001,684000000,684600001,686200000,686800000,687400000,688000000,688600000,689200000,689800000,690400000,691000000,691600001,693200000,693800000,694400000,695000000,695600000,696200000,696800000,697400000,698000000,698600001,700200000,700800000,701400000,702000000,702600000,703200000,703800000,704400000,705000000,705600001,707200000,707800000,708400000,709000000,709600000,710200000,710800000,711400000,712000000,712600001,714200000,714800000,715400000,716000000,716600000,717200000,717800000,718400000,719000000,719600001,721200000,721800000,722400000,723000000,723600000,724200000,724800000,725400000,726000000,726600001,728200000,728800000,729400000,730000000,730600000,731200000,731800000,732400000,733000000,733600001,735200000,735800000,736400000,737000000,737600000,738200000,738800000,739400000,740000000,740600001,742200000,742800000,743400000,744000000,744600000,745200000,745800000,746400000,747000001,748600002,751200001,752800001,754400001,756000001,757600001,759200001,760800001,762400001,764000000,764600001,766200000,766800000,767400000,768000000,768600000,769200000,769800000,770400000,771000000,771600001,773200000,773800000,774400000,775000000,775600000,776200000,776800000,777400000,778000000,778600001,780200000,780800000,781400000,782000000,782600000,783200000,783800000,784400000,785000000,785600001,787200000,787800000,788400000,789000000,789600000,790200000,790800000,791400000,792000000,792600001,794200000,794800000,795400000,796000000,796600000,797200000,797800000,798400000,799000000,799600001,801200000,801800000,802400000,803000000,803600000,804200000,804800000,805400000,806000000,806600001,808200000,808800000,809400000,810000000,810600000,811200000,811800000,812400000,813000000,813600001,815200000,815800000,816400000,817000000,817600000,818200000,818800000,819400000,820000000,820600001,822200000,822800000,823400000,824000000,824600000,825200000,825800000,826400000,827000001,828600002,831200001,832800001,834400001,836000001,837600001,839200001,840800001,842400001,844000000,844600001,846200000,846800000,847400000,848000000,848600000,849200000,849800000,850400000,851000000,851600001,853200000,853800000,854400000,855000000,855600000,856200000,856800000,857400000,858000000,858600001,860200000,860800000,861400000,862000000,862600000,863200000,863800000,864400000,865000000,865600001,867200000,867800000,868400000,869000000,869600000,870200000,870800000,871400000,872000000,872600001,874200000,874800000,875400000,876000000,876600000,877200000,877800000,878400000,879000000,879600001,881200000,881800000,882400000,883000000,883600000,884200000,884800000,885400000,886000000,886600001,888200000,888800000,889400000,890000000,890600000,891200000,891800000,892400000,893000000,893600001,895200000,895800000,896400000,897000000,897600000,898200000,898800000,899400000,900000001,

最终程序：

#include<iostream>
#include<cstdio> 
using namespace std;

int n,ans=0;
void check(int x){
    while(x){
        if(x%10==1)
            ans++;
        x/=10;
    }
}
int a[]={0,600001,2200000,2800000,3400000,4000000,4600000,5200000,5800000,6400000,7000001,8600002,11200001,12800001,14400001,16000001,17600001,19200001,20800001,22400001,24000000,24600001,26200000,26800000,27400000,28000000,28600000,29200000,29800000,30400000,31000000,31600001,33200000,33800000,34400000,35000000,35600000,36200000,36800000,37400000,38000000,38600001,40200000,40800000,41400000,42000000,42600000,43200000,43800000,44400000,45000000,45600001,47200000,47800000,48400000,49000000,49600000,50200000,50800000,51400000,52000000,52600001,54200000,54800000,55400000,56000000,56600000,57200000,57800000,58400000,59000000,59600001,61200000,61800000,62400000,63000000,63600000,64200000,64800000,65400000,66000000,66600001,68200000,68800000,69400000,70000000,70600000,71200000,71800000,72400000,73000000,73600001,75200000,75800000,76400000,77000000,77600000,78200000,78800000,79400000,80000001,81600002,84200001,85800001,87400001,89000001,90600001,92200001,93800001,95400001,97000002,99600003,103200002,105800002,108400002,111000002,113600002,116200002,118800002,121400002,124000001,125600002,128200001,129800001,131400001,133000001,134600001,136200001,137800001,139400001,141000001,142600002,145200001,146800001,148400001,150000001,151600001,153200001,154800001,156400001,158000001,159600002,162200001,163800001,165400001,167000001,168600001,170200001,171800001,173400001,175000001,176600002,179200001,180800001,182400001,184000001,185600001,187200001,188800001,190400001,192000001,193600002,196200001,197800001,199400001,201000001,202600001,204200001,205800001,207400001,209000001,210600002,213200001,214800001,216400001,218000001,219600001,221200001,222800001,224400001,226000001,227600002,230200001,231800001,233400001,235000001,236600001,238200001,239800001,241400001,243000001,244600002,247200001,248800001,250400001,252000001,253600001,255200001,256800001,258400001,260000000,260600001,262200000,262800000,263400000,264000000,264600000,265200000,265800000,266400000,267000001,268600002,271200001,272800001,274400001,276000001,277600001,279200001,280800001,282400001,284000000,284600001,286200000,286800000,287400000,288000000,288600000,289200000,289800000,290400000,291000000,291600001,293200000,293800000,294400000,295000000,295600000,296200000,296800000,297400000,298000000,298600001,300200000,300800000,301400000,302000000,302600000,303200000,303800000,304400000,305000000,305600001,307200000,307800000,308400000,309000000,309600000,310200000,310800000,311400000,312000000,312600001,314200000,314800000,315400000,316000000,316600000,317200000,317800000,318400000,319000000,319600001,321200000,321800000,322400000,323000000,323600000,324200000,324800000,325400000,326000000,326600001,328200000,328800000,329400000,330000000,330600000,331200000,331800000,332400000,333000000,333600001,335200000,335800000,336400000,337000000,337600000,338200000,338800000,339400000,340000000,340600001,342200000,342800000,343400000,344000000,344600000,345200000,345800000,346400000,347000001,348600002,351200001,352800001,354400001,356000001,357600001,359200001,360800001,362400001,364000000,364600001,366200000,366800000,367400000,368000000,368600000,369200000,369800000,370400000,371000000,371600001,373200000,373800000,374400000,375000000,375600000,376200000,376800000,377400000,378000000,378600001,380200000,380800000,381400000,382000000,382600000,383200000,383800000,384400000,385000000,385600001,387200000,387800000,388400000,389000000,389600000,390200000,390800000,391400000,392000000,392600001,394200000,394800000,395400000,396000000,396600000,397200000,397800000,398400000,399000000,399600001,401200000,401800000,402400000,403000000,403600000,404200000,404800000,405400000,406000000,406600001,408200000,408800000,409400000,410000000,410600000,411200000,411800000,412400000,413000000,413600001,415200000,415800000,416400000,417000000,417600000,418200000,418800000,419400000,420000000,420600001,422200000,422800000,423400000,424000000,424600000,425200000,425800000,426400000,427000001,428600002,431200001,432800001,434400001,436000001,437600001,439200001,440800001,442400001,444000000,444600001,446200000,446800000,447400000,448000000,448600000,449200000,449800000,450400000,451000000,451600001,453200000,453800000,454400000,455000000,455600000,456200000,456800000,457400000,458000000,458600001,460200000,460800000,461400000,462000000,462600000,463200000,463800000,464400000,465000000,465600001,467200000,467800000,468400000,469000000,469600000,470200000,470800000,471400000,472000000,472600001,474200000,474800000,475400000,476000000,476600000,477200000,477800000,478400000,479000000,479600001,481200000,481800000,482400000,483000000,483600000,484200000,484800000,485400000,486000000,486600001,488200000,488800000,489400000,490000000,490600000,491200000,491800000,492400000,493000000,493600001,495200000,495800000,496400000,497000000,497600000,498200000,498800000,499400000,500000000,500600001,502200000,502800000,503400000,504000000,504600000,505200000,505800000,506400000,507000001,508600002,511200001,512800001,514400001,516000001,517600001,519200001,520800001,522400001,524000000,524600001,526200000,526800000,527400000,528000000,528600000,529200000,529800000,530400000,531000000,531600001,533200000,533800000,534400000,535000000,535600000,536200000,536800000,537400000,538000000,538600001,540200000,540800000,541400000,542000000,542600000,543200000,543800000,544400000,545000000,545600001,547200000,547800000,548400000,549000000,549600000,550200000,550800000,551400000,552000000,552600001,554200000,554800000,555400000,556000000,556600000,557200000,557800000,558400000,559000000,559600001,561200000,561800000,562400000,563000000,563600000,564200000,564800000,565400000,566000000,566600001,568200000,568800000,569400000,570000000,570600000,571200000,571800000,572400000,573000000,573600001,575200000,575800000,576400000,577000000,577600000,578200000,578800000,579400000,580000000,580600001,582200000,582800000,583400000,584000000,584600000,585200000,585800000,586400000,587000001,588600002,591200001,592800001,594400001,596000001,597600001,599200001,600800001,602400001,604000000,604600001,606200000,606800000,607400000,608000000,608600000,609200000,609800000,610400000,611000000,611600001,613200000,613800000,614400000,615000000,615600000,616200000,616800000,617400000,618000000,618600001,620200000,620800000,621400000,622000000,622600000,623200000,623800000,624400000,625000000,625600001,627200000,627800000,628400000,629000000,629600000,630200000,630800000,631400000,632000000,632600001,634200000,634800000,635400000,636000000,636600000,637200000,637800000,638400000,639000000,639600001,641200000,641800000,642400000,643000000,643600000,644200000,644800000,645400000,646000000,646600001,648200000,648800000,649400000,650000000,650600000,651200000,651800000,652400000,653000000,653600001,655200000,655800000,656400000,657000000,657600000,658200000,658800000,659400000,660000000,660600001,662200000,662800000,663400000,664000000,664600000,665200000,665800000,666400000,667000001,668600002,671200001,672800001,674400001,676000001,677600001,679200001,680800001,682400001,684000000,684600001,686200000,686800000,687400000,688000000,688600000,689200000,689800000,690400000,691000000,691600001,693200000,693800000,694400000,695000000,695600000,696200000,696800000,697400000,698000000,698600001,700200000,700800000,701400000,702000000,702600000,703200000,703800000,704400000,705000000,705600001,707200000,707800000,708400000,709000000,709600000,710200000,710800000,711400000,712000000,712600001,714200000,714800000,715400000,716000000,716600000,717200000,717800000,718400000,719000000,719600001,721200000,721800000,722400000,723000000,723600000,724200000,724800000,725400000,726000000,726600001,728200000,728800000,729400000,730000000,730600000,731200000,731800000,732400000,733000000,733600001,735200000,735800000,736400000,737000000,737600000,738200000,738800000,739400000,740000000,740600001,742200000,742800000,743400000,744000000,744600000,745200000,745800000,746400000,747000001,748600002,751200001,752800001,754400001,756000001,757600001,759200001,760800001,762400001,764000000,764600001,766200000,766800000,767400000,768000000,768600000,769200000,769800000,770400000,771000000,771600001,773200000,773800000,774400000,775000000,775600000,776200000,776800000,777400000,778000000,778600001,780200000,780800000,781400000,782000000,782600000,783200000,783800000,784400000,785000000,785600001,787200000,787800000,788400000,789000000,789600000,790200000,790800000,791400000,792000000,792600001,794200000,794800000,795400000,796000000,796600000,797200000,797800000,798400000,799000000,799600001,801200000,801800000,802400000,803000000,803600000,804200000,804800000,805400000,806000000,806600001,808200000,808800000,809400000,810000000,810600000,811200000,811800000,812400000,813000000,813600001,815200000,815800000,816400000,817000000,817600000,818200000,818800000,819400000,820000000,820600001,822200000,822800000,823400000,824000000,824600000,825200000,825800000,826400000,827000001,828600002,831200001,832800001,834400001,836000001,837600001,839200001,840800001,842400001,844000000,844600001,846200000,846800000,847400000,848000000,848600000,849200000,849800000,850400000,851000000,851600001,853200000,853800000,854400000,855000000,855600000,856200000,856800000,857400000,858000000,858600001,860200000,860800000,861400000,862000000,862600000,863200000,863800000,864400000,865000000,865600001,867200000,867800000,868400000,869000000,869600000,870200000,870800000,871400000,872000000,872600001,874200000,874800000,875400000,876000000,876600000,877200000,877800000,878400000,879000000,879600001,881200000,881800000,882400000,883000000,883600000,884200000,884800000,885400000,886000000,886600001,888200000,888800000,889400000,890000000,890600000,891200000,891800000,892400000,893000000,893600001,895200000,895800000,896400000,897000000,897600000,898200000,898800000,899400000,900000001};
int main(){
    cin>>n;
    ans=a[n/1000000];
    for(int i=(n/1000000)*1000000+1;i<=n;i++)
        check(i);
    cout<<ans;
    return 0;
}

这个你总不能复制粘贴了吧（全写在同一行）