关键词：
URAL 1501
思路：
dp+记忆化搜索
状态：dp[i][j]表示选取第一堆前i个和第二堆前j的状态：0:0多1个 1：0和1相等 2：1多一个 -2:不能达到题目所描述的状态
初始状态：dp[0][0]=1
状态转移：见代码
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_bck
#define mem(a,b) memset(a,b,sizeof(a))
const int N=1e3+5;
int n1[N],n2[N];
int dp[N][N];//0:0more 1:equal 2:1more
int ans[N*2];
int dfs(int x,int y){
if(~dp[x][y])return dp[x][y];
if(x==0&&y==0)return dp[x][y]=1;
if(x!=0){
int t=dfs(x-1,y);
if(t==0){
if(n1[x]==1){
ans[x+y]=1;
return dp[x][y]=1;
}
}
else if(t==1){
if(n1[x]==1){
ans[x+y]=1;
return dp[x][y]=2;
}
else if(n1[x]==0){
ans[x+y]=1;
return dp[x][y]=0;
}
}
else if(t==2){
if(n1[x]==0){
ans[x+y]=1;
return dp[x][y]=1;
}
}
}
if(y!=0){
int t=dfs(x,y-1);
if(t==0){
if(n2[y]==1){
ans[x+y]=2;
return dp[x][y]=1;
}
}
else if(t==1){
if(n2[y]==1){
ans[x+y]=2;
return dp[x][y]=2;
}
else if(n2[y]==0){
ans[x+y]=2;
return dp[x][y]=0;
}
}
else if(t==2){
if(n2[y]==0){
ans[x+y]=2;
return dp[x][y]=1;
}
}
}
return dp[x][y]=-2;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
string a[3];
cin>>n;
cin>>a[1]>>a[2];
for(int i=1;i<=n;i++)n1[i]=a[1][i-1]-‘0‘;
for(int i=1;i<=n;i++)n2[i]=a[2][i-1]-‘0‘;
mem(dp,-1);
if(dfs(n,n)!=-2){
for(int i=1;i<=2*n;i++)cout<<ans[i];
cout<<endl;
}else cout<<"Impossible"<<endl;
return 0;
}
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 查看详情
ural2015zhenyamovesfromthedormitory
2015.ZhenyamovesfromthedormitoryTimelimit:1.0secondMemorylimit:64MBAftermovingfromhisparents’placeZhenyahasbeenlivingintheUniversitydormitoryforamonth.However,hegotprettytiredofthecurfewtimeandq 查看详情
ural2017bestofabadlot
2017.BestofabadlotTimelimit:1.0secondMemorylimit:64MBAcruiselinerhasn’tmovedawayfromthelandevenforthreemileswhenitbecameapparentthatsomebodyhasdrownedoneofthestewardsintheswimmingpool.Thecaptain 查看详情
ural2012aboutgrishan.
2012.AboutGrishaN.Timelimit:1.0secondMemorylimit:64MBGrishaN.toldhistwoteammatesthathewasgoingtosolveallgivenproblemsatthesubregionalcontest,eveniftheteammateswouldn’tshowupatthecompetition.Thet 查看详情
ural2014zhenyamovesfromparents
2014.ZhenyamovesfromparentsTimelimit:1.0secondMemorylimit:64MBZhenyamovedfromhisparents’hometostudyinothercity.Hedidn’ttakeanycashwithhim,heonlytookhisfather’screditcardwithzerobalan 查看详情
ural2022ridingatoad
2022.RidingaToadTimelimit:1.0secondMemorylimit:64MBAtribeofleafmenliveintheoldforest.Leafmenareverytinyandfast,that’swhywecan’tnoticethemevenwhentheyareunderourverynose.Leafmenguardthefore 查看详情
ural1196.historyexam（二分）
1196.HistoryExamTimelimit:1.5secondMemorylimit:64MBProfessorofhistorydecidedtosimplifytheexaminationprocess.Attheexam,everystudentshouldwritealistofhistoricdatessheknows(sheshouldwritetheyearsonlyand, 查看详情
ural1224.spiral（规律）
1224.SpiralTimelimit:1.0secondMemorylimit:64MBAbrandnewsapperrobotisabletoneutralizeminesinarectangularregionhavingintegerheightandwidth(NandMrespectively).Beforetherobotbeginsitsworkitisplacednearthe 查看详情
ural2031.overturnednumbers（枚举）
2031.OverturnedNumbersTimelimit:1.0secondMemorylimit:64MBLittlePierrewassurfingtheInternetandcameacrossaninterestingpuzzle:Whatisthenumberunderthecar?IttooksometimebeforePierresolvedthepuzzle,butevent 查看详情
ural1081binarylexicographicsequence（递归）(代码片段)
URAL1081.BinaryLexicographicSequenceTimelimit:0.5secondMemorylimit:64MBDescriptionConsiderallthesequenceswithlength(0<N<44),containingonlytheelements0and1,andnotwoonesareadjacent(110isnotavalids 查看详情
ural1343.fairytale打表
1343.FairyTaleTimelimit:1.0secondMemorylimit:64MB 12monthstosinganddanceinaringtheircelestialdance.Oneafteranothertheyholdathrone.ThefirstisyoungandfierceJanuaryandthelastiselderlyandwiseDecember 查看详情