ural1244gentlemen

关键词：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))

const int N=1e5+5;
int dp[N];
int pre[N];
int a[N];
bool vis[N];
vector<int>ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m,n;
    cin>>m;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    if(m>1e5){
        cout<<0<<endl;
        return 0;
    }
    dp[0]=1;
    mem(pre,-1);
    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i];j--){
            if(dp[j-a[i]]){
                dp[j]+=dp[j-a[i]];
                if(pre[j]==-1)pre[j]=i;
            }
        }
    }
    if(dp[m]==0)cout<<0<<endl;
    else if(dp[m]==1){
        int t=pre[m];
        int sum=m;
        while(~t){
            vis[t]=true;
            m-=a[t];
            t=pre[m];
        }
        for(int i=1;i<=n;i++)if(!vis[i])ans.pb(i);
        for(int i=0;i<ans.size();i++){
            if(i==ans.size()-1)cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }
    else cout<<-1<<endl;
    return 0;
}

codeforces-1244c-thefootballseason-思维

ThefootballseasonhasjustendedinBerland.AccordingtotherulesofBerlandfootball,eachmatchisplayedbetweentwoteams.Theresultofeachmatchiseitheradraw,oravictoryofoneoftheplayingteams.Ifateamwinsthematch,itge 查看详情

洛谷p1244青蛙过河

P1244青蛙过河362通过525提交题目提供者该用户不存在标签难度普及-时空限制1s/128MB 提交  讨论  题解  最新讨论更多讨论题目什么意思题目看不懂啊题目描述有一条河，左边一个石墩(A区)上有编号为1，2... 查看详情

51nod1244莫比乌斯函数之和

Description求(sum_{i=a}^bmu(i),1leqslantlleqslantrleqslant10^{10})Solution杜教筛..贴代码..Code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=2000500;constllp=1000000007;int 查看详情

51nod1244莫比乌斯函数之和

题目链接：51nod1244莫比乌斯函数之和推荐学习博客:http://blog.csdn.net/skywalkert/article/details/50500009然后，这题解法里面提到了，我就不打公式了，，，好好看大神的博客唉orz用筛法预处理前N^(2/3)项，后面的记忆化搜索解决。还不会... 查看详情

洛谷p1244青蛙过河

 P1244青蛙过河题目描述有一条河，左边一个石墩(A区)上有编号为1，2，3，4，…，n的n只青蛙，河中有k个荷叶(C区)，还有h个石墩(D区)，右边有一个石墩(B区)，如下图所示。n只青蛙要过河(从左岸石墩A到右岸石墩B)，规则为... 查看详情

p1244青蛙过河

P1244青蛙过河题目描述有一条河，左边一个石墩(A区)上有编号为1，2，3，4，…，n的n只青蛙，河中有k个荷叶(C区)，还有h个石墩(D区)，右边有一个石墩(B区)，如下图所示。n只青蛙要过河(从左岸石墩A到右岸石墩B)，规则为：(1)石墩... 查看详情

洛谷p1244青蛙过河dp/思路

...实是思路题).原文戳>>https://www.luogu.org/problem/show?pid=1244<<这题的意思给的挺模糊,需要一定的人生经验理解能力.题目想必已知,我就提几点可能会搞错的点吧.1.题目说了青蛙可以：A→B(表示可以从A跳到B，下同)，A→C，A→D... 查看详情

hdu1244：maxsumplusplusplus

题目链接：MaxSumPlusPlusPlus题意：在n个数中取m段数使得这m段数之和最大，段与段之间不能重叠分析：见代码//dp[i][j]表示前i个数取了j段的最大值//状态转移：dp[i][j]=max(dp[k][j-1]+(sum[k+l[j]-sum[k]或者sum[i]-sum[i-l[j])(0<=k<=i-l[j])//这种... 查看详情

[51nod1244]莫比乌斯函数之和

推公式，设$A(n)=\sum\limits_i=1^n\mu(i)$，令$B(n)=1$，则推出$C(n)=(A*B)(n)=[n=1]$$$\beginalign*\sum\limits_i=1^n[i=1]&=\sum\limits_i=1^n\sum\limits_d|i\mu(d)\\1&=\sum\limits_d=1^n\sum\limits_ 查看详情

ural-1901spaceelevators

题目：NowadaysspaceshipsareneverlaunchedfromtheEarth‘ssurface.ThereisahugespaceportplacedinthegeostationaryorbitandconnectedtotheEarthwithcarbonnanotubecables.Peopleandcargoaredeliveredtotheorbitbyelevat 查看详情

ural2089experiencedcoachtwosat

DescriptionMishatrainsseveralACMteamsattheuniversity.Heisanexperiencedcoach,andhedoesnotunderestimatethemeaningoffriendlyandcollaborativeatmosphereduringtrainingsessions.Itusedtobethatway,butoneofthet 查看详情

ural2020trafficjaminflowertown

2020.TrafficJaminFlowerTownTimelimit:1.0secondMemorylimit:64MBHavingreturnedfromSunCity,Dunnotoldallhisfriendsthateveryshortymayhaveapersonalautomobile.Immediatelyafterthatsomanycitizenstookafancyofbe 查看详情

ural1424minibus

MinibusTimelimit:1.0secondMemorylimit:64MBBackgroundMinibusdriverSergeyA.Greedsonhasbecometotallyfamousforhisphenomenalgreediness.Heclaimedtimeandagainthatheheldhimselfinreadinesstothrottlehisbrothera 查看详情

ural1855tradeguildsoferathia

TradeGuildsofErathiaTimelimit:2.0secondMemorylimit:64MBThecontinentofAntagarichwascolonizedslowly.LongagoitsnorthernpartwasinhabitedbytheelvesofAvlee.Later,thehotsoutherndesertofBracadawasoccupiedbyth 查看详情

ural2016magicandscience

2016.MagicandScienceTimelimit:1.0secondMemorylimit:64MBScientistswhospecializeinwitchcrafthaverecentlydiscoveredanewelementaryparticlecalledamagion.Studyingthelawsofmagions’movement,agroupofthre 查看详情

ural2021scarilyinteresting!

2021.Scarilyinteresting!Timelimit:1.0secondMemorylimit:64MBThisyearatMonstersUniversityitisdecidedtoarrangeScareGames.AttheGamesallcampusgathersatthestadiumstands,andtheScareprogramstudentsdivideintot 查看详情

[ural1519]formula1

[URAL1519]Formula1试题描述Regardlessofthefact,thatVologdacouldnotgetrightstoholdtheWinterOlympicgamesof20**,itiswell-known,thatthecitywillconductoneoftheFormula1events.Surely,forsuchanimportantthinganewra 查看详情

ural1118.nontrivialnumbers

1118.NontrivialNumbersTimelimit:2.0secondMemorylimit:64MB SpecialistsofSKBKonturhavedevelopedauniquecryptographicalgorithmforneedsofinformationprotectionwhiletransmittingdataovertheInternet.Thema 查看详情